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

来源：计算机工程与应用杂志2022年第24期北京时间：

作者：黄梦涛, 李智伟

单位：西安科技大学 电气与控制工程学院，西安 710600

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

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