  Multi-Agent Path Finding (MAPF) is the problem of finding collision-free
paths for multiple agents from their start locations to end locations. We
consider an extension to this problem, Precedence Constrained Multi-Agent Path
Finding (PC-MAPF), wherein agents are assigned a sequence of planning tasks
that contain precedence constraints between them. PC-MAPF has various
applications, for example in multi-agent pickup and delivery problems where
some objects might require multiple agents to collaboratively pickup and move
them in unison. Precedence constraints also arise in warehouse assembly
problems where before a manufacturing task can begin, its input resources must
be manufactured and delivered. We propose a novel algorithm, Precedence
Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal
solutions for this class of problems. PC-CBS utilizes a Precedence-Constrained
Task-Graph to define valid intervals for each planning task and updates them
when precedence conflicts are encountered. We benchmark the performance of this
algorithm over various warehouse assembly, and multi-agent pickup and delivery
tasks, and use it to evaluate the sub-optimality of a recently proposed
efficient baseline.
