Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2013 | public
Book Section - Chapter

Efficient reactive controller synthesis for a fragment of linear temporal logic

Abstract

Motivated by robotic motion planning, we develop a framework for control policy synthesis for both non-deterministic transition systems and Markov decision processes that are subject to temporal logic task specifications. We introduce a fragment of linear temporal logic that can be used to specify common motion planning tasks such as safe navigation, response to the environment, persistent coverage, and surveillance. This fragment is computationally efficient; the complexity of control policy synthesis is a doubly-exponential improvement over standard linear temporal logic for both non-deterministic transition systems and Markov decision processes. This improvement is possible because we compute directly on the original system, as opposed to the automata-based approach commonly used. We give simulation results for representative motion planning tasks and compare to generalized reactivity.

Additional Information

© 2013 IEEE. The authors would like to thank Scott Livingston, Matanya Horowitz, and the anonymous reviewers for helpful input. This work was supported by a NDSEG fellowship, the Boeing Corporation, and AFOSR award FA9550-12-1-0302.

Additional details

Created:
August 19, 2023
Modified:
October 26, 2023