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