Sage Journals: Discover world-class research

Abstract

We present an anytime algorithm for coordinating multiple autonomous searchers to find a potentially adversarial target on a graphical representation of a physical environment. This problem is closely related to the mathematical problem of searching for an adversary on a graph. Prior methods in the literature treat multi-agent search as either a worst-case problem (i.e. clear an environment of an adversarial evader with potentially infinite speed), or an average-case problem (i.e. minimize average capture time given a model of the target’s motion). Both of these problems have been shown to be NP-hard, and optimal solutions typically scale exponentially in the number of searchers. We propose treating search as a resource allocation problem, which leads to a scalable anytime algorithm for generating schedules that clear the environment of a worst-case adversarial target and have good average-case performance considering a non-adversarial motion model. Our algorithm yields theoretically bounded average-case performance and allows for online and decentralized operation, making it applicable to real-world search tasks. We validate our proposed algorithm through a large number of experiments in simulation and with a team of robot and human searchers in an office building.

Keywords

multi-robot coordination autonomous search pursuit/evasion decentralized planning

Get full access to this article

View all access options for this article.

References

Alspach, B. ( 2006). Searching and sweeping graphs: a brief survey. Matematiche, 59: 5-37.

Barrière, L. , Flocchini, P. , Fraigniaud, P. and Santoro, N. ( 2002). Capture of an intruder by mobile agents. Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures, pp. 200-209.

Borie, R. , Tovey, C. and Koenig, S. ( 2009). Algorithms and complexity results for pursuit-evasion problems. Proceedings of the International Joint Conference on Artificial Intelligence.

Calisi, D. , Farinelli, A. , Locchi, L. and Nardi, D. ( 2007). Multi-objective exploration and search for autonomous rescue robots. Journal of Field Robotics, 24(8-9): 763-777.

Fomin, F. and Thilikos, D. ( 2008). An annotated bibliography on guaranteed graph searching . Theoretical Computer Science, 399: 236-245.

Gerkey, B. , Thrun, S. and Gordon, G. ( 2005). Parallel stochastic hill-climbing with small teams. Proceedings of the 3rd International NRL Workshop Multi-Robot Systems.

Gerkey, B. , Vaughan, R. and Howard, A. ( 2003). The player/stage project: Tools for multi-robot and distributed sensor systems. Proceedings of the International Conference on Advanced Robotics, pp. 317-323.

Guibas, L. , Latombe, J. , LaValle, S. , Lin, D. and Motwani, R. ( 1999). Visibility-based pursuit-evasion in a polygonal environment . International Journal of Computational Geometry and Applications , 9(5): 471-494.

Hollinger, G. , Kehagias, A. and Singh, S. ( 2009a). Efficient, guaranteed search with multi-agent teams . Proceedings of the Robotics: Science and Systems Conference

10.

Hollinger, G. , Kehagias, A. and Singh, S. ( 2010). GSST: Anytime guaranteed search. Autonomous Robots, DOI: 10.1007/s10514-010-9189-9.

11.

Hollinger, G. , Kehagias, A. , Singh, S. , Ferguson, D. , and Srinivasa, S. ( 2008). Anytime guaranteed search using spanning trees. Technical Report CMU-RI-TR-08-36, Robotics Institute, Carnegie Mellon Univ.

12.

Hollinger, G. , Singh, S. , Djugash, J. and Kehagias, A. ( 2009b). Efficient multi-robot search for a moving target. The International Journal of Robotics Research, 28(2): 201- 219.

13.

Kehagias, A. , Hollinger, G. and Gelastopoulos, A. ( 2009). Searching the Nodes of a Graph: Theory and Algorithms. arXiv Repository Technical Report 0905.3359 [cs.DM], May 2009.

14.

Kolling, A. and Carpin, S. ( 2008). Extracting surveillance graphs from robot maps. Proceedings of the International Conference on Intelligent Robots and Systems.

15.

Kolling, A. and Carpin, S. ( 2009). Probabilistic graph-clear. Proceedings of the IEEE International Conference on Robotics and Automation .

16.

Kolling, A. and Carpin, S. ( 2010). Pursuit-evasion on trees by robot teams. IEEE Transactions on Robotics, 26: 32-47.

17.

Krause, A. , McMahan, B. , Guestrin, C. and Gupta, A. ( 2007). Selecting observations against adversarial objectives . Proceedings of Neural Information Processing Systems.

18.

Krause, A. , McMahan, B. , Guestrin, C. and Gupta, A. ( 2008). Robust submodular observation selection. Journal of Machine Learning Research, 9: 2761-2801.

19.

Kumar, V. , Rus, D. and Singh, S. ( 2004). Robot and sensor networks for first responders. Pervasive Computing, 3(4): 24-33.

20.

Megiddo, N. , Hakimi, S. , Garey, M. , Johnson, D. and Papadimitriou, C. ( 1988). The complexity of searching a graph. Journal of the ACM, 35(1): 18-44.

21.

Ong, S. , Png, S. , Hsu, D. and Lee, W. ( 2009). POMDPs for robotic tasks with mixed observability. Proceedings of the Robotics: Science and Systems Conference

22.

Parsons, T. ( 1976). Pursuit-evasion in a graph. Theory and Applications of Graphs, Alavi, Y. and Lick, D. (eds). Berlin, Springer, pp. 426-441.

23.

Roy, N. , Gordon, G. and Thrun, S. ( 2003). Planning under uncertainty for reliable health care robotics . Proceedings of the International Conference on Field and Service Robotics.

24.

Sarmiento, A. , Murrieta-Cid, R. and Hutchinson, S. ( 2004). A multi-robot strategy for rapidly searching a polygonal environment. Proceedings of the 9th Ibero-American Conference Artificial Intelligence.

25.

Shewchuk, J. ( 2002). Delaunay refinement algorithms for triangular mesh generation . Computational Geometry: Theory and Applications, 22(1-3): 21-74.

26.

Singh, A. , Krause, A. , Guestrin, C. , Kaiser, W. and Batalin, M. ( 2007). Efficient planning of informative paths for multiple robots. Proceedings of the International Joint Conference on Artificial Intelligence.

27.

Smith, T. ( 2007). Probabilistic Planning for Robotic Exploration. PhD Thesis , Robotics Institute, Carnegie Mellon University.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB