Extending Conflict-Based Search for Optimal and Efficient Quadrotor Swarm Motion Planning

Multi-agent pathfinding has been extensively studied in the robotics and artificial intelligence communities. The classical algorithm, Conflict-Based Search(CBS), is widely used in various real-world applications due to its ability to solve large-scale conflict-free paths. However, classical CBS assumes discrete time-space planning and overlooks physical constraints in actual scenarios, making it unsuitable for direct application in Unmanned Aerial Vehicle(UAV) swarm. Inspired by the decentralized planning and centralized conflict resolution ideas of CBS, we propose an optimal and efficient UAV swarm motion planner that integrates State Lattice with CBS, named SL-CBS. SL-CBS is a two-layer search algorithm: (1) The low-level search utilizes an improved State Lattice. We design emergency stop motion primitives to ensure complete UAV dynamics and handle spatio-temporal constraints from high-level conflicts. (2) The high-level algorithm defines comprehensive conflict types and proposes a motion primitive conflict detection method with linear-time complexity based on Sturm’s theory. Additionally, our modified Independence Detection(ID) technique is applied to enable parallel conflict processing. We validate the planning capabilities of SL-CBS in classical scenarios and compare it with State-Of-The-Art(SOTA) algorithms, showing great improvements in success rate, computation time, and flight time. Finally, we conduct large-scale tests to analyze the performance boundaries of SL-CBS+ID.