Multi-Agent Path Finding With Velocity Profile and Rotation Cost

This paper presents Continuous-time Conflict-Based Search with Velocity Profile and Rotation Cost (CCBS-VP-RC) for multi-agent path finding under kinematic constraints. Continuous-time Conflict-Based Search (CCBS) is a two-level algorithm that resolves agent conflicts through constraint generation in continuous time domains. However, CCBS does not consider real-world kinematic constraints such as velocity profiles, angular velocity limits, or a rotation cost matrix for differential drive robots. The rotation cost matrix precomputes the rotation time for all heading transitions, enabling efficient cost retrieval during path planning. The CCBS-VP-RC integrates velocity profiles with rotation costs to generate physically feasible trajectories that satisfy kinematic bounds. Simulations were conducted on grid-based environments with varying obstacle densities and agent populations. Compared to traditional Multi-Agent Path Finding (MAPF) algorithms, the CCBS-VP-RC has slightly longer makespan and flowtime due to kinematic constraints. Nevertheless, the proposed method achieves higher success rates in complex environments, demonstrating its effectiveness for practical multi-robot systems operating under real-world kinematic constraints.