CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spatiotemporal Constraints.

摘要: Multi-Agent Path Finding has been widely studied in the past few years due to its broad application field of robotics and AI. However, previous solvers rely on several simplifying assumptions. They limit their applicability numerous real-world domains that adopt nonholonomic car-like agents rather than holonomic ones. In this paper, we give a mathematical formalization for Car-Like robots (CL-MAPF) problem. For first time, propose novel hierarchical search-based solver called Car-like Conflict-Based Search address It applies body conflict tree collisions considering shapes agents. We introduce new algorithm Spatiotemporal Hybrid-State A* as single-agent path planner generate satisfying both kinematic spatiotemporal constraints. also present sequential planning version our method sake efficiency. compare with two baseline algorithms dedicated benchmark containing 3000 instances validate it scenarios. The experiment results clear evidence scales well large number is able produce solutions can be directly applied real world. source code are released https://github.com/APRIL-ZJU/CL-CBS.