AnyGeometry-CBS: Any Geometry Conflict-Based Search for Multi-Agent Path Finding

Abstract

The Multi-Agent Path Finding (MAPF) problem seeks to find conflict-free paths for multiple agents. However, most existing MAPF methods simplify agents to points or uniform circles, a model that fails when agents have diverse geometries or carry oversized loads. This oversimplification can lead to undetected collisions or the failure to find feasible paths. To address this, we propose AnyGeometry-CBS (AG-CBS), a novel extension of Conflict-Based Search (CBS) that accommodates agents of arbitrary, non-convex shapes. AG-CBS represents each geometry of agent via a set of grid cells and introduces enriched conflict definitions to handle complex interactions. To improve search efficiency, we develop a Multi-Constraint (MC) technique and a Shape Heuristic (SH) for suboptimal variants. Experimental results demonstrate that our method reduces runtime by up to 84.43% against optimal baselines and 88.24% against bounded-suboptimal ones, providing a general and effective solution to complex MAPF problems.