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

📄 arXiv: 2508.21205v1 📥 PDF

作者: Usman A. Khan, Mouhacine Benosman, Wenliang Liu, Federico Pecora, Joseph W. Durham

分类: cs.RO, cs.LG

发布日期: 2025-08-28

备注: 2025 IEEE Conference on Decision and Control

💡 一句话要点

提出基于模型预测最优传输的多机器人路径规划与调度方法

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 多机器人路径规划 最优传输 模型预测控制 路径调度 机器人导航

📋 核心要点

  1. 多机器人路径规划中，先分配目标再规划路径易导致路径重叠和死锁。
  2. 利用最优传输理论，在离散空间中寻找机器人到目标的最优且无重叠的单元格转换。
  3. 结合模型预测控制和重规划机制，解决轨迹重叠和考虑机器人动力学的问题。

📝 摘要（中文）

本文提出了一种基于最优传输理论和模型预测控制的多机器人导航路径规划与调度新方法。考虑了N个机器人在一个有障碍物的公共空间中导航到M个目标的场景。先将机器人映射到目标，然后规划路径可能会导致路径重叠，从而导致死锁。我们推导出一种基于最优传输的策略，该策略不仅提供从机器人到目标的最小成本路径，而且保证非重叠轨迹。通过将感兴趣的空间离散化为K个单元格，并施加一个描述从一个单元格过渡到另一个单元格的成本的K×K成本结构来实现这一点。然后，最优传输为机器人到达目标提供最优和非重叠的单元格转换，无需任何调度考虑即可轻松部署。所提出的解决方案在最坏情况下需要O(K^3logK)次计算，对于表现良好的问题需要O(K^2logK)次计算。为了进一步适应潜在的重叠轨迹（在某些情况下不可避免）以及机器人动力学，我们表明，借助重规划和模型预测控制，可以将时间结构集成到最优传输中。

🔬 方法详解

问题定义：多机器人路径规划与调度问题，目标是在有障碍物的环境中，为多个机器人找到到达各自目标的最优路径，同时避免碰撞和死锁。现有方法通常先进行目标分配，然后独立规划路径，容易导致路径重叠，需要复杂的调度机制来解决冲突。

核心思路：将路径规划问题转化为最优传输问题。通过定义空间中单元格之间的转移成本，利用最优传输理论找到机器人到目标的最优单元格序列，从而保证路径的非重叠性。这种方法将路径规划和调度问题统一解决，避免了传统方法中先规划后调度的复杂性。

技术框架：该方法主要包含以下几个阶段：1) 空间离散化：将环境离散化为K个单元格。2) 成本矩阵构建：构建一个K×K的成本矩阵，表示从一个单元格移动到另一个单元格的成本。3) 最优传输求解：利用最优传输理论，求解机器人到目标的最优单元格转移方案。4) 路径生成：根据最优传输结果，生成机器人的路径。5) 模型预测控制与重规划：当出现轨迹重叠或需要考虑机器人动力学时，利用模型预测控制进行局部重规划。

关键创新：将最优传输理论应用于多机器人路径规划与调度，实现了路径规划和调度的统一优化。通过空间离散化和成本矩阵构建，将复杂的连续空间路径规划问题转化为离散的最优传输问题，简化了求解过程。结合模型预测控制，能够处理动态环境和机器人动力学约束。

关键设计：成本矩阵的设计是关键。成本矩阵需要反映单元格之间的距离、障碍物信息以及其他约束条件。最优传输问题的求解可以使用现有的算法，如Sinkhorn算法。模型预测控制部分需要设计合适的控制策略和目标函数，以保证机器人的安全性和路径的平滑性。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文提出方法通过最优传输理论保证了路径的非重叠性，避免了传统方法中复杂的调度机制。虽然论文中没有给出具体的实验数据，但理论分析表明，该方法在最坏情况下需要O(K^3logK)次计算，对于表现良好的问题需要O(K^2logK)次计算，计算复杂度相对较低。

🎯 应用场景

该研究成果可应用于仓储物流、自动驾驶、机器人编队等领域。在仓储物流中，可以优化AGV的路径规划，提高物流效率。在自动驾驶领域，可以实现多车辆的协同驾驶，提高交通效率和安全性。在机器人编队领域，可以实现多个机器人的协同任务，提高任务完成效率。

📄 摘要（原文）

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}.