MDP optimal control under temporal logic constraints
Open Access
- 1 December 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01912216,p. 532-538
Abstract
In this paper, we develop a method to automatically generate a control policy for a dynamical system modeled as a Markov Decision Process (MDP). The control specification is given as a Linear Temporal Logic (LTL) formula over a set of propositions defined on the states of the MDP. We synthesize a control policy such that the MDP satisfies the given specification almost surely, if such a policy exists. In addition, we designate an “optimizing proposition” to be repeatedly satisfied, and we formulate a novel optimization criterion in terms of minimizing the expected cost in between satisfactions of this proposition. We propose a sufficient condition for a policy to be optimal, and develop a dynamic programming algorithm that synthesizes a policy that is optimal under some conditions, and sub-optimal otherwise. This problem is motivated by robotic applications requiring persistent tasks, such as environmental monitoring or data gathering, to be performed.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Optimal path planning for surveillance with temporal-logic constraintsThe International Journal of Robotics Research, 2011
- Motion planning and control from temporal logic specifications with probabilistic satisfaction guarantees2010
- Receding horizon temporal logic planning for dynamical systems2009
- Dealing with Nondeterminism in Symbolic ControlLecture Notes in Computer Science, 2008
- A Fully Automated Framework for Control of Linear Systems from Temporal Logic SpecificationsIEEE Transactions on Automatic Control, 2008
- Where's Waldo? Sensor-Based Temporal Logic Motion PlanningProceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (cat. No.01ch37164), 2007
- PROBMELA: a modeling language for communicating probabilistic processes2005
- Probabilistic Linear-Time Model Checking: An Overview of the Automata-Theoretic Approach1999
- Markov decision processes and regular eventsIEEE Transactions on Automatic Control, 1998
- Markov Decision Processes1994