💻 computer science

Multiagent Stochastic Shortest Path Problem

本文介绍了多智能体随机最短路径问题，分析了其在自主与协调场景下的计算复杂性与策略复杂性，并提出了高效的策略合成算法，且通过自然基线进行了实验验证。

原作者： Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák

发布于 2026-05-08

📖 1 分钟阅读☕ 轻松阅读

原作者： Martin Jonáš, Antonín Kučera, Vojtěch Kůr, Jan Mačák, Vojtěch Řehák

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

想象一下，你正试图将一份非常紧急的包裹送往医院。你拥有一张城市地图，但交通状况变幻莫测。有时道路畅通无阻，有时却完全堵死。这是一个经典的“随机最短路径”问题：在充满不确定性的未来中寻找最快路线。

现在，想象你拥有的不只是一辆车，而是十辆车组成的车队，它们同时从同一个仓库出发。你的目标并不是让每一辆车都尽快到达医院；你的目标是确保至少有一辆车尽快抵达。第一辆到达的车负责送达包裹；其他车辆可以等待或稍后使用。

本文介绍了一种解决这种“多智能体随机最短路径”（MSSP）问题的新方法。作者问道：我们应该如何调度这些车辆，以最小化第一辆车抵达的时间？

以下是他们研究发现的拆解，辅以简单的类比：

1. 两种驾驶方式：“指挥家”与“独奏者”

本文探讨了管理车队的两种不同方式：

协调方法（指挥家）： 想象有一个中央控制室（指挥家），它能俯瞰整个城市，并在每一时刻精确指示每辆车该做什么。如果 A 车遇到拥堵，指挥家会立即指示 B 车改走另一条路线。
- 结果： 作者发现，虽然这是最高效的驾驶方式，但随着车辆数量的增加，计算难度会变得极其巨大。如果有 2 辆车，计算很容易；如果有 10 辆，数学运算量之大使得在普通计算机上完美求解实际上变得不可能。他们证明，随着每增加一辆新车，难度呈指数级爆炸式增长。
- 好消息： 如果车辆数量是固定的（例如，你总是恰好有 3 辆车），那么你可以快速且完美地解决这个问题。
自主方法（独奏者）： 想象每辆车都有自己的 GPS，并独立做出决策，不与其他车辆或中央大脑交流。它们不知道其他车辆在做什么。
- 结果： 这在数学上更难求解。事实上，为这些独立车辆寻找完美的规则集是一个“噩梦”般的问题（技术上称为 NP 难问题）。即使只有两辆车，寻找绝对最佳策略在计算上也极其困难。
- 关键点： 有时，车辆需要“记住”某些事情。例如，A 车可能需要记住：“我三个街区前左转了，所以我现在应该右转以避免与其他车辆冲突。”论文表明，完美的策略可能需要无限记忆，但“足够好”的策略只需要极少量的记忆。

2. “自主的代价”

作者计算了“自主的代价”。这是一种委婉的说法，意在询问：“与指挥家方法相比，独奏者方法慢了多少？”

在某些场景下，答案是“不多”。独奏者的表现几乎与指挥家一样好。
在其他场景下，答案是“很多”。由于无法协调以避免相互冲突或有效覆盖不同路线，独奏者可能会显著变慢。
论文证明，这种“代价”可以是任意大的。在最坏的情况下，让车辆在没有协调的情况下自动驾驶，其表现可能比有指挥家指挥时无限糟糕。

3. 解决方案："AUTOHIT"（智能优化器）

由于为独立车辆寻找完美解在数学上无法快速完成，作者发明了一种名为AUTOHIT的算法。

工作原理： 它不试图寻找完美答案（这就像试图在广阔多雾的山脉中找到唯一的最高峰），而是使用一种称为“梯度下降”的技术。想象你蒙着眼睛站在山上，想要下山。你用脚感受地面；如果地面倾斜向下，你就朝那个方向迈一步。你不断重复这个过程，直到无法再低为止。
转折： 他们将问题转化为一个平滑的数学景观，从而可以利用强大的现代工具（类似于训练 AI 所使用的工具）来“滑向”一个非常好的解。
权衡： 他们承认这不能保证是完美的解（因为完美解太难寻找），但它找到的解显著优于标准的“让每辆车只做单车最佳路线”的方法。

4. 实验：在虚拟城市中测试

为了测试他们的想法，他们构建了一个拥有网格状街道的虚拟城市。某些十字路口设有“交通拥堵”（随机延迟）。他们让车队（从 1 辆到 20 辆不等）穿过这些城市。

基线： 他们将新方法与“显而易见”的策略进行了比较：即告诉每辆车走单车的最佳路线，而忽略其他车辆。
结果： AUTOHIT 始终优于基线。在某些情况下，它将第一辆车的预期到达时间缩短了近20%。
速度： “指挥家”方法（COORHIT）对于大型车队来说太慢了（在大型地图上，仅 4 辆车就导致超时）。而“独奏者”方法（AUTOHIT）速度快且可扩展，能在不到一分钟内处理大型地图上的 20 辆车。

总结

论文指出：

协调多个智能体以率先到达目标在理论上是可行的，但随着群体规模扩大，计算负担会变得非常沉重。
让智能体独立行动在数学上极难完美优化，但我们可以利用智能的现代优化技术，非常接近最佳结果。
他们的新算法AUTOHIT是一个实用工具，它帮助独立智能体协同工作（实际上并不交流），从而比它们单独行动时更快地完成任务。

简而言之：如果你需要一支司机团队尽快送达包裹，你应该尝试协调他们。但如果无法协调，不要只是让他们随机驾驶——使用智能算法教导他们如何独立驾驶，从而以超越概率的方式击败对手。

技术摘要：多智能体随机最短路径问题

问题定义

本文介绍并研究了多智能体随机最短路径（MSSP）问题。在该设定下， $k$ 个智能体在一个已知且显式表示的马尔可夫决策过程（MDP）中运行。其目标是最小化至少一个智能体到达指定目标状态所需的期望时间。这与经典的随机最短路径（SSP）问题形成对比，后者中单个智能体旨在最小化其自身的期望路径长度。

作者区分了两种运行设定：

协调式 MSSP：智能体由中央机构控制，该机构根据全局状态和共享记忆发出联合动作。
自主式 MSSP：智能体独立行动，每个智能体基于其局部历史和记忆遵循各自的策略，无需协调。

文中提供了一个激励性示例：多辆车辆紧急运输血液；其目标是最小化第一辆车辆的期望到达时间，而非所有车辆的平均到达时间。论文指出，为每个智能体独立求解单智能体 SSP 问题（一种自然的基线）通常是非最优的，且在特定情况下可能是最差的解决方案。

方法论与复杂度分析

理论复杂度

作者分析了两种设定下的计算复杂度和策略复杂度：

协调式 MSSP：
- 复杂度：该问题被证明是 PSPACE-hard 的。然而，对于固定数量的智能体 $k$ ，该问题可在关于 MDP $M$ 规模的多项式时间内求解，尽管时间复杂度随 $k$ 呈指数增长。
- 策略类型：存在一种最优的协调策略，它是无记忆的（决策仅取决于当前位置）且确定性的。
- 算法：作者提出了 COORHIT，该算法将 $k$ 智能体问题归约为大小为 $|S|^k$ 的乘积 MDP 上的单智能体 SSP 问题，可通过标准线性规划（LP）求解。
自主式 MSSP：
- 复杂度：决策问题（判断是否存在期望时间 $\le B$ ）是 NP-hard 的，即使对于 $k=2$ 个智能体，甚至限制在无记忆策略配置下也是如此。因此，该问题在 $k$ 上不是固定参数可解的。
- 策略类型：最优的自主策略配置可能需要任意大小的有限记忆。然而，对于任何 $\epsilon > 0$ ，存在使用有限记忆随机策略的 $\epsilon$ -最优配置。
- 随机化：论文证明，对于固定的记忆大小，随机策略配置比确定性策略配置具有严格更强的能力。
- 归约：有限记忆策略配置的合成可归约为扩展 MDP 中无记忆策略配置的合成，但核心问题仍然是 NP-hard 的。

算法解决方案：AUTOHIT

鉴于自主设定的 NP-hard 性质，作者设计了 AUTOHIT，这是一种高效的启发式合成算法，它牺牲了最优性保证以换取可扩展性。

可微分编程：核心创新是将无记忆随机策略表示为实值参数向量。利用 Softmax 函数，这些参数定义了动作概率。
目标函数：到达目标的期望时间被表达为这些参数的可微分函数。作者推导了一个截断的无穷级数近似 $E^{\langle \gamma \rangle}_\pi[M_{Hit}]$ ，该函数可在多项式时间内计算。
优化：AUTOHIT 使用梯度下降（具体通过 PyTorch 的 ADAM 优化器）来最小化该可微分目标函数。
初始化：算法可以使用随机参数或预计算策略（例如，源自单智能体 LP 解的策略）进行初始化。

实验结果

作者在随机生成的基准测试上评估了其算法，这些基准测试类似于带有随机交通延误（拥堵）的网格状城市地图。

协调式与自主式对比：
- 由于乘积 MDP 的状态空间呈指数级增长，COORHIT 随智能体数量的增加而扩展性较差。在 3 以上规模的网格上，对于 4 个智能体，它在 5 分钟内未能终止。
- AUTOHIT 的扩展性显著更好，在不到 85 秒的时间内处理了具有 250 个状态的网格上多达 20 个智能体的情况。
- 自主性代价：在两种算法均终止的情况下，性能差距（自主性代价）很小（期望时间的平均差异为 0.01），这表明对于这些特定基准测试，协调相比精心调优的自主策略提供的额外收益有限。
性能与基线对比：
- AUTOHIT 始终优于独立的单智能体最优策略（通过 LP 求解）这一自然基线。
- 在某些情况下，与基线相比，AUTOHIT 将到达目标的期望时间减少了近 20%。
- 使用 LP 解的“随机化版本”初始化 AUTOHIT，其结果略优于纯随机初始化。

主要贡献

问题形式化：正式定义了 MSSP 问题，区分了协调式和自主式设定，并将目标确定为最小化首次到达的期望时间。
复杂度刻画：
- 证明了协调式 MSSP 是 PSPACE-hard 的，但在 $k$ 上是固定参数可解的（具有无记忆确定性最优策略）。
- 证明了自主式 MSSP 即使在 $k=2$ 和无记忆策略配置下也是 NP-hard 的，需要有限记忆随机策略以实现 $\epsilon$ -最优性。
- 证明了“自主性代价”可以是任意大的。
算法创新：开发了 AUTOHIT，一种用于合成自主策略的可微分编程方法。该方法通过对期望时间的可微分近似进行基于梯度的优化，绕过了 NP-hard 障碍。
实证验证：实验证据表明，AUTOHIT 能够生成高质量解决方案，显著优于独立的单智能体基线，并且可扩展到精确协调方法失效的智能体数量规模。

意义与主张

本文主张，尽管 MSSP 问题存在根本性的复杂度障碍（协调的 PSPACE-hard 性，自主的 NP-hard 性），但高效的合成算法仍能产生显著优于自然基线的解决方案。

作者强调，他们的工作开启了 MSSP 的研究。他们指出，尽管计算复杂度很高，但 AUTOHIT 算法成功克服了更具挑战性的自主设定中的障碍。结果表明，对于可以复制物品的时间敏感型交付问题（如血液运输示例），部署具有合成策略的多个自主智能体是一种可行且有效的方法，通常能在无需昂贵中央协调的情况下产生近乎最优的性能。

论文以谦逊的结论收尾，指出虽然 AUTOHIT 是有效的，但针对协调设定（超越指数级爆炸）是否存在同样高效的算法，以及是否存在更好的合成替代方案，仍是未来研究有待解决的开放问题。