Abstract
This paper addresses a visibility-based pursuit-evasion problem in which a team of mobile robots with limited sensing and communication capabilities must coordinate to detect any evaders in an unknown, multiply-connected planar environment. Our distributed algorithm to guarantee evader detection is built around maintaining complete coverage of the frontier between cleared and contaminated regions while expanding the cleared region. We detail a novel distributed method for storing and updating this frontier without building a map of the environment or requiring global localization. We demonstrate the functionality of the algorithm through simulations in realistic environments and through hardware experiments. We also compare Monte Carlo results for our algorithm to the theoretical optimum area cleared as a function of the number of robots available.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Adler, M., Räcke, H., Sivadasan, N., Sohler, C., & Vöcking, B. (2003). Randomized pursuit-evasion in graphs. Combinatorics, Probability & Computing, 12(3), 225–244.
Bopardikar, S. D., Bullo, F., & Hespanha, J. P. (2008). On discrete-time pursuit-evasion games with sensing limitations. IEEE Transactions on Robotics, 24(6), 1429–1439.
Censi, A. (2008). An ICP variant using a point-to-line metric. In 2008 IEEE int. conf. on robotics and automation, Pasadena, CA (pp. 19–25).
Durham, J. W., & Bullo, F. (2008). Smooth nearness-diagram navigation. In IEEE/RSJ int. conf. on intelligent robots and systems, Nice, France (pp. 690–695).
Durham, J. W., Franchi, A., & Bullo, F. (2010). Distributed pursuit-evasion with limited-visibility sensor via frontier-based exploration. In 2010 IEEE int. conf. on robotics and automation, Anchorage, AK (pp. 3562–3568).
Franchi, A., & Stegagno, P. (2009). Multirobot Integrated Platform. http://www.dis.uniroma1.it/~labrob/software/MIP/.
Franchi, A., Freda, L., Oriolo, G., & Vendittelli, M. (2009a). The sensor-based random graph method for cooperative robot exploration. IEEE/ASME Transactions on Mechatronics, 14(2), 163–175.
Franchi, A., Oriolo, G., & Stegagno, P. (2009b). Mutual localization in a multi-robot system with anonymous relative position measures. In IEEE/RSJ int. conf. on intelligent robots and systems, St. Louis, MO (pp. 3974–3980).
Gerkey, B., et al. (2009). The Player/Stage Project. http://playerstage.sourceforge.net, version 2.13.
Gerkey, B. P., Thrun, S., & Gordon, G. (2006). Visibility-based pursuit-evasion with limited field of view. The International Journal of Robotics Research, 25(4), 299–315.
Hollinger, G., Singh, S., & Kehagias, A. (2010). Improving efficiency of clearing with multi-agent teams. The International Journal of Robotics Research, 29(8), 1088–1105.
Howard, A., Matarić, M. J., & Sukhatme, G. S. (2002). An incremental self-deployment algorithm for mobile sensor networks. Autonomous Robots, 13(2), 113–126.
Jung, B., & Sukhatme, G. S. (2002). Tracking targets using multiple robots: the effect of environment occlusion. Autonomous Robots, 13(3), 191–205.
Kolling, A., & Carpin, S. (2008). Multi-robot surveillance: an improved algorithm for the graph-clear problem. In 2008 IEEE int. conf. on robotics and automation, Pasadena, CA (pp. 2360–2365).
Kolling, A., & Carpin, S. (2010). Multi-robot pursuit-evasion without maps. In 2010 IEEE int. conf. on robotics and automation, Anchorage, Alaska (pp. 3045–3051).
Parsons, T. D. (1978). Pursuit-evasion in a graph. In Y. Alavi & D. Lick (Eds.), Lecture notes in mathematics: Vol. 642. Theory and applications of graphs (pp. 426–441). Berlin: Springer.
Sachs, S., Rajko, S., & LaValle, S. M. (2004). Visibility-based pursuit-evasion in an unknown planar environment. The International Journal of Robotics Research, 23(1), 3–26.
Suzuki, I., & Yamashita, M. (1992). Searching for a mobile intruder in a polygonal region. SIAM Journal on Computing, 21(2), 863–888.
Yamauchi, B. (1998). Frontier-based exploration using multiple robots. In 2nd int. conf. on autonomous agents, Minneapolis, MN (pp. 47–53).
Author information
Authors and Affiliations
Corresponding author
Electronic Supplementary Material
Below are the links to the electronic supplementary material.
Video of a simple illustrative simulation where three robots clear an environment using the proposed distributed clearing algorithm (MPG 3.46 MB)
Video of a hardware experiment in which three robots execute the distributed clearing algorithm. The video includes explanatory captions (MPG 12.3 MB)
Video of a simulation where six robots clear a complex environment modeled off of section of a hospital (MPG 12.5 MB)
10514_2011_9260_MOESM4_ESM.mpg
Video of a simulation where 12 robots expand to clear as much space as possible in an infinite empty environment using the proposed distributed clearing algorithm (MPG 4.64 MB)
Rights and permissions
About this article
Cite this article
Durham, J.W., Franchi, A. & Bullo, F. Distributed pursuit-evasion without mapping or global localization via local frontiers. Auton Robot 32, 81–95 (2012). https://doi.org/10.1007/s10514-011-9260-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-011-9260-1