Learning-based Formal Synthesis of Cooperative Multi-agent Systems
Authors:
- Jin DaiJDJin Dai
- Alessandro BeniniABAlessandro Benini
- Hai LinHai Lin
- Panos J. AntsaklisPAPanos J. Antsaklis
- Matthew J. RutherfordMRMatthew J. Rutherford
- Kimon P. ValavanisKimon P. Valavanis
Preprint
Abstract
We propose a formal design framework for synthesizing coordination and control policies for cooperative multi-agent systems to accomplish a global mission. The global performance requirements are specified as regular languages while dynamics of each agent as well as the shared environment are characterized by finite automata, upon on which a formal design approach is carried out via divide-and-conquer. Specifically, the global mission is decomposed into local tasks; and local mission supervisors are designed to accomplish these local tasks while maintaining the multi-agent performance by integrating supervisor synthesis with compositional verification techniques; finally, motion plans are automatically synthesized based on the obtained mission plans. We present three modifications of the L* learning algorithm such that they are adapted for the synthesis of the local mission supervisors, the compositional verification and the synthesis of local motion plans, to guarantee that the collective behavior of the agents will ensure the satisfaction of the global specification. Furthermore, the effectiveness of the proposed framework is demonstrated by a detailed experimental study based on the implementation of a multi-robot coordination scenario. The proposed hardware-software architecture, with each robot's communication and localization capabilities, is exploited to examine the automatic supervisor synthesis with inter-robot communication.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Multi-agent planning under local LTL specifications and event-based synchronizationAutomatica, 2016
- Generation of fiducial marker dictionaries using Mixed Integer Linear ProgrammingPattern Recognition, 2016
- Guaranteed global performance through local coordinationsAutomatica, 2011
- Temporal logic motion planning for dynamic robotsAutomatica, 2009
- Learning to divide and conquer: applying the L* algorithm to automate assume-guarantee reasoningFormal Methods in System Design, 2008
- Symbolic planning and control of robot motion [Grand Challenges of Robotics]IEEE Robotics & Automation Magazine, 2007
- Modeling and Control of Logical Discrete Event Systems1995
- Intelligent Robotic Systems: Theory, Design and Applications1992
- Supervisory control of concurrent discrete-event systemsInternational Journal of Control, 1991
- Learning regular sets from queries and counterexamplesInformation and Computation, 1987