Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2024, Vol. 58 Issue (2): 360-369    DOI: 10.3785/j.issn.1008-973X.2024.02.014
    
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
Download: HTML     PDF(2840KB) HTML
Export: BibTeX | EndNote (RIS)      

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 wordsrobot path planning      dynamic obstacle avoidance      improved A* algorithm      random obstacle avoidance dynamic window algorithm (ROA-DWA)      fusion algorithm     
Received: 21 August 2023      Published: 23 January 2024
CLC:  TP 242  
Fund:  国家自然科学基金资助项目(52065053);科技部国家重点研发计划资助项目(2018YFB1307501);中央引导地方科技发展专项资助项目(2020ZY0002);内蒙古关键技术攻关资助项目(2020GG0255);内蒙古自然科学基金资助项目(2022FX01, 2023LHMS05018);内蒙古自治区高等学校科学研究资助项目(NJZY21308);内蒙古自治区直属高校基本科研业务费资助项目(JY20220046);内蒙古自治区高等学校青年科技英才支持计划资助项目(NJYT23043);内蒙古自治区高等学校创新团队发展支持计划资助项目(NMGIRT2213);内蒙古自治区科技计划资助项目(2021GG0259)
Corresponding Authors: Shijie GUO     E-mail: 1511260827@qq.com;sjguo@imut.edu.cn;tangshufeng@imut.edu.cn
Cite this article:

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.

URL:

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


改进A*与ROA-DWA融合的机器人路径规划

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


关键词: 机器人路径规划,  动态避障,  改进A*算法,  随机避障动态窗口法(ROA-DWA),  融合算法 
Fig.1 Distance diagram of three heuristic functions
Fig.2 Path smoothing optimization strategy
Fig.3 Fusion flow chart of improved A* and ROA-DWA
Fig.4 Comparison of simulation results for 20×20 raster map
Fig.5 Comparison of simulation results for 30×30 raster map
Fig.6 Comparison of simulation results for 50×50 raster map
地图尺寸算法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
Tab.1 Simulation data of global path planning
参数数值参数数值
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
Tab.2 Kinematic parameters of robot
Fig.7 Motion trajectory in static environments
Fig.8 Motion trajectory in dynamic environments
算法L/mT/sK/m?1是否碰撞/
到达终点
文献[17]融合算法29.746183.7640.21是/是
文献[18]融合算法29.341167.2730.19是/是
改进A*-ROA-DWA融合算法29.548117.1620.16否/是
Tab.3 Simulation data of fusion algorithm
Fig.9 Robot states in dynamic environments
Fig.10 Experimental equipment and laboratory space of path planning for fusion algorithm
Fig.11 Fusion algorithm path planning
算法L/mT/sK/m?1
传统融合算法7.26928.4690.23
本文融合算法7.17625.7240.21
Tab.4 Performance comparison of traditional fusion algorithm with proposed fusion algorithm
[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] Wan-jin GUO,Wu-duan ZHAO,Qian-hui LI,Li-jun ZHAO,Chu-qing CAO. Ensemble probabilistic model based variable impedance for robotic grinding force control[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(12): 2356-2366.
[2] Yu-feng JIANG,Dong-sheng CHEN. Assembly strategy for large-diameter peg-in-hole based on deep reinforcement learning[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2210-2216.
[3] Ya-li XUE,Jin-ze YE,Han-yan LI. Multi-agent pursuit and evasion games based on improved reinforcement learning[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(8): 1479-1486.
[4] Wan-jin GUO,Wu-duan ZHAO,Su-yang YU,Li-jun ZHAO,Chu-qing CAO. Active adaptive online trajectory prediction for robotic grinding on surface without prior model[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(8): 1655-1666.
[5] Chong-liang ZHONG,Yun-feng LIU,Wei-dong ZHU,Fu-dong ZHU. Multi-orientation trajectory smoothing planning of robot for dental implant[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(5): 1030-1037.
[6] Chao-fan ZHANG,Yi-ming QIAO,Lu CAO,Zhi-gang WANG,Shao-wei CUI,Shuo WANG. Tactile slip detection method based on neuromorphic modeling[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(4): 683-692.
[7] Tong-li CHANG,Wan-bin FU. Human-robot matching design of self-aligning artificial knee joint[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(4): 753-759.
[8] Zhi-tong TAO,Jian-feng TAO,Cheng-jin QIN,Cheng-liang LIU. Trajectory planning of TBM disc cutter changing robot based on time-jerk optimization[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(1): 1-9.
[9] Lin JIANG,Lin-rui LIU,An-na ZHOU,Lu HAN,Ping-yuan LI. Improved ORB-SLAM algorithm based on motion prediction[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(1): 170-177.
[10] Ye-he ZHAO,Da-xin LIU,Zhen-yu LIU,Jian-rong TAN. Time-optimal trajectory planning of manipulator based on multi-group competition squirrel search algorithm[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(12): 2321-2329.
[11] Meng-jia YE,Yu-xuan WANG,Yun WANG,Zhou-nian LAI,Lin-lin CAO,Da-zhuan WU. Straight-line path tracking control algorithm of AUV planar motion[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(11): 2127-2134.
[12] Shi-yu ZHANG,Dong-sheng CHEN,Ying-hui SONG. Impedance control technology of assembly robot based on active disturbance rejection[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(9): 1876-1881.
[13] Ming XU,Di ZHANG,Cheng RONG,Li-rong SU,Wan-qiang WANG. Modified Bouc-Wen based hysteresis modeling of flexible joint actuator[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(8): 1560-1567, 1621.
[14] Xia HUA,Xin-qing WANG,Ting RUI,Fa-ming SHAO,Dong WANG. Vision-driven end-to-end maneuvering object tracking of UAV[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(7): 1464-1472.
[15] Ce GUO,Zhi-wen ZENG,Peng-ming ZHU,Zhi-qian ZHOU,Hui-min LU. Decentralized swarm control based on graph convolutional imitation learning[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(6): 1055-1061.