Fusion Algorithm Based on Improved A* and DWA for USV Path Planning

Abstract

The traditional A* algorithm exhibits a low efficiency in the path planning of unmanned surface vehicles (USVs). In addition, the path planned presents numerous redundant inflection waypoints, and the security is low, which is not conducive to the control of USV and also affects navigation safety. In this paper, these problems were addressed through the following improvements. First, the path search angle and security were comprehensively considered, and a security expansion strategy of nodes based on the 5×5 neighborhood was proposed. The A* algorithm search neighborhood was expanded from 3×3 to 5×5, and safe nodes were screened out for extension via the node security expansion strategy. This algorithm can also optimize path search angles while improving path security. Second, the distance from the current node to the target node was introduced into the heuristic function. The efficiency of the A* algorithm was improved, and the path was smoothed using the Floyd algorithm. For the dynamic adjustment of the weight to improve the efficiency of DWA, the distance from the USV to the target point was introduced into the evaluation function of the dynamic-window approach (DWA) algorithm. Finally, combined with the local target point selection strategy, the optimized DWA algorithm was performed for local path planning. The experimental results show the smooth and safe path planned by the fusion algorithm, which can successfully avoid dynamic obstacles and is effective and feasible in path planning for USVs.

References

[1] Alireza M, Vincent D, Tony W. Experimental study of path planning problem using EMCOA for a holonomic mobile robot. Journal of Systems Engineering and Electronics, 2021, 32(6): 1450-1462.

[2] Bai X, Li B, Xu X, Xiao Y. USV path planning algorithm based on plant growth. Ocean Engineering, 2023, 273: 113965.

[3] Chen P, Huang Y, Papadimitriou E, Mou J, Van Gelder P. Global path planning for autonomous ship: A hybrid approach of fast marching square and velocity obstacles methods. Ocean Engineering, 2020, 214: 107793.

[4] Chiang HTL, Tapia L. COLREG-RRT: An RRT-based COLREGS-compliant motion planner for surface vehicle navigation. IEEE Robotics and Automation Letters, 2018, 3(3): 2024-2031.

[5] Fox D, Burgard W, Thrun S. The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine, 1997, 4(1): 23-33.

[6] Guan W, Wang K. Autonomous collision avoidance of unmanned surface vehicles based on improved A-Star and dynamic window approach algorithms. IEEE Intelligent Transportation Systems Magazine, 2023, 15(3): 36-50.

[7] Hu S, Tian S, Zhao J, Shen R. Path planning of an unmanned surface vessel based on the improved A-Star and dynamic window method. Journal of Marine Science and Engineering, 2023, 11(5): 1060.

[8] Li W, Wang L, Fang D, Li Y, Huang J. Path planning algorithm combining A* with DWA. Syst. Eng. Electron, 2021, 43: 3694-3702

[9] Liang C, Zhang X, Watanabe Y, Deng Y. Autonomous collision avoidance of unmanned surface vehicles based on improved A Star and minimum course alteration algorithms. Applied Ocean Research, 2021, 113: 102755.

[10] Long Y, Liu S, Qiu D, Li C, Guo X, Shi B, AbouOmar MS. Local path planning with multiple constraints for USV based on improved bacterial foraging optimization algorithm. Journal of Marine Science and Engineering, 2023, 11(3): 489.

[11] Lyridis DV. An improved ant colony optimization algorithm for unmanned surface vehicle local path planning with multi-modality constraints. Ocean Engineering, 2021, 241: 109890.

[12] Ma J, Jin J, Liu D, Liu L, Wang D, Chen M. An improved adaptive dynamic window algorithm for target tracking of unmanned surface vehicles. 2021 IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC), 2021 1-5

[13] Mao S, Yang P, Gao D, Bao C, Wang Z. A motion planning method for unmanned surface vehicle based on improved RRT algorithm. Journal of Marine Science and Engineering, 2023, 11(4): 687.

[14] Niu Y, Zhang J, Wang Y, Yang H, Mu Y A review of path planning algorithms for USV, 2022 263-273

[15] Öztürk Ü, Akdaǧ M, Ayabakan T. A review of path planning algorithms in maritime autonomous surface ships: Navigation safety perspective. Ocean Engineering, 2022, 251: 111010.

[16] Qin H, Shao S, Wang T, Yu X, Jiang Y, Cao Z. Review of autonomous path planning algorithms for mobile robots. Drones, 2023, 7(3): 211.

[17] Song R, Liu Y, Bucknall R. Smoothed A* algorithm for practical unmanned surface vehicle path planning. Applied Ocean Research, 2019, 83: 9-20.

[18] Tan Z, Wei N, Liu Z. Local path planning for unmanned surface vehicle based on the improved DWA algorithm. 2022 41st Chinese Control Conference (CCC), 2022 3820-3825.

[19] Vagale A, Oucheikh R, Bye RT, Osen OL, Fossen TI. Path planning and collision avoidance for autonomous surface vehicles I: a review. Journal of Marine Science and Technology, 2021, 26(4): 1292-1306.

[20] Wang N, Xu H, Li C, Yin J. Hierarchical path planning of unmanned surface vehicles: A fuzzy artificial potential field approach. International Journal of Fuzzy Systems, 2020, 23(6): 1797-1808.

[21] Xu D, Yang J, Zhou X, Xu H. Hybrid path planning method for USV using bidirectional A* and improved DWA considering the manoeuvrability and COLREGs. Ocean Engineering, 2024, 298: 117210.

[22] Yang Z, Li N, Zhang Y, Li J. Mobile robot path planning based on improved particle swarm optimization and improved dynamic window approach. Journal of Robotics, 2023, 23: 1-16.

[23] Yin X, Cai P, Zhao K, Zhang Y, Zhou Q, Yao D. Dynamic path planning of AGV based on kinematical constraint A* algorithm and following DWA fusion algorithms. Sensors, 2023, 23(8): 4102.

[24] Zhang J, Zhao H, Wang N, Guo C. Fuzzy dual-window DWA algorithm for USV in dense obstacle conditions. Chinese Journal of Ship Research, 2021, 16(6): 10

[25] Zhong X, Tian J, Hu H, Peng X. Hybrid path planning based on safe A* algorithm and adaptive window approach for mobile robot in Large-Scale dynamic environment. Journal of Intelligent & Robotic Systems, 2020, 99(1): 65-77.

[26] Zhou C, Gu S, Wen Y, Du Z, Xiao C, Huang L, Zhu M. The review unmanned surface vehicle path planning: Based on multi-modality constraint. Ocean Engineering, 2020, 200: 107043.