Multi-Agent Path Finding With Heterogeneous Geometric and Kinematic Constraints in Continuous Space

Abstract

Multi-Agent Path Finding (MAPF) represents a pivotal area of research within multi-agent systems. Existing algorithms typically discretize the movement space of agents into grid or topology, neglecting agents' geometric characteristics and kinematic constraints. This limitation hampers their applicability and efficiency in practical industrial scenarios. In this paper, we propose a Priority-Based Search algorithm for heterogeneous mobile robots working in continuous space, addressing both geometric and kinematic constraints. This algorithm, named Continuous-space Heterogeneous Priority-Based Search (CHPBS), employs a two-level search structure and a priority tree for collision detection. To expedite single-agent path finding in continuous space, we introduce a Weighted Hybrid Safe Interval Path Planning algorithm (WHSIPP<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$_{d}$</tex-math></inline-formula>). Furthermore, we present three strategies to enhance our algorithm, collectively termed Enhanced-CHPBS (ECHPBS): Partial Expansion, Target Reasoning, and Adaptive Induced Priority. Comparative analysis against two baseline algorithms on a specialized benchmark demonstrates that ECHPBS achieves a success rate of 100% on a 100 m × 100 m map featuring 50 agents, with an average runtime of under 1 s, and maintains the same 100% success rate on a 300 m × 300 m map with 100 agents.