Conflict-Based Search for Multi-Robot Path Planning Using Optimal Motion Primitives

Abstract

This work presents a two-level path planning approach for multi-robot systems considering kinematic constraints. Classical search-based methods for multi-robot path planning simplify robot models, making it difficult to directly apply the obtained paths. To tackle this problem, we combine the enhanced conflict-based search (E-CBS) with the optimal motion primitive (OMP). Firstly, a series of motion primitives containing multiple waypoints are generated using nonlinear programming (NLP) offline. Then the high-level planner conducts focal conflict search over OMPs. To further accelerate the solving process, a conflict merging strategy is conducted. The low-level planner adopts a focal spatiotemporal A* algorithm with OMPs to generate a collision-free path with consideration of high-level constraints. Finally, we implement simulations to verify the effectiveness of the proposed algorithm. The simulation results show that techniques used in our approach can effectively improve the efficiency of path planning.