{"ID":2877369,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.21205","arxiv_id":"2508.21205","title":"Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT)","abstract":"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 \\textit{optimal 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 $\\unicode{x1D4AA}(K^3\\log K)$ computations in the worst-case and $\\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 \\textit{replans} and \\textit{model predictive control}.","short_abstract":"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 a...","url_abs":"https://arxiv.org/abs/2508.21205","url_pdf":"https://arxiv.org/pdf/2508.21205v1","authors":"[\"Usman A. Khan\",\"Mouhacine Benosman\",\"Wenliang Liu\",\"Federico Pecora\",\"Joseph W. Durham\"]","published":"2025-08-28T20:47:33Z","proceeding":"cs.RO","tasks":"[\"cs.RO\",\"cs.LG\"]","methods":"[]","has_code":false}