時相論理制約下でのMDP最適制御
MDP Optimal Control under Temporal Logic Constraints
マルコフ決定過程で表されたシステムに対し、線形時相論理の仕様をほぼ確実に満たしつつ、特定命題の再達成間の期待コストを最小化する制御方策を動的計画法で合成する手法を提案した。
著者: Xu Chu Ding, Stephen L. Smith, Calin Belta, Daniela Rus
分類: cs.RO, cs.SY, eess.SY, math.OC
原文アブストラクト
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.
