计算机工程

作者：王志特, 罗丽平, 廖义奎

单位：1. 广西民族大学电子信息学院, 广西 南宁 5300062. 广西高校智慧无人系统与智能装备重点实验室, 广西 南宁 530006

关键词：路径规划,A^*算法,动态窗口法,复杂环境,时间效率

基金：国家自然科学基金(61762011); 广西自然科学基金(2018GXNSFAA294059); 广西科技重大专项(2023AA17010)

针对机器人路径规划对于路径最短、搜索效率以及平滑度的性能要求, 提出一种改进A*算法与改进动态窗口法(DWA)相融合的算法。针对传统A*算法在复杂场景下输出非最优路径、寻路效率低等问题, 结合曼哈顿距离和对角线距离设计新的启发函数, 并对其动态分配权重, 实现全局路径最短, 减少寻路时间。针对传统8邻域8方向搜索方式搜索效率低、耗时长等问题, 提出一种基于8邻域改进的搜索策略, 对当前节点实时动态分配最优的搜索方向。针对路径存在多余无用节点的问题, 使用Floyd算法去除冗余节点, 减少转向次数, 缩短路径长度。针对传统动态窗口法规划的路径非全局最优、目标点附近存在障碍物时规划的路径长度增加或者规划失败的问题, 加入全局关键节点信息和引入目标点距离评估子函数。针对关键节点距离较长导致融合算法规划的路径偏离全局最优路径的问题, 提出关键点密集化策略。最后, 将提出的改进A*算法、融合算法和已有的其他改进算法进行比较, 仿真结果表明: 改进的A*算法能够在复杂环境中生成最短全局路径, 平均转向次数减少16.3%, 平均寻路时间缩短55.66%;融合算法在临时障碍物环境下, 平均路径长度和平均运行时间分别缩短6.1%和14.7%, 在移动障碍物环境下, 平均路径长度和平均运行时间分别缩短1.6%和39.8%。

来源：2024年第8期

《计算机工程》期刊编辑部

查看计算机工程杂志2024年第8期