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