Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT)

In this paper, we propose a novel methodology for path planning and scheduling for multi-robot navigation that is based on optimal transport theory and model predictive control. We consider a setup where $N$ robots are tasked to navigate to $M$ targets in a common space with obstacles. Mapping robots to targets first and then planning paths can result in overlapping paths that lead to deadlocks. We derive a strategy based on optimal transport that not only provides minimum cost paths from robots to targets but also guarantees non-overlapping trajectories. We achieve this by discretizing the space of interest into $K$ cells and by imposing a $K\times K$ cost structure that describes the cost of transitioning from one cell to another. Optimal transport then provides $\mathit{\text{optimal}}\mathit{\text{and}}\mathit{\text{non-overlapping}}$ cell transitions for the robots to reach the targets that can be readily deployed without any scheduling considerations. The proposed solution requires $\text{unicode}x1D4AA(K^3\log K)$ computations in the worst-case and $\text{unicode}x1D4AA(K^2\log K)$ for well-behaved problems. To further accommodate potentially overlapping trajectories (unavoidable in certain situations) as well as robot dynamics, we show that a temporal structure can be integrated into optimal transport with the help of $\mathit{\text{replans}}$ and $\mathit{\text{model}}\mathit{\text{predictive}}\mathit{\text{control}}$.