• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2023, Vol. 45 ›› Issue (09): 1661-1669.

• 人工智能与数据挖掘 • 上一篇    下一篇

基于局部障碍率预获取和双向父节点变更的A*算法优化

张志远,陈海进,章一鸣   

  1. (南通大学信息科学技术学院,江苏 南通 226019)
  • 收稿日期:2021-08-03 修回日期:2022-04-26 接受日期:2023-09-25 出版日期:2023-09-25 发布日期:2023-09-12

An optimized A* algorithm based on local obstacle rate pre-acquisition and bidirectional parent node change

ZHANG Zhi-yuan,CHEN Hai-jin,ZHANG Yi-ming   

  1. (School of Information Science and Technology,Nantong University,Nantong 226019,China)
  • Received:2021-08-03 Revised:2022-04-26 Accepted:2023-09-25 Online:2023-09-25 Published:2023-09-12

摘要: 针对传统A*算法未能有效识别环境信息造成的路径优化差、搜索效率低和灵活性低的一系列问题,提出了一种基于局部障碍率预获取和双向父节点变更的改进A*算法。首先,基于漂移矩阵算法获取栅格地图各个部分的局部障碍率;其次,将预获取的局部障碍信息融入改进的A*算法评价函数中,依据地图各个区域的不同复杂程度自适应地调整搜索空间;最后,用改进的父节点变更方式进一步优化路径,减少生成路径的冗余点和拐点。仿真结果表明,本文设计的算法在路径长度、拐点数量、搜索效率和运行时间等指标上有明显提高。

关键词: A*算法, 路径规划, 栅格地图, 漂移矩阵, 节点变更

Abstract: Aiming at the problems of poor path optimization, low search efficiency and low flexibility caused by the traditional A* algorithms failure to identify the environmental information effectively, an improved A* algorithm based on local obstacle rate pre-acquisition and bidirectional parent node change is proposed. Firstly, the local obstacle rate of each part of the grid map is obtained based on the drift matrix algorithm. Then, the pre-acquired local obstacle information is integrated into the improved A* algorithms evaluation function, and the search space is adaptively adjusted according to the different complexity of each region of the map. Finally, the improved parent node change method is used to further optimize the path and reduce the redundant points and inflection points of the generated path. The simulation results show that the algorithm has a significant improvement in the path length, the number of inflection points, search efficiency, running time and other indicators.

Key words: A* algorithm, path planning, grid map, drift matrix, node change