Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (8): 168-174.DOI: 10.3778/j.issn.1002-8331.2010-0222

• Pattern Recognition and Artificial Intelligence • Previous Articles     Next Articles

Improved A* Algorithm Based on Neighbor Extension in Static Environment

GUO Xiaojing, YANG Zhuocheng   

  1. College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
  • Online:2022-04-15 Published:2022-04-15

基于邻域拓展的静态路径规划A*算法研究

郭晓静,杨卓橙   

  1. 中国民航大学 电子信息与自动化学院,天津 300300

Abstract: The traditional A* algorithm only has 8 searching-direction, which leads to the long and uneven path searching result. In order to solve this problem, the traditional A* algorithm is improved in two aspects in this paper. Firstly, the traditional 8-neighborhood A* algorithm is extended to 24-neighborhood, and then the guiding vectors are used to reduce the invalid neighborhood search and improve the efficiency. The vector is formed by the nodes, which have the minimum value in evaluation function of [f(n)]. Secondly, path smoothing algorithm is used to eliminate the redundant nodes of the path. Under the grid map environment and real scenes map, the improved A* algorithm is applicable. Compared with the traditional A* algorithm, the 24-neighborhood A* algorithm, the Dijkstra algorithm and the rapidly-exploring random trees(RRT) algorithm, according to the results of simulation experiments in Matlab, the improved A* algorithm has great advantages in performance items, such as the success rate, path length and searching time, and also, it performs well in the real scene map.

Key words: path planning, A* algorithm, neighborhood extension, smoothing

摘要: 为了解决传统的A*算法搜索自由度低,规划出的路径长度长且转角大的问题,提出了一种改进的A*算法。改进算法将传统的8邻域搜索拓展到24邻域,并利用引导向量优化邻域数量,提升搜索效率;采用路径平滑算法消除路径中的冗余节点,优化平滑路径。在不同障碍率、不同栅格地图等12种模拟场景下的100次有效实验与真实地图下的20次有效实验中,改进后算法总体较好。在Matlab中的仿真结果表明,与8邻域A*算法、24邻域A*算法、Dijkstra算法、快速拓展随机树算法等传统方法比较,改进的A*算法搜索成功率、路径长度、搜索时间等指标明显优化,搜索出路径平滑,且在真实场景下该算法仍稳定有效。

关键词: 路径规划, A*算法, 邻域拓展, 平滑处理