基于图论节点的改进A-star栅格路径规划算法

作者：赵玉玲; 邵腾戊; 苏德国^*

来源：廊坊师范学院学报(自然科学版), 2023, 23(04): 34-38.

• 栅格地图
• A-star算法
• 图论
• 路径规划

提出了一种将图论最短问题中的路径节点及栅格地图中的栅格节点位置信息结合的路径规划算法。依据图论最短问题思想，提取室内具有特殊信息的位置节点，并判断节点间可视性，加入到先决地图信息中。在此基础上改进的A-star算法在扩展节点时，根据启发函数，只在特殊节点位置进行扩展，避免计算大量不必要栅格点的启发函数，从而提高算法效率。实验结果表明，改进后的A-star算法较之前时间缩短了79.2%，所遍历栅格节点减少了99.4%，且栅格分辨率大小不影响路径规划效率。最后总结改进方法的优缺点，期望改进算法可用于室内多目标同时导航。

• 单位
  河北工程大学; 中国测绘科学研究院