平滑ARA*算法在智能车辆路径规划的应用

摘要

A*算法是一种经典的启发式搜索算法,广泛应用于智能车辆的路径规划问题.但A*算法效率低,不具有实时性.针对A*算法的缺点,改进得到一种高效、实时的路径搜索算法ARA*,ARA*算法首先在一个松弛的约束条件下快速搜索到一条次优路径;然后在规划时间内逐渐加强约束条件,利用已搜索过的节点信息连续改进次优解,直到找到最优解或规划时间结束.其次,针对ARA*算法得到的路径存在折线多、转折次数多等问题,对ARA*算法得到的路径进行基于关键点的平滑处理.给出了平滑ARA*算法流程,分析对比了各自的特点,通过栅格地图路径规划的MATLAB仿真结果验证了理论分析,同时仿真结果也说明平滑ARA*算法的高效性、实时性.%A* algorithm is a classical heuristic search algorithm,which is widely used in the path planning of intelligent vehicles.However,the efficiency of A * algorithm is low,and also it has no real time performance.Anytime repairing A* (ARA *),an efficient and real-time path searching algorithm,can solve the shortcoming of the A * algorithm.First,ARA* algorithm searches the suboptimal path in a relaxed constraint condition.Then,within the planning time,the constraint condition is gradually enhanced,and the solution is improved by using the information that has been searched until the optimal solution is found or planning time is run out.Next,because the path planned by ARA* algorithm is flaw with much broken lines,frequently turning points,we give a smooth method based on key points to make the path smoothly.The flow of smoothing ARA * algorithm is given,meanwhile,analyzing and comparing their respective characteristics.The theoretical analysis is verified by Matlab simulation results of path planning in the grid map.The simulation results also show that the smoothing ARA * algorithm is efficient and real-time.