Conflict-Based Model Predictive Control for Scalable Multi-Robot Motion Planning

This paper presents a scalable multi-robot motion planning algorithm called Conflict-Based Model Predictive Control (CB-MPC). Inspired by Conflict-Based Search (CBS), the planner leverages a modified high-level conflict tree to efficiently resolve robot-robot conflicts in the continuous space, while reasoning about each agent’s kinematic and dynamic constraints and actuation limits using MPC as the low-level planner. We show that tracking high-level multi-robot plans with a vanilla MPC controller is insufficient, and results in unexpected collisions in tight navigation scenarios under realistic execution. Compared to other variations of multi-robot MPC like joint, prioritized, and distributed, we demonstrate that CB-MPC improves the executability and success rate, allows for closer robot-robot interactions, and scales better with higher numbers of robots without compromising the solution quality across a variety of environments.