Iterative Refinement for Real-Time Multi-Robot Path Planning
Iterative Refinement for Real-Time Multi-Robot Path Planning
复制标题
DOI：
10.1109/iros51168.2021.9636071
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Keisuke Okumura;Yasumasa Tamura;X. Défago
中科院分区：
文献类型：
--
作者：
Keisuke Okumura;Yasumasa Tamura;X. Défago
研究了多机器人路径规划的迭代求精方法，即多智能体寻路算法(MAPF)。给定一个图、代理、它们的初始位置和目的地，MAPF的解决方案是一组没有冲突的路径。MAPF的迭代求精是可取的，原因有三：1)优化是棘手的，2)次最优解可以立即得到，3)它是随时随地规划，在考虑时间有限的在线场景中是理想的。尽管需求很高，但MAPF对此的探索不足，因为到目前为止，找到好的社区还不清楚。该算法使用次优MAPF求解器快速得到初始解，然后迭代两个过程：1)选择一个智能体子集，2)使用一个最优MAPF求解器在保持其他路径不变的情况下对所选智能体的路径进行精化。由于最优解算器用于问题的小实例，因此该方案在提供高可伸缩性的同时，快速地产生足够有效的解。我们还就如何选择智能体的子集提出了合理的候选人。在各种场景中的评估表明，该方案前景看好，收敛速度快，可扩展，质量合理。
We study the iterative refinement of path planning for multiple robots, known as multi-agent pathfinding (MAPF). Given a graph, agents, their initial locations, and destinations, a solution of MAPF is a set of paths without collisions. Iterative refinement for MAPF is desirable for three reasons: 1) optimization is intractable, 2) sub-optimal solutions can be obtained instantly, and 3) it is anytime planning, desired in online scenarios where time for deliberation is limited. Despite the high demand, this is under-explored in MAPF because finding good neighborhoods has been unclear so far. Our proposal uses a sub-optimal MAPF solver to obtain an initial solution quickly, then iterates the two procedures: 1) select a subset of agents, 2) use an optimal MAPF solver to refine paths of selected agents while keeping other paths unchanged. Since the optimal solvers are used on small instances of the problem, this scheme yields efficient-enough solutions rapidly while providing high scalability. We also present reasonable candidates on how to select a subset of agents. Evaluations in various scenarios show that the proposal is promising; the convergence is fast, scalable, and with reasonable quality.