Using Hierarchical Constraints to Avoid Conflicts in Multi-Agent Pathfinding

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.

Authors

• Thayne T. Walker
• David M. Chan
• Nathan R. Sturtevant

Keywords

No keywords are indexed for this paper.