Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (24): 291-297.DOI: 10.3778/j.issn.1002-8331.2106-0408

• Engineering and Applications • Previous Articles     Next Articles

Path Planning of Mobile Robot Based on Improved ARA* Algorithm

HUANG Mengtao, LI Zhiwei   

  1. College of Electrical and Control Engineering, Xi'an University of Science and Technology, Xi'an 710600, China
  • Online:2022-12-15 Published:2022-12-15

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

黄梦涛,李智伟   

  1. 西安科技大学 电气与控制工程学院,西安 710600

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

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