联合A*与动态窗口法的路径规划算法

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

Abstract

Abstract:

As the marine environment in which the unmanned boat travels is more complicated, the path planning system in the intelligent system of the unmanned boat becomes more and more important. Aiming at the shortcomings of the A^* algorithm and the dynamic window algorithm (DWA), a hybrid path planning algorithm that combines the two is proposed. By iteratively updating the local target points obtained by the A^* algorithm, the unmanned surface vessel (USV) uses DWA to obtain the best search path. The simulation results show that the path length and path turning points searched by the algorithm proposed are reduced by 21% and 59% respectively compared with the A^* algorithm, which verifies the superiority of the proposed algorithm.

Key words: unmanned surface vessel (USV), path planning, hybrid path planning, A^* algorithm, dynamic window algorithm (DWA)

CLC Number:

TP242

Wengang LI, Liujiang WANG, Dexiang FANG, Yuwei LI, Jun Huang. Path planning algorithm combining A^* with DWA[J]. Systems Engineering and Electronics, 2021, 43(12): 3694-3702.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 1

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Table 2

References 21

1	张伟, 廖煜雷, 姜峰, 等. 无人水面艇技术发展回顾与趋势分析[J]. 无人系统技术, 2019, 2 (6): 1- 9.
	ZHANG W , LIAO Y L , JIANG F , et al. Technology development review and trend analysis of unmanned surface craft[J]. Unmanned System Technology, 2019, 2 (6): 1- 9.
2	LIU Z X , ZHANG Y M , YU X , et al. Unmanned surface vehicles: an overview of developments and challenges[J]. Annual Review in Control, 2016, 41, 71- 93. doi: 10.1016/j.arcontrol.2016.04.018
3	刘钰. 基于导航误差约束的水面无人艇路径规划方法研究[D]. 南京: 东南大学, 2017.
	LIU Y. Research on the path planning method of surface unmanned craft based on navigation error constraints[D]. Nanjing: Southeast University, 2017.
4	WANG Y L, LIANG X, LI B A, et al. Research and implementation of global path planning for unmanned surface vehicle based on electronic chart[C]//Proc. of the International Conference on Mechatronics and Intelligent Robotics, 2018.
5	巩敦卫, 耿娜, 张勇. 多地貌环境下的移动机器人路径规划研究[J]. 控制与决策, 2012, 27 (5): 708- 712.
	GONG D W , GENG N , ZHANG Y . Robot path planning in environment of many terrains[J]. Control and Decision, 2012, 27 (5): 708- 712.
6	KOZYNCHENKO A I , KOZYNCHENKO S A . Applying the dynamic predictive guidance to ship collision avoidance: crossing case study simulation[J]. Ocean Engineering, 2018, 164 (7): 640- 649.
7	巩敦卫, 耿娜, 张勇. 密集障碍物环境下基于凸包和微粒群优化的机器人路径规划[J]. 控制理论与应用, 2012, 29 (5): 609- 616.
	GONG D W , GENG N , ZHANG Y . Robot path planning in environment with dense obstacle based on convex hull and particle swarm optimization[J]. Control Theory and Application, 2012, 29 (5): 609- 616.
8	ZHANG Y , GONG D W , ZHANG J H . Robot path planning in uncertain environment using multi-objective particle swarm optimization[J]. Neurocomputing, 2013, 103 (9): 172- 185.
9	YU J B , DENG W , ZHAO Z Y , et al. A hybrid path planning method for an unmanned cruise ship in water quality sampling[J]. IEEE Access, 2019, 7, 87127- 87140. doi: 10.1109/ACCESS.2019.2925894
10	GENG N , MENG Q G , GONG D W , at el . How good are distributed allocation algorithms for solving urban search and rescue problems? a comparative study with centralized algorithms[J]. IEEE Trans.on Automation Science and Engineering, 2019, 16 (1): 478- 485. doi: 10.1109/TASE.2018.2866395
11	WANG N , JIN X Z , JOOER M , at el . A multilayer path planner for a USV under complex marine environments[J]. Ocean Engineering, 2019, 184 (5): 1- 10.
12	NAIR R S, SUPRIYA P. Robotic path planning using recurrent neural networks[C]//Proc. of the 11th International Conference on Computing, Communication and Networking Technologies, 2020.
13	RAMEZANLOU M T, AZIMIRAD V, ZAKERI M. Hybrid path planning of robots through optimal control and PSO algorithm[C]//Proc. of the 7th International Conference on Robotics and Mechatronics, 2019.
14	NOGUCHI Y, MAKI T. Path planning method based on artificial potential field and reinforcement learning for intervention AUVs[C]//Proc. of the IEEE Underwater Technology, 2019.
15	PANDA R K, CHOUDHURY B B. An effective path planning of mobile robot using genetic algorithm[C]//Proc. of the IEEE International Conference on Computational Intelligence & Communication Technology, 2015.
16	GOYAL J K, NAGLA K S. A new approach of path planning for mobile robots[C]//Proc. of the International Conference on Advances in Computing, Communications and Informatics, 2014.
17	贾茂良. 基于电子海图的无人艇路径规划[D]. 天津: 天津理工大学, 2019.
	JIA M L. Unmanned boat path planning based on electronic chart[D]. Tianjin: Tianjin University of Technology, 2019.
18	SHI B H , SU Y X , ZHANG H J . Obstacles modeling method in cluttered environments using satellite images and its application to path planning for USV[J]. International Journal of Naval Architecture and Ocean Engineering, 2019, 11 (1): 202- 210. doi: 10.1016/j.ijnaoe.2018.04.001
19	冯凯, 吉星, 杨昕. A^*算法在自动驾驶车辆路径规划中的应用[J]. 汽车实用技术, 2020, 45 (22): 25- 28.
	FENG K , JI X , YANG X . Application of A^* algorithm in path planning of autonomous vehicles[J]. Automobile Applied Technology, 2020, 45 (22): 25- 28.
20	EIFFERT S, KONG H, PIRMARZDASHTI N. Path planning in dynamic environments using generative RNNs and Monte Carlo tree search[C]//Proc. of the IEEE International Confe-rence on Robotics and Automation, 2020.
21	梁波, 杨新民. 一种基于改进型Dijkstra算法的路线规划方法研究[J]. 信息化研究, 2020, 46 (2): 13- 16.
	LIANG B , YANG X M . Study on a path planning method based on the improved Dijkstra algorithm[J]. Informatization Research, 2020, 46 (2): 13- 16.

路径	算法	路径长度	运行时间/s	OPEN表搜索节点数	CLOSE表搜索节点数
1	A^*	134.04	10.95	132	1 404
1	双向A^*	134.20	6.91	70	1 143
2	A^*	55.25	4.91	124	550
2	双向A^*	56.08	2.12	84	317
3	A^*	150.34	14.25	160	2 040
3	双向A^*	151.02	10.30	112	1 623

[1]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[2]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[3]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[4]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.
[5]	Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method [J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.
[6]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[7]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[8]	Zhiqiang JIAO, Jieyong ZHANG, Peiyang YAO, Xun WANG, Yichao HE. Distributed evolution method of C4ISR service deployment based on hierarchical structure [J]. Systems Engineering and Electronics, 2021, 43(6): 1572-1585.
[9]	Wenming WANG, Jialu DU. Agent path planning based on regular hexagon grid JPS algorithm [J]. Systems Engineering and Electronics, 2021, 43(12): 3635-3642.
[10]	Yanan LI, Haibin HUANG, Liangming CHEN, Yufei ZHUANG, Xiaoli WANG. Energy-optimal three-dimensional path planning for AUV under changing ocean current environment [J]. Systems Engineering and Electronics, 2021, 43(12): 3667-3674.
[11]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[12]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[13]	Quanxian ZHANG, Bin ZENG, Houpu LI. Underway replenishment path planning method for distributed naval warfare under the influence of sea conditions [J]. Systems Engineering and Electronics, 2020, 42(10): 2312-2319.
[14]	Sheng GAO, Jianliang AI, Zhihao WANG. Mixed population RRT algorithm for UAV path planning [J]. Systems Engineering and Electronics, 2020, 42(1): 101-107.
[15]	LIAN Qingpo, WANG Hongjian, YUAN Jianya, GAO Na, HU Wenyue. USV cluster collision avoidance based on particle swarm optimization algorithm [J]. Systems Engineering and Electronics, 2019, 41(9): 2034-2040.

Path planning algorithm combining A^* with DWA

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 21

Related Articles 15

Recommended Articles

Metrics

Comments

路径	算法	路径长度	路径拐点
1	改进A^*算法	50	10
1	混合路径规划算法	39	4
2	改进A^*算法	25	8
2	混合路径规划算法	17	3

Path planning algorithm combining A* with DWA

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 21

Related Articles 15

Recommended Articles

Metrics

Comments

Path planning algorithm combining A^* with DWA