In the Multi-Agent Path Finding (MAPF) problem, a set of agents moving on a graph must
reach their own respective destinations without inter-agent collisions. In practical MAPF
applications such as navigation in automated warehouses, where occasionally there are
hundreds or more agents, MAPF must be solved iteratively online on a lifelong basis. Such
scenarios rule out simple adaptations of offline compute-intensive optimal approaches; and
scalable sub-optimal algorithms are hence appealing for such settings. Ideal algorithms
are scalable, applicable to iterative scenarios, and output plausible solutions in predictable
computation time.
For the aforementioned purpose, this study presents Priority Inheritance with Backtracking
(PIBT), a novel sub-optimal algorithm to solve MAPF iteratively. PIBT relies on an adaptive
prioritization scheme to focus on the adjacent movements of multiple agents; hence it
can be applied to several domains. 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 (e.g., biconnected).
Experimental results covering various scenarios, including a demonstration with real
robots, reveal the benefits of the proposed method. Even with hundreds of agents, PIBT
yields acceptable solutions almost immediately and can solve large instances that other
established MAPF methods cannot. In addition, PIBT outperforms an existing approach on
an iterative scenario of conveying packages in an automated warehouse in both runtime
and solution quality.
各種検索
サポート
ヘルプ