liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Hierarchical Visibility for Guaranteed Search in Large-Scale Outdoor Terrain
2013 (English)In: Autonomous Agents and Multi-Agent Systems, ISSN 1387-2532, E-ISSN 1573-7454, Vol. 26, no 1, 1-36Article in journal (Refereed) Published
Abstract [en]

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.

National Category
Computer and Information Science Computer Science
Identifiers
urn:nbn:se:liu:diva-70862 (URN)10.1007/s10458-011-9180-7 (DOI)oai:DiVA.org:liu-70862 (OAI)diva2:442226 (DiVA)
Available from2011-09-22 Created:2011-09-20 Last updated:2013-01-16Bibliographically approved

Open Access in DiVA

fulltext(6660 kB)237 downloads
File information
File name FULLTEXT04.pdfFile size 6660 kBChecksum SHA-512
2c6bed48dc594d42d4729c09b68afc421ba02c754c51b72c979c79b0aa25d27173cef57bac429f258561ee2770891c731d9aa4d0bb387d7198e16a01d2fe187d
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Kleiner, AlexanderKolling, A.Lewis, M.Sycara, K.
By organisation
University of Freiburg
In the same journal
Autonomous Agents and Multi-Agent Systems
Computer and Information ScienceComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 237 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 43 hits
ReferencesLink to record
Permanent link

Direct link