Abstract:A hybrid algorithm combining the improved A* algorithm and the dynamic window method is proposed, to solve the problem of mobile robot path planning in multi-target complex environments. In order to improve the algorithm efficiency by planning a path passing through multiple target points in a single run, and to improve the flexibility of path smoothing and meet the non-holonomic constraints of mobile robots, the target cost function is used to prioritize all targets firstly. Furthermore, the improved A* algorithm is used to plan an optimal path passing through multiple target points. Meanwhile, the adaptive arc optimization algorithm and the weighted obstacle step adjustment algorithm are used to effectively shorten the path length by 5% and reduce the total turning angle by 26.62%. Secondly, an online path planning method combining the improved dynamic window algorithm and the global path planning information is proposed for mobile robots to avoid the local obstacles and pursue the dynamic target points in dynamic complex environments. The preview-deviation-yaw based tracking method is used to successfully capture the moving target points and improve the path planning efficiency. Finally, the simulation experiments with the proposed method are carried out, and the results show that it can achieve the path planning more effectively in complex dynamic environments.
[1] Sariff N, Buniyamin N. An overview of autonomous mobile robot path planning algorithms[C]//4th Student Conference on Research and Development. Piscataway, USA:IEEE, 2007:182-187. [2] Mac T T, Copot C, Tran D T, et al. A hierarchical global path planning approach for mobile robots based on multi-objective particle swarm optimization[J]. Applied Soft Computing, 2017, 59:68-76. [3] Song B Y, Wang Z D, Zou L. On global smooth path planning for mobile robots using a novel multimodal delayed PSO algorithm[J]. Cognitive Computation, 2017, 9(1):5-17. [4] Chen H, Fei J Y. UAV path planning based on particle swarm optimization with global best path competition[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2018, 32(6). DOI:10.1142/S0218001418590085. [5] Guo J M, Liu L, Liu Q, et al. An improvement of D* algorithm for mobile robot path planning in partial unknown environment[C]//2nd International Conference on Intelligent Computation Technology and Automation. Piscataway, USA:IEEE, 2009:394-397. [6] Nieuwenhuisen M, Behnke S. Layered mission and path planning for MAV navigation with partial environment knowledge[M]//Advances in Intelligent Systems and Computing, Vol. 302. Berlin, Germany:Springer, 2016:307-319. [7] 赵晓,王铮,黄程侃,等.基于改进A* 算法的移动机器人路径规划[J].机器人,2018,40(6):903-910. Zhao X, Wang Z, Huang C K, et al. Path planning of mobile robot based on improved A* algorithm[J]. Robot, 2018, 40(6):903-910. [8] 王殿君.基于改进A* 算法的室内移动机器人路径规划[J].清华大学学报(自然科学版),2012,52(8):1085-1089. Wang D J. Path planning of indoor mobile robot based on improved A* algorithm[J]. Journal of Tsinghua University (Science and Technology), 2012, 52(8):1085-1089. [9] Yuan Q, Han C S. Research on robot path planning based on smooth A* algorithm for different grid scale obstacle environment[J]. Journal of Computational and Theoretical Nanoscience, 2016, 13(8):5312-5321. [10] Osmankovic D, Tahirovic A, Magnani G. All terrain vehicle path planning based on D* lite and MPC based planning paradigm in discrete space[C]//IEEE International Conference on Advanced Intelligent Mechatronics. Piscataway, USA:IEEE, 2017:334-339. [11] Yu L L, Kong D C, Shao X Y, et al. A path planning and navigation control system design for driverless electric bus[J]. IEEE Access, 2018(6):53960-53975. [12] Liu J H, Yang J G, Liu H D, et al. An improved ant colony algorithm for robot path planning[J]. Soft Computing, 2017, 21(19):5829-5839. [13] 辛煜,梁华为,杜明博,等.一种可搜索无限个邻域的改进A* 算法[J].机器人,2014,36(5):627-633. Xin Y, Liang H W, Du M B, et al. An improved A* algorithm for searching infinite neighborhoods[J]. Robots, 2014, 36(5):627-633. [14] 卜新苹,苏虎,邹伟,等.基于非均匀环境建模与三阶Bezier曲线的平滑路径规划[J].自动化学报,2017, 43(5):710-724. Bu X P, Su H, Zou W, et al. Smooth path planning based on non-uniform environment modeling and third-order Bezier curve[J]. Acta Automatica Sinica, 2017, 43(5):710-724. [15] Kaplan A, Kingry N, Uhing P, et al. Time-optimal path planning with power schedules for a solar-powered ground robot[J]. IEEE Transactions on Automation Science and Engineering, 2017, 14(2):1235-1244. [16] 姚远,周兴社,张凯龙,等.基于稀疏A* 搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用,2010,27(7):953-959. Yao Y, Zhou X S, Zhang K L, et al. Dynamic trajectory planning for unmanned aerial vehicle based on sparse A* search and improved artificial potential field[J]. Control Theory and Applications, 2010, 27(7):953-959. [17] Seder M, Petrovic I. Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[C/CD]//IEEE International Conference on Robotics and Automation. Piscataway, USA:IEEE, 2007. DOI:10.1109/ROBOT. 2007.363613.