改进A-star算法的无人船动态路径规划

doi:10.12305/j.issn.1001-506X.2025.07.24

摘要/Abstract

摘要：

为了解决无人船动态路径规划中路径转折点多、路径安全性差以及传统A-star算法在动态环境中应用受限的问题, 提出一种改进的A-star算法。首先，通过修改open-list的存储方式和增加邻域搜索方向, 灵活调整无人船的行进方向, 提升其在动态环境中的适应能力。其次, 通过引入直线引导函数和安全距离代价公式, 有效优化路径规划过程, 避免不必要的路径绕行和碰撞风险。最后, 通过聚焦搜索方法, 减少无人船振荡反复运动。仿真结果表明, 改进的A-star算法能够成功躲避动态障碍物, 并且与其他动态路径规划算法相比, 改进A-star在路径长度方面减少了4.88%和0.09%, 平滑度方面减少了37.32%和23.17%。改进后的算法能生成更平滑、安全的路径, 适用于无人船的动态路径规划。

关键词: 路径规划, 无人船, A-star算法, 海洋巡航, 动态路径规划

Abstract:

In order to solve the problems of multiple turning points, poor path safety, and limited application of traditional A-star algorithms in dynamic environments in unmanned ship dynamic path planning, an improved A-star algorithm is proposed. Firstly, this method modifies the storage method of open-list and increases the direction of neighborhood search to flexibly adjust the direction of unmanned ships and improve their adaptability in dynamic environments. Secondly, by introducing a straight-line guidance function and a safety distance cost formula, the path planning process is effectively optimized to avoid unnecessary path detours and collision risks. Finally, by focusing on search methods, the oscillation and repeated motion of unmanned ship are reduced. The simulation results show that the improved A-star algorithm can avoid dynamic obstacles, and compared with other dynamic path planning algorithms, the improved A-star reduces path length by 4.88% and 0.09%, and smoothness by 37.32% and 23.17%. The improved algorithm can generate smoother and safer paths, suitable for dynamic path planning of unmanned ships.

Key words: path planning, unmanned ship, A-star algorithm, ocean cruise, dynamic path planning

中图分类号:

TP391

焉晓贞, 周新悦, 罗清华. 改进A-star算法的无人船动态路径规划[J]. 系统工程与电子技术, 2025, 47(7): 2314-2328.

Xiaozhen YAN, Xinyue ZHOU, Qinghua LUO. Improved A-star algorithm for dynamic path planning of unmanned ships[J]. Systems Engineering and Electronics, 2025, 47(7): 2314-2328.

图/表 33

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

表1

表2

图16

图17

图18

表3

图19

表4

表5

图20

表6

表7

图21

图22

表8

图23

图24

表9

参考文献 31

1	赵贵祥, 周健, 李云淼, 等. 改进双向快速搜索随机树的无人艇路径规划[J]. 系统工程与电子技术, 2024, 46 (4): 1364- 1371. doi: 10.12305/j.issn.1001-506X.2024.04.25
	ZHAO G X , ZHOU J , LI Y M , et al. Improved bi-directional rapidly-exploring random tree path planning for USV[J]. Systems Engineering and Electronics, 2024, 46 (4): 1364- 1371. doi: 10.12305/j.issn.1001-506X.2024.04.25
2	YUAN S Y , LI Y , BAO F W , et al. Marine environmental monitoring with unmanned vehicle platforms: present applications and future prospects[J]. Science of The Total Environment, 2023, 858, 159741- 159755.
3	MA Y , ZHU P X , ZHU G B , et al. Cooperative towing for double unmanned surface vehicles connected with a floating rope via vertical formation and adaptive moment control[J]. Ocean Engineering, 2023, 279, 114486- 114497.
4	CHO S W , PARK H J , LEE H , et al. Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations[J]. Computers & Industrial Engineering, 2021, 161, 107612- 107626.
5	GAO K Z , GAO M L , ZHOU M C , et al. Artificial intelligence algorithms in unmanned surface vessel task assignment and path planning: a survey[J]. Swarm and Evolutionary Computation, 2024, 86, 101505- 101518.
6	JIANG C J, ZHU H, XIE Y. Dynamic obstacle avoidance research for mobile robots incorporating improved A-star algorithm and DWA algorithm[C]//Proc. of the IEEE International Conference on Computer Science, Electronic Information Engineering and Intelligent Control Technology, 2023: 896-900.
7	ZHANG R , GUO H , ANDRIUKAITIS D , et al. Intelligent path planning by an improved RRT algorithm with dual grid map[J]. Alexandria Engineering Journal, 2024, 88, 91- 104.
8	ZHANG W , WANG N X , WU W H . A hybrid path planning algorithm considering AUV dynamic constraints based on improved A* algorithm and APF algorithm[J]. Ocean Engineering, 2023, 285, 115333- 115342.
9	ZENG Y X , XU K . Recognition and interfere deceptive behavior based on inverse reinforcement learning and game theory[J]. Journal of Systems Engineering and Electronics, 2023, 34 (2): 270- 288.
10	ZHAO J L , DEENG C S , YU H H , et al. Path planning of unmanned vehicles based on adaptive particle swarm optimization algorithm[J]. Computer Communications, 2024, 216, 112- 129.
11	MIYOMBO M E , LIU Y K , MULENGA C M , et al. Optimal path planning in a real-world radioactive environment: a comparative study of A-star and Dijkstra algorithms[J]. Nuclear Engineering and Design, 2024, 420, 113039- 113048.
12	SIEVER M , VALENTINO A , SURYANINGRUM K M , et al. Dijkstra's algorithm to find the nearest vaccine location[J]. Procedia Computer Science, 2023, 216, 5- 12.
13	BAO W, LI J, PAN Z H, et al. Improved A-star algorithm for mobile robot path planning based on sixteen-direction search[C]// Proc. of the IEEE China Automation Congress, 2022: 1332-1336.
14	ZHANG Y , LI L L , LIN H C , et al. Development of path planning approach using improved A-star algorithm in AGV system[J]. Journal of Internet Technology, 2019, 20 (3): 915- 924.
15	SONG R , LIU Y C , BUCKNALL R . Smoothed A* algorithm for practical unmanned surface vehicle path planning[J]. Applied Ocean Research, 2019, 83, 9- 20.
16	GUO B , KUANG Z , GUAN J H , et al. An improved a-star al gorithm for complete coverage path planning of unmanned ships[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2022, 36 (3): 2259009.
17	LIU C G , MAO Q Z , CHU X M , et al. An improved A-star algorithm considering water current, traffic separation and berthing for vessel path planning[J]. Applied Sciences, 2019, 9 (6): 1057.
18	CHANG T G , TIAN G F . Hybrid A-Star path planning method based on hierarchical clustering and trichotomy[J]. Applied Sciences, 2024, 14 (13): 5582.
19	LI Y, WANG Z X, ZHANG S Y. Path planning of robots based on an improved A-star algorithm[C]//Proc. of the IEEE Electronic and Automation Control Conference, 2022: 826-831.
20	LIU H Y , LIU J X . Research on automatic path planning method of warehouse inspection robot[J]. Applied Artificial Intelligence, 2023, 37 (1): 2306- 2321.
21	王子静, 陈熙源. 基于改进A*和DWA的无人艇路径规划算法[J]. 传感技术学报, 2021, 34 (2): 249- 254.
	WANG Z J , CHEN X Y . An unmanned boat path planning algorithm based on improved A* and DWA[J]. Journal of Sensing Technology, 2021, 34 (2): 249- 254.
22	XIE S R , WU P , LIU H L , et al. A novel method of unmanned surface vehicle autonomous cruise[J]. Industrial Robot: an International Journal, 2016, 43 (1): 121- 130.
23	李文刚, 汪流江, 方德翔, 等. 联合A与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43 (12): 3694- 3702. doi: 10.12305/j.issn.1001-506X.2021.12.33
	LI W G , WANG L J , FANG D X , et al. Path planning algorithm combining A with DWA[J]. Systems Engineering and Electronics, 2021, 43 (12): 3694- 3702. doi: 10.12305/j.issn.1001-506X.2021.12.33
24	LIU H X , ZHANG Y H . ASL-DWA: an improved A-star algorithm for indoor cleaning robots[J]. IEEE Access, 2022, 10, 99498- 99515.
25	LIU Y J , WANG C , WU H , et al. Mobile robot path planning based on kinematically constrained A-star algorithm and DWA fusion algorithm[J]. Mathematics, 2023, 11 (21): 4552- 4571.
26	LIU L S , WANG B , XU H . Research on path-planning algorithm integrating optimization A-star algorithm and artificial potential field method[J]. Electronics, 2022, 11 (22): 3660.
27	徐淑萍, 杨定哲, 闫索遥, 等. 室内环境下改进的混合路径规划算法[J]. 西安工业大学学报, 2024, 44 (2): 232- 243.
	XU S P , YANG D Z , YAN S Y , et al. An improved hybrid path planning algorithm for indoor environments[J]. Journal of Xi'an University of Technology, 2024, 44 (2): 232- 243.
28	余翔, 姜陈, 段思睿, 等. 改进A*算法和人工势场法的路径规划[J]. 系统仿真学报, 2024, 36 (3): 782- 794.
	YU X , JIANG C , DUAN S R , et al. Path planning for im provement of A* algorithm and artificial potential field method[J]. Journal of System Simulation, 2024, 36 (3): 782- 794.
29	汤玉春, 王睿忠. 基于改进A-star与DWA相融合的移动机器人动态路径规划算法[J]. 智能计算机与应用, 2024, 14 (2): 18- 27.
	TANG Y C , WANG R Z . Dynamic path planning algorithm for mobile robots based on improved A-star and DWA fusion[J]. Intelligent Computer and Applications, 2024, 14 (2): 18- 27.
30	YAN X Z , ZHOU X Y , LUO Q H . A safe heuristic path-planning method based on a search strategy[J]. Sensors, 2023, 24 (1): 101.
31	ZHANG Z M, JIA R X, CHEN X M, et al. Dynamic obstacle avoidance path planning of unmanned vehicle based on improved APF[C]//Proc. of the IEEE International Symposium on Computer Science and Intelligent Control, 2023: 135-140.

位置	地图 1	地图 2	地图 3
起点	(6, 3)	(3, 3)	(3, 3)
目标点1	(30, 36)	(16, 19)	(17, 18)
目标点2	—	(25, 35)	(25, 30)
目标点3	—	(39, 5)	(35, 20)
目标点4	—	—	(27, 8)

评价指标	IAPF	IA*-APF	DIA-star
路径长度/m	47.61	45.33	45.29
P_length/%	4.88	0.09	—
平滑度/rad	20.12	16.41	12.61
P_angle/%	37.32	23.17	—
碰撞风险度	56.26	66.19	0
P_coll/%	100	100	—

算法	评价指标	第1段	第2段	第3段	合计
IAPF	路径长度/m	22.85	20.1	35.2	78.15
	平滑度/rad	13.9	7.8	12.42	34.12
	碰撞风险度	0	0	21.99	21.99
IA*-APF	路径长度/m	22.5	21.2	35.15	78.85
	平滑度/rad	15.8	6.79	14.67	37.26
	碰撞风险度	0	0	14.99	14.99
DIA-star	路径长度/m	22.72	19.01	34.62	76.35
	平滑度/rad	9.34	2.43	11.86	23.63
	碰撞风险度	0	0	2.73	2.73

算法	P_length	P_angle	P_coll
IAPF	2.3	30.76	87.58
IA*-APF	3.17	36.57	81.79

算法	评价指标	第1段	第2段	第3段	第4段	合计
IAPF	路径长度/m	24	16.5	16.1	16	72.6
	平滑度/rad	13.15	15.61	12.21	11.3	52.27
	碰撞风险度	29.36	0	79.11	58.80	167.27
IA*-APF	路径长度/m	23.05	16.5	16.05	15.25	70.85
	平滑度/rad	10.81	9.23	13.27	13.49	46.8
	碰撞风险度	18.51	26.20	0	19.41	64.12
DIA-star	路径长度/m	22.14	16.08	15.84	14.60	68.66
	平滑度/rad	8.67	9.17	10.6	4.78	33.22
	碰撞风险度	0	0	0	0	0