Selection of Optimal Path Planning Algorithm for Autonomous Robots in Structured Environment
Abstract
To determine a collision free path for a robot between start and goal positions in an environment filled with obstacles is a very challenging task in the design of an autonomous robot path planning. This paper aims to select an optimal path planning algorithm for a mobile robot in structured environment. To achieve the goal, comprehensive strengths and weaknesses of different path planning algorithm are discussed and evaluated. A wooden box with some fixed obstacles and robot inside it is basically the environment. Information about the environment is used to build a roadmap or graph of the environment. After getting a convenient representation of the environment, then graph search methods can be used to obtain shortest possible path through this roadmap. It is well known that computing shortest paths for autonomous robots is an important task in many path planning applications. Selecting a suitable algorithm from the various algorithms reported in the literature is a decisive step in many applications including path planning task. A set of three shortest path algorithms that compute optimal path from start to goal location has been identified and these are Uniform Cost Search, Greedy Search and A* algorithm. After comparing execution time and path length of path computed by these three algorithms, A * algorithm proves to be best suited for this particular application of path planning.References
N. Padoy, T. Blum, A. Ahmadi, H. Feußner, M.O. Berger and
N. Navab, J. Med. Image Analysis 16 (2010) 632.
M. V. Kreveld, M. de Berg and M. Overmars, Computational
Geometry: Algorithms and Applications, Springer, Berlin (1997).
D. Dolgov, S. Thrun, M. Montemerlo and J. Diebel, Springer Tracts
in Advanced Robotics 54 (2009) 55.
J.Reif, Complexity of the Mover's Problem and Generalizations,
Proc. of 20th Symp. on the Foundations of Computer Science (1979)
pp. 421–427.
J. Bruce, T. Balch and Manuela Veloso, Fast and Inexpensive Color
Image Segmentation for Interactive Robots, Proc. of IEEE/RSJ Int.
Conf. on Intelligent Robots and Systems, Takamatsu (2000)
pp. 2061-2066.
R. T. McKeon, M. Krishnan and M. Paulik, Obstacle Recognition
Using Region- Based Color Segmentation Techniques for Mobile
Robot Navigation, Proc. SPIE 6384, Intelligent Robots and
Computer Vision (2006) 63840R.
M. Agrawal, A. Sundaresan, M.R. Blas and K. Konolige, Fast Color/
Texture Segmentation for Outdoor Robots, IEEE/RSJ Inter. Conf. on
Intelligent Robots and Systems (2008) pp. 22-26.
A. Mishra, Y. Aloimonos, and C. Fermuller, Active Segmentation for
Robotics, IEEE/RSJ Inter. Conf. on Intelligent Robots and Systems
(2009) pp. 3133-3139.
C. Harris and M. Stephens, A Combined Corner and Edge Detector,
th ALVEY Vision Conf.(1988) pp. 147-151.
J.M.B. Susan and S.M. Smith, Inter. J. of Comp. Vision 23 (1997)
X. C. He and N. H. C. Yung, Optical Engg.47 (2008) 5.
A. Rattarangsi and R. T. Chin, IEEE Trans. Pattern Anal. Mach.
Intell. 14 (1992) 430.
J. Canny, Artificial Intelligence 37 (1988) 203.
S.R. Lindemann and S.M. LaValle, Incremental Low-Discrepancy
Lattice Methods for Motion Planning, IEEE Inter. Conf. on Robotics
and Automation (2003) pp. 2920-2927.
M.H. Overmars and E. Welzl, New Methods for Computing
Visibility Graphs, 4th Annual Symp.on Computational Geometry,
New York, NY, USA (1988) pp. 164-171.
S. K. Ghosh and D.M. Mount, SIAM Journal on Computing 20
(1991) 888.
H. Choset, Sensor Based Motion Planning: The Hierarchical
Generalized Voronoi Graph, Ph.D Thesis, California Institute of
Technology (1996).
F.P. Preparata and M.I. Shamos, Computational Geometry:
An Introduction, Springer-Verlag (1985).
A.A. Rizzi, P. Atkar, E. U. Acar, H. Choset and D. Hull, Inter.
J. of Robotics Res. 21 (2002) 331.
P. E. Hart, N. J. Nilsson and B. Raphael, SIGART Bulletin 37 (1972)
A. Stentz, The focused D* Algorithm for Real-time Re-planning,
th Inter. Joint Conf. on Artificial intelligence, San Francisco, CA,
USA (1995) pp. 1652-1659.
