Using Hierarchical Constraints to Avoid Conflicts in Multi-Agent Pathfinding

Abstract

Recent work in multi-agent path planning has provided a number of optimal and suboptimal solvers that can efficiently find solutions to problems of growing complexity. Solvers based on Conflict-Based Search (CBS) combine single-agent solvers with shared constraints between agents to find feasible solutions. Suboptimal variants of CBS introduce alternate heuristics to avoid conflicts. In this paper we study the multi-agent planning problem in the context of non-holonomic vehicles planning on a lattice. We propose that in addition to using heuristics to avoid conflicts, we can plan using a hierarchy of movement constraints to efficiently avoid conflicts. We develop a new extension to the CBS algorithm, CBS with constraint layering (CBS+CL), which iteratively applies different movement constraint models during the CBS planning process. Our results show that this approach allows us to solve for about 2.4 times more agents in the same amount of time when compared to regular CBS without using a constraint hierarchy.