摘要
针对时效A*算法为了大幅减少算法时间,导致路径规划长度增加和路径锯齿过多的问题,提出一种改进的双向时效A*算法,该方法从起点和终点同时运行时效A*算法寻找路径,并采用多近邻栅格距离计算方案;同时,根据不同环境地图对传统A*算法、时效A*算法和双向时效A*算法运行结果进行对比研究及分析;最后,制定算法时间、路径长度两个指标来评判算法的优劣。实验结果显示,双向时效A*算法相对于传统A*算法,算法时间最大减少76. 8%,相对于时效A*算法,时间最大减少55. 4%,并解决了时效A*算法规划路径距离增加、路径不够平滑的问题。
As for the tme-efficient A*algorithm significantly reduces the algorithm time,lead to the problem of increase path planning length and path sawtooth.This paper proposed an improved bidirectional time-efficient A*algorithm,which ran the A*algorithm from the start and the end point to find the path and applied the multiple neighbor grid distance computation scheme.At the same time,according to different environment map,this paper compared and analyzed the A*algorithm,time-efficient A*algorithm and bidirectional time-efficient A*algorithm.Finally,it chose the index of algorithm time and path length as two indicators to evaluate the merits and demerits of the algorithm.Experimental results show that compared with traditional A*algorithm,the bidirectional time-efficient A*decreases the time of the algorithm by 76.8%at the maximum,and reduces the maximum time by 55.4%compared with time-efficient A*algorithm.It also solves the problem that the path distance of the time-efficient A*algorithm is augmented and the path is not smooth enough.
作者
高民东
张雅妮
朱凌云
Gao Mindong;Zhang Yani;Zhu Lingyun(College of Computer Science&Engineering,Chongqing University of Technology,Chongqing 400054,China)
出处
《计算机应用研究》
CSCD
北大核心
2019年第3期792-795,800,共5页
Application Research of Computers
基金
国家自然科学基金资助项目(61502064)
重庆市教委科学技术研究项目(KJ1709206)
重庆理工大学研究生创新基金资助项目(YCX2016228)
关键词
路径规划
启发式算法
时效A*算法
path planning
heuristic algorithm
time-efficient A*algorithm