大规模AGV的改进时间窗路径规划

Improved time window path planning for large-scale AGV

在机器人路径规划中,A^(*)算法搜索路径时存在大量冗余节点,随着任务量增加,其搜索效率也会急剧下降,因此无法适应大规模任务下的路径规划。为此提出一种改进时间窗的有界次优A^(*)算法用于求解大规模自动导引车(automatic guided vehicle,AGV)路径规划问题。算法使用时间启发式,并在搜索过程中采用时空搜索,规划无冲突的最优或次优路径。算法主要进行了三处改进:采用时间启发式,缩短了路径时间;采用动态时间窗算法,避免多次路径规划;优化了聚焦搜索算子,降低负反馈。通过MATLAB实验结果证明改进后的算法在进行多机器人路径规划时,能快速有效地规划出无冲突的平滑次优路径,搜索效率高,稳定性强。

In robot path planning,A^(*)algorithm has a large number of redundant nodes when searching paths.With the increase of tasks,its search efficiency will decrease sharply,so it cannot adapt to path planning under large-scale tasks.Therefore,this paper proposed an improved time-window bounded suboptimal A^(*)algorithm to solve the path planning problem of large-scale AGV.The algorithm used time heuristic and spatio-temporal search in the search process to plan the optimal or suboptimal path without conflict.The algorithm mainly has three improvements.This paper used time heuristic to shorten the path time.This algorithm adopted dynamic time window algorithm to avoid multiple path planning.This paper optimized the focal search operator to reduce negative feedback.MATLAB experimental results show that the improved algorithm can plan a smooth suboptimal path quickly and effectively without conflicts when multi-robot path planning,with high search efficiency and strong stability.