The shortest path planning for mobile robots using improved A* algorithm
WANG Wei1, PEI Dong1,2, FENG Zhang1
1. College of Physics and Electronic Engineering, Northwest Normal University, Lanzhou Gansu 730030, China; 2. Engineering Research Center of Gansu Province for Intelligence Information Technology and Application, Lanzhou Gansu 730030, China
Abstract：Aiming at the poor real-time performance of mobile robot path planning in complex indoor environment, a further improvement on A* algorithm was proposed by analyzing and comparing Dijkstra algorithm, traditional A* algorithm and some improved A* algorithms. Firstly, the estimated path cost of the current node and its parent node were weighted in exponentially decreasing way. In this way, when the current code was far away from the target, the improved algorithm could search towards to the target quickly instead of searching around the start node. While the current code was near to the target, the algorithm could search the target carefully to ensure that the target was reachable. Secondly, the generated path was smoothed by quintic polynomia to further shorten the path and facilitate robot control. The simulation results show that compared with the traditional A* algorithm, the proposed algorithm can reduce the searching time by 93.8% and reduce the path length by 17.6% and get the path without quarter turning point, so that the robot could get to the destination along the planned path without a break. The proposed algorithm is verified in different scenarios, and the results show that the proposed algorithm can adapt to different environments and has good real-time performance.
[1] ULUSOY A, SMITH S L, DING X, et al. Optimal multi-robot path planning with temporal logic constraints[C]//Proceedings of the 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway, NJ:IEEE, 2011:3087-3092. [2] HOU Y B, WANG W, LU X. Mobile robot path planning and research in the improved artificial immune algorithm[J]. Advanced Materials Research, 2012, 466/467:864-869. [3] ABBADI A, MATOUSEK R, MINAR P, et al. RRTs review and options[EB/OL].[2017-06-20].http://wseas.us/e-library/conferences/2011/Iasi/IAASAT/IAASAT-32.pdf. [4] BERG J P V D, OVERMARS M H. Roadmap-based motion planning in dynamic environments[J]. IEEE Transactions on Robotics, 2005, 21(5):885-897. [5] BOSCHIAN V, PTUSKI A. Grid modeling of robot cells:a memory-efficient approach[J]. Journal of Intelligent & Robotic Systems, 1993, 8(2):201-223. [6] GEOPERIN D. On the optimality of A[J]. Artificial Intelligence, 1977, 8(1):69-76. [7] LI J, SUN X X. Route planning's method for unmanned aerial vehicles based on improved A* algorithm[J]. Acta Armamentarii, 2008, 29(7):788-792. [8] MENG M, YANG X. A neural network approach to real-time trajectory generation[C]//Proceedings of the 1998 IEEE International Conference on Robotics and Automation. Piscataway, NJ:IEEE, 1998:1725-1730. [9] NI B, XIONG C. New approach of neural network for robot path planning[C]//Proceedings of the 2004 IEEE International Conference on Systems, Man and Cybernetics. Piscataway, NJ:IEEE, 2004:735-739. [10] 诸静. 模糊控制原理与应用[M]. 机械工业出版社, 2005:344-355.(ZHU J. Fuzzy Control Theories and Applications[M]. Beijing:China Machine Press, 2005:344-355.) [11] 韩启纲. 计算机模糊控制技术与仪表装置[M]. 中国计量出版社, 1999:78-80.(HAN Q G. Computer Fuzzy Control Technology and Instrument Device[M]. Beijing:China Measurement Press, 1999:78-80.) [12] CORMEN T H, LEISERSON C E, RIVEST R L, et al. Introduction to Algorithms[M]. 3rd ed. Cambridge:MIT Press, 2009:415-423. [13] MOHAJER B, KIANI K, SAMIEI E, et al. A new online random particles optimization algorithm for mobile robot path planning in dynamic environments[J]. Mathematical Problems in Engineering,2013, 2013(2):Article ID 491346. [14] ARAUJO R. Prune-able fuzzy ART neural architecture for robot map learning and navigation in dynamic environments[J]. IEEE Transactions on Neural Networks, 2006, 17(5):1235-1249. [15] LIN M, YUAN K, SHI C, et al. Path planning of mobile robot based on improved A* algorithm[C]//Proceedings of the 201729th Chinese Control and Decision Conference. Piscataway, NJ:IEEE, 2017:3570-3576. [16] 赵真明,孟正大. 基于加权A*算法的服务型机器人路径规划[J]. 华中科技大学学报(自然科学版),2008,36(S1):196-198.(ZHAO Z M, MENG Z D. Path planning of service mobile robot based on adding-weight A* algorithm[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2008,36(S1):196-198.) [17] 王红卫,马勇, 谢勇,等. 基于平滑A*算法的移动机器人路径规划[J]. 同济大学学报(自然科学版),2010,38(11):1647-1650.(WANG H W, MA Y, XIE Y, et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University (Natural Science), 2010,38(11):1647-1650.) [18] 吴宪祥,郭宝龙, 王娟. 基于粒子群三次样条优化的移动机器人路径规划算法[J]. 机器人,2009,31(6):556-560.(WU X X, GUO B L, WANG J. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. Robot, 2009,31(6):556-560.) [19] 张文,刘勇, 张超凡,等. 基于方向A*算法的温室机器人实时路径规划[J]. 农业机械学报, 2017,48(7):22-28.(ZHANG W, LIU Y, ZHANG C F, et al. Real-time path planning of the greenhouse robot based on directional A* algorithm[J].Transactions of the Chinese Society for Agricultural Machinery, 2017,48(7):22-28.) [20] CORKE P. Robotics, Vision and Control[M]. Berlin:Springer, 2011:63-67. WANG Wei, born in 1991, M. S. candidate. His research interests include robot localization and navigation, machine learning.PEI Dong, born in 1965, associate professor. His research interests include pattern recognition, robot control.FENG Zhang, born in 1992, M. S. candidate. His research interests include computer vision, image processing.
2018, Vol. 38 
