A Caltech Library Service

Decomposing GR(1) Games with Singleton Liveness Guarantees for Efficient Synthesis

Dathathri, Sumanth and Murray, Richard M. (2017) Decomposing GR(1) Games with Singleton Liveness Guarantees for Efficient Synthesis. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC). IEEE , Piscataway, NJ, pp. 911-917. ISBN 978-1-5090-2873-3.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Accepted Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Temporal logic based synthesis approaches are often used to find trajectories that are correct-by-construction for systems with complex behavior. However, the scalability of such approaches is of concern and at times a bottleneck when transitioning from theory to practice. In this paper, we identify a class of problems in the GR(1) fragment of linear-time temporal logic (LTL) where the synthesis problem allows for a decomposition that enables easy parallelization. This decomposition also reduces the alternation depth, resulting in more efficient synthesis. A multi-agent robot gridworld example with coordination tasks is presented to demonstrate the application of the developed ideas and also to perform empirical analysis for benchmarking the decomposition-based synthesis approach.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Murray, Richard M.0000-0002-5785-7481
Additional Information:© 2017 IEEE. The authors would like to thank Scott C. Livingston and Tung M. Phan for helpful input. This work was supported by STARnet, a Semiconductor Research Corporation program, sponsored by MARCO and DARPA.
Group:Control and Dynamical Systems Technical Reports
Funding AgencyGrant Number
Microelectronics Advanced Research Corporation (MARCO)UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Record Number:CaltechAUTHORS:20170920-152025463
Persistent URL:
Official Citation:S. Dathathri and R. M. Murray, "Decomposing GR(1) games with singleton liveness guarantees for efficient synthesis," 2017 IEEE 56th Annual Conference on Decision and Control (CDC), Melbourne, VIC, 2017, pp. 911-917. doi: 10.1109/CDC.2017.8263775
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:81642
Deposited By: Sumanth Dathathri
Deposited On:20 Sep 2017 22:28
Last Modified:15 Nov 2021 19:44

Repository Staff Only: item control page