  We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing
prioritized MAPF algorithms depend on rule-of-thumb heuristics and random
assignment to determine a fixed total priority ordering of all agents a priori.
We instead explore the space of all possible partial priority orderings as part
of a novel systematic and conflict-driven combinatorial search framework. In a
variety of empirical comparisons, we demonstrate state-of-the-art solution
qualities and success rates, often with similar runtimes to existing
algorithms. We also develop new theoretical results that explore the
limitations of prioritized planning, in terms of completeness and optimality,
for the first time.
