Multi-agent path finding with kinematic constraints via conflict based search

The paper considers a problem of planning a set of collision-free trajectories for a group of mobile agents operating in the shared environment, i.e. multi-agent path-finding (MAPF). A modification of the Continuous Conflict Based Search (CCBS) algorithm is proposed that takes kinematic constraints into account. The resultant planner explicitly supports rotation actions as well as agents of different sizes and moving speeds. Thus, it is more suitable for a range of practical applications involving real robots subject to kinematic constraints. An extensive empirical evaluation is conducted in which the suggested algorithm is compared to the state-of-the-art MAPF planners. The results of this evaluation provide a clear evidence that the proposed method is as efficient as predecessor that is limited to translation-only action model. © Springer Nature Switzerland AG 2020.