A Caltech Library Service

Enhancing tolerance to unexpected jumps in GR(1) games

Dathathri, Sumanth and Livingston, Scott C. and Murray, Richard M. (2017) Enhancing tolerance to unexpected jumps in GR(1) games. In: Proceedings of the 8th ACM/IEEE International Conference on Cyber-Physical Systems, Pitssburgh, PA USA, April 2017 (ICCPS). ACM , New York, NY, pp. 37-47. ISBN 978-1-4503-4965-9.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


When used as part of a hybrid controller, finite-memory strategies synthesized from linear-time temporal logic (LTL) specifications rely on an accurate dynamics model in order to ensure correctness of trajectories. In the presence of uncertainty about the underlying model, there may exist unexpected trajectories that manifest as unexpected transitions under control of the strategy. While some disturbances can be captured by augmenting the dynamics model, such approaches may be conservative in that bisimulations may fail to exist for which strategies can be synthesized. In this paper, we consider games of the GR(1) fragment of LTL, and we characterize the tolerance of hybrid controllers to perturbations that appear as unexpected jumps (transitions) to states in the discrete strategy part of the controller. As a first step, we show robustness to certain unexpected transitions that occur in a finite manner, i.e., despite a certain number of unexpected jumps, the sequence of states obtained will still meet a stricter specification and hence the original specification. Additionally, we propose algorithms to improve robustness by increasing tolerance to additional disturbances. A robot gridworld example is presented to demonstrate the application of the developed ideas and also to perform empirical analysis.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Murray, Richard M.0000-0002-5785-7481
Additional Information:© 2017 ACM. This work was partially supported by United Technologies Corporation and IBM, through the industrial cyber-physical systems (iCyPhy) consortium and by STARnet, a Semiconductor Research Corporation program, sponsored by MARCO and DARPA.
Funding AgencyGrant Number
United Technologies CorporationUNSPECIFIED
Semiconductor Research CorporationUNSPECIFIED
Microelectronics Advanced Research Corporation (MARCO)UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Subject Keywords:Linear Temporal Logic, Formal Methods, Synthesis, Robustness
Record Number:CaltechAUTHORS:20170303-084805424
Persistent URL:
Official Citation:Sumanth Dathathri, Scott C. Livingston, and Richard M. Murray. 2017. Enhancing tolerance to unexpected jumps in GR(1) games. In Proceedings of the 8th ACM/IEEE International Conference on Cyber-Physical Systems, Pittsburgh, PA USA, April 2017 (ICCPS), 11 pages. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:74682
Deposited By: Sumanth Dathathri
Deposited On:03 Mar 2017 18:20
Last Modified:11 Nov 2021 05:29

Repository Staff Only: item control page