Game tree search for minimizing detectability and maximizing visibility
Abstract 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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131973 |
| _version_ | 1826215084836257792 |
|---|---|
| author | Zhang, Zhongshun Smereka, Jonathon M. Lee, Joseph Zhou, Lifeng Sung, Yoonchang Tokekar, Pratap |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Zhang, Zhongshun Smereka, Jonathon M. Lee, Joseph Zhou, Lifeng Sung, Yoonchang Tokekar, Pratap |
| author_sort | Zhang, Zhongshun |
| collection | MIT |
| description | Abstract
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. |
| first_indexed | 2024-09-23T16:16:17Z |
| format | Article |
| id | mit-1721.1/131973 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T16:16:17Z |
| publishDate | 2021 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1319732023-11-14T19:54:21Z Game tree search for minimizing detectability and maximizing visibility Zhang, Zhongshun Smereka, Jonathon M. Lee, Joseph Zhou, Lifeng Sung, Yoonchang Tokekar, Pratap Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abstract 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. 2021-09-20T17:41:11Z 2021-09-20T17:41:11Z 2021-01-20 2021-03-02T04:51:43Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131973 en https://doi.org/10.1007/s10514-020-09963-4 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Zhang, Zhongshun Smereka, Jonathon M. Lee, Joseph Zhou, Lifeng Sung, Yoonchang Tokekar, Pratap Game tree search for minimizing detectability and maximizing visibility |
| title | Game tree search for minimizing detectability and maximizing visibility |
| title_full | Game tree search for minimizing detectability and maximizing visibility |
| title_fullStr | Game tree search for minimizing detectability and maximizing visibility |
| title_full_unstemmed | Game tree search for minimizing detectability and maximizing visibility |
| title_short | Game tree search for minimizing detectability and maximizing visibility |
| title_sort | game tree search for minimizing detectability and maximizing visibility |
| url | https://hdl.handle.net/1721.1/131973 |
| work_keys_str_mv | AT zhangzhongshun gametreesearchforminimizingdetectabilityandmaximizingvisibility AT smerekajonathonm gametreesearchforminimizingdetectabilityandmaximizingvisibility AT leejoseph gametreesearchforminimizingdetectabilityandmaximizingvisibility AT zhoulifeng gametreesearchforminimizingdetectabilityandmaximizingvisibility AT sungyoonchang gametreesearchforminimizingdetectabilityandmaximizingvisibility AT tokekarpratap gametreesearchforminimizingdetectabilityandmaximizingvisibility |