Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schrödinger Bridges¶

会议: ICML 2026
arXiv: 2605.10917
代码: 未公开
领域: 机器人 / 多智能体路径规划 / 最优传输
关键词: MAPF, 多边际最优传输, Schrödinger bridge, 全单模性, Sinkhorn

一句话总结¶

本文把匿名多机器人路径规划（MAPF）证明为一类马尔可夫多边际最优传输（MMOT），从而把原本 \(K^{T+1}\) 维的传输张量压缩成多项式规模 LP（P1），并通过全单模性保证最优解整数性；再把它推广为 Schrödinger bridge 得到 Sinkhorn 风格 entropic 松弛 P2 产出"影子传输"，最后在影子上做剪枝并解 LP（P3）恢复整数解，在 \(K^{1.15}\) 复杂度下实现 3.6×–7.1× 加速、代价差距 <10%。

研究背景与动机¶

领域现状：MAPF（在共享图上让多个机器人无冲突到达目标）经典解法以 Conflict-Based Search (CBS)、SAT 编码、时间扩展流网络等为主，最优性算法在中等规模上可行，大规模 anonymous MAPF（任何机器人去任何目标）仍是难点。

现有痛点：现有 IP/LP 公式（time-expanded network flow）虽然能给最优解，但没人系统刻画其 LP 的整数性来源——大家凭经验知道某些 case 整数解存在，但缺乏"哪些结构性条件足以保证全单模 (TU)"的统一框架；同时面对大规模（数千节点、上万变量）就只能近似。

核心矛盾：要"最优性 + 整数性"通常意味着 IP（NP-hard），要"可扩展"通常意味着分布式启发式（无保证）。MAPF 缺少一个把这两端连起来的、有理论保证又能跑大规模的统一框架。

本文目标：1) 给 MAPF 找一个统一的最优传输视角；2) 在该视角下证明 LP 可以多项式且整数；3) 通过概率松弛（Schrödinger bridge）得到可扩展的 Sinkhorn 算法；4) 把概率松弛的好处变回整数可执行轨迹。

切入角度：把 \(N\) 个机器人在 \(T\) 步内的所有可能联合轨迹看作一个 \((T+1)\) 阶张量 \(\mathbf{P}\in\mathbb{R}_{\ge 0}^{K\times\cdots\times K}\)，每个条目是一条 path 的概率质量；MAPF 就是要找最小代价 transport plan，满足起止 marginals。这天然就是 MMOT，但因为机器人运动是马尔可夫的，张量有标准因子分解 \(\mathbf{P}_{i_0,\ldots,i_T} \propto \prod_t [\Pi_t]_{i_{t-1}i_t}\)，把变量从 \(O(K^{T+1})\) 砸到 \(O(K^2T)\)。

核心 idea：MAPF = Markovian MMOT；其 anonymous 设定下的 LP 在自然假设下全单模，所以多项式时间能得整数最优解；用 Schrödinger bridge 引入概率松弛得到可扩展求解器，再用剪枝 LP 恢复整数性。

方法详解¶

整体框架¶

全文走"先严谨建模，再概率松弛，再剪枝回整数"三步：(1) P1：在马尔可夫张量参数化下把 MAPF 写成相邻时刻间 transport plan \(\{\Pi_t\}_{t=1}^T\) 的 LP，证全单模性给出整数最优；(2) P2：以 Gibbs kernel \(\bar g_{ij,t} \propto \exp(-c_{ij,t}/\varepsilon)\) 为 reference distribution 写 Schrödinger bridge，得到 P1 的 entropic 正则化，用多边际 Sinkhorn 求"影子"分数传输 \(\tilde\Pi_t\)；(3) P3：用影子高质量边做图剪枝（保留 mass 大的边），在缩小后的图上重解 LP 恢复整数解 \(\hat\Pi_t\)。pipeline 把"最优性 + 整数性"和"可扩展性"两段拼起来，整体复杂度从经典 IPM 的 \(O(K^{1.68})\) 降到 \(O(K^{1.15})\)。

关键设计¶

P1：MAPF 的 MMOT-LP 与全单模性保证:
- 功能：给 anonymous MAPF 一个多项式时间能解、且保证 \(\{0,1\}\) 整数解的 LP 公式。
- 核心思路：决策变量是相邻时刻间转移矩阵 \(\{\Pi_t\}\)，目标 \(\sum_t \langle \Pi_t, C_t\rangle\)，关键约束三组——gluing（mass 守恒 \(\Pi_t^\top\mathbf{1} = \Pi_{t+1}\mathbf{1}\)）确保马尔可夫性、terminal 固定起止分布 \(\Pi_1\mathbf{1}=\mu, \Pi_T^\top\mathbf{1}=\nu\)、vertex-capacity \(0\le\Pi_t^\top\mathbf{1}\le\mathbf{1}\) 防止 vertex 上挤进 >1 个机器人。Assumption 3.1 给出自然结构（self-loop 允许、不共享端点的边可并行、move cost > wait cost > 0、target wait cost = 0）。Lemma 3.3 证明在这些假设下 LP 的约束矩阵全单模（TU），所以所有基本可行解（极点）都是整数，且数量为多项式 \(O(KT)\) 个变量。Theorem 3.4 把整数解翻译回"机器人不碰撞、轨迹不在时空重叠、每个机器人到达独立目标"。
- 设计动机：之前的 MAPF time-expanded IP 缺一个"为什么整数解存在"的清楚答案，本文给出 TU 这个第一性原理解释，并把 min-cost / min-move / min-makespan 这些不同目标统一在调整 \(C_t\) 的方式下（如 Assumption 3.5 用指数增长 \(c_{ij,t} = B^t \tilde c_{ij}\) 隐式逼出 min-makespan，Lemma 3.7 给出 \(T^* \le N + K - 1\) 的 makespan 上界并通过 \(O(\log K)\) 次二分搜索找最小 horizon）。
P2：Schrödinger bridge 与 entropic 松弛:
- 功能：用概率框架获得可大规模并行的 Sinkhorn 求解器，得到一张"哪些边重要"的影子地图。
- 核心思路：把 P1 推广为找联合分布 \(\mathbf{P}\) 在约束集 \(\mathcal{C}\) 上最小化 \(\mathrm{KL}(\mathbf{P}\,\|\,\mathbf{G})\)，其中 \(\mathbf{G}\) 是参考马尔可夫张量。Lemma 4.1 证明 \(\mathrm{KL}(\mathbf{P}\|\mathbf{G})\) 分解为各时层 \(\mathrm{KL}(\frac{1}{N}\Pi_t\|\mathbf{G}_t)\) 之和加上 boundary 项。当 reference 取 Gibbs kernel \(g_{ij,t}=\exp(-c_{ij,t}/\varepsilon)\) 时，Lemma 4.2 把整个目标化为 P1 的 entropic 正则：\(\min \sum_t \langle\Pi_t,C_t\rangle + \varepsilon\sum_{i,j}\pi_{ij,t}(\log\pi_{ij,t}-1)\)。这就是 P2，可以用多边际 Sinkhorn 块坐标下降高效求解（附录 G）。注意 P2 放松了 vertex-capacity 约束，所以解可以是 fractional——但这恰恰是"影子"的意义：它告诉你最优 transport 倾向于走哪些边。\(\varepsilon\to 0\) 时影子收缩到 min-cost 几何走廊上。
- 设计动机：经典 multi-marginal Sinkhorn 对一般 MMOT 已经成熟，但直接套到 MAPF 缺一个"为什么是 entropic 松弛了 P1"的桥；本文把 Schrödinger bridge 与 P1 严格对接，使得 P2 不只是工程加速器，而是一个有概率诠释的"先验感知"求解器（可以通过选不同 reference \(\mathbf{G}\) 注入结构性偏好）。
P3：影子剪枝 + LP 恢复整数性:
- 功能：把 P2 的快但分数解变回可执行的 \(\{0,1\}\) 整数路径。
- 核心思路：对 \(\Pi_t\) 加 KL penalty 拉向影子 \(\tilde\Pi_t\)，再线性化得到目标 \(\sum_t \sum_{i,j}\pi_{ij,t}(c_{ij,t} - \lambda\log(\tilde\pi_{ij,t}+\delta))\)，并把所有质量 \(\le\eta\) 的边砍掉（即 \(\Pi_t \subseteq [\tilde\Pi_t]_\eta\)）。这等价于在影子高亮的"稀疏子图"上重新解一遍 P1：仍然 TU，仍然整数，但变量数从 \(|\mathcal{E}|T\) 减到 \(\zeta|\mathcal{E}|T\)，实验里 \(\zeta\in[0.2, 0.4]\)。三个超参 \(\varepsilon, \lambda, \eta\) 共同调节"最优—可扩展"权衡：\(\lambda=\eta=0\) 退化回 P1；\(\varepsilon\uparrow\) 影子越糊、剪枝越多、代价上升越多。
- 设计动机：把 P2 当成 P3 的"特征选择器"——这是 OT 文献里少见的把"分数解的 mass 分布作为问题结构先验"的优雅用法，既保留了 P1 的最优性证书，又借了 P2 的可扩展性。

损失函数 / 训练策略¶

非学习方法，无 loss/训练；超参选择基于 260 次 \(K=10000\) 实验：\(\varepsilon=0.2, \lambda=0\) 是稳健默认值，给出 4.3% 代价差距、5× 加速。Sinkhorn 迭代数在实践中很少（几十轮即足以构造剪枝图）。

实验关键数据¶

主实验¶

在 \(K = W\times H\) 网格（边长 50–150，5% 机器人密度，\(T=30\)，Gurobi 求解器）上做 162 次独立运行：

方法	求解时间随 \(K\) 缩放	加速倍数	代价差距	整数性
P1（原始 LP）	\(O(K^{1.68})\)	1×	0%（最优）	100%
P2 + P3 pipeline	\(O(K^{1.15})\)	3.6× – 7.1×	< 10%	100%（每个解都验证为整数）

消融实验¶

设置	关键现象	说明
边保留比例从 100% 降到 ~20-40%	代价差距 < 10%，可行性保持	影子剪枝高效
\(\varepsilon = 0.2, \lambda = 0\)（默认）	4.3% 代价差距，5× 加速	鲁棒平衡
\(\varepsilon\) 增大	影子越扩散，剪枝越多，代价差距随之增大	\(\varepsilon\) 是 dominant factor
\(\lambda\) 变化	影响较小	线性化 KL 的权重次要
与 CBM (Ma & Koenig 2016) 对比	P2+P3 在大规模上更稳	附录 H.5

关键发现¶

影子剪枝在问题规模越大时收益越大：\(K\uparrow\) 时只需越来越少边即可保持可行，60-80% 的边都可被砍掉。
TU 性在剪枝后仍保持，这是 P3 能稳定给整数解的核心。
最优性 (P1) 与可扩展性 (P2 → P3) 的 trade-off 由三个超参连续调节，给工程师一条平滑滑杆。

亮点与洞察¶

把 MAPF 嫁接到 MMOT/Schrödinger bridge 是漂亮的统一视角：不仅把 LP 的整数性来源解释清了（TU），还自然引入概率松弛的 Sinkhorn 加速。这种"经典组合优化 + 现代 OT 工具"的桥梁对其他类似问题（车辆调度、多商品流）很有迁移价值。
"影子作 feature selector" 的思想可推广：任何拥有 entropic 松弛的整数 LP，都可以先用 Sinkhorn 找"重要变量"，再回到 LP 精解。
用 \(B^t\) 指数增长 cost 隐式逼 min-makespan，比显式 max-min 公式（破坏 TU）更聪明，但要小心数值溢出，论文也给了 \(O(\log K)\) 二分版作替代。
三超参 \(\varepsilon, \lambda, \eta\) 提供连续的"最优性 vs 可扩展性"调节杠，让工程师根据场景需求在两端间平滑切换，而不是二选一。

局限与展望¶

主要针对 anonymous MAPF，非匿名（指派固定机器人到固定目标）需要更一般的 MMOT 公式，作者指出可扩但未实现。
假设 graph 满足 Assumption 3.1 的"无对角碰撞"等条件，对真实带动力学约束的多机器人（如有转向半径）的连续运动需先离散化。
Schrödinger bridge 的 reference \(\mathbf{G}\) 选 Gibbs kernel 才能化成 entropic regularization；其他先验（如风险规避、行驶偏好）形式上能塞进去但求解器需要重新推导。
复杂度结论基于网格图实验，对一般稀疏图、有动态障碍的实时场景未直接验证。

评分¶

新颖性: ⭐⭐⭐⭐⭐ MAPF↔MMOT/Schrödinger bridge 的统一视角是真正新意。
实验充分度: ⭐⭐⭐⭐ 大规模 scaling、参数敏感性、CBM 对比都有，但缺动态/连续场景。
写作质量: ⭐⭐⭐⭐⭐ 数学推导整洁，三段式 P1/P2/P3 结构清晰易懂。
价值: ⭐⭐⭐⭐⭐ 对仓库机器人、多无人机协调等大规模 MAPF 应用有直接工程意义。