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× K cost structure that describes the cost of transitioning from one cell to another. Optimal transport then provides textitoptimal and non-overlapping cell transitions for the robots to reach the targets that can be readily deployed without any scheduling considerations. The proposed solution requires unicodex1D4AA(K3log K) computations in the worst-case and unicodex1D4AA(K2log 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 textitreplans and textitmodel predictive control.