Automatic Generation of Communication Requirements for Enforcing Multi-Agent Safety

Eric S. Kim
(University of California, Berkeley)
Murat Arcak
(University of California, Berkeley)
Sanjit A. Seshia
(University of California, Berkeley)
BaekGyu Kim
(Toyota InfoTechnology Center, U.S.A.)
Shinichi Shiraishi
(Toyota InfoTechnology Center, U.S.A.)

Distributed controllers are often necessary for a multi-agent system to satisfy safety properties such as collision avoidance. Communication and coordination are key requirements in the implementation of a distributed control protocol, but maintaining an all-to-all communication topology is unreasonable and not always necessary. Given a safety objective and a controller implementation, we consider the problem of identifying when agents need to communicate with one another and coordinate their actions to satisfy the safety constraint. We define a coordination-free controllable predecessor operator that is used to derive a subset of the state space that allows agents to act independently, without consulting other agents to double check that the action is safe. Applications are shown for identifying an upper bound on connection delays and a self-triggered coordination scheme. Examples are provided which showcase the potential for designers to visually interpret a system's ability to tolerate delays when initializing a network connection.

In Mario Gleirscher, Stefan Kugele and Sven Linker: Proceedings 2nd International Workshop on Safe Control of Autonomous Vehicles (SCAV 2018), Porto, Portugal, 10th April 2018, Electronic Proceedings in Theoretical Computer Science 269, pp. 3–16.
Published: 10th April 2018.

ArXived at: https://dx.doi.org/10.4204/EPTCS.269.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org