Hybrid path planning for USVs using improved A* and DWA

doi:10.23919/JSEE.2026.000025

Journal of Systems Engineering and Electronics ›› 2026, Vol. 37 ›› Issue (1): 45-63.doi: 10.23919/JSEE.2026.000025

收稿日期:2025-12-12 出版日期:2026-02-18 发布日期:2026-03-09

Hybrid path planning for USVs using improved A* and DWA

Guangwei WANG¹^,²^,³(), Le YANG⁴(), Zhikun TAN¹^,²(), Yichen LI¹^,²(), Wenbin YU¹^,²^,*()

¹School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China
²Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai 200240, China
³Tianjin Navigation Instruments Research Institute, Tianjin 300074, China
⁴Hangzhou Changwangzhichuang Co., Ltd, Hangzhou 310013, China

Received:2025-12-12 Online:2026-02-18 Published:2026-03-09
Contact: Wenbin YU E-mail:ray7772008@163.com;anti_i@163.com;zhikuntan@sjtu.edu.cn;liyichensjtu@sjtu.edu.cn;yuwenbin@sjtu.edu.cn
About author:
WANG Guangwei was born in 1983. He received his B.E. degree in electrical engineering and automation from Northwestern Polytechnical University, Xi’an, China, in 2007, and M.E. degree in motors and electrical appliances from Northwestern Polytechnical University, Xi’an, China, in 2010. He is currently pursuing his Ph.D. degree in electronic information at Shanghai Jiao Tong University, Shanghai, China. His main research interests include underwater navigation and data analysis technologies. E-mail: ray7772008@163.com

YANG Le was born in 1992. He received his B.S. degree in geographic information system from Anhui Normal University, Wuhu, China, in 2015, and M.A. degree in agricultural informatization from Nanjing Agricultural University, Nanjing, China, in 2018. He is currently serving as deputy director of the Large Model Center at Hangzhou Changwang Zhichuang Technology Co., Ltd., Hangzhou, China. His main research interests include algorithm research in individual and swarm intelligence for unmanned equipment, covering target detection, tracking, re-identification, path planning, swarm collaboration, multimodal large models and intelligent agent development in the field of computer vision. E-mail: anti_i@163.com

TAN Zhikun was born in 1999. He received his B.E. degree in marine engineering from Huazhong University of Science and Technology, Wuhan, China, in 2020, and M.E. degree in fluid mechanics from China Ship Science Research Center, Wuxi, China, in 2020. He is currently pursuing his Ph.D. degree in control science and engineering at Shanghai Jiao Tong University, Shanghai, China. His main research interests include cross-domain formation control and target tracking. E-mail: zhikuntan@sjtu.edu.cn

LI Yichen was born in 1993. He received his B.S. degree in detection, guidance and control technology from Northwestern Polytechnical University, Xi’an, China, in 2016, and Ph.D. degree in control science and engineering from Shanghai Jiao Tong University, Shanghai, China, in 2022. He is now a postdoc in control science and engineering with Shanghai Jiao Tong University, Shanghai, China. His main research interests include underwater multi-robot localization and trajectory planning, wireless networks, and information fusion. E-mail: liyichensjtu@sjtu.edu.cn

YU Wenbin was born in 1983. He received his Ph.D. degree in control science and engineering from Shanghai Jiao Tong University, Shanghai, China, in 2016. He is currently an associate professor with the Department of Automation, Shanghai Jiao Tong University. His main research interests include data fusion and control strategy for autonomous underwater vehicle system. E-mail: yuwenbin@sjtu.edu.cn
Supported by:
This work was supported by the National Nature Science Foundation of China (62203299;62373246;62388101), the Research Fund of State Key Laboratory of Deep-Sea Manned Vehicles (2024SKLDMV04), the Oceanic Interdisciplinary Program of Shanghai Jiao Tong University (SL2023MS007), and the Startup Fund for Young Faculty at SJTU (24X010502929).

摘要/Abstract

Abstract:

A safe and reliable path planning algorithm is fundamental for unmanned surface vehicles (USVs) to perform autonomous navigation tasks. However, a single global or local planning strategy cannot fully meet the requirements of complex maritime environments. Global planning alone cannot effectively handle dynamic obstacles, while local planning alone may fall into local optima. To address these issues, this paper proposes a multi-dynamic-obstacle avoidance path planning method that integrates an improved A* algorithm with the dynamic window approach (DWA). The traditional A* algorithm often generates paths that are too close to obstacle boundaries and contain excessive turning points, whereas the traditional DWA tends to skirt densely clustered obstacles, resulting in longer routes and insufficient dynamic obstacle avoidance. To overcome these limitations, improved versions of both algorithms are developed. Key points extracted from the optimized A* path are used as intermediate start-destination pairs for the improved DWA, and the weights of the DWA evaluation function are adjusted to achieve effective fusion. Furthermore, a multi-dynamic-obstacle avoidance strategy is designed for complex navigation scenarios. Simulation results demonstrate that the USV can adaptively switch between dynamic obstacle avoidance and path tracking based on obstacle distribution, validating the effectiveness of the proposed method.

Key words: multiple dynamic obstacles, A* algorithm, dynamic window approach (DWA), unmanned surface vehicle (USV), path planning, collision avoidance

. [J]. Journal of Systems Engineering and Electronics, 2026, 37(1): 45-63.

Guangwei WANG, Le YANG, Zhikun TAN, Yichen LI, Wenbin YU. Hybrid path planning for USVs using improved A* and DWA[J]. Journal of Systems Engineering and Electronics, 2026, 37(1): 45-63.

图/表 34

参考文献 40

1	JIANG X L, XIA G H Dissipative leaderless formation via nonfragile memory sampled-data control for unmanned surface vehicles with switching topologies. IEEE/ASME Trans. on Mechatronics, 2024, 30 (1): 203- 214. doi: 10.1109/tmech.2024.3391748
2	SHI J, YE M J Distributed optimal formation control for unmanned surface vessels by a regularized game-based approach. IEEE/CAA Journal of Automatica Sinica, 2024, 11 (1): 276- 278. doi: 10.1109/JAS.2023.123930
3	XIA J W, ZHU X F, ZHONG L, et al LSTM-DPPO based deep reinforcement learning controller for path following optimization of unmanned surface vehicle. Journal of Systems Engineering and Electronics, 2023, 34 (5): 1343- 1358. doi: 10.23919/JSEE.2023.000113
4	LIU Z X, ZHANG Y M, YU X, et al Unmanned surface vehicles: an overview of developments and challenges. Annual Reviews in Control, 2016, 41, 71- 93. doi: 10.1016/j.arcontrol.2016.04.018
5	LOU M M, YANG X F, HU J B, et al Design and field test of collision avoidance method with prediction for USVs: a deep deterministic policy gradient approach. IEEE Internet of Things Journal, 2024, 12 (3): 3363- 3372. doi: 10.1109/jiot.2024.3479322
6	PATIL G, KASHID S, RANE A, et al. Analyzing and implementing pathfinding algorithms for flight route planning in Java. Proc. of the IEEE International Conference on Inventive Computation Technologies, 2025: 28−33.
7	BABU T, NAYAK D, MISHRA S. Enhancing greedy best-first search with dynamic heuristic for puzzle solving. Proc. of the IEEE International Conference on Emerging Technologies in Computing and Communication, 2025. DOI: 10.1109/ETCC65847.2025.11108541.
8	LIN Z, WU K, SHEN R L, et al An efficient and accurate A-star algorithm for autonomous vehicle path planning. IEEE Trans. on Vehicular Technology, 2023, 73 (6): 9003- 9008. doi: 10.1109/tvt.2023.3348140
9	ZHENG D L, RIDDERHOF J, ZHANG Z Y, et al CS-BRM: a probabilistic roadmap for consistent belief space planning with reachability guarantees. IEEE Trans. on Robotics, 2024, 40, 1630- 1649. doi: 10.1109/TRO.2024.3355375
10	KHUAT T H, BUI D N, NGUYEN H T, et al Multi-goal rapidly exploring random tree with safety and dynamic constraints for UAV cooperative path planning. IEEE Trans. on Vehicular Technology, 2025, 74 (9): 13446- 13457. doi: 10.1109/TVT.2025.3560658
11	HOU Y, QIN X M, HAN H G, et al Multiobjective ant colony optimization algorithm based on dynamic constraint evaluation strategy for highly constrained optimization. IEEE Trans. on Cybernetics, 2025, 55 (10): 4570- 4582. doi: 10.1109/TCYB.2025.3591275
12	FENG T P, LI J M, JIANG H, et al The optimal global path planning of mobile robot based on improved hybrid adaptive genetic algorithm in different tasks and complex road environments. IEEE Access, 2024, 12, 18400- 18415. doi: 10.1109/ACCESS.2024.3357990
13	GAN X L, HUO Z H, LI W DP-A*: for path planning of UGV and contactless delivery. IEEE Trans. on Intelligent Transportation Systems, 2023, 25 (1): 907- 919. doi: 10.1109/tits.2023.3258186
14	JONNALAGADDA A, SAI Y, BHARAT M V, et al Efficient path planning in multi-agent environment of AAVS with payloads. IEEE Access, 2025, 13, 57932- 57942. doi: 10.1109/ACCESS.2025.3554546
15	DANIEL K, NASH A, KOENIG S, et al Theta*: any-angle path planning on grids. Journal of Artificial Intelligence Research, 2010, 39, 533- 579. doi: 10.1613/jair.2994
16	MANYAM S G, CASBEER D W, TAYLOR C Hybrid Theta*: motion planning for dubins vehicles with integral constraints. IEEE Robotics and Automation Letters, 2024, 10 (2): 1497- 1504. doi: 10.1109/lra.2024.3522786
17	LIU H X, ZHANG Y H ASL-DWA: an improved A-star algorithm for indoor cleaning robots. IEEE Access, 2022, 10, 99498- 99515. doi: 10.1109/ACCESS.2022.3206356
18	WANG M H, XU J, ZHANG J, et al An autonomous navigation method for orchard rows based on a combination of an improved A-star algorithm and SVR. Precision Agriculture, 2024, 25 (3): 1429- 1453. doi: 10.1007/s11119-024-10118-z
19	SANG H Q, YOU Y S, SUN X J, et al The hybrid path planning algorithm based on improved A* and artificial potential field for unmanned surface vehicle formations. Ocean Engineering, 2021, 223, 108709. doi: 10.1016/j.oceaneng.2021.108709
20	ZHANG H X, TAO Y D, ZHU W L Global path planning of unmanned surface vehicle based on improved A-star algorithm. Sensors, 2023, 23 (14): 6647. doi: 10.3390/s23146647
21	WANG Y L, YU X M, LIANG X, et al A COLREGs-based obstacle avoidance approach for unmanned surface vehicles. Ocean Engineering, 2018, 169 (1): 110- 124. doi: 10.1016/j.oceaneng.2018.09.012
22	GIBSON J, SCHULER T, MCGUIRE L, et al Swarm and multi-agent time-based A* path planning for lighter-than-air systems. Unmanned Systems, 2020, 8 (3): 253- 260. doi: 10.1142/S2301385020500181
23	HE Z B, LIU C G, CHU X M, et al Dynamic anti-collision A-star algorithm for multi-ship encounter situations. Applied Ocean Research, 2022, 118, 102995. doi: 10.1016/j.apor.2021.102995
24	SHAN S F, SHAO J J, ZHANG H J, et al Research and validation of self-driving path planning algorithm based on optimized A*-artificial potential field method. IEEE Sensors Journal, 2024, 24 (15): 24708- 24722. doi: 10.1109/JSEN.2024.3410271
25	SONG Y C, WANG R H, BI Q C, et al STVO: spatial-temporal constrained velocity obstacle for safe navigation among pedestrians. IEEE Trans. on Vehicular Technology, 2025, 74 (9): 13580- 13591. doi: 10.1109/TVT.2025.3565734
26	CHEN Z, ZHANG Y M, ZHANG Y G, et al A hybrid path planning algorithm for unmanned surface vehicles in complex environment with dynamic obstacles. IEEE Access, 2019, 7, 126439- 126449. doi: 10.1109/ACCESS.2019.2936689
27	ZHANG J, CUI Y N, LI G F, et al Dynamic path planning algorithm for unmanned surface vehicle under island-reef environment. IEEE Trans. on Aerospace and Electronic Systems, 2023, 59 (5): 7252- 7268. doi: 10.1109/taes.2023.3286823
28	CHEN H, LIN Z L, CHEN Z M, et al Adaptive DWA algorithm with decision tree classifier for dynamic planning in USV navigation. Ocean Engineering, 2025, 321, 120328. doi: 10.1016/j.oceaneng.2025.120328
29	ZHU W L, CHEN Z F Research on path planning for mobile charging robots based on improved A* and DWA algorithms. Electronics, 2025, 14 (12): 2318. doi: 10.3390/electronics14122318
30	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. doi: 10.1109/MITS.2022.3229109
31	SONG R, LIU Y C, BUCKNALL R Smoothed A* algorithm for practical unmanned surface vehicle path planning. Applied Ocean Research, 2019, 83, 9- 20. doi: 10.1016/j.apor.2018.12.001
32	DU Z, WEN Y Q, XIAO C S, et al Trajectory-cell based method for the unmanned surface vehicle motion planning. Applied Ocean Research, 2019, 86, 207- 221. doi: 10.1016/j.apor.2019.02.005
33	BITAR G, MARTINSEN A B, LEKKAS A M, et al Two-stage optimized trajectory planning for ASVs under polygonal obstacle constraints: theory and experiments. IEEE Access, 2020, 8, 199953- 199969. doi: 10.1109/ACCESS.2020.3035256
34	WANG Y L, YU X M, LIANG X Design and implementation of global path planning system for unmanned surface vehicle among multiple task points. International Journal of Vehicle Autonomous Systems, 2018, 14 (1): 82- 105. doi: 10.1504/ijvas.2018.10014293
35	SU Y X, XIN J Y, SUN C Y Dynamic path planning for mobile robots based on improved RRT* and DWA algorithms. IEEE Trans. on Industrial Electronics, 2025, 72 (10): 10595- 10604. doi: 10.1109/TIE.2025.3546349
36	JIAN Z Q, ZHANG S Y, SUN L F, et al Long-term dynamic window approach for kinodynamic local planning in static and crowd environments. IEEE Robotics and Automation Letters, 2023, 8 (6): 3294- 3301. doi: 10.1109/LRA.2023.3266664
37	YASUDA S, KUMAGAI T, YOSHIDA H Safe and efficient dynamic window approach for differential mobile robots with stochastic dynamics using deterministic sampling. IEEE Robotics and Automation Letters, 2023, 8 (5): 2614- 2621. doi: 10.1109/LRA.2023.3257681
38	HU Y W, CHEN X F, TANG P P, et al A path planning framework for robots based on improved parallel sampling RRT and offset guidance DWA. IEEE Sensors Journal, 2025, 25 (18): 35597- 35608. doi: 10.1109/JSEN.2025.3596346
39	HUANG J H, ZENG J, CHI X M, et al Dynamic collision avoidance using velocity obstacle-based control barrier functions. IEEE Trans. on Control Systems Technology, 2025, 33 (5): 1601- 1615. doi: 10.1109/TCST.2025.3546076
40	DE BOOIJ A, THEUNISSEN E. Analyzing the impact of sensor noise in the TCPA-DCPA domain. Proc. of the AIAA DATC/IEEE 43rd Digital Avionics Systems Conference, 2024. DOI: 10.1109/DASC62030.2024.10749449.

Parameter	Traditional A*	A* considering obstacles	Optimization algorithm
Number of inflection nodes	15	10	5
Turning angle/(°)	675.00	450.00	164.06
Path length/m	63.91	63.91	61.94

Parameter	Value
$ {v}_{\max}/\text{(m/s)} $	$ 1.0 $
$ {w}_{\max}/({\mathrm{rad/s}}) $	$ 0.523\;6 $
$ \dot{{v}_{a}} $/($ {\mathrm{m/{s}}}^{2} $)	$ 0.2 $
$ \dot{{w}_{a}}/({\mathrm{rad/{s}}}^{2}) $	$ 0.872\;7 $
$ \alpha $	$ 0.05 $
$ \gamma $	$ 0.1 $
$ \varphi $	$ \text{π} /3 $
$ r/\mathrm{m} $	0.2/0.5/0.7
$ {v}_{\min}/\text{(m/s)} $	$ -1.0 $
$ {w}_{\min}/({\mathrm{rad/s}}) $	$ -0.523\;6 $
$ \dot{{v}_{b}}/({\mathrm{m/{s}}}^{2}) $	$ -0.2 $
$ \dot{{w}_{b}}/({\mathrm{rad/{s}}}^{2}) $	$ -0.872\;7 $
$ \beta $	$ 0.2 $
$ {t}_\text{sim}/{\mathrm{s}} $	$ 3.0 $
$ \mu $	$ 0.05/0.1/0.3 $

Radius of obstacle expansion circle/m	Time of navigation/s			Path length/m			Average velocity/(m/s)
Radius of obstacle expansion circle/m	Traditional algorithm	Improved algorithm	Time reduction rate/%	Traditional algorithm	Improved algorithm	Time reduction rate/%	Traditional algorithm	Improved algorithm	Time reduction rate/%
0.2	48.72	22.83	53.14	14.91	14.27	4.29	0.31	0.63	103.22
0.5	83.85	33.27	60.32	20.32	14.71	27.61	0.24	0.44	83.33
0.7	33.36	19.78	40.70	19.94	17.76	10.93	0.60	0.90	50.00

$ \mu $	Time of navigation/s	Path length/m	Average velocity/(m/s)
0	72.40	14.63	0.20
0.05	57.34	14.32	0.25
0.1	56.91	14.95	0.26
0.3	54.88	15.80	0.29

Hybrid path planning for USVs using improved A* and DWA

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 34

参考文献 40

相关文章 0

编辑推荐

Metrics

本文评价