Electronic Proceedings in Theoretical Computer Science (Apr 2018)

Automatic Generation of Communication Requirements for Enforcing Multi-Agent Safety

  • Eric S. Kim,
  • Murat Arcak,
  • Sanjit A. Seshia,
  • BaekGyu Kim,
  • Shinichi Shiraishi

DOI
https://doi.org/10.4204/EPTCS.269.2
Journal volume & issue
Vol. 269, no. Proc. SCAV 2018
pp. 3 – 16

Abstract

Read online

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.