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

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

作　　者：张志远 陈海进[1] 章一鸣 ZHANG Zhi-yuan;CHEN Hai-jin;ZHANG Yi-ming(School of Information Science and Technology,Nantong University,Nantong 226019,China)

机构地区：[1]南通大学信息科学技术学院,江苏南通226019

出　　处：《计算机工程与科学》2023年第9期1661-1669,共9页Computer Engineering & Science

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

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

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]