Iterative Refinement
for Real-Time Multi-Robot Path Planning

Keisuke Okumura, Yasumasa Tamura and Xavier Défago

[conference paper (IROS-21)] [preprint (arXiv)] [code (GitHub)]

Overview

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.

News

  • Upload the slide. (Oct. 2021)
  • This paper has been accepted to IROS-21! (Jul. 2021)

Video

Slides

Citation

@inproceedings{okumura2021iterative,
  author={Okumura, Keisuke and Tamura, Yasumasa and Défago, Xavier},
  booktitle={2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
  title={Iterative Refinement for Real-Time Multi-Robot Path Planning},
  year={2021},
  pages={9690-9697},
  doi={10.1109/IROS51168.2021.9636071}
}

Contact

okumura.k [at] coord.c.titech.ac.jp