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

• URL: http://arxiv.org/abs/2508.21205v1
• Date: Thu, 28 Aug 2025 20:47:33 GMT
• Title: Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT)
• Authors: Usman A. Khan, Mouhacine Benosman, Wenliang Liu, Federico Pecora, Joseph W. Durham,
• Abstract summary: We consider a setup where $M robots are tasked to navigate to $M targets in a common space with deadlock obstacles.<n>We derive a strategy based on optimal plannings and guarantee non-overlapping trajectories.<n>We show that a temporal structure can be integrated into optimal transport with the help of textitremodelplans and textitremodelplans as predictive.
• Score: 5.013737017051114
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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}.

Related papers

• Semantic Intelligence: Integrating GPT-4 with A Planning in Low-Cost Robotics [8.943924354248622]
  We present a framework that integrates GPT-4's semantic reasoning with A* on a low-cost robot platform operating on ROS2 Humble.<n>We demonstrate multi-step reasoning for sequential tasks, such as first navigating to a resource goal and then reaching a final destination safely.<n>Results show that while A* is faster and more accurate for basic route generation and obstacle avoidance, the GPT-4-integrated system achieves high success rates (96-100%) on semantic tasks that are infeasible for pure geometric planners.
  arXiv  Detail & Related papers  (2025-05-03T21:49:14Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  Optimal transport (OT) theory provides a principled framework for constructing such mappings.<n>We propose a novel solver based on Wasserstein-1 ($W$) dual formulation.<n>Our experiments demonstrate that the proposed $W$ neural optimal transport solver can mimic the $W$ OT in finding a unique and mon" map.
  arXiv  Detail & Related papers  (2024-11-01T14:23:19Z)
• Neural Potential Field for Obstacle-Aware Local Motion Planning [46.42871544295734]
  We propose a neural network model that returns a differentiable collision cost based on robot pose, obstacle map, and robot footprint. Our architecture includes neural image encoders, which transform obstacle maps and robot footprints into embeddings. Experiment on Husky UGV mobile robot showed that our approach allows real-time and safe local planning.
  arXiv  Detail & Related papers  (2023-10-25T05:00:21Z)
• POA: Passable Obstacles Aware Path-planning Algorithm for Navigation of a Two-wheeled Robot in Highly Cluttered Environments [53.41594627336511]
  Passable Obstacles Aware (POA) planner is a novel navigation method for two-wheeled robots in a cluttered environment. Our algorithm allows two-wheeled robots to find a path through passable obstacles.
  arXiv  Detail & Related papers  (2023-07-16T19:44:27Z)
• Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization [11.638394339813154]
  This paper presents a fully decentralized approach for realtime non-cooperative multi-robot navigation in social mini-games. Our contribution is a new realtime bi-level optimization algorithm, in which the top-level optimization consists of computing a fair and collision-free ordering. We successfully deploy the proposed algorithm in the real world using F$1/10$ robots, a Clearpath Jackal, and a Boston Dynamics Spot.
  arXiv  Detail & Related papers  (2023-06-15T02:18:21Z)
• DDPEN: Trajectory Optimisation With Sub Goal Generation Model [70.36888514074022]
  In this paper, we produce a novel Differential Dynamic Programming with Escape Network (DDPEN) We propose to utilize a deep model that takes as an input map of the environment in the form of a costmap together with the desired position. The model produces possible future directions that will lead to the goal, avoiding local minima which is possible to run in real time conditions.
  arXiv  Detail & Related papers  (2023-01-18T11:02:06Z)
• Neural Optimal Transport with General Cost Functionals [66.41953045707172]
  We introduce a novel neural network-based algorithm to compute optimal transport plans for general cost functionals. As an application, we construct a cost functional to map data distributions while preserving the class-wise structure.
  arXiv  Detail & Related papers  (2022-05-30T20:00:19Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)
• Optimal Cost Design for Model Predictive Control [30.86835688868485]
  Many robotics domains use non model control (MPC) for planning, which sets a reduced time horizon, performs optimization, and replans at every step. In this work, we challenge the common assumption that the cost we optimize using MPC should be the same as the ground truth cost for the task (plus a terminal cost) We propose a zeroth-order trajectory-based approach that enables us to design optimal costs for an MPC planning robot in continuous MDPs.
  arXiv  Detail & Related papers  (2021-04-23T00:00:58Z)
• The Value of Planning for Infinite-Horizon Model Predictive Control [0.0]
  We show how the intermediate data structures used by modern planners can be interpreted as an approximate value function. We show that this value function can be used by MPC directly, resulting in more efficient and resilient behavior at runtime.
  arXiv  Detail & Related papers  (2021-04-07T02:21:55Z)
• Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning [42.38068056643171]
  We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints. We propose a hierarchical algorithm for computing makespan-optimal solutions to the problem.
  arXiv  Detail & Related papers  (2020-06-16T00:45:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.