Optimal Control of Non-deterministic Systems for a Computationally Efficient Fragment of Temporal Logic

From Murray Wiki
Revision as of 06:15, 15 May 2016 by Murray (talk | contribs) (htdb2wiki: creating page for 2013b_wtm13-cdc.html)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Eric M. Wolff, Ufuk Topcu, and Richard M. Murray
2013 Conference on Decison and Control (CDC)

We develop a framework for optimal control policy synthesis for non-deterministic transition systems subject to temporal logic specifications. We use a fragment of temporal logic to specify tasks such as safe navigation, response to the environment, persistence, and surveillance. By restricting specifications to this fragment, we avoid a potentially doubly-exponential automaton construction. We compute feasible con- trol policies for non-deterministic transition systems in time polynomial in the size of the system and specification. We also compute optimal control policies for average, minimax (bottleneck), and average cost-per-task-cycle cost functions. We highlight several interesting cases when these can be computed in time polynomial in the size of the system and specification. Additionally, we make connections between computing optimal control policies for an average cost-per-task-cycle cost function and the generalized traveling salesman problem. We give simulation results for motion planning problems.