Multi-Agent Path Finding for Precedence-Constrained Goal Sequences
Abstract
With the rising demand for deploying robot teams in autonomous warehouses and factories, the Multi-Agent Path Finding (MAPF) problem has drawn more and more attention. The classical MAPF problem and most of its variants focus on navigating agent teams to goal locations while avoiding collisions. However, they do not take into account any precedence constraints that agents should respect when reaching their goal locations. Planning with precedence constraints is important for real-world multi-agent systems. For example, a mobile robot can only pick up a package at a station after it has been delivered by another robot. In this paper, we study the Multi-Agent Path Finding with Precedence Constraints (MAPF-PC) problem, in which agents need to visit sequences of goal locations while satisfying precedence constraints between the goal locations. We propose two algorithms for solving this problem systematically: Conflict-Based Search with Precedence Constraints (CBS-PC) is complete and optimal, and Priority-Based Search with Precedence Constraints (PBS-PC) is incomplete but more efficient in finding near-optimal solutions in practice. Our experimental results show that CBS-PC scales to dozens of agents and hundreds of goal locations and precedence constraints, and PBS-PC scales to hundreds of agents, around one thousand goal locations, and hundreds of precedence constraints.
BibTeX
@conference{Zhang-2022-131387,author = {Han Zhang and Jingkai Chen and Jiaoyang Li and Brian Williams and Sven Koenig},
title = {Multi-Agent Path Finding for Precedence-Constrained Goal Sequences},
booktitle = {Proceedings of 21th International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS '22)},
year = {2022},
month = {May},
}