Multi-agent planning under local LTL specifications and event-based synchronization

DOI10.1016/J.AUTOMATICA.2016.04.006zbMATH Open1339.93080arXiv1610.08380OpenAlexW2343223723MaRDI QIDQ290878FDOQ290878

Authors: Jana Tůmová, Dimos V. Dimarogonas 

Publication date: 3 June 2016

Published in: Automatica (Search for Journal in Brave)

Abstract: We study the problem of plan synthesis for multi-agent systems, to achieve complex, high-level, long-term goals that are assigned to each agent individually. As the agents might not be capable of satisfying their respective goals by themselves, requests for other agents' collaborations are a part of the task descriptions. We consider that each agent is modeled as a discrete state-transition system and its task specification takes a form of a linear temporal logic formula, which may contain requirements and constraints on the other agent's behavior. A traditional automata-based approach to multi-agent plan synthesis from such specifications builds on centralized team planning and full team synchronization after each agents' discrete step, and thus suffers from extreme computational demands. We aim at reducing the computational complexity by decomposing the plan synthesis problem into finite horizon planning problems that are solved iteratively, upon the run of the agents. As opposed to full synchronization, we introduce an event-based synchronization that allows our approach to efficiently adapt to different time durations of different agents' discrete steps. We discuss the correctness of the solution and find assumptions, under which the proposed iterative algorithm leads to provable eventual satisfaction of the desired specifications.

Full work available at URL: https://arxiv.org/abs/1610.08380

Recommendations

• On the timed temporal logic planning of coupled multi-agent systems
• Multi-agent system motion planning under temporal logic specifications and control barrier function
• Parallel decomposition and concurrent satisfaction for heterogeneous multi-robot task and motion planning under temporal logic specifications
• Compositional and symbolic synthesis of reactive controllers for multi-agent systems
• Multi-robot LTL planning under uncertainty

zbMATH Keywords

decentralized controlsynchronizationpath planningtemporal logicformal verificationfinite state machinesrobot control

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Decentralized systems (93A14) Synthesis problems (93B50) Discrete event control/observation systems (93C65)

Cites Work

• Introduction to algorithms
• Title not available (Why is that?)
• Linear temporal logic vehicle routing with applications to multi-UAV mission planning
• Receding horizon control for temporal logic specifications
• A Fully Automated Framework for Control of Linear Systems from Temporal Logic Specifications
• Controlling a Class of Nonlinear Systems on Rectangles
• Planning Algorithms

Cited In (13)

• A distributed approach to robust control of multi-robot systems
• PuRSUE -- from specification of robotic environments to synthesis of controllers
• Decentralized route-planning for multi-vehicle teams to satisfy a subclass of linear temporal logic specifications
• Multi-agent system motion planning under temporal logic specifications and control barrier function
• Multi-robot LTL planning under uncertainty
• Funnel control for fully actuated systems under a fragment of signal temporal logic specifications
• Path planning for robotic teams based on LTL specifications and Petri net models
• Resource-aware networked control systems under temporal logic specifications
• Feedback control strategies for multi-agent systems under a fragment of signal temporal logic tasks
• Parallel decomposition and concurrent satisfaction for heterogeneous multi-robot task and motion planning under temporal logic specifications
• Time minimization and online synchronization for multi-agent systems under collaborative temporal logic tasks
• Finite horizon discrete models for multi-agent control systems with coupled dynamics
• Decentralized abstractions for multi-agent systems under coupled constraints

This page was built for publication: Multi-agent planning under local LTL specifications and event-based synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290878)