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

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

系统工程与电子技术 ›› 2021, Vol. 43 ›› Issue (12): 3694-3702.doi: 10.12305/j.issn.1001-506X.2021.12.33

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

李文刚^1,², 汪流江^1,^2,*, 方德翔^1,², 李玉玮^1,², 黄郡³

1. 西安电子科技大学通信工程学院, 陕西西安 710071
2. 西安电子科技大学综合业务网理论及关键技术国家重点实验室, 陕西西安 710071
3. 国防科技大学电子对抗学院, 安徽合肥 230037

收稿日期:2020-09-01 出版日期:2021-11-24 发布日期:2021-11-30
通讯作者: 汪流江
作者简介:李文刚(1980—), 男, 副教授, 博士, 主要研究方向为宽带无线通信关键技术与卫星导航定位系统关键技术|汪流江(1997—), 男, 硕士研究生, 主要研究方向为高精度组合导航技术与传感器数据融合技术|方德翔(1995—), 男, 硕士研究生, 主要研究方向为高精度组合导航技术|李玉玮(1995—), 女, 助理工程师，硕士, 主要研究方向为智能路径规划技术|黄郡(1983—), 男, 副教授, 博士, 主要研究方向为无线网络信息安全技术
基金资助:
中国教育部联合基金(6141A02022383);中央高校基本科研业务费专项资金(20101195611);轨道交通工程信息化国家重点实验室(中铁一院)开放课题研究项目(90109210022)

Path planning algorithm combining A^* with DWA

Wengang LI^1,², Liujiang WANG^1,^2,*, Dexiang FANG^1,², Yuwei LI^1,², Jun Huang³

1. School of Communication Engineering, Xidian University, Xi'an 710071, China
2. State Key Laboratory of Integrated Services Networks, Xidian University, Xi'an 710071, China
3. College of Electronic Engineering, National University of Defense Technology, Hefei 230037, China

Received:2020-09-01 Online:2021-11-24 Published:2021-11-30
Contact: Liujiang WANG

摘要/Abstract

摘要：

由于无人艇所行驶的海洋环境比较复杂, 因此无人艇智能系统中的路径规划系统显得越来越重要。针对A^*算法与动态窗口法(dynamic window algorithm, DWA)存在的不足之处, 提出一种将二者进行结合的混合路径规划算法。通过对A^*算法得到的局部目标点进行迭代更新使水面无人艇(unmanned surface vessel, USV)利用DWA得到最佳搜索路径。仿真结果表明, 提出的算法所搜索的路径长度以及路径的拐点相对于A^*算法分别缩短了21%和减少了59%, 验证了所提算法的优越性。

关键词: 水面无人艇, 路径规划, 混合路径规划, A^*算法, 动态窗口法

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)

中图分类号:

TP242

李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.

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.

图/表 15

图1

图2

图3

图4

图5

图6

表1

图7

图8

图9

图10

图11

图12

图13

表2

参考文献 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]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[2]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[3]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[4]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[5]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[6]	王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
[7]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[8]	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42(9): 1988-1994.
[9]	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42(10): 2312-2319.
[10]	杨秀霞, 曹唯一, 张毅. 时间和角度约束下的双圆弧路径规划[J]. 系统工程与电子技术, 2019, 41(8): 1835-1843.
[11]	胡腾, 刘占军, 刘洋, 夏帅帅, 陈前斌. 多无人机3D侦察路径规划[J]. 系统工程与电子技术, 2019, 41(7): 1551-1559.
[12]	高春庆, 寇英信, 李战武, 徐安, 李游, 常一哲. 小型无人机协同覆盖侦察路径规划[J]. 系统工程与电子技术, 2019, 41(6): 1294-1299.
[13]	王瑛, 郑煜坤, 姚頔, 李正欣, 李超. 危险天气下改航路径网络规划[J]. 系统工程与电子技术, 2019, 41(6): 1309-1315.
[14]	吴云华, 牛康, 李磊, 陈志明. 基于3D-APF和约束动力学的无人机编队飞行控制[J]. 系统工程与电子技术, 2018, 40(5): 1104-1108.
[15]	刘源, 李玉玲, 郝勇, 赵琳. 基于遗传算法的多星协同攻击轨道优化方法[J]. 系统工程与电子技术, 2017, 39(8): 1815-1822.

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

Path planning algorithm combining A^* with DWA

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 21

相关文章 15

编辑推荐

Metrics

本文评价

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

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

Path planning algorithm combining A* with DWA

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 21

相关文章 15

编辑推荐

Metrics

本文评价

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

Path planning algorithm combining A^* with DWA