应用于机器人路径规划的双向时效A*算法

Bidirectional time-efficient A* algorithm for robot path planning

针对时效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.