Efficient reactive controller synthesis for a fragment of linear temporal logic

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 c...

Full description

Saved in:
Bibliographic Details
Main Authors: Wolff, Eric M., Topcu, Ufuk, Murray, Richard M.
Format: Conference Proceeding
Language:English
Subjects:
Complexity theory
Control systems
Markov processes
Planning
Probabilistic logic
Process control
Robots
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(1).
ISSN:1050-4729
2577-087X
DOI:10.1109/ICRA.2013.6631296