信念抽象による監視戦略の合成
Synthesis of surveillance strategies via belief abstraction
移動する敵対的ターゲットの位置を把握し続ける監視タスクを時相論理で定式化し、部分情報ゲームを抽象化で完全情報ゲームに変換して戦略を合成する手法を提案した。
著者: Suda Bharadwaj, Rayna Dimitrova, Ufuk Topcu
分類: cs.RO, cs.GT, cs.SY, eess.SY
原文アブストラクト
We study the problem of synthesizing a controller for a robot with a surveillance objective, that is, the robot is required to maintain knowledge of the location of a moving, possibly adversarial target. We formulate this problem as a one-sided partial-information game in which the winning condition for the agent is specified as a temporal logic formula. The specification formalizes the surveillance requirement given by the user, including additional non-surveillance tasks. In order to synthesize a surveillance strategy that meets the specification, we transform the partial-information game into a perfect-information one, using abstraction to mitigate the exponential blow-up typically incurred by such transformations. This enables the use of off-the-shelf tools for reactive synthesis. We use counterexample-guided refinement to automatically achieve abstraction precision that is sufficient to synthesize a surveillance strategy. We evaluate the proposed method on two case-studies, demonstrating its applicability to large state-spaces and diverse requirements.
