Conflict-Based Search with Partitioned Groups of Agents for Real-World Scenarios

摘要

Multi-agent pathfinding (MAPF) is the problem of planning optimal paths for a group of agents without conflict. Because of the high computational complexity of MAPF, several powerful techniques have been developed to reduce the runtime under assumptions, such as the ideal kinematics of point-like agents and a discretized time domain. However, these assumptions restrict the applicability of the MAPF algorithms to real-world scenarios. Continuous-time conflict-based search (CCBS), a variant of CBS, was recently proposed to generalize MAPF problems to continuous-time and non-grid domains. In this study, we propose CCBS with partitioned groups of agents (CCBS-PGA), a hybrid approach that uses CCBS as the main MAPF solver and adopts the idea of prioritized planning (PP) for enhanced scalability. CCBS-PGA runs CCBS for each group of the partitioned agents and assigns unique priorities to the individual group. We also introduce two features that reflect realistic robot kinematics; rotational velocities of robots and safety distances. This approach does not rely on the simplified assumptions while alleviating the computational complexity of MAPF problems involving numerous agents. We demonstrate its effectiveness in various environments using differential-wheeled robots.