Hierarchical Search-Based Cooperative Motion Planning

Cooperative path planning, a crucial aspect of multi-agent systems research, serves a variety of sectors, including military, agriculture, and industry. Many existing algorithms, however, come with certain limitations, such as sim- plified kinematic models and inadequate support for multiple group scenarios. Focusing on the planning problem associated with a nonholonomic Ackermann model for Unmanned Ground Vehicles (UGV), we propose a leaderless, hierarchical Search- Based Cooperative Motion Planning (SCMP) method. The high- level utilizes a binary conflict search tree to minimize runtime, while the low-level fabricates kinematically feasible, collision- free paths that are shape-constrained. Our algorithm can adapt to scenarios featuring multiple groups with different shapes, outlier agents, and elaborate obstacles. We conduct algorithm comparisons, performance testing, simulation, and real-world testing, verifying the effectiveness and applicability of our algorithm. The implementation of our method will be open- sourced at https://github.com/WYCUniverStar/SCMP.