改进ARA*算法的移动机器人路径规划

doi:10.3778/j.issn.1002-8331.2106-0408

摘要/Abstract

摘要： 针对传统ARA*移动机器人全局路径规划算法效率和安全性的缺陷，在ARA*算法的基础上进行了改进。用二叉排序树代替传统ARA*算法中用来存储节点信息的线性表，减少搜索一维数据结构最小值时需要查阅的数据个数，降低节点更新模块的时间复杂度，提高算法效率；为了保持机器人与障碍物之间的安全距离，提出了一种自适应的节点间连接方式选择策略，通过4连接与8连接的融合，移动机器人可以在局部无障碍范围内减少自身折转次数，避免路径冗余，在障碍物角点直角折转，降低移动机器人执行任务时的安全风险。仿真结果表明，改进后的ARA*算法搜索时间相比传统ARA*算法减少了43%；改进算法规划出的路径保证机器人始终能与障碍物保持安全距离。

关键词: 移动机器人, 路径规划, ARA*算法, 二叉树, 线性表, 启发函数

Abstract: Aiming at the shortcomings of efficiency and security of traditional algorithms for global path planning of ARA* mobile robot, the algorithm is improved based on ARA* algorithm. Firstly, binary sorting tree is used to replace the linear table used to store node information in traditional ARA* algorithm, which reduces the number of data to be consulted for the minimum value of one-dimensional data structure, reduces the time complexity of node update module and improves the efficiency of algorithm. In addition, in order to keep the safe distance between the robot and the obstacle, an adaptive node connection method selection strategy is proposed. Through the fusion of 4 connections and 8 connections, the mobile robot can reduce the number of self rotation within the local accessibility range, avoid redundant paths, and turn at right angles at the corner of obstacles, and reduce the safety risk of the mobile robot when performing tasks. The simulation results show that the search time of the improved ARA* algorithm is 43% less than that of the traditional ARA* algorithm. The path planned by the improved algorithm ensures that the robot can always keep a safe distance from the obstacle.

Key words: mobile robot, path planning, ARA* algorithm, binary sort tree, linear list, heuristic function

黄梦涛, 李智伟. 改进ARA*算法的移动机器人路径规划[J]. 计算机工程与应用, 2022, 58(24): 291-297.

HUANG Mengtao, LI Zhiwei. Path Planning of Mobile Robot Based on Improved ARA* Algorithm[J]. Computer Engineering and Applications, 2022, 58(24): 291-297.

参考文献

[1] 陈慧岩，熊光明，龚建伟，等.无人驾驶汽车概论[M].北京：北京理工大学出版社，2014：53-54.
CHEN H Y，XIONG G M，GONG J W，et al.Introduction to driverless vehicle[M].Beijing：Beijing University of Technology Press，2014：53-54.
[2] 战强.机器人学——机构、运动学、动力学及运动规划[M].北京：清华大学出版社，2019：34-35.
ZHAN Q.Robotics—mechanism，kinematics，dynamics and motion planning[M].Beijing：Tsinghua University Press，2019：34-35.
[3] 王梓强，胡晓光，李晓筱，等.移动机器人全局路径规划算法综述[J].计算机科学，2021，48（10）：19-29.
WANG Z Q，HU X G，LI X X，et al.Overview of global path planning algorithms for mobile robots[J].Computer Science，2021，48（10）：19-29.
[4] 孔继利，张鹏坤，刘晓平.双向搜索机制的改进A*算法研究[J].计算机工程与应用，2021，57（8）：231-237.
KONG J L，ZHANG P K，LIU X P.Research on improved A* algorithm of bidirectional search mechanism[J].Computer Engineering and Applications，2021，57（8）：231-237.
[5] 钟志峰，易明星，陈智军，等.基于改进A*算法的导购路径规划方法[J].计算机工程与应用，2019，55（5）：129-134.
ZHONG Z F，YI M X，CHEN Z J，et al.Method of shopping guide path planning based on modified A* algorithm[J].Computer Engineering and Applications，2019，55（5）：129-134.
[6] 李二超，齐款款.改进双向蚁群算法的移动机器人路径规划[J].计算机工程与应用，2021，57（18）：281-288.
LI E C，QI K K.Improved bidirectional ant colony algorithm mobile robot path planning[J].Computer Engineering and Applications，2021，57（18）：281-288.
[7] 刘建娟，薛礼啟，张会娟，等.融合改进A*与DWA算法的机器人动态路径规划[J].计算机工程与应用，2021，57（15）：73-81.
LIU J J，XUE L Q，ZHANG H J，et al.Robot dynamic path planning based on improved A* and DWA algorithm[J].Computer Engineering and Applications，2021，57（15）：73-81.
[8] 许万，杨晔，余磊涛，等.一种基于改进RRT*的全局路径规划算法[J].控制与决策，2022，37（4）：829-838.
XU W，YANG Y，YU L T，et al.A global path planning algorithm based on improved RRT*[J].Control and Decision，2022，37（4）：829-838.
[9] 胡章芳，程亮，张杰，等.多约束条件下基于改进遗传算法的移动机器人路径规划[J].重庆邮电大学学报（自然科学版），2021，33（6）：999-1006.
HU Z F，CHENG L，ZHANG J，et al.Path planning of mobile robot based on improved genetic algorithms under multiple constraints[J].Journal of Chongqing University of Posts and Telecommunications（Natural Science Edition），2021，33（6）：999-1006.
[10] 徐菱，付文浩，江文辉，等.基于16方向24邻域改进蚁群算法的移动机器人路径规划[J].控制与决策，2021，36（5）：1137-1146.
XU L，FU W H，JIANG W H，et al.Mobile robot path planning based on 16-direction 24-neighborhoods improved ant colony algorithm[J].Control and Decision，2021，36（5）：1137-1146.
[11] LIKHACHEV M，GORDON G，THRUN S.ARA*：formal analysis[R].Pittsburgh：Carnegie Mellon University，2003.
[12] EBENDT R，DRECHSLER R.Weighted A* search-unifying view and application[J].Artificial Intelligence，2009，173（14）：1310-1342.
[13] BONET B，GEFFNER H.Planning as heuristic search：new results[C]//European Conference on Planning：Recent Advances in Ai Planning.[S.l.]：Springer-Verlag，1999：360-372.
[14] 赵鑫，胡广地.平滑ARA*算法在智能车辆路径规划的应用[J].机械科学与技术，2017，36（8）：1272-1275.
ZHAO X，HU G D.Application of smoothing ARA* algorithm in intelligent vehicle path planning[J].Mechanical Science and Technology for Aerospace Engineering，2017，36（8）：1272-1275.
[15] 科尔曼，雷瑟尔森，李维斯，等.算法导论[M].3版.潘金贵，顾铁成，译.北京：机械工业出版社，2009：758-759.
THOMAS H C，CHARLES E L，RONALD L R，et al.Introduction to algorithms[M].3rd ed.PAN J G，GU T C.Beijing：China Machine Press，2009：758-759.
[16] 耿国华，刘晓宁，张德同，等.数据结构——C语言描述[M].
3版.西安：西安电子科技大学出版社，2020：122-123.
GENG G H，LIU X N，ZHANG D T，et al.Data structure—C language description[M].3rd ed.Xi’an：Xidian University Press，2020：122-123.
[17] 特龙，比加尔，福克斯.概率机器人[M].曹红玉，谭志，史晓霞，等译.北京：机械工业出版社，2019：22-23.
THRUN S，BURGARD W，FOX D.Probabilistic robotics[M].CAO H Y，TAN Z，SHI X X，et al.Beijing：China Machine Press，2019：22-23.
[18] 韩明，刘教民，吴朔媚，等.粒子群优化的移动机器人路径规划算法[J].计算机应用，2017，37（8）：2258-2263.
HAN M，LIU J M，WU S M，et al.Path planning algorithm of mobile robot based on particle swarm optimization[J].Journal of Computer Applications，2017，37（8）：2258-2263.