On fast exploration in 2D and 3D terrains with multiple robots

ABSTRACT

We present a fast multi-robotic exploration methodology for 2D and 3D terrains. An asynchronous exploration strategy is introduced which shows significant improvements over the existing synchronous ones. A per-time visibility metric is being utilized by the algorithm. The metric allots the same weight for points for next view whose visibility over time ratios are equal. The outcome of this is that while the number of points visited to explore a terrain is nearly the same as other popular metrics found in literature, the time length of the paths are smaller in this case resulting in reduced time exploration. The results have been verified through extensive simulations in 2D and 3D. In 2D multiple robots explore unknown terrains that are office like, cluttered, corridor like and various combinations of these. In 3D we consider the case of multiple UAVs exploring a terrain represented as height fields. We introduce a way for calculating expected visibilities and a way of incorporating explored features in the per-time metric. The maximum height of the UAV at each location is governed by the so called exposure surface, beneath which the UAVs are constrained to fly. We also show performance gain of the present metric over others in experiments on a Pioneer 3DX robot.

REFERENCES

• 1: W. Burgard, M. Moors, C. Stachniss, and F. Schneider, "Coordinated Multi Robot Exploration", IEEE Transactions on Robotics, 21(3), 2005.
• 2: 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
• 3: B. Yamauchi, A frontier-based approach for autonomous exploration, Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, p.146, June 10-11, 1997
• 4: I. M. Rekeleitis, G Dudek and E Millios, "Multi-robot Collaboration for Robust Exploration", IEEE ICRA, 2000
• 5: D. Fox, J. Ko, K. Konolige, B. Limketkai, D. Schulz, and B. Stewart, "Distributed Multi-robot Exploration and Mapping", Proc of IEEE, 2006
• 6: M. Batalin and G. S. Sukhatme, (2007), "The Design and Analysis of an Efficient Local Algorithm for Coverage and Exploration Based on Sensor Network Deployment", In IEEE Transactions on Robotics, 23(4):661--675, Aug 2007
• 7: S. Poduri and G. S. Sukhatme "Constrained Coverage for MobileSensor Network". IEEE ICRA (2004), 165--171
• 8: S. K. Ghosh, J. W. Burdick, A. Bhattacharya and S. Sarkar, Online Algorithms with Discrete Visibility: Exploring Unknown Polygonal Environments, Special issue on Computational Geometry approaches in Path Planning, IEEE Robotics&Automation Magazine, vol. 15, no. 2, pp. 67--76, 2008.
• 9: Stephan Eidenbenz, Approximation algorithms for terrain guarding, Information Processing Letters, v.82 n.2, p.99-105, 30 April 2002 [doi>10.1016/S0020-0190(01)00255-1]
• 10: Dominik Joho, Cyrill Stachniss, Patrick Pfaff, and Wolfram Burgard, "Autonomous Exploration for 3D Map Learning", Autonome Mobile Systeme (AMS). Kaiserslautern, Germany, 2007.
• 11: Surmann H, Nüchter A, Hertzberg J, "An autonomous mobile robot with a 3D laser range finder for 3D exploration and digitalization of indoor environments", Robotics and Autonomous Systems, 45(3--4):181--198, 2003.
• 12: Rahul Sawhney , K. Madhava Krishna , Kannan Srinathan , Mahesh Mohan, On reduced time fault tolerant paths for multiple UAVs covering a hostile terrain, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 13: M. Mohan, R. Sawhney, K. M. Krishna, K. Srinathan, M. B. Srikanth, "Covering hostile terrains with partial and complete visibilities: On minimum distance paths". IROS: 2572--2577, 2008
• 14: Alberto Elfes, Occupancy grids: a probabilistic framework for robot perception and navigation, Carnegie Mellon University, Pittsburgh, PA, 1989

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

General Terms:
Algorithms

Keywords:
3D, UAV, exploration, metric, multi robots, terrain