DCPCBS: A Scalable Dynamically Prioritized Framework for Optimal Multi Agent Pathfinding

Conflict Based Search(CBS) is one of the best-known methods to solve MAPF optimally. Its performance, however, degrades in large scale instances because it involves sequential high-level search and uninformed conflict resolution. In this work, we present the DCPCBS (Dynamically Conflict Prioritized CBS) algorithm with three enhancements to CBS that are intended to enhance scalability and runtime performance without compromising on completeness and optimality. First, we augment CBS with earliest-k conflict detection to allow the algorithm to detect and consider several early conflicts per node and branch on the most important one. Second, we add a conflict prioritization component that gives a dynamic criticality score to each conflict based on frequency of occurrence, proximity to agent goals in space, and proximity to temporal objectives, and direct the search towards the most influential conflicts. Third, we introduce parallel constraint tree (CT) expansion via multi-core processing and adaptive batching, enabling simultaneous resolution of multiple CT nodes to speed up search. All these improvements result in dramatic runtime and node expansions reductions without any degradation of solution quality. We experimentally validate our approach on challenging grid environments with high-density agent populations and show improved scalability.