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

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

作　　者：张俊林 贾兵 聂玲 石冬阳 ZHANG Junlin;JIA Bing;NIE Ling;SHI Dongyang(School of Electronic and Electrical Engineering,Chongqing University of Science and Technology,Chongqing 401331,China)

机构地区：[1]重庆科技大学电子与电气工程学院,重庆401331

出　　处：《重庆科技大学学报（自然科学版）》2024年第4期89-97,共9页Journal of Chongqing University of Science and Technology(Natural Sciences Edition)

基　　金：重庆市科技局自然科学基金项目“基于操作行为的驾驶人疲劳特征学习方法研究”(CSTC2020JCYJ-MSXMX0927)。

摘　　要：为了提高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.

关 键 词：A^(*)算法 双向搜索策略 偏离最优距离 动态加权 路径规划 

分 类 号：TM85[电气工程—高电压与绝缘技术]