Files and links (1)
SubmittedCC BY-NC V4.0, Open
Journal article
Game tree search for minimizing detectability and maximizing visibility
Autonomous robots, v 45(2), pp 283-297
01 Feb 2021
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 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.
Metrics
Details
- Title
- Game tree search for minimizing detectability and maximizing visibility
- Creators
- Zhongshun Zhang - University of Maryland, College ParkJonathon M. Smereka - United States Department of the ArmyJoseph Lee - Aptiv (United States)Lifeng Zhou - Virginia TechYoonchang Sung - Massachusetts Institute of TechnologyPratap Tokekar - University of Maryland, College Park
- Publication Details
- Autonomous robots, v 45(2), pp 283-297
- Publisher
- Springer Nature
- Number of pages
- 15
- 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
- Journal article
- Language
- English
- Academic Unit
- Electrical and Computer Engineering
- Web of Science ID
- WOS:000609046500001
- Scopus ID
- 2-s2.0-85099578026
- Other Identifier
- 991021945764204721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Industry collaboration
- Domestic collaboration
- Web of Science research areas
- Computer Science, Artificial Intelligence
- Robotics