Change search
ReferencesLink to record
Permanent link

Direct link
Multi-agent planning under local LTL specifications and event-based synchronization
KTH, School of Electrical Engineering (EES), Automatic Control.ORCID iD: 0000-0003-4173-2593
KTH, School of Electrical Engineering (EES), Automatic Control.ORCID iD: 0000-0001-7309-8086
2016 (English)In: Automatica, ISSN 0005-1098, E-ISSN 1873-2836, Vol. 70, 239-248 p.Article in journal (Refereed) PublishedText
Abstract [en]

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. 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. 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.

Place, publisher, year, edition, pages
Elsevier, 2016. Vol. 70, 239-248 p.
Keyword [en]
Decentralized control, Finite state machines, Formal verification, Path planning, Robot control, Synchronization, Temporal logic, Algorithms, Computer circuits, Finite automata, Iterative methods, Logic circuits, Motion planning, Reconfigurable hardware, Robot programming, Specifications, Computational demands, Discrete state transition systems, Event-based synchronization, Iterative algorithm, Linear temporal logic, Multi-agent planning, Robot controls, Task specifications, Multi agent systems
National Category
Control Engineering
Identifiers
URN: urn:nbn:se:kth:diva-186904DOI: 10.1016/j.automatica.2016.04.006ISI: 000378182700028ScopusID: 2-s2.0-84964336561OAI: oai:DiVA.org:kth-186904DiVA: diva2:930570
Funder
EU, European Research Council
Note

Funding Details: KTH, European Research Council

QC 20160524

Available from: 2016-05-24 Created: 2016-05-16 Last updated: 2016-07-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Tumova, JanaDimarogonas, Dimos V.
By organisation
Automatic Control
In the same journal
Automatica
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 4931 hits
ReferencesLink to record
Permanent link

Direct link