|Table of Contents|

Citation:
　Changyi Li,Lei Yao,Chao Mi.Fusion Algorithm Based on Improved A* and DWA for USV Path Planning[J].Journal of Marine Science and Application,2025,(1):224-237.[doi:10.1007/s11804-024-00434-1]
Click and Copy

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

Info

Title:
Fusion Algorithm Based on Improved A* and DWA for USV Path Planning
Author(s):
Changyi Li1;  Lei Yao2;  Chao Mi1; 2
Affilations:
Author(s):
Changyi Li1;  Lei Yao2;  Chao Mi1; 2
1. Container Supply Chain Technology Engineering Research Center, Ministry of Education, Shanghai Maritime University, Shanghai 201306, China;
2. Shanghai SMUVision Smart Technology Ltd, Shanghai 201306, China
Keywords:
Improved A* algorithm; Optimized DWA algorithm; Unmanned surface vehicles; Path planning; Fusion algorithm
分类号:
-
DOI:
10.1007/s11804-024-00434-1
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:

Alireza M, Vincent D, Tony W (2021) Experimental study of path planning problem using EMCOA for a holonomic mobile robot. Journal of Systems Engineering and Electronics 32(6): 1450-1462. https://doi.org/10.23919/jsee.2021.000123
Bai X, Li B, Xu X, Xiao Y (2023) USV path planning algorithm based on plant growth. Ocean Engineering 273: 113965. https://doi.org/10.1016/j.oceaneng.2023.113965
Chen P, Huang Y, Papadimitriou E, Mou J, Van Gelder P (2020) Global path planning for autonomous ship: A hybrid approach of fast marching square and velocity obstacles methods. Ocean Engineering 214: 107793. https://doi.org/10.1016/j.oceaneng.2020.107793
Chiang HTL, Tapia L (2018) COLREG-RRT: An RRT-based COLREGS-compliant motion planner for surface vehicle navigation. IEEE Robotics and Automation Letters 3(3): 2024-2031. https://doi.org/10.1109/lra.2018.2801881
Fox D, Burgard W, Thrun S (1997) The dynamic window approach to collision avoidance. IEEE Robotics & Automation Magazine 4(1): 23-33. https://doi.org/10.1109/100.580977
Guan W, Wang K (2023) Autonomous collision avoidance of unmanned surface vehicles based on improved A-Star and dynamic window approach algorithms. IEEE Intelligent Transportation Systems Magazine 15(3): 36-50. https://doi.org/10.1109/mits.2022.3229109
Hu S, Tian S, Zhao J, Shen R (2023) Path planning of an unmanned surface vessel based on the improved A-Star and dynamic window method. Journal of Marine Science and Engineering 11(5): 1060. https://doi.org/10.3390/jmse11051060
Li W, Wang L, Fang D, Li Y, Huang J (2021) Path planning algorithm combining A* with DWA. Syst. Eng. Electron 43: 3694-3702. DOI: 10.12305/j.issn.1001-506X.2021.12.33
Liang C, Zhang X, Watanabe Y, Deng Y (2021) Autonomous collision avoidance of unmanned surface vehicles based on improved A Star and minimum course alteration algorithms. Applied Ocean Research 113: 102755. https://doi.org/10.1016/j.apor.2021.102755
Long Y, Liu S, Qiu D, Li C, Guo X, Shi B, AbouOmar MS (2023) Local path planning with multiple constraints for USV based on improved bacterial foraging optimization algorithm. Journal of Marine Science and Engineering 11(3): 489. https://doi.org/10.3390/jmse11030489
Lyridis DV (2021) An improved ant colony optimization algorithm for unmanned surface vehicle local path planning with multi-modality constraints. Ocean Engineering 241: 109890. https://doi.org/10.1016/j.oceaneng.2021.109890
Ma J, Jin J, Liu D, Liu L, Wang D, Chen M (2021) An improved adaptive dynamic window algorithm for target tracking of unmanned surface vehicles. 2021 IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC), 1-5. https://doi.org/10.1109/icspcc52875.2021.9564615
Mao S, Yang P, Gao D, Bao C, Wang Z (2023) A motion planning method for unmanned surface vehicle based on improved RRT algorithm. Journal of Marine Science and Engineering 11(4): 687. https://doi.org/10.3390/jmse11040687
Niu Y, Zhang J, Wang Y, Yang H, Mu Y (2022) A review of path planning algorithms for USV. Lecture Notes in Electrical Engineering, 263-273. https://doi.org/10.1007/978-981-16-9492-9_27
?ztürk ü, Akda? M, Ayabakan T (2022) A review of path planning algorithms in maritime autonomous surface ships: Navigation safety perspective. Ocean Engineering 251: 111010. https://doi.org/10.1016/j.oceaneng.2022.111010
Qin H, Shao S, Wang T, Yu X, Jiang Y, Cao Z (2023) Review of autonomous path planning algorithms for mobile robots. Drones 7(3): 211. https://doi.org/10.3390/drones7030211
Song R, Liu Y, Bucknall R (2019) Smoothed A* algorithm for practical unmanned surface vehicle path planning. Applied Ocean Research 83: 9-20. https://doi.org/10.1016/j.apor.2018.12.001
Tan Z, Wei N, Liu Z (2022) Local path planning for unmanned surface vehicle based on the improved DWA algorithm. 2022 41st Chinese Control Conference (CCC), 3820-3825. https://doi.org/10.23919/ccc55666.2022.9901807
Vagale A, Oucheikh R, Bye RT, Osen OL, Fossen TI (2021) Path planning and collision avoidance for autonomous surface vehicles I: a review. Journal of Marine Science and Technology 26(4): 1292-1306. https://doi.org/10.1007/s00773-020-00787-6
Wang N, Xu H, Li C, Yin J (2020) Hierarchical path planning of unmanned surface vehicles: A fuzzy artificial potential field approach. International Journal of Fuzzy Systems 23(6): 1797-1808. https://doi.org/10.1007/s40815-020-00912-y
Xu D, Yang J, Zhou X, Xu H (2024) Hybrid path planning method for USV using bidirectional A* and improved DWA considering the manoeuvrability and COLREGs. Ocean Engineering 298: 117210. https://doi.org/10.1016/j.oceaneng.2024.117210
Yang Z, Li N, Zhang Y, Li J (2023) Mobile robot path planning based on improved particle swarm optimization and improved dynamic window approach. Journal of Robotics 23: 1-16. https://doi.org/10.1155/2023/6619841
Yin X, Cai P, Zhao K, Zhang Y, Zhou Q, Yao D (2023) Dynamic path planning of AGV based on kinematical constraint A* algorithm and following DWA fusion algorithms. Sensors 23(8): 4102. https://doi.org/10.3390/s23084102
Zhang J, Zhao H, Wang N, Guo C (2021) Fuzzy dual-window DWA algorithm for USV in dense obstacle conditions. Chinese Journal of Ship Research 16(6): 10. DOI: 10.19693/j.issn.1673-3185.02095
Zhong X, Tian J, Hu H, Peng X (2020) 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 99(1): 65-77. https://doi.org/10.1007/s10846-019-01112-z
Zhou C, Gu S, Wen Y, Du Z, Xiao C, Huang L, Zhu M (2020) The review unmanned surface vehicle path planning: Based on multi-modality constraint. Ocean Engineering 200: 107043. https://doi.org/10.1016/j.oceaneng.2020.107043

Memo

Memo:
Received date:2023-1-1;Accepted date:2023-11-25。
Foundation item:Supported by the EDD of China (No. 80912020104) and the Science and Technology Commission of Shanghai Municipality (No. 22ZR1427700 and No. 23692106900).
Corresponding author:Chao Mi,E-mail:chaomi@shmtu.edu.cn
Last Update: 2025-02-26