Coordination for Multi-Robot Exploration and Mapping

Reid G. Simmons David Apfelbaum Wolfram Burgard
Dieter Fox Mark Moors Sebastian Thrun Håkan L. S. Younes

Abstract
This paper addresses the problem of exploration and mapping of an unknown environment by multiple robots. The mapping algorithm is an on-line approach to likelihood maximization that uses hill climbing to find maps that are maximally consistent with sensor data and odometry. The exploration algorithm explicitly coordinates the robots. It tries to maximize overall utility by minimizing the potential for overlap in information gain amongst the various robots. For both the exploration and mapping algorithms, most of the computations are distributed. The techniques have been tested extensively in real-world trials and simulations. The results demonstrate the performance improvements and robustness that accrue from our multi-robot approach to exploration.

Full paper: PDF, PS (7 pages, 22 references)
Copyright © 2000, American Association for Artificial Intelligence. All rights reserved.

Citings

  1. Benjamín Tovar, Lourdes Muñoz-Gómez, Rafael Murrieta-Cid, Moisés Alencastre-Miranda, Raúl Monroy, and Seth Hutchinson. 2006. Planning exploration strategies for simultaneous localization and mapping. Robotics and Autonomous Systems 54(4):314–331.

  2. Robert Zlot and Anthony Stentz. 2006. Market-based multirobot coordination for complex tasks. The International Journal of Robotics Research 25(1):73–101.

  3. Francesco Amigoni and Alessandro Gallo. 2005. A multi-objective exploration strategy for mobile robots. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 3850–3855. IEEE Robotics and Automation Society.

  4. Jeremy Grace and John Baillieul. 2005. Stochastic strategies for autonomous robotic surveillance. In Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference 2005, 2200–2205. IEEE Control Systems Society.

  5. Weihua Sheng, Qizhi Wang, Qingyan Yang, and Shenghuo Zhu. 2005. Minimizing data exchange in ad hoc multi-robot networks. In Proceedings of the 12th International Conference on Advanced Robotics, 811–816. IEEE.

  6. Weihua Sheng and Qingyan Yang. 2005. Peer-to-peer multi-robot coordination algorithms: Petri net based analysis and design. In Proceedings of the 2005 IEEE/ASME International Conference on Advanced Intelligent Mechatronics, 1407–1412. IEEE.

  7. Weihua Sheng, Qingyan Yang, Shenghuo Zhu, and Qizhi Wang. 2005. Efficient map synchronization in ad hoc mobile robot networks for environment exploration. In Proceedings of the 2005 IEEE/RSJ International Conference on Intelligent Robots and Systerms, 2297–2302. IEEE.

  8. Fei Zhang, Weidong Chen, and Yugeng Xi. 2005. Improving collaboration through fusion of bid information for market-based multi-robot exploration. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 1157–1162. IEEE Robotics and Automation Society.

  9. Robert Zlot and Anthony Stentz. 2005. Complex task allocation for multiple robots. In Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 1515–1522. IEEE Robotics and Automation Society.

  10. Michail G. Lagoudakis, Marc Berhault, Sven Koenig, Pinar Keskinocak, and Anton J. Kleywegt. 2004. Simple auctions with performance guarantees for multi-robot task allocation. In Proceedings of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems, 698–705. IEEE.

  11. Luís Macedo and Amílcar Cardoso. 2004. Exploration of unknown environments with motivational agents. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 328–335. IEEE Computer Society.

  12. Luís Macedo and Amílcar Cardoso. 2004. Using CBR in the exploration of unknown environments with an autonomous agent. In Proceedings of the 7th European Conference on Advances in Case-Based Reasoning, 272–286. Springer.

  13. Alexei Makarenko, Alex Brooks, Stefan Williams, Hugh Durrant-Whyte, and Ben Grocholsky. 2004. A decentralized architecture for active sensor networks. In Proceedings of the 2004 IEEE International Conference on Robotics and Automation, 1097–1102. IEEE Robotics and Automation Society.

  14. Alexei Makarenko and Hugh Durrant-Whyte. 2004. Decentralized data fusion and control in active sensor networks. In Proceedings of the Seventh International Conference on Information Fusion, 479–486.

  15. Dan O. Popa, Arthur C. Sanderson, Rick J. Komerska, Sai S. Mupparapu, D. Richard Blidberg, and Steven G. Chappel. 2004. Adaptive sampling algorithms for multiple autonomous underwater vehicles. In 2004 IEEE/OES Autonomous Underwater Vehicles, 108–118. IEEE.

  16. Chomchana Trevai, Yusuke Fukazawa, Hideo Yuasa, Jun Ota, Tamio Arai, and Hajime Asama. 2004. Exploration path generation for multiple mobile robots using reaction-diffusion equation on a graph. Integrated Computer-Aided Engineering 11(3):195–212.

  17. Junko Araki. 2003. Action vectors: Modeling spatial relations between objects and routes. Journal of Universal Computer Science 9(9):1046–1072.

  18. M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby, P. Griffin, and A. Kleywegt. 2003. Robot exploration with combinatorial auctions. In Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 1957–1962. IEEE.

  19. Jérémi Gancet and Simon Lacroix. 2003. PG2P: A perception-guided path planning approach for long range autonomous navigation in unknown natural environments. In Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2992–2997. IEEE.

  20. Robert Grabowski, Pradeep Khosla, and Howie Choset. 2003. An enhanced occupancy map for exploration via pose separation. In Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 705–710. IEEE.

  21. Robert Grabowski, Pradeep Khosla, and Howie Choset. 2003. Autonomous exploration via regions of interest. In Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 1691–1696. IEEE.

  22. Alexei Makarenko, Tobias Kaupp, Ben Grocholsky, and Hugh Durrant-Whyte. 2003. Human-robot interactions in active sensor networks. In Proceedings of the 2003 IEEE International Symposium on Computational Intelligence in Robotics and Automation, 247–252. IEEE.

  23. Craig Tovey and Sven Koenig. 2003. Improved analysis of greedy mapping. In Proceedings of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems, 3251–3257. IEEE.

  24. Chomchana Trevai, Tusuke Fukazawa, Hideo Yuasa, Jun Ota, Tamio Arai, and Hajime Asama. 2003. Exploration-path generation of multiple mobile robots using reaction-diffusion equation on a graph. In Proceedings of the 2003 IEEE International Symposium on Computational Intelligence in Robotics and Automation, 1114–1119. IEEE.

  25. M. Baglietto, M. Paolucci, L. Scardovi, and R. Zoppoli. 2002. Information-based multi-agent exploration. In Proceedings of the Third International Workshop on Robot Motion and Control, 173–179. IEEE.

  26. Sebastian Buck, Thorsten Schmitt, and Michael Beetz. 2002. Reliable multi-robot coordination using minimal communication and neural prediction. In Advances in Plan-Based Control of Robotic Agents, 36–51. Springer.

  27. Andrew Howard, Maja J. Mararić, and Gaurav S. Sukhatme. 2002. An incrementral self-deployment algorithm for mobile sensor networks. Autonomous Robots 13(2):113–126.

  28. Andrew Howard, Maja J. Mararić, and Gaurav S. Sukhatme. 2002. An incremental deployment algorithm for mobile robot teams. In Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2849–2854. IEEE.

  29. Alexei A. Makarenko, Stefan B. Williams, Frederic Bourgault, and Hugh F. Durrant-Whyte. 2002. An experiment in integrated exploration. In Proceedings of the 2002 IEEE/RSJ International Conference on Intelligent Robots and Systems, 534–539. IEEE.

  30. Amitabha Mukerjee and Amol Dattatraya Mali. 2002. Modular models of intelligence—review, limitations, and prospects. Artificial Intelligence Review 17(1):39–64.

  31. B. Trouvian and H. L. Wolf. 2002. Evaluation of multi-robot control and monitoring performance. In Proceedings of the 2002 IEEE International Workshop on Robot and Human Interactive Communication, 111–116. IEEE.

  32. Robert Zlot, Anthony Stentz, M. Bernardine Dias, and Scott Thayer. 2002. Multi-robot exploration controlled by a market economy. In Proceedings of the 2002 IEEE International Conference on Robotics and Automation, 3016–3023. IEEE Robotics and Automation Society.

  33. Robert Grabowski and Pradeep Khosla. 2001. Localization techniques for a team of small robots. In Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems, 1067–1072. IEEE.

  34. Sven Koenig. 2001. Agent-centered search. AI Magazine 22(4):109-131.


Valid XHTML 1.0! Håkan L. S. Younes Home > Publications ]
Last modified: Thu May 25 14:44:00 EDT 2006