In-Depth Cluster Conflict-Based Search for Multi-Agent Path Finding

This paper addresses a variant of the conflict-based search (CBS) algorithm for multi-agent path finding, presenting an effective cluster reasoning heuristic that searches for and detects conflicts involving more than two agents. The proposed in-depth cluster reasoning technique systematically alters the reference agent when computing the heuristic cost-to-go, and this yields a tighter estimate. It then balances the complexity of expanding CBS nodes against that of locating clusters by systematically scheduling the associated parameters. Numerical experiments demonstrate that the proposed algorithm successfully detects clusters that state-of-the-art algorithms cannot identify and produces solutions for various extreme scenarios that existing algorithms cannot solve.