用最优传输理论解决多机器人路径规划中的拥堵与死锁问题
Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT)
- 基于最优传输构建非重叠路径，避免机器人冲突
- 复杂度为O(K³log K)，在合理条件下可降至O(K²log K)
- 适合需要高可靠路径规划的工业级多机系统
本文提出一种基于最优传输理论和模型预测控制的多机器人路径规划与调度新方法。考虑N个机器人需在有障碍物的公共空间中导航至M个目标。传统先匹配后规划的方法易导致路径重叠引发死锁。我们通过将兴趣空间离散化为K个单元，并定义K×K的转移代价矩阵，利用最优传输算法获得从机器人到目标的最小代价且无重叠的单元转移路径，可直接部署而无需额外调度。该方法最坏情况计算复杂度为O(K³log K)，良好情况下可降至O(K²log K)。为进一步处理不可避免的路径重叠及机器人动力学约束，引入重规划机制与模型预测控制，实现动态调整。
原文摘要 · Abstract (English)
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}.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。