A~＊路径规划算法的改进及实现

Improvement and Implementation of A~＊ Path Planning Algorithm

针对A*算法在路径规划过程中因遍历节点多而导致搜索时间长和路径规划距离长的问题,对A*算法进行了改进.改进算法采用两点间的欧氏距离作为估价函数,并以前向搜索和后向搜索交替进行的方式来减少路径规划时间.仿真结果表明,改进算法在搜索时间和距离上分别比A*算法减少了0.0184s和42m,在搜索得到的路径长度和算法运行时间上明显优于A*算法.

For the problem of long searching time and long distance path planning caused by much more traversal nodes in the A＊ algorithm path planning process,the improved A＊ algorithm is presented in this paper.The improved algorithm adopts the Euclidean distance between two points as appraisal function,and makes forward search and backward search alternately to reduce path planning time.The simulation results show that the search time and distance of the improved algorithm are 0.0184 s and 42 m respectively,which are obviously better than A＊ algorithm in search length and running time.