An Integrated Algorithm for Autonomous Navigation of a Mobile Robot in an Unknown Environment
Lee Gim Hee* and Marcelo H. Ang Jr.**
*DSO National Laboratories, 20 Science Park Drive, Singapore 118230
**Department of Mechanical Engineering, National University of Singapore, 9 Engineering Drive 1, Singapore 117576
Global path planning algorithms are good in planning an optimal path in a known environment, but would fail in an unknown environment and when reacting to dynamic and unforeseen obstacles. Conversely, local navigation algorithms perform well in reacting to dynamic and unforeseen obstacles but are susceptible to local minima failures. A hybrid integration of both the global path planning and local navigation algorithms would allow a mobile robot to find an optimal path and react to any dynamic and unforeseen obstacles during an operation. However, the hybrid method requires the robot to possess full or partial prior information of the environment for path planning and would fail in a totally unknown environment. The integrated algorithm proposed and implemented in this paper incorporates an autonomous exploration technique into the hybrid method. The algorithm gives a mobile robot the ability to plan an optimal path and does online collision avoidance in a totally unknown environment.
-  J. -C. Latombe, “Robot Motion Planning,” Boston Kluwer Academic Publishers, 1991.
-  V. Akman, “Unobstructed Shortest Paths in Polyhedral Environments,” Lecture Notes in Computer Science, Springer-Verlag, 1987.
-  C. ’Dnliang and C. Yap, “Retraction: A New Approach to Motion Planning,” Proceeding of the 15th ACM Symposium on the Theory of Computing, Boston, pp. 207-220, 1983.
-  J. Schwartz and M. Sharir, “On the Piano Movers’ Problem: The Case if a Two-Dimensional Rigid Polygonal Body Moving Amidst Polygonal Barriers,” Communications on Pure and Applied Mathematics, Vol.36, pp. 345-398, 1983.
-  J. Borenstien and Y. Koren, “The Vector Field Histogram – Fast Obstacle Avoidance For Mobile Robots,” IEEE Journal of Robotics and Automation Vol.7, No.3, pp. 278-288, June 1991.
-  J. Borenstien and Y. Koren, “Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation,” Proc. of the IEEE Conf. on Robotics and Automation, Sacramento, California, pp.1398-1404, April 7-12, 1991.
-  O. Khatib, “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” Int. Journal of Robotic Research, Vol.5, No.1, pp. 90-98, 1986.
-  B. Yamauchi, “A Frontier-Based Approach for Autonomous Exploration,” Proc. of the IEEE Int. Symposium on the Computational Intelligence in Robotics and Automation, Monterey, CA, pp. 146-151, 1997.
-  C. W. Lim, S. Y. Lim, and M. H. Ang Jr., “Hybrid of Global Path Planning and Local Navigation implemented on a Mobile Robot in Indoor Environment,” Proc. of the 2002 IEEE Int. Symposium on Intelligent Control, Vancouver Canada, pp. 821-826, 2002.
-  S. Thrun, W. Burgard, and D. Fox, “Probabilistic Robotics,” The MIT Press, Cambridge Massachusetts, London, England, 2005.