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.

I. Introduction

In order to unlock the potential of robots in real-world applications, they often need to be deployed in numbers performing multiple tasks. These applications include picking and replenishment in warehouse fulfillment, environmental monitoring, coordinated search and rescue, material handling in hospitals, assembly operations in manufacturing, and more. Enabling such applications for multi-robot systems requires generating scalable and executable motion plans that operate in continuous time. In addition, these plans must reason about robot-robot and robot-environment constraints, be adaptable to online changes, and respect the robot kinematics, dynamics, and actuation limits.