CB-BSH: Multi-Agent Motion Planning With Heterogeneous Kinematics and Geometric Envelopes

This letter addresses the collision-free planning problem for heterogeneous multi-agent systems. Heterogeneity primarily refers to two aspects: differences in geometric configurations and variations in kinematic models. For non-point-mass agent models, it is essential to consider both geometric constraints arising from their physical dimensions and kinematic constraints. The proposed planning algorithm is an improvement upon the Conflict-Based Search (CBS) framework, consisting of high-level conflict detection and low-level single-agent path planning. The low-level planner employs a bidirectional space-time Hybrid A* algorithm (BSH) to accommodate the requirements of different kinematic models. The high-level planner introduces the concept of geometric envelopes to design conflict detection and constraint resolution methods in continuous space, effectively handling collision detection and conflict resolution among heterogeneous agents. To alleviate the computational burden caused by the high dimensionality of the search tree in CBS-like algorithms, a heuristic high-level node selection strategy is also proposed. Experimental results demonstrate that, compared to priority-based planning methods, the proposed approach yields more cost-effective planning solutions but more computational overhead while exhibiting an efficiency-optimality trade-off.