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

文章摘要

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

Research on improved A* algorithm path planning method based on two-way search

投稿时间：2023-06-13 修订日期：2023-06-13

DOI：

英文关键词: A* algorithm Bidirectional search strategy deviation from the optimal distance dynamic weighting Path planning

基金项目:重庆市科技局自然科学基金项目( cstc2020jcyj-msxmX0927)

作者	单位	邮编
贾兵	重庆科技学院	628317
张俊林^*	重庆科技学院	401331
聂玲	重庆科技学院
石冬阳	重庆科技学院

摘要点击次数: 119

全文下载次数: 0

中文摘要:

在A*算法以及其改进算法的应用过程中,所得到的路径往往存在节点冗余、转折点较多和搜索时间较长等问题,为提高A*算法在运用过程中的搜索效率,并保证路径的最优性,文章提出一种基于双向搜索的优化A*算法,该算法以正向、反向搜索的当前节点互为目标点进行双向相互搜索。首先,对代价函数退化的问题,引入加权曼哈顿作为距离启发函数,动态调整代价函数内部的权重比,保证了算法搜索时的实时性以及所得路径的优越性。其次,针对双向路径搜索过程中存在的局部路径最优,偏离全局最优路径的问题,在启发函数中加入偏离最优距离作为代价因素,引入搜索过程对全局最优的考虑。实验结果表明：优化后的算法搜索效率更高,遍历节点和路径代价也更少,验证了算法的有效性。

英文摘要:

In the application process of A* algorithm and its improvement algorithm, the obtained paths often have problems such as node redundancy, more turning points and longer search time, etc. In order to improve the search efficiency of A* algorithm in the application process and ensure the optimality of the paths, the article proposes an optimized A* algorithm based on two-way search, which uses the current nodes of forward and reverse search as each other''s target points for two-way mutual search. Firstly, for the problem of cost function degradation, weighted Manhattan is introduced as the distance heuristic function, and the weight ratio inside the cost function is dynamically adjusted to ensure the real-time performance of the algorithm when searching and the superiority of the obtained paths. Second, to address the problem of local path optimality and deviation from the global optimal path in the two-way path search process, deviation from the optimal distance is added as the cost factor in the heuristic function to introduce the consideration of the global optimum in the search process. The experimental results show that the optimized algorithm has higher search efficiency and less cost of traversing nodes and paths, which verifies the effectiveness of the algorithm.

View Fulltext 查看/发表评论下载PDF阅读器

关闭