Abstract
The Multi-agent Path Finding (MAPF) problem
consists in all agents having to move to their own
destinations while avoiding collisions. In practical
applications to the problem, such as for navigation
in an automated warehouse, MAPF must be solved
iteratively. We present here a novel approach to iterative MAPF, that we call Priority Inheritance with
Backtracking (PIBT). PIBT gives a unique priority
to each agent every timestep, so that all movements
are prioritized. Priority inheritance, which aims at
dealing effectively with priority inversion in path
adjustment within a small time window, can be applied iteratively and a backtracking protocol prevents agents from being stuck. We prove that, regardless of their number, all agents are guaranteed
to reach their destination within finite time, when
the environment is a graph such that all pairs of adjacent nodes belong to a simple cycle of length 3
or more (e.g., biconnected). Our implementation
of PIBT can be fully decentralized without global
communication. Experimental results over various scenarios confirm that PIBT is adequate both
for finding paths in large environments with many
agents, as well as for conveying packages in an automated warehouse