基于双向搜索的改进A^(*)算法路径规划研究

Research on Improved A*Algorithm Path Planning Based on Bidirectional Search

为了提高A^(*)算法的搜索效率、保证路径的最优性,提出了一种基于双向搜索的改进A^(*)算法,以正向、反向搜索的当前节点互为目标点进行双向搜索。首先,引入加权曼哈顿作为距离启发函数,动态调整代价函数的权重比,以保证算法的实时性和路径的优越性;其次,针对双向路径搜索过程中存在的局部路径最优问题,在启发函数中加入偏离最优距离作为代价因素。仿真实验结果表明,该算法的搜索效率更高、遍历节点和路径代价更少,验证了算法的有效性。

In order to improve the search efficiency of A*algorithm and ensure the optimality of paths,an improved A*algorithm based on bidirectional search is proposed.The current nodes of forward and reverse search are mutual target points for bidirectional search.Firstly,the weighted Manhattan is introduced as the distance heuristic function,and the weight ratio of the cost function is dynamically adjusted to ensure the real-time performance and path superiority of the algorithm.Secondly,in order to solve the problem of local path optimization in bidirectional path search,the deviation from the optimal distance is added as a cost factor in the heuristic function.Simulation results show that the algorithm has higher search efficiency and less cost of traversing nodes and paths,which verifies the effectiveness of the algorithm.