Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2024, Vol. 58 Issue (2): 360-369    DOI: 10.3785/j.issn.1008-973X.2024.02.014
机械工程     
改进A*与ROA-DWA融合的机器人路径规划
刘宇庭1(),郭世杰1,*(),唐术锋1(),张学炜1,2,李田田1
1. 内蒙古工业大学 机械工程学院，内蒙古 呼和浩特 010051
2. 浙江大学 机械工程学院，浙江 杭州 310058
Path planning based on fusion of improved A* and ROA-DWA for robot
Yuting LIU1(),Shijie GUO1,*(),Shufeng TANG1(),Xuewei ZHANG1,2,Tiantian LI1
1. School of Mechanical Engineering, Inner Mongolia University of Technology, Hohhot 010051, China
2. School of Mechanical Engineering, Zhejiang University, Hangzhou 310058, China
 全文: PDF(2840 KB)   HTML
摘要：

为了解决机器人路径规划中传统A*算法和动态窗口法(DWA)存在的遍历节点较多、冗余点较多以及路径不平滑, 缺乏全局引导, 易陷入局部最优以及安全性低等问题, 提出融合改进A*算法和随机避障动态窗口法(ROA-DWA)的路径规划算法. 该算法通过启发式函数的权重调整、Floyd算法、冗余点删除策略、静态和动态障碍物分类处理和速度自适应因子等方式来提高搜索效率, 减少路径长度和拐点数量, 将已知障碍物对路径的影响最小化,大幅提高动态避障效率，使得机器人在平稳到达目标点的同时还提升了机器人的安全性, 更好地适应复杂的动态和静态环境. 实验结果表明, 该算法具有较好的全局最优性和局部避障能力, 在大型地图中展现出更好的优势.
关键词： 机器人路径规划;  动态避障;  改进A*算法;  随机避障动态窗口法（ROA-DWA）;  融合算法    
Abstract:

A path planning algorithm based on the fusion of the improved A* algorithm and the random obstacle avoidance dynamic window method (ROA-DWA) was proposed in order to address the issues of excessive traversal nodes, redundant points, non-smooth paths, lack of global guidance, susceptibility to local optima, and low safety in traditional A* algorithm and dynamic window approach (DWA) for robot path planning. The search efficiency was improved by adjusting the weights of heuristic functions, Floyd’s algorithm, redundant point deletion strategy, static and dynamic obstacle classification, and speed adaptive factor. The length of the path and the number of inflection points were reduced, and the influence of known obstacles on the path was minimized to improve the efficiency of dynamic obstacle avoidance, which enabled the robot to smoothly arrive at the target point and improved the safety of the robot, and better adapted to complex dynamic and static environments. The experimental results show that the algorithm has better global optimality and local obstacle avoidance ability, and shows better advantages in large maps.
Key words: robot path planning    dynamic obstacle avoidance    improved A* algorithm    random obstacle avoidance dynamic window algorithm (ROA-DWA)    fusion algorithm
收稿日期: 2023-08-21 出版日期: 2024-01-23
CLC:  TP 242  
基金资助: 国家自然科学基金资助项目（52065053）；科技部国家重点研发计划资助项目（2018YFB1307501）；中央引导地方科技发展专项资助项目（2020ZY0002）；内蒙古关键技术攻关资助项目（2020GG0255）；内蒙古自然科学基金资助项目（2022FX01, 2023LHMS05018）；内蒙古自治区高等学校科学研究资助项目（NJZY21308）；内蒙古自治区直属高校基本科研业务费资助项目（JY20220046）；内蒙古自治区高等学校青年科技英才支持计划资助项目（NJYT23043）；内蒙古自治区高等学校创新团队发展支持计划资助项目（NMGIRT2213）；内蒙古自治区科技计划资助项目（2021GG0259)
通讯作者: 郭世杰     E-mail: 1511260827@qq.com;sjguo@imut.edu.cn;tangshufeng@imut.edu.cn
作者简介: 刘宇庭（1998—），男，硕士生，从事路径规划和自主导航的研究. orcid.org/0009-0008-8941-8310. E-mail：1511260827@qq.com
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
刘宇庭
郭世杰
唐术锋
张学炜
李田田

引用本文:

刘宇庭,郭世杰,唐术锋,张学炜,李田田. 改进A*与ROA-DWA融合的机器人路径规划[J]. 浙江大学学报(工学版), 2024, 58(2): 360-369.

Yuting LIU,Shijie GUO,Shufeng TANG,Xuewei ZHANG,Tiantian LI. Path planning based on fusion of improved A* and ROA-DWA for robot. Journal of ZheJiang University (Engineering Science), 2024, 58(2): 360-369.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2024.02.014    或    https://www.zjujournals.com/eng/CN/Y2024/V58/I2/360

图 1  3种启发函数距离的示意图
图 2  路径平滑优化策略
图 3  改进A*与ROA-DWA的融合流程图
图 4  20×20栅格地图的仿真结果对比图
图 5  30×30栅格地图的仿真结果对比图
图 6  50×50栅格地图的仿真结果对比图
地图尺寸算法L/mT/sNP$\Sigma \theta $/(°)
20×20传统A*算法29.7960.5281497265.45
文献[17]算法29.3760.3251497254.85
文献[18]算法29.5830.2811218265.45
本文改进算法29.3760.1461137254.85
30×30传统A*算法44.5560.96630113627.67
文献[17]算法44.3680.74330112652.81
文献[18]算法44.2740.67721512559.44
本文改进算法44.2660.18319511544.32
50×50传统A*算法80.6363.0991087251543.96
文献[17]算法79.8682.8531087251524.61
文献[18]算法79.3741.573544281478.82
本文改进算法77.7841.379499251406.98
表 1  全局路径规划的仿真数据
参数数值参数数值
vmax/(m·s?1)2.0ωmax/(${{(^\circ) \cdot {\rm{s}}^{-1}}}$)40.0
amax/(${\text{m}}\cdot{{\text{s}}^{-\text{2}}}$)0.4βmax/(${{(^\circ) }}\cdot {{\text{s}}^{-\text{2}}}$)100.0
vres/(${\text{m}\cdot {\rm{s}}^{-1}}$)0.01ωres/(${{(^\circ) \cdot {\rm{s}^{-1}}}}$)1.0
Tres/s0.1Tpred/s3.0
表 2  机器人运动学参数
图 7  静态环境下的运动轨迹
图 8  动态环境下的运动轨迹
算法L/mT/sK/m?1是否碰撞/
到达终点
文献[17]融合算法29.746183.7640.21是/是
文献[18]融合算法29.341167.2730.19是/是
改进A*-ROA-DWA融合算法29.548117.1620.16否/是
表 3  融合算法仿真数据
图 9  动态环境下的机器人状态
图 10  融合算法的路径规划实验设备与实验场地
图 11  融合算法路径规划
算法L/mT/sK/m?1
传统融合算法7.26928.4690.23
本文融合算法7.17625.7240.21
表 4  传统融合算法和本文融合算法性能的对比
1 吴敬理, 伊国栋, 裘乐淼, 等 高温混合障碍空间中的移动机器人路径规划[J]. 浙江大学学报: 工学版, 2021, 55 (10): 1806- 1814
WU Jingli, YI Guodong, QIU Lemiao, et al Path planning for mobile robots in high-temperature hybrid obstacle space[J]. Journal of Zhejiang University: Engineering Science, 2021, 55 (10): 1806- 1814
2 JEDDISARAVI K, ALITAPPEH R J, PIMENTA L C A, et al Multiobjective approach for robot motion planning in search tasks[J]. Applied Intelligence, 2016, 45 (2): 305- 321
doi: 10.1109/TSSC.1968.300136
3 江明, 王飞, 葛愿, 等 基于改进蚁群算法的移动机器人路径规划研究[J]. 仪器仪表学报, 2019, 40 (2): 113- 121
JIANG Ming, WANG Fei, GE Yuan, et al Research on path planning of mobile robots based on improved ant colony algorithm[J]. Chinese Journal of Scientific Instrument, 2019, 40 (2): 113- 121
4 GUO J, LIU L, LIU Q, et al. An improvement of D* algorithm for mobile robot path planning in partial unknown environment [C]// 2009 Second International Conference on Intelligent Computation Technology and Automation. Changsha: IEEE, 2009: 394-397.
5 林依凡, 陈彦杰, 何炳蔚, 等 无碰撞检测RRT~*的移动机器人运动规划方法[J]. 仪器仪表学报, 2020, 41 (10): 257- 267
LIN Yifan, CHEN Yanjie, HE Bingwei, et al A motion planning method for mobile robots with collision-free detection RRT~*[J]. Chinese Journal of Scientific Instrument, 2020, 41 (10): 257- 267
6 KAVRAKI L E, SVESTKA P, LATOMBE J C, et al Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation, 1996, 12 (4): 566- 580
doi: 10.1109/70.508439
7 DENG Y, CHEN Y, ZHANG Y, et al Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment[J]. Applied Soft Computing, 2012, 12 (3): 1231- 1237
doi: 10.1016/j.asoc.2011.11.011
8 王殿君 基于改进A~*算法的室内移动机器人路径规划[J]. 清华大学学报: 自然科学版, 2012, 52 (8): 1085- 1089
WANG Dianjun Path planning for indoor mobile robots based on improved A~* algorithm[J]. Journal of Tsinghua University: Natural Science Edition, 2012, 52 (8): 1085- 1089
9 刘军, 冯硕, 任建华 移动机器人路径动态规划有向D~*算法[J]. 浙江大学学报: 工学版, 2020, 54 (2): 291- 300
LIU Jun, FENG Shuo, REN Jianhua Path dynamic planning for mobile robot based on directed D~* algorithm[J]. Journal of Zhejiang University: Engineering Science, 2020, 54 (2): 291- 300
10 李志锟, 黄宜庆, 徐玉琼 改进变步长蚁群算法的移动机器人路径规划[J]. 电子测量与仪器学报, 2020, 34 (8): 15- 21
LI Zhikun, HUANG Yiqing, XU Yuqiong Improved variable-step ant colony algorithm for mobile robot path planning[J]. Journal of Electronic Measurement and Instrumentation, 2020, 34 (8): 15- 21
11 PATLE B K, PARHI D R K, JAGADEESH A, et al Matrix-binary codes based genetic algorithm for path planning of mobile robot[J]. Computers and Electrical Engineering, 2018, 67 (2): 708- 728
12 MA Y, HU M, YAN X Multi-objective path planning for unmanned surface vehicle with currents effects[J]. ISA Transactions, 2018, 75 (10): 137- 156
13 王洪斌, 尹鹏衡, 郑维, 等 基于改进的A~*算法与动态窗口法的移动机器人路径规划[J]. 机器人, 2020, 42 (3): 346- 353
WANG Hongbin, YIN Pengheng, ZHENG Wei, et al Path planning for mobile robots based on improved A~* algorithm and dynamic window method[J]. Robot, 2020, 42 (3): 346- 353
14 RATH A K, PARHI D R, DAS H C, et al Analysis and use of fuzzy intelligent technique for navigation of humanoid robot in obstacle prone zone[J]. Defence Technology, 2018, 14 (6): 677- 682
doi: 10.1016/j.dt.2018.03.008
15 OROZCO R U, MONTIEL O, SEPULVEDA R Mobile robot path planning using membrane evolutionary artificial potential field[J]. Applied Soft Computing, 2019, 77 (5): 236- 251
16 张瑜, 宋荆洲, 张琪祁 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人, 2020, 42 (5): 617- 625
ZHANG Yu, SONG Jingzhou, ZHANG Qiqi Local path planning for outdoor sweeping robots based on improved dynamic window method[J]. Robot, 2020, 42 (5): 617- 625
17 陈娇, 徐菱, 陈佳, 等 改进A~*和动态窗口法的移动机器人路径规划[J]. 计算机集成制造系统, 2022, 28 (6): 1650- 1658
CHEN Jiao, XU Ling, CHEN Jia, et al Improved A~* and dynamic window method for mobile robot path planning[J]. Computer Integrated Manufacturing Systems, 2022, 28 (6): 1650- 1658
18 迟旭, 李花, 费继友 基于改进A~*算法与动态窗口法融合的机器人随机避障方法研究[J]. 仪器仪表学报, 2021, 42 (3): 132- 140
CHI Xu, LI Hua, FEI Jiyou Research on randomized obstacle avoidance method for robots based on the fusion of improved A~* algorithm and dynamic window method[J]. Chinese Journal of Scientific Instrument, 2021, 42 (3): 132- 140
19 劳彩莲, 李鹏, 冯宇 基于改进A~*与DWA算法融合的温室机器人路径规划[J]. 农业机械学报, 2021, 52 (1): 14- 22
LAO Cailian, LI Peng, FENG Yu Greenhouse robot path planning based on improved A~* and DWA algorithm fusion[J]. Journal of Agricultural Machinery, 2021, 52 (1): 14- 22
doi: 10.6041/j.issn.1000-1298.2021.01.002
20 张志文, 张鹏, 毛虎平, 等 改进A*算法的机器人路径规划研究[J]. 电光与控制, 2021, 28 (4): 21- 25
ZHANG Zhiwen, ZHANG Peng, MAO Huping, et al Improved A* algorithm for robot path planning[J]. Electro-Optics and Control, 2021, 28 (4): 21- 25
21 LI X, LIU F, LIU J, et al Obstacle avoidance for mobile robot based on improved dynamic window approach[J]. Turkish Journal of Electrical Engineering and Computer Sciences, 2017, 25 (2): 666- 676
22 程传奇, 郝向阳, 李建胜, 等 融合改进A~*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报, 2017, 51 (11): 137- 143
CHENG Chuanqi, HAO Xiangyang, LI Jiansheng, et al Fusion of improved A~* algorithm and dynamic window method for global dynamic path planning[J]. Journal of Xi’an Jiaotong University, 2017, 51 (11): 137- 143
23 康博涵, 黄静雯 基于环境复杂度的移动机器人变步长RRT路径规划算法与仿真研究[J]. 北京化工大学学报: 自然科学版, 2023, 50 (4): 87- 93
KANG Bohan, HUANG Jingwen Research on variable step size RRT path planning algorithm and simulation of mobile robot based on environment complexity[J]. Journal of Beijing University of Chemical Technology: Natural Science Edition, 2023, 50 (4): 87- 93
[1] 郭万金,赵伍端,利乾辉,赵立军,曹雏清. 基于集成概率模型的变阻抗机器人打磨力控制[J]. 浙江大学学报(工学版), 2023, 57(12): 2356-2366.
[2] 姜玉峰,陈东生. 基于深度强化学习的大口径轴孔装配策略[J]. 浙江大学学报(工学版), 2023, 57(11): 2210-2216.
[3] 薛雅丽,叶金泽,李寒雁. 基于改进强化学习的多智能体追逃对抗[J]. 浙江大学学报(工学版), 2023, 57(8): 1479-1486.
[4] 郭万金,赵伍端,于苏扬,赵立军,曹雏清. 无先验模型曲面的机器人打磨主动自适应在线轨迹预测方法[J]. 浙江大学学报(工学版), 2023, 57(8): 1655-1666.
[5] 仲重亮,刘云峰,朱伟东,朱赴东. 面向口腔种植的机器人多姿态轨迹平滑规划[J]. 浙江大学学报(工学版), 2023, 57(5): 1030-1037.
[6] 张超凡,乔一铭,曹露,王志刚,崔少伟,王硕. 基于神经形态的触觉滑动感知方法[J]. 浙江大学学报(工学版), 2023, 57(4): 683-692.
[7] 常同立,傅万斌. 自对准人工膝关节的人机匹配设计[J]. 浙江大学学报(工学版), 2023, 57(4): 753-759.
[8] 陶治同,陶建峰,覃程锦,刘成良. 基于时间冲击最优的TBM换刀机器人轨迹规划[J]. 浙江大学学报(工学版), 2023, 57(1): 1-9.
[9] 蒋林,刘林锐,周安娜,韩璐,李平原. 基于运动预测的改进ORB-SLAM算法[J]. 浙江大学学报(工学版), 2023, 57(1): 170-177.
[10] 赵业和,刘达新,刘振宇,谭建荣. 基于多种群竞争松鼠搜索算法的机械臂时间最优轨迹规划[J]. 浙江大学学报(工学版), 2022, 56(12): 2321-2329.
[11] 叶梦佳,王宇轩,王赟,赖周年,曹琳琳,吴大转. AUV平面直线航迹跟踪控制算法[J]. 浙江大学学报(工学版), 2022, 56(11): 2127-2134.
[12] 张世玉,陈东生,宋颖慧. 基于自抗干扰的装配机器人阻抗控制技术[J]. 浙江大学学报(工学版), 2022, 56(9): 1876-1881.
[13] 许明,张帝,戎铖,苏礼荣,王万强. 基于Bouc-Wen修正模型的柔性关节驱动器迟滞建模[J]. 浙江大学学报(工学版), 2022, 56(8): 1560-1567, 1621.
[14] 华夏,王新晴,芮挺,邵发明,王东. 视觉感知的无人机端到端目标跟踪控制技术[J]. 浙江大学学报(工学版), 2022, 56(7): 1464-1472.
[15] 郭策,曾志文,朱鹏铭,周智千,卢惠民. 基于图卷积模仿学习的分布式群集控制[J]. 浙江大学学报(工学版), 2022, 56(6): 1055-1061.