Email this article GA-based Global Path Planning for Mobile Robot Employing A* Algorithm
Abstract
Global path planning for mobile robot using genetic algorithm and A* algorithm is investigated in this paper. The proposed algorithm includes three steps: the MAKLINK graph theory is adopted to establish the free space model of mobile robots firstly, then Dijkstra algorithm is utilized for finding a feasible collision-free path, finally the global optimal path of mobile robots is obtained based on the hybrid algorithm of A* algorithm and genetic algorithm. Experimental results indicate that the proposed algorithm has better performance than Dijkstra algorithm in term of both solution quality and computational time, and thus it is a viable approach to mobile robot global path planning.
References
Ge S S, Cui Y J. 2000. New potential functions for mobile robot path planning. IEEE Transactions on Robotics and Automation, 16, 5 (Oct. 2000), 615-620.
http://dx.doi.org/10.1109/70.880813
LI Lei, YE Tao, TAN Min. 2002. Present state and future development of mobile robot technology research. Robot, 24,5 (Sept. 2002), 475-480.
WANG Xing-ce, ZHANG Ru-bo, GU Guo-chang. 2003.Potential grids based on path planning for robots. Journal of Harbin Engineering University, 24, 2(Apr. 2003), 170-174.
Boschian V, Pruski A. 1993. Grid modeling of robot cells: a memory-efficient approach [J]. Journal of Intelligent and Robotic Systems, 8, 2(Oct. 1993), 201-223.
http://dx.doi.org/10.1007/BF01257995
ZHUANG Hui-zhong, DU Shu-xin, WU Tie-jun. 2004. Research on path planning and related algorithms for robots. Bulletin of Science and Technology, 20, 3(May 2004), 210-215.
Yung N H C. Cang Ye. 1999. An intelligent mobile vehicle navigator based on fuzzy logic and reinforcement learning. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 29, 2(Apr. 1999), 314-321.
http://dx.doi.org/10.1109/3477.752807
PMid:18252306
Lebedev D. 2001. Neural network model for robot path planning in dynamically changing environment. Modeling and Analysis of Information Systems, 18,1 (2001),12-18.
Liu Cai-hong, Hu Ji-quan, Qi Xiao-ning. 2003. Path design of robot with continuous space based on hybrid genetic algorithm. Journal of Wuhan University of Technology (Transportation Science & Engineering), 27, 6 (Dec. 2003),819-821.
S. Kirkpatrick, C. D. Gelatt Jr., and M. P. Vecchi. 1983.Optimization by Simulated Annealing. Science, 220, 4598(May 1983), 671-680.
http://dx.doi.org/10.1126/science.220.4598.671
PMid:17813860
Romeijn H E. Smith R L. 1994. Simulated Annealing for Constrained Global Optimization. Journal of Global Optimization, 5, 2 (Sept. 1994), 101-124.
http://dx.doi.org/10.1007/BF01100688
Zhao Ming-ru,Guo Jian,Sun Yuan.2009. Application of A* Algorithm in Map Path-Searching. Journal of Science&Technology Information. 31,6(Oct.2009),411- 413.
Yahya Rahmat-Samii, Eric Michielssen. 1999. Electromagnetic Optimization by Genetic Algorithms. John Wiley & Sons, Inc., New York, USA.
Ming Zhou, ShuDong Kong. 1999. Genetic Algorithm:Theory and Applications. National defense industry publishing company, Beijing
Sugihara, K. and Smith, J., 1997 . “Genetic Algorithms for Adaptive Motion Planning of an autonomous Mobile Robot”, Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, CA, pp. 138-146
Obitko, M., “Genetic Algorithms”, Internet publication, 1998, http://cs.felk.cvut.cz/~xobitko/ga/main.html
Hwang, Y.K., Ahuja, N.,September 1992. “Gross Motion Planning – A Survey”,ACM Computing Surveys, volume 24, issue 3, pp. 219-291.
http://dx.doi.org/10.1145/136035.136037
Arsene, C.T.C. and Zalzala, A.M.S., 1999. “Control of Autonomous Robots Using Fuzzy Logic Controllers Tuned by Genetic Algorithms”, Proceedings of the 1999 Congress on Evolutionary Computation (CEC99), pp. 428-435.
Kubota, N., Morioka, T., Kojima, F. and Fukuda, T., 1999. “Perception-Based Genetic Algorithm for a Mobile Robot with Fuzzy Controllers”, Proceedings of the 1999 Congress on Evolutionary Computation (CEC99), pp. 397-404.
Pratihar, D.K., Deb, K. and Ghosh, A. 1999. “Fuzzy-Genetic Algorithms and Mobile Robot Navigation among Static Obstacles”, Proceedings of the 1999 Congress on Evolutionary Computation (CEC99), pp. 327-334.
Cazangi, R.R. and Figuieredo, M., 2002. “Simultaneous Emergence of Conflicting Basic Behaviors and Their Coordination in an Evolutionary Autonomous Navigation System”, Proc. 2002 IEEE Conf. on Evol. Comp. (CEC '02), IEEE.
Di Gesu, V., Lenzitti, B., Lo Bosco, G. and Tegolo, D., 2000. “A Distributed Architecture for Autonomous Navigation of Robots”, Proceedings Fifth IEEE International Workshop on Computer Architectures for Machine Perception, pp. 190 – 194.
http://dx.doi.org/10.1109/CAMP.2000.875977
Gallardo, D. and Colomina, O., “A Genetic Algorithm for Robust Motion Planing”, Eleventh International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Castellon, Spain, June, pp. 115-121, 1998.
Vadakkepat, P. and Chen, T.K., “Evolutionary Artificial Potential Fields and Their Application in Real Time Robot Path Planning”,Proceeding of the 2000 Congress on Evolutionary Computation, San Diego, CA, pp. 256-264, 2000.
Hocaoglu, C. and Sanderson, A.C., "Planning Multiple Paths with Evolutionary Speciation", IEEE Trans. Evolutionary Computation,vol. 5, no. 3, pp. 169-191, June 2001.
http://dx.doi.org/10.1109/4235.930309
Xiao, J. and Zhang, L., “Adaptive Evolutionary Planner/Navigator for Mobile Robots”, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, pp. 18-28, April 1997.
http://dx.doi.org/10.1109/4235.585889
Trivedi, N., Lai, W. and Zhang, Z., “Optimizing Windows Layout by Applying a Genetic Algorithm”, Proceedings of the 2001 Congress on Evolutionary Computation, Seoul, Korea, pp. 431-435, 2001
Filho, J.L.R. and Treleaven, P.C., “Genetic Algorithm Programming Environment”, IEEE Computer, pp. 28-43, June 1994.
Srinivas, M. and Patnaik, L.M., “Genetic Algorithms: A survey”,IEEE computer, pp. 17-26, June 1994.
Full Text: PDF