偵察エージェントのための検出回避と可視性最大化を両立する木探索計画法
Tree Search Techniques for Minimizing Detectability and Maximizing Visibility
敵の監視者に検出されずに偵察するエージェントの経路計画を、可視性最大化と検出回避のトレードオフを考慮した2人ゼロ和ゲームとして定式化し、最適性を保ちつつ探索を大幅に削減する枝刈り手法を提案した。
著者: Zhongshun Zhang, Yoonchang Sung, Lifeng Zhou, Jonathon M. Smereka, Joseph Lee, Pratap Tokekar
分類: cs.RO
原文アブストラクト
We introduce and study the problem of planning a trajectory for an agent to carry out a scouting mission while avoiding being detected by an adversarial guard. This introduces an adversarial version of classical visibility-based planning problems such as the Watchman Route Problem. The agent receives a positive reward for increasing its visibility and a negative penalty when it is detected by the guard. The objective is to find a finite-horizon path for the agent that balances the trade-off maximizing visibility and minimizing detectability. We model this problem as a sequential two-player zero-sum discrete game. A minimax tree search can give the optimal policy for the agent but requires an exponential-time computation and space. We propose several pruning techniques to reduce the computational cost while still preserving optimality guarantees. Simulation results show that the proposed strategy prunes approximately three orders of magnitude nodes as compared to the brute-force strategy.
