@article {48,
	title = {Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain},
	journal = {JAAMAS},
	volume = {26},
	year = {2013},
	pages = {1{\textendash}36},
	abstract = {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.},
	keywords = {Exploration, guaranteed search, HRI, Human{\textendash}robot-interaction, Moving target search, path planning, pursuit-evasion, task allocation},
	issn = {1387-2532},
	doi = {10.1007/s10458-011-9180-7},
	url = {http://dx.doi.org/10.1007/s10458-011-9180-7},
	author = {Kleiner, A. and Kolling, A. and Lewis, M. and Sycara, K.}
}
@conference {42,
	title = {Multi-UAV Motion Planning for Guaranteed Search},
	booktitle = {Proc. of the 12th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2013)},
	year = {2013},
	address = {St. Paul, MN, USA},
	abstract = {We consider the problem of detecting all moving and evading targets in 2.5D environments with teams of UAVs. Targets are assumed to be fast and omniscient while UAVs are only equipped with limited range detection sensors and have no prior knowledge about the location of targets. We present an algorithm that, given an elevation map of the environment, computes synchronized trajectories for the UAVs to guarantee the detection of all targets. The approach is based on coordinating the motion of multiple UAVs on sweep lines to clear the environment from contamination, which represents the possibility of an undetected target being located in an area. The goal is to compute trajectories that minimize the number of UAVs needed to execute the guaranteed search. This is achieved by converting 2D strategies, computed for a polygonal representation of the environment, to 2.5D strategies. We present methods for this conversion and consider cost of motion and visibility constraints. Experimental results demonstrate feasibility and scalability of the approach. Experiments are carried out on real and artificial elevation maps and provide the basis for future deployments of large teams of real UAVs for guaranteed search.},
	keywords = {guaranteed search, multi-robot, multi-UAV, pursuit-evasion},
	isbn = {978-1-4503-1993-5},
	url = {http://dl.acm.org/citation.cfm?id=2484920.2484936},
	author = {A. Kolling and A. Kleiner}
}
