Search papers, labs, and topics across Lattice.
This paper re-evaluates the node-selection strategy in Conflict-Based Search (CBS) for Multi-Agent Path Finding (MAPF) by introducing Dual-Informed Vertical Expansion (DIVE), a novel policy that optimizes the balance between dive efficiency and depth-oriented exploration. DIVE enhances performance by starting dives from the best-bound frontier, pruning unproductive paths, and maintaining parent-child locality, which collectively lead to fewer dive breaks and reduced memory usage compared to traditional best-first search. Experimental results demonstrate that DIVE not only provides early incumbent solutions with certified gaps but also significantly improves memory efficiency while preserving the exactness of the CBS algorithm.
DIVE redefines node selection in CBS, achieving dive efficiency and early incumbents while slashing memory usage compared to conventional methods.
Conflict-Based Search (CBS) is a leading exact algorithm for Multi-Agent Path Finding (MAPF), but its high-level node-selection rule is usually treated as a fixed implementation detail. Standard best-first selection is strong for minimizing expanded nodes and closing the optimality certificate, yet it can maintain a large frontier, interrupt parent-child expansion sequences, and provide no feasible incumbent until termination. This paper studies node selection as a first-class design choice for exact CBS. We introduce Dual-Informed Vertical Expansion (DIVE), a policy that is best-bound between dives and depth-oriented within a dive. DIVE starts each dive from the current best-bound frontier, follows promising children to exploit parent-child locality, and uses incumbent pruning to limit unproductive excursions. We formalize CBS node selection through a branch-and-bound view, prove that the traversal policy can be changed without affecting exactness, and analyze the resulting trade-offs among expanded nodes, dive breaks, queue size, and primal-dual bound progress. The analysis predicts three complementary extremes. Best-first search is node efficient, iterative deepening is memory efficient, and DIVE is dive efficient while retaining regular best-bound reanchoring. Experiments on standard MAPF benchmarks support this trade-off map. DIVE consistently reduces dive breaks, provides early incumbents with certified gaps, uses substantially less queue memory than best-first search, and benefits from warm starts and simple responsive variants in dense or memory-limited regimes.
