⚡ electrical engineering

Minimizing Worst-Case Weighted Latency for Multi-Robot Persistent Monitoring: Theory and RL-Based Solutions

本文通过提出一系列尾部性能目标、确立其理论性质，并开发一种基于强化学习的解决方案（即等价的 TWLO-MDP），解决了多机器人持续监控中标准最坏情况延迟目标的局限性，该方案在最小化加权延迟方面优于现有基线方法。

原作者： Weizhen Wang, Ziheng Wang, Jianping He, Xinping Guan, Xiaoming Duan

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Weizhen Wang, Ziheng Wang, Jianping He, Xinping Guan, Xiaoming Duan

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

想象一支安保团队在城市街区巡逻。他们的工作不仅仅是走一圈，而是要永远持续下去，反复检查每个角落、小巷和建筑物。有些建筑物比其他地方更重要（例如银行与公园相比），因此警卫需要更频繁地访问银行。

这项研究的目标是为这些机器人制定出完美的巡逻计划，使得“最坏情况”尽可能好。在此语境下，“最坏情况”是指任何单栋建筑物未被访问的最长时间，并根据该建筑物的重要性进行调整。

以下是用简单类比对论文核心思想的分解说明：

1. 问题：“糟糕开局”陷阱

通常，当我们评估巡逻计划的好坏时，会考察从第一秒开始的整个历史过程。

类比：想象一名警卫在城市的错误一端开始换班。他需要 10 分钟才能跑到银行。在这 10 分钟内，银行处于无人看守状态。如果你仅凭这 10 分钟的空白期来评判整个班次，那么即使该警卫在接下来的 100 年里都完美巡逻，他看起来也会表现得很糟糕。
论文的解决方案：作者意识到，通过“糟糕开局”来评判策略是不公平的。他们引入了**“尾部性能”（Tail-Performance）**概念。这就像老师忽略开学第一周（即“瞬态”阶段），只根据学生进入常规状态后的表现来评分。这确保了评估的是巡逻的长期、稳定质量，而不仅仅是初期的混乱。

2. 理论：证明“完美循环”的存在

在编写计算机程序解决此问题之前，作者进行了大量的数学推导以证明以下几点：

存在性：他们证明了“完美”的巡逻计划确实存在。你不必担心该问题无解。
循环：他们表明，最佳策略始终是一个重复循环。你不需要每天发明新计划，只需找到一个可以无限重复的完美循环即可。
等待是可以的：他们证明了机器人不需要持续移动。有时，最佳策略是在特定位置停留一段时间。他们还证明了可以将这些“等待时间”四舍五入为简单的数字（例如等待 1 分钟、2 分钟等），而不会破坏计划。

3. 解决方案：将巡逻转化为游戏

该问题最困难的部分在于，目标（最小化最坏等待时间）对计算机来说很怪异。标准的计算机学习（强化学习）通常试图最大化分数总和（例如每访问一所房子得 +1 分）。但在这里，一个糟糕的时刻（长时间的等待）会毁掉整个得分，无论之前发生了多少个好时刻。

类比：想象玩一款电子游戏，你的得分不是收集的硬币总数，而是你未收集硬币的最长时间。标准的游戏人工智能不知道如何玩这种游戏。
论文的解决方案：作者构建了一个特殊的“游戏引擎”（称为TWLO-MDP）来“欺骗”计算机。他们在游戏状态中添加了一个“记忆追踪器”。该追踪器会记住迄今为止看到的最长等待时间。
- 现在，计算机不再试图最小化那个奇怪的“最坏情况”数值，而是玩一个标准游戏，试图随时间推移将该“记忆追踪器”保持在尽可能低的水平。
- 这将一个超级困难、怪异的问题转化为一个标准的、可解的游戏，现代人工智能可以学习并完美地玩好它。

4. 工具：M2Bench（机器人巡逻的“健身房”）

为了测试他们的新方法，作者构建了一个名为M2Bench的平台。

类比：在此之前，如果你想测试新的机器人巡逻策略，你可能不得不从头构建自己的模拟环境，就像为了测试新跑鞋而专门制造自己的健身器材一样。
论文的解决方案：M2Bench 是一个预构建的通用健身房。它拥有不同的“赛道”（模拟城市，从简单的三角形到旧金山犯罪热点的真实地图）。它允许研究人员插入他们的新 AI 策略，并在相同的规则和测量标准下，与旧的、标准的方法（如随机行走或简单循环）进行公平比较。

5. 结果：AI 获胜

当他们在这些赛道上测试其新的“尾部性能”AI（使用名为 MAPPO 的方法）时：

它学会了忽略“糟糕开局”，专注于长期常规。
它一致地找到了巡逻循环，使得“最坏等待时间”低于旧的、标准的方法。
它在简单的虚构地图和具有不同建筑物优先级的复杂、真实地图上均表现良好。

总结

论文指出：“停止根据机器人巡逻最初几分钟的混乱来评判它们。相反，应关注其稳定、长期的节奏。我们在数学上证明了完美重复循环的存在，并构建了一个特殊的‘游戏’，让 AI 能够学习找到这些循环。我们还建立了一个通用测试平台（M2Bench），以证明我们的新 AI 方法在保护重要场所方面优于旧方法。”

技术摘要：最小化多机器人持久监控中的最坏情况加权延迟

问题表述

本文研究了加权图上的多机器人持久监控问题。环境被建模为一个有限加权图 $G = (V, E, A, \phi)$ ，其中节点代表关键位置，其关联的权重 $\phi(v)$ 表示监控优先级；边代表物理路径，其长度为 $A(e)$ 。一个由 $k$ 个机器人组成的团队在该图上移动，最大速度为 1，并能够在任意点等待。

核心目标是设计联合机器人轨迹，以最小化无限时间范围内的最坏情况加权延迟。节点 $v$ 的延迟 $L_v(t)$ 定义为自其上次被访问以来所经过的时间。瞬时最坏加权延迟为 $L(t) = \max_{v \in V} \phi(v) L_v(t)$ 。

作者指出了标准最坏情况延迟目标（ $\sup_{t \ge 0} L(t)$ ）的一个局限性：它对由机器人初始部署引起的瞬态行为高度敏感。一种策略可能由于不利的起始位置而表现出较差的初始性能，但最终收敛到最优稳态。标准指标无法将此类策略与那些性能永久较差的策略区分开来。

为解决这一问题，本文引入了一族尾部性能目标。对于给定的瞬态时间范围 $T \ge 0$ ，目标是 minimize：
$J_T(\pi) = \sup_{t \ge T} L(t)$
该公式排除了初始瞬态阶段，专注于长期监控质量。

方法论

1. 理论分析

作者确立了尾部性能目标的几个基本理论性质：

最优策略的存在性：利用 Arzelà–Ascoli 定理以及紧集上下半连续泛函的性质，他们证明了对于任意 $T \in \mathbb{R}_{\ge 0}$ ，最优策略均存在。
不变性与单调性：他们表明最优值 $J^*$ 与 $T$ 无关（即对于所有 $T$ ， $J^*_T = J^*$ ）。此外，最优策略集合具有单调性；针对 $T=0$ 的最优策略对于更大的 $T$ 仍然最优，而增加 $T$ 通过容忍更多的瞬态行为，扩大了可接受的最优策略集合。
周期近似：他们证明了对于任何具有有限性能的可行策略，都存在一个周期策略可以任意精确地逼近它。这将无限时域泛函优化简化为对有限时域重复模式的搜索。
离散化等待时间：作者证明，限制机器人在节点间全速移动，并仅在节点处以离散时间步长等待，仅会引入有界且可控的近似误差（ $O(\Delta)$ ）。

2. MDP 重构（TWLO-MDP）

核心贡献之一是将连续时间、非加性泛函优化问题重构为等价的事件驱动马尔可夫决策过程（MDP），称为最坏情况延迟优化尾部马尔可夫决策过程（TWLO-MDP）。

状态空间：状态包括所有机器人的联合位置、所有节点的当前延迟、自时间 $T$ 以来观测到的最坏加权延迟追踪器，以及经过时间的计数器。
动作空间：机器人决定移动到相邻节点或等待离散化的时长。
奖励与目标：非加性尾部目标被转化为标准的平均奖励准则。每个事件步的奖励是当前最坏延迟追踪器的值。作者证明了该 MDP 的最优平均奖励恰好等于原始监控问题的最优尾部性能。这种等价性使得可以使用标准强化学习（RL）算法直接解决原始问题，而无需依赖启发式代理奖励。

3. 强化学习解决方案

基于 TWLO-MDP，作者开发了基于 RL 的求解方法（具体利用 MAPPO 作为代表性算法），并包含若干针对问题的增强措施：

时间归一化目标：为了使训练与物理时间语义保持一致， rollout 按经过的物理时间而非决策步数进行截断。奖励根据事件间隔的持续时间（ $z_n \Delta t_n$ ）进行加权，以防止策略通过选择最小等待时间来人为抑制延迟。
透明 GAE（Trans-GAE）：一种修改后的广义优势估计，通过折叠非活动的“无操作”步骤来处理异步事件转换，确保在可变时间间隔内正确分配信用。
反事实信用分配：为了解决多智能体设置中全局奖励稀疏的问题，该方法通过比较实际结果与智能体采取基线动作的反事实场景，来估计单个智能体的贡献。
模仿学习：该流程使用启发式策略生成演示数据以进行预训练（行为克隆），为 RL 智能体在微调前提供强有力的初始化。

4. M2Bench 平台

作者引入了 M2Bench，这是一个模块化基准测试平台，旨在整合启发式和基于 RL 的监控算法。其特点包括：

统一的配置驱动工作流（基于 YAML），用于定义图、MDP 公式和算法。
支持同步和事件驱动异步仿真。
集成了 15 种经典启发式算法和 10 种现代 RL 算法的实现。
统一的评估指标（瞬时/平均/最坏图空闲时间），并扩展至加权节点。

关键结果

实验在合成图（包括“长边”图）和基于旧金山犯罪地图的真实场景中进行了。

学习性能：提出的 TWLO-MDP 公式使得代表性的多智能体强化学习（MARL）算法（MAPPO、IPPO、VDPPO）能够有效最小化最坏情况加权延迟。策略梯度方法收敛到较低的延迟值，显著优于独立价值学习方法（IQL）。
基准比较：在旧金山犯罪地图上，MAPPO-TWLO（经模仿学习初始化）在所有对比算法中实现了最低的最坏情况加权延迟，包括经典启发式算法（如 BBLA、GBLA）和其他 RL 基线（如 MAGEC、S4R1）。
鲁棒性：与固定的启发式规则相比，基于学习的方法在具有异质边长和节点优先级的复杂加权图上表现出更优越的适应性。

意义与主张

本文声称做出了以下贡献：

理论基础：确立了尾部性能目标的最优策略存在性，并证明了周期解可以任意精确地逼近最优性能，从而为关注有限时域模式提供了理论依据。
精确重构：提供了将非加性最坏情况延迟问题重构为平均奖励 MDP 的理论精确方法。这弥合了泛函优化与标准 RL 之间的差距，允许在不进行启发式奖励塑造的情况下直接优化真实的监控目标。
统一基准测试：通过引入 M2Bench，解决了缺乏统一平台来比较异构监控算法的问题，促进了启发式和学习范式之间的公平评估。
实际有效性：实证结果表明，所提出的框架在合成和真实场景中均能有效降低最坏情况加权延迟，优于最先进的基线。

作者总结道，虽然单机器人情况已有成熟的结构性结果，但将其扩展到多机器人设置并非易事。他们的工作为此扩展提供了严谨的理论和算法框架，未来的工作计划解决动态图、不确定的旅行时间以及更大规模的团队问题。