Game tree search for minimizing detectability and maximizing visibility
Game tree search for minimizing detectability and maximizing visibility
复制标题
博弈树搜索可最小化可检测性并最大化可见性
作者：
Zhongshun Zhang;J. Smereka;Joseph Lee;Lifeng Zhou;Yoonchang Sung;Pratap Tokekar
我们介绍并研究了为智能体规划轨迹以执行侦察任务同时避免被对手发现的问题。这引入了经典的基于可见性的目标搜索和追击回避问题的多目标版本。在我们的公式中，代理会因增加其可见性（通过探索新区域）而获得正奖励，并在每次被对手检测到时获得负惩罚。目标是为代理找到一条有限范围的路径，以平衡最大化可见性和最小化可检测性之间的权衡。我们将此问题建模为离散、顺序、两人、零和游戏。我们使用两种类型的博弈树搜索算法来解决这个问题：极小极大搜索树和蒙特卡罗搜索树。两种搜索树都可以产生最优策略，但可能需要指数计算时间和空间。我们首先提出三种修剪技术来减少计算时间，同时保持最优性保证。当智能体和对手最初距离较远时，我们提出了一种具有更长规划范围的可变分辨率技术，以进一步减少计算时间。仿真结果表明所提出的策略在计算时间方面的有效性。
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 opponent. This introduces a multi-objective version of classical visibility-based target search and pursuit-evasion problem. In our formulation, the agent receives a positive reward for increasing its visibility (by exploring new regions) and a negative penalty every time it is detected by the opponent. The objective is to find a finite-horizon path for the agent that balances the trade off between maximizing visibility and minimizing detectability. We model this problem as a discrete, sequential, two-player, zero-sum game. We use two types of game tree search algorithms to solve this problem: minimax search tree and Monte-Carlo search tree. Both search trees can yield the optimal policy but may require possibly exponential computational time and space. We first propose three pruning techniques to reduce the computational time while preserving optimality guarantees. When the agent and the opponent are located far from each other initially, we present a variable resolution technique with longer planning horizon to further reduce computational time. Simulation results show the effectiveness of the proposed strategies in terms of computational time.
影响因子：
5.2
作者：
Zhou, Lifeng;Tzoumas, Vasileios;Tokekar, Pratap
通讯作者：
Tokekar, Pratap