A decentralized strategy for cooperative robot exploration

ABSTRACT

We present a decentralized cooperative exploration strategy for mobile robots. A roadmap of the explored area, with the associate safe region, is built in the form of a compact data structure, called Sensor-based Random Graph. This is incrementally expanded by the robots by using a randomized local planner which automatically realizes a trade-off between information gain and navigation cost. Connecting structures, called bridges, are incrementally added to the graph to create shortcuts and improve the connectivity of the roadmap. Decentralized cooperation and coordination mechanisms are used so as to guarantee exploration efficiency and avoid conflicts. Simulations are presented to show the performance of the proposed technique.

REFERENCES

• 1: Y. Uny Cao , Alex S. Fukunaga , Andrew Kahng, Cooperative Mobile Robotics: Antecedents and Directions, Autonomous Robots, v.4 n.1, p.7-27, March 1997 [doi>10.1023/A:1008855018923]
• 2: G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, "A taxonomy for multi-agent robotics," Autonomous Robots, vol. 3, pp. 375--397, 1996.
• 3: Ioannis Rekleitis , Gregory Dudek , Evangelos Milios, Multi-robot collaboration for robust exploration, Annals of Mathematics and Artificial Intelligence, v.31 n.1-4, p.7-40, 2001 [doi>10.1023/A:1016636024246]
• 4: D. Goldberg and M. Mataric, "Interference as a tool for designing and evaluating multi-robot controllers," in 14th AAAI/9th IAAI, 1997, pp. 637--642.
• 5: Tucker Balch , Ronald C. Arkin, Communication in reactive multiagent robotic systems, Autonomous Robots, v.1 n.1, p.27-52, 1994 [doi>10.1007/BF00735341]
• 6: Brian Yamauchi, Frontier-based exploration using multiple robots, Proceedings of the second international conference on Autonomous agents, p.47-53, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280773]
• 7: W. Burgard, M. Moors, C. Stachniss, and F. Schneider, "Coordinated multi-robot exploration," IEEE Trans. on Robotics and Automation, vol. 1, no. 3, pp. 376--386, 2005.
• 8: J. Ko, B. Stewart, D. Fox, K. Konolige, and B. Limketkai, "A practical, decision-theoretic approach to multi-robot mapping and exploration," in 2003 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2003, pp. 3232--3238.
• 9: A. Howard, M. Mataric, and S. Sukhatme, "An incremental deployment algorithm for mobile robot teams," in 2003 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2003, pp. 2849--2854.
• 10: R. Zlot, A. Stenz, M. Dias, and S. Thayer, "Multi-robot exploration controlled by a market economy," in 2002 IEEE Int. Conf. on Robotics and Automation, 2002, pp. 3016--3023.
• 11: Reid G. Simmons , David Apfelbaum , Wolfram Burgard , Dieter Fox , Mark Moors , Sebastian Thrun , Håkan L. S. Younes, Coordination for Multi-Robot Exploration and Mapping, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.852-858, July 30-August 03, 2000
• 12: A. Franchi, L. Freda, G. Oriolo, and M. Vendittelli, "A randomized strategy for cooperative robot exploration," 2007 IEEE Int. Conf. on Robotics and Automation, pp. 768--774, 2007.
• 13: G. Oriolo, M. Vendittelli, L. Freda, and L. Troso, "The SRT method: Randomized strategies for exploration," in 2004 IEEE Int. Conf. on Robotics and Automation, 2004, pp. 4688--4694.
• 14: L. Freda and G. Oriolo, "Frontier-based probabilistic strategies for sensor-based exploration," in 2005 IEEE Int. Conf. on Robotics and Automation, 2005, pp. 3892--3898.
• 15: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 16: L. Freda, F. Loiudice, and G. Oriolo, "A randomized method for integrated exploration," 2006 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2006.
• 17: Jean Serra, Image Analysis and Mathematical Morphology, Academic Press, Inc., Orlando, FL, 1983
• 18: A. Franchi, L. Freda, G. Oriolo, and M. Vendittelli, "A randomized strategy for cooperative robot exploration," DIS, Università di Roma "La Sapienza", Tech. Rep., 2006.
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 20: F. Harary, Graph Theory. Reading, MA: Addison-Wesley, 1994.
• 21: T. Simeon, J.-P. Laumond, and F. Lamiraux, "Move3d: A generic platform for path planning," in 4th Int. Symp. on Assembly and Task Planning, 2001, pp. 25--30.
• 22: R. Olfati-Saber, J. A. Fax, and R. M. Murray, "Consensus and cooperation in networked multi-agent systems," Proceedings of the IEEE, vol. 95, pp. 215--233, 2007.