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

From Murray Wiki
Revision as of 07:33, 22 March 2017 by Murray (talk | contribs) (Created page with "{{Paper |Title=Decomposing GR(1) Games with Singleton Liveness Guarantees for Efficient Synthesis |Authors=Sumanth Dathathri and Richard M. Murray |Source=Submitted, 2017 Conf...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search
Title Decomposing GR(1) Games with Singleton Liveness Guarantees for Efficient Synthesis
Authors Sumanth Dathathri and Richard M. Murray
Source Submitted, 2017 Conference on Decision and Control (CDC)
Abstract Temporal logic based synthesis approaches are often used to find trajectories that are correct-by-construction in systems–eg. synchronization for multi-agent hybrid systems, reactive motion planning for robots. 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.
Type Conference paper
URL http://www.cds.caltech.edu/~murray/preprints/dm17-cdc s.pdf
Tag dm17-cdc
ID 2016b
Funding SRC TerraSwarm
Flags