A Caltech Library Service

Backtracking temporal logic synthesis for uncertain environments

Livingston, Scott C. and Murray, Richard M. and Burdick, Joel W. (2012) Backtracking temporal logic synthesis for uncertain environments. In: 2012 IEEE International Conference on Robotics and Automation (ICRA). IEEE , Piscataway, NJ, pp. 5163-5170. ISBN 978-1-4673-1403-9.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


This paper considers the problem of synthesizing correct-by-construction robotic controllers in environments with uncertain but fixed structure. “Environment” has two notions in this work: a map or “world” in which some controlled agent must operate and navigate (i.e., evolve in a configuration space with obstacles); and an adversarial player that selects continuous and discrete variables to try to make the agent fail (as in a game). Both the robot and the environment are subjected to behavioral specifications expressed as an assume-guarantee linear temporal logic (LTL) formula. We then consider how to efficiently modify the synthesized controller when the robot encounters unexpected changes in its environment. The crucial insight is that a portion of this problem takes place in a metric space, which provides a notion of nearness. Thus if a nominal plan fails, we need not resynthesize it entirely, but instead can “patch” it locally. We present an algorithm for doing this, prove soundness (correctness of output), and demonstrate it on an example gridworld.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Murray, Richard M.0000-0002-5785-7481
Additional Information:© 2012 IEEE. Date of Current Version: 28 June 2012. The authors gratefully acknowledge Eric Wolff and Sandeep Chinchali for comments on an earlier draft. This work is partially supported by the Boeing Corporation.
Funding AgencyGrant Number
Boeing CorporationUNSPECIFIED
Record Number:CaltechAUTHORS:20120703-084401806
Persistent URL:
Official Citation:Livingston, Scott C.; Murray, Richard M.; Burdick, Joel W.; , "Backtracking temporal logic synthesis for uncertain environments," Robotics and Automation (ICRA), 2012 IEEE International Conference on , vol., no., pp.5163-5170, 14-18 May 2012 doi: 10.1109/ICRA.2012.6225208 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:32245
Deposited By: Tony Diaz
Deposited On:06 Jul 2012 20:25
Last Modified:09 Nov 2021 21:26

Repository Staff Only: item control page