⚡ 电气工程

Predictive congestion externality aware online scheduling for multi-robot warehouses under execution uncertainty

本文介绍了 PACE，这是一种用于多机器人仓库的在线调度策略，它通过将预测的任务完成成本与源自随机展开的估计分配诱导拥塞外部性相结合，从而缓解交通拥堵，进而优化车队性能，特别是在高交通流量条件下。

原作者： Chen Li

发布于 2026-09-29

📖 1 分钟阅读☕ 轻松阅读

原作者： Chen Li

原始论文采用 CC BY 4.0 许可（https://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在现代仓库中，地面不再仅仅是存储空间，而是一条动态的运动河流。成百上千的小型自主机器人穿梭在网格中，将装载着货物的货架从存储区运送到包装站。这些机器是快速交付的支柱，每小时能够移动数千件物品。然而，它们的效率依赖于一种微妙的平衡。当一个机器人被分配一项任务时，它并不只是孤立地移动；它进入了一个由路径、交叉路口和狭窄通道组成的共享网络。如果一个机器人选择了一条对自己而言看似完美的路线，它可能会阻塞一个关键的节点，迫使数十个其他机器人等待。这会产生一种连锁反应，即单个决策会导致整个系统的减速。工程师面临的挑战不仅是告诉机器人该去哪里，而是要在机器人开始移动之前，预测那个选择将如何影响整个机群。

武汉理工大学的李晨（音译）开展的一项新研究通过观察机器人旅程中的“隐藏成本”来解决这一问题。该研究聚焦于一个被称为“拥堵外部性”（congestion externality）的概念，简单来说，就是当一个机器人选择特定路径时，强加给其他所有人的额外等待时间。在传统的调度中，计算机通常会根据机器人自身的距离和速度，选择完成任务最快的机器人。这种新方法认为，如果一个机器人的路径会导致繁忙的交叉路口发生拥堵，那么对于整个仓库而言，它即使是完成单项任务最快的机器人，也可能是最糟糕的选择。为了解决这个问题，研究人员开发了一种名为“基于拥堵外部性的预测性分配”（Predictive Assignment with Congestion Externalities，简称 PACE）的方法。PACE 不仅仅关注眼前的任务，而是通过模拟未来，来观察将任务分配给某个机器人将如何改变其他所有机器人的流动情况。

该方法的工作原理是在计算机内存中运行数千次快速的并行模拟。对于每一对可能的“机器人-任务”组合，系统都会创建两个版本的未来：一个是机器人接受该任务的版本，另一个是它不接受该任务的版本。至关重要的是，这些模拟包含了随机延迟，以模拟现实世界中的不可预测性，例如机器人轻微减速或传感器故障。通过比较整个机群在两种情景下的总等待时间，系统可以计算出“边际拥堵外部性”。这个数值代表了该次分配将给剩余机群造成的具体额外延迟量。如果一个机器人离任务最近，但它的路径会导致其他机器人在瓶颈处滞留，系统就会识别出这对仓库而言成本过高，即便该机器人自身完成得很快。

研究结果表明，这种预见性在仓库繁忙时最为珍贵。在包括狭窄走廊和复杂十字路口在内的各种仓库布局模拟中，这种新方法始终优于标准的调度规则。当交通流量较轻时，差异很小；但随着机器人数量和任务量的增加并趋向系统极限，其优势便显露无疑。PACE 方法实现了更高的吞吐量，这意味着每小时完成的任务更多，并显著减少了任务在排队中的等待时间。它还防止了分布的“尾部”变得过长，确保不会出现少数困难任务被无限期卡住而其他任务却流动顺畅的情况。研究发现，该系统在避免“公地悲剧”（即个体机器人为了自身利益最大化而集体造成交通拥堵）方面特别有效。

该研究的一个核心发现是，性能的提升专门来自于这种分配层面的反馈，而不仅仅是更好的路径规划或碰撞规避。研究人员通过移除外部性计算进行了测试，发现性能增益消失了，这证明其价值在于移动开始之前的任务分配阶段。该系统还证明了其对不确定性的鲁棒性；即使在模拟包含意外延迟或爆发式流量模式的情况下，该方法依然能做出比传统方法更好的决策。研究人员指出，该方法并不会强迫机器人采取不必要的长途绕行；相反，它只有在某个选择能防止整个机群发生更大规模延迟的前提下，才会接受某个机器人稍长的路径。

研究结论认为，这种方法最好被视为现有规划系统的补充。虽然其他算法确保机器人之间不会发生碰撞，但 PACE 确保它们从一开始就不会互相阻碍。模拟表明，对于仓库运营商而言，这种类型的调度在高峰时段或在存在紧凑瓶颈的设施中最为关键。通过将整个机群的等待时间视为一种需要管理的成本，该系统将原本混乱的独立智能体流转变为一个协调的整体。研究表明，在拥挤的数字世界中，最明智的举措往往不是对个体看起来最快的动作，而是能让整个网络保持运转的动作。

技术摘要：面向多机器人仓库的预测性拥堵外部性感知在线调度

1. 问题定义

本文研究了在密集型多机器人仓库环境下进行在线任务分配的挑战，其中自动导引车（AGV）和自主移动机器人（AMR）在执行不确定性的条件下运行。核心问题在于，将一项任务分配给特定的机器人并非一个孤立的决策，它会产生拥堵外部性（congestion externality）。局部最优的分配方案（例如，选择最近的机器人或预测行驶时间最短的机器人）可能会迫使该机器人通过瓶颈区域，从而导致整个机群产生不成比例的等待时间。

现有的方法通常仅根据附加在所选机器人自身的指标（行驶距离、完成时间、工作量）来评估候选机器人-任务对，或者侧重于分配后的路径可行性。这些方法往往无法在分配提交之前，量化该决策对非选中机器人造成的增量系统级延迟。这一差距在共享瓶颈和交叉路口处最为显著，在这些区域，选择一条稍长的焦点路径可以防止显著的下游系统延迟。

2. 方法论：PACE

作者提出了预测性分配与拥堵外部性感知（Predictive Assignment with Congestion Externalities, PACE），这是一种旨在在分配阶段将这些外部性内部化的在线调度策略。该方法由三个主要部分组成：

随机反事实展开（Stochastic Counterfactual Rollouts）： 为了估计拥堵外部性，PACE 使用基于**共同随机数（Common Random Numbers, CRN）**的配对短时界随机展开。对于每一个可行的机器人-任务对 $(i, k)$ ：
1. **基准展开（Baseline Rollout）**模拟当前计划下的机群未来行为（即任务 $k$ 未分配给机器人 $i$ ）。
2. **候选展开（Candidate Rollout）**模拟如果将任务 $k$ 分配给机器人 $i$ 时机群的行为。
3. 两种展开均使用相同的执行不确定性实现（对遍历时间的乘性扰动），以确保比较的公平性。
4. **边际拥堵外部性（ $\hat{E}_{ik}$ ）**计算为：在候选场景与基准场景之间，除候选机器人 $i$ 以外的所有机器人的累计等待时间之差。
外部性感知成本函数： 机器人-任务对的分配成本结合了机器人的自身预测完成成本（ $\hat{T}_{ik}$ ）和估计的机群级外部性（ $\hat{E}_{ik}$ ）。两者都在当前候选集中进行归一化处理，以应对规模差异。目标函数最小化：
$c_{ik} = \alpha \mathcal{N}_t(\hat{T}_{ik}) + \beta \mathcal{N}_t(\hat{E}_{ik})$
其中 $\alpha$ 和 $\beta$ 是权重参数。若 $\beta=0$ ，则该策略退化为标准的滚动时界自成本基准。
滚动时界执行（Rolling-Horizon Execution）： 优化问题作为一个匹配问题（使用匈牙利算法）进行求解，用于将任务分配给机器人或将其延迟执行。生成的分配结果通过共享的、无冲突的**安全间隔路径规划（Safe Interval Path Planning, SIPP）**层进行执行。这种分离确保了性能提升归功于分配决策，而非碰撞规避机制的变化。

3. 核心贡献

形式化定义分配诱导的外部性： 本文正式定义并量化了特定机器人-任务分配对剩余机群造成的边际等待，并将其视为一个独立的成本组件。
通过配对展开进行估计： 引入了一种实用的在线方法，利用带有共同随机数的配对随机模拟来估计这些外部性，从而在执行不确定性下实现稳健的比较。
集成至在线调度中： 研究将此外部性信号集成到滚动时界分配框架中，证明了优化系统级流量需要超越关注焦点机器人的完成时间。

4. 实验结果

研究在四种布局家族（规则通道、狭窄瓶颈、交叉路口以及 MAPF 基准测试）下，针对不同的机群规模、任务强度和执行噪声分布（高斯分布、对数正态分布、突发延迟）对 PACE 进行了评估。

估计器准确性： 在线外部性估计器与离线参考值表现出很强的秩相关性（ $r_s = 0.87$ ）。它成功识别了离线最优候选者的比例为 72% (Hit@1)，且有 94% 的概率将其包含在前 3 个候选者中。随着交通密度的增加，准确性也会随之提高，因为外部性效应变得更加显著。
系统性能： PACE 实现了最高的吞吐量和最低的平均/P95 流转时间，特别是在具有高交互潜力（交叉口、瓶颈）的布局以及系统接近容量极限时。
鲁棒性： 性能增益在执行不确定性和分布偏移下依然存在。其收益随负载呈现非单调性：在稀疏交通中（外部性接近于零时）收益极小；在接近饱和时（瓶颈最为关键时）达到峰值；而在持续过载时（大多数分配都会导致拥堵时）收益则会递减。
消融实验： 移除外部性反馈（ $\beta=0$ ）几乎消除了相对于自成本基准的性能增益。这证实了改进源于分配层面的外部性反馈，而非仅仅是路径安全性或候选过滤。

5. 意义与主张

本文声称 PACE 提供了一种机制，可以在不需要全局重新规划所有路径的情况下，将多机器人调度从“焦点机器人”视角转向“系统级”视角。

上下文价值： 作者断言，在易发生拥堵的时期以及在交叉口或瓶颈容量稀缺的布局中，外部性感知调度最具价值。在轻载操作中，简单的自成本分配仍然足够。
互补作用： 该方法被定位为路径规划器（如 SIPP 或 MAPF）的补充而非替代品。虽然路径层负责强制执行可行移动，但 PACE 决定了哪个机器人接收哪个任务，以避免预先制造可避免的拥堵。
运营洞察： 研究表明，接受焦点机器人行驶距离的适度增加，可以通过将流量重新分配到远离瓶颈的区域，从而获得显著的系统级效率提升。这种权衡是从当前的交通状态中内生产生的，而非固定的启发式规则。

作者总结认为，该框架有效地量化了“分配诱导的拥堵外部性”，为高密度、高不确定性的仓库环境中的动态任务分配提供了一种稳健的方法。未来的工作建议在物理机群上验证该框架，并将其扩展到异构容量和任务捆绑领域。