Hostile, Compatible, or Free: A constant time classification of pairwise shortest path conflicts in obstacle-free MAPF

A fundamental challenge in Multi-Agent Pathfinding (MAPF) is managing conflicts among agents following their shortest paths. While some conflicts can be resolved by switching to alternative shortest paths, others are intrinsic, requiring at least one agent to deviate to a longer, suboptimal path, thereby increasing the total cost. This paper presents a formal, analytical methodology for classifying the intrinsic conflict relationship between any two agents in obstacle-free grid environments. We propose a ternary classification, partitioning pairwise relationships into three exhaustive types: Hostile , where a conflict is inevitable for all shortest path pairs; Free , where no conflict occurs for any pair; and Compatible , which admits both conflicting and conflict-free path pairs. We establish the theoretical soundness of this classification through rigorous mathematical proofs, leading directly to a constant-time (O(1)) classification algorithm. This algorithm uses only agent coordinates, entirely bypassing the combinatorial explosion of exhaustively checking all path pairs. Empirically, we validate our method’s utility by integrating the classifier as an advanced heuristic into the leading LaCAM3 solver. Experimental results reveal a clear trade-off: our heuristic incurs a higher computational cost per decision but guides the search so effectively that its initial solution often surpasses the baseline’s final solution, ultimately yielding a significantly lower sum of costs with fewer node expansions. This work provides a fast, provably correct, and empirically validated framework for analyzing the intrinsic agent relationships in MAPF problems, establishing a theoretical foundation for designing more efficient and informed MAPF heuristics.