Conference proceeding
Tree Search Techniques for Minimizing Detectability and Maximizing Visibility
2019 International Conference on Robotics and Automation (ICRA), pp 8791-8797
01 Jan 2019
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We introduce and study the problem of planning a trajectory for an agent to carry out a reconnaissance mission while avoiding being detected by an adversarial guard. 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 guard. 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 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. We also find that the Monte-Carlo search tree saves approximately one order of computational time as compared to the minimax search tree.
Metrics
Details
- Title
- Tree Search Techniques for Minimizing Detectability and Maximizing Visibility
- Creators
- Zhongshun Zhang - Virginia TechJoseph Lee - United States ArmyJonathon M. Smereka - United States ArmyYoonchang Sung - Virginia TechLifeng Zhou - Virginia TechPratap Tokekar - Virginia Tech
- Publication Details
- 2019 International Conference on Robotics and Automation (ICRA), pp 8791-8797
- Conference
- 2019 International Conference on Robotics and Automation (ICRA) (Montreal, Quebec, Canada, 20 May 2019–24 May 2019)
- Series
- IEEE International Conference on Robotics and Automation ICRA
- Publisher
- IEEE
- Number of pages
- 7
- Grant note
- W56HZV-14-2-0001 / Department of Defense; United States Department of Defense Automotive Research Center (ARC) at the University of Michigan
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000494942306069
- Scopus ID
- 2-s2.0-85071511878
- Other Identifier
- 991021945756604721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
Source: SDGs in the Output
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Automation & Control Systems
- Robotics