Hierarchical visibility for guaranteed search in large-scale outdoor terrain

Alexander Dieter Kleiner, Andreas Kolling, Michael Lewis and Katia Sycara
Journal Article, Carnegie Mellon University, Journal of Autonomous Agents and Multi-Agent Systems, 2011, DOI 10.1007/s10458-011-9180-7, July, 2011

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Searching for moving targets in large environments is a challenging task that is relevant in several problem domains, such as capturing an invader in a camp, guarding security facilities, and searching for victims in large-scale search and rescue scenarios. The guaranteed search problem is to coordinate the search of a team of agents to guarantee the discovery of all targets. In this paper we present a self-contained solution to this problem in 2.5D real-world domains represented by digital elevation models (DEMs). We introduce hierarchical sampling on DEMs for selecting heuristically the close to minimal set of locations from which the entire surface of the DEM can be guarded. Locations are utilized to form a search graph on which search strategies for mobile agents are computed. For these strategies schedules are derived which include agent paths that are directly executable in the terrain. Presented experimental results demonstrate the performance of the method. The practical feasibility of our approach has been validated during a field experiment at the Gascola robot training site where teams of humans equipped with iPads successfully searched for adversarial and omniscient evaders. The field demonstration is the largest-scale implementation of a guaranteed search algorithm to date.

author = {Alexander Dieter Kleiner and Andreas Kolling and Michael Lewis and Katia Sycara},
title = {Hierarchical visibility for guaranteed search in large-scale outdoor terrain},
journal = {Journal of Autonomous Agents and Multi-Agent Systems, 2011, DOI 10.1007/s10458-011-9180-7},
year = {2011},
month = {July},
keywords = {Guaranteed search, Pursuit-evasion, Exploration, Task allocation, Path planning, Moving target search, Human-robot-interaction, HRI},
} 2017-09-13T10:40:13-04:00