AnyGeometry-CBS: Any Geometry Conflict-Based Search for Multi-Agent Path Finding
Yichen Li, Xuebo Zhang, Jingjin Yu, Yaonan Wang
AI summary
Problem
Existing MAPF solvers oversimplify agents as points or uniform circles, failing to handle diverse geometries, oversized loads, or rotation, which leads to undetected collisions or infeasible paths.
Approach
The method models agents as sets of grid cells to capture arbitrary shapes and rotation, introduces enriched shape conflict definitions, and adds a Multi-Constraint technique and Shape Heuristic to accelerate search.
Key results
- Supports arbitrarily shaped, rotating agents with new shape conflict types.
- Proactively resolves future shape conflicts via a Multi-Constraint method.
- Guides suboptimal search using a Shape Heuristic based on geometric complexity.
- Cuts runtime by up to 84.43% against optimal baselines and 88.24% against suboptimal ones.
Why it matters
Provides a scalable, optimal framework for real-world robotic automation and logistics where agents have complex, non-uniform physical profiles.
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 base- lines and 88.24% against bounded-suboptimal ones, providing a general and effective solution to complex MAPF problems.