💻 computer science

Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem

本文针对多监视者路径问题（MWRP），提出了一种通过剪枝状态空间实现高效最优规划的算法 MWRP-CP3，以及多种具有质量界限的次优算法，显著提升了在大规模地图上的求解速度与可扩展性。

原作者： Srikar Gouru, Ariel Felner, Jiaoyang Li

发布于 2026-04-20

📖 1 分钟阅读☕ 轻松阅读

原作者： Srikar Gouru, Ariel Felner, Jiaoyang Li

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

这篇论文解决了一个非常有趣且实用的问题：如何安排多名“巡逻员”（Watchmen），让他们用最少的总时间，把一张地图上的每一个角落都“看”到。

想象一下，你是一家大型博物馆的馆长，或者是一个灾难救援队的指挥官。你需要派出几个保安或救援人员，确保博物馆的每个角落（或者灾区）都被他们看到过，没有死角。你的目标不是让某个人跑得最快，而是让最后一个人完成任务的时间尽可能短（这叫“最大完工时间”或 Makespan），因为只要还有一个人没看完，整个任务就没结束。

这篇论文就像是为这些巡逻员设计了一套超级高效的“寻宝攻略”。

以下是用通俗语言和比喻对论文核心内容的解读：

1. 核心难题：为什么这很难？

这就好比你让几个保安在迷宫里巡逻。

传统方法太慢：以前的算法就像是一个笨拙的导游，他要把所有可能的路线都试一遍，看看哪条路能让所有人最快看完。如果地图很大（比如几千个格子），或者保安很多，这种“穷举法”会让电脑算到天荒地老，根本没法用在现实中。
视野问题：巡逻员不是走到哪里就能看哪里，他们只能看到视线范围内的东西（比如被墙挡住就看不到了）。这增加了计算的复杂度。

2. 我们的解决方案：MWRP-CP3（超级优化版）

作者提出了一种名为 MWRP-CP3 的新算法，它能让计算速度提升 200 倍 以上。它是如何做到的呢？用了三个“独门秘籍”：

秘籍一：剪枝（Cell & Path Dominance）——“聪明的偷懒”

比喻：想象你在看一个房间。如果你已经看到了房间最里面的那个角落（死角），那么根据物理规律，你肯定也看到了通往那个角落的走廊。
做法：算法发现，有些点只要被看到了，其他一些点就自动被看到了。所以，它直接把这些“自动被看到”的点从任务清单里划掉，不用专门去安排人看。
效果：这就像是你去超市买东西，如果买了“全家桶”，就不用单独买里面的汉堡和可乐了。这直接砍掉了 95% 以上需要计算的无用路径，让搜索空间瞬间变小。

秘籍二：枢纽修剪（Pivot Pruning）——“拒绝绕远路”

比喻：在规划路线时，算法会选几个关键的“检查点”（Pivots）。有时候，为了看两个点，算法可能会选一条绕远的路，因为中间有个点看起来能“顺路”看。
做法：算法会检查这些“顺路点”，如果发现它们其实是在帮倒忙（比如为了看 A 点，特意绕路经过 B 点，结果反而让总时间变长了），就直接把这个“顺路点”删掉，强制走直线。
效果：这就像导航软件帮你避开那些看似捷径、实则拥堵的小巷，直接走最快的大道。

秘籍三：并行计算（Parallel Heuristic）——“多核大脑”

比喻：以前的算法是一个人在做数学题，算一步想一步。现在的算法像是开了一个“多人会议室”，大家同时算不同的题目。
做法：在计算下一步怎么走时，它不再一个个慢慢算，而是把接下来要算的一百个可能性打包，利用电脑的多核处理器同时计算。
效果：大大加快了“思考”的速度。

3. 当地图太大怎么办？（次优解算法）

如果地图超级大（比如整个城市），就算用了上面的“超级优化”，电脑可能还是算不过来。这时候，作者提供了**“次优解”**方案：

MxWA（加权 A）**：
- 比喻：这就像是你不再追求“绝对完美”的路线，而是接受“差不多好”的路线。你给算法一个“宽容度”（比如允许慢 20%），它就能在几秒钟内给你出一个方案，而不是等几个小时。
- 特点：它专门针对“让最后一个人尽快结束”这个目标进行了优化，比通用的方法更快。
后处理框架（Postprocessing）——“事后诸葛亮”：
- 比喻：假设你已经有了一个大概的巡逻方案，但发现有个保安跑得太累了（时间最长）。这时候，你把这个保安单独叫出来，让他重新规划一条只看他负责区域的“短路线”，其他人不动。
- 做法：把大任务拆成小任务，专门优化那个“拖后腿”的人。
- 效果：用很少的时间，就能把原本不太完美的方案变得非常接近完美。

4. 总结与成果

这篇论文就像给巡逻任务装上了**“涡轮增压”**：

快：对于中等规模的地图，新算法比旧算法快 200 倍，能处理以前算不动的复杂地图。
大：对于超大规模地图，虽然不能保证 100% 完美，但能在极短时间内给出一个非常接近完美的方案（比如地图扩大 3 倍也能解）。
灵活：无论是迷宫、随机生成的地图，还是像《我的世界》那样的游戏地图，这套方法都管用。

一句话总结：
这就好比以前派保安巡逻，需要花几天时间算路线；现在用了这套新算法，几秒钟就能算出最优路线，或者在几秒钟内给出一个“几乎完美”的路线，让救援和巡逻工作变得既高效又智能。

论文技术总结：具有可证明最优性界限的可扩展多巡警路线问题算法

1. 问题背景与定义

多巡警路线问题 (Multiple Watchman Route Problem, MWRP) 是覆盖路径规划 (CPP) 领域的一个核心挑战。

定义：给定 $M$ 个巡警（智能体）和一个环境地图（通常表示为网格图），目标是找到一组路径，使得地图上的每一个位置（或特定目标区域 $U$ ）至少能被其中一个巡警的视线（Line-of-Sight, LOS）覆盖。
目标函数：本文主要关注最小化最大路径长度 (Makespan)，即最小化所有巡警中路径最长的那一条。这在灾难救援、火灾探测等时间敏感型任务中至关重要。
挑战：该问题已被证明是 NP-hard 的。现有的最优算法（如 MWRP-A*）在地图规模稍大（如超过 200 个自由单元格）或智能体数量增加时，计算时间呈指数级增长，无法应用于现实世界的大规模场景。

2. 核心方法论

本文提出了一套完整的解决方案，包含最优搜索算法、有界次优搜索算法以及后处理框架。

2.1 最优搜索算法：MWRP-CP3

MWRP-CP3 是对现有 MWRP-A* 算法的增强版本，旨在通过减少搜索空间和优化启发式计算来大幅提升效率。

状态空间缩减 (State Space Reduction)：
- 单元格支配 (Cell Dominance, CD)：基于观察发现，如果单元格 $s_1$ 的所有“观察者”集合是单元格 $s_2$ 观察者集合的子集（ $W(s_1) \subseteq W(s_2)$ ），那么只要看到了 $s_1$ ，就必然看到了 $s_2$ 。因此，可以将 $s_2$ 从待覆盖集合 $U$ 中剪枝，从而减少状态空间。
- 路径支配 (Path Dominance, PD)：基于智能体的起始位置，如果从起点到看到 $s_1$ 的所有路径都必须经过 $s_2$ （即看到 $s_1$ 必然先看到 $s_2$ ），则 $s_1$ 支配 $s_2$ 。利用多源 BFS 算法识别此类关系并剪枝。
- 效果：这两种方法结合（CPD）能在复杂地图上减少超过 95% 的待覆盖单元格数量，且不影响最优性保证。
枢轴剪枝 (Pivot Pruning)：
- 在计算基于多旅行商问题 (mTSP) 的启发式函数时，传统的贪婪策略会选择尽可能多的枢轴点。
- 本文提出移除那些在 mTSP 图中充当“捷径”的枢轴点。虽然移除某些枢轴可能降低启发式的信息量，但实验表明，移除特定枢轴能显著减少 mTSP 求解器的计算负担，从而加速整体搜索。
并行启发式计算 (Parallel Heuristic Calculation)：
- 针对 MWRP-A* 中 mTSP 启发式计算耗时的问题，采用 Batch A* 策略。
- 在 A* 扩展循环中，预先收集接下来 $N$ 个待扩展节点，并行计算它们的 mTSP 启发式值，而不是串行计算。这在不改变 A* 理论复杂度的前提下，显著降低了实际运行时间。

2.2 有界次优搜索 (Bounded Suboptimal Search, BSS)

为了处理更大规模的地图和更多的智能体，本文引入了次优算法，保证解的质量在最优解的 $w$ 倍以内 ( $w \ge 1$ )。

Minimax Weighted A (MxWA)**：
- 这是加权 A* (WA*) 在最小化最大路径 (Makespan) 问题上的推广。
- 传统 WA* 使用 $f(n) = g(n) + w \cdot h(n)$ 。MxWA* 针对多智能体场景，定义 $f_{MxW}(n) = \max_k \{g_k(n) + w \cdot h_k(n)\}$ 。
- 该算法优先扩展剩余搜索努力较小的智能体路径，同时保证解的代价 $C \le w \cdot C^*$ 。
- 支持 Anytime (即时) 模式，在找到初始解后继续搜索更优解。
Focal Search (FS) 变体：
- 利用 Focal Search 框架，维护一个 OPEN 列表和一个 FOCAL 列表（包含 $f(n) \le w \cdot f_{min}$ 的节点）。
- 提出了两种新的启发式函数用于 FOCAL 列表排序：
  - SORC (Sum Of Remaining Costs)：剩余成本之和。
  - MORC (Max Of Remaining Costs)：剩余成本的最大值。
- 同样支持 Anytime 模式 (AFS)。

2.3 后处理框架 (Postprocessing Framework)

机制：针对已有的次优解，识别路径最长的智能体（瓶颈智能体）。
分解：将该智能体的任务分解为一个单智能子问题。计算其他智能体无法覆盖的“责任区域” ( $r$ )，然后利用 MWRP-CP3 为瓶颈智能体重新规划覆盖 $r$ 的最优路径。
迭代：重复此过程，直到所有智能体的路径都经过优化。虽然不能保证全局最优，但能显著提升解的质量。

3. 主要贡献

MWRP-CP3：提出了一种新的最优搜索算法，通过单元格/路径支配剪枝、枢轴剪枝和并行计算，将搜索空间减少了 95% 以上，运行速度比现有最优算法快 200 倍以上。
MxWA：首次将加权 A 推广到多智能体最小化最大路径问题，并证明了其有界次优性。
新启发式与框架：提出了 SORC 和 MORC 启发式函数，以及一个通用的后处理框架，能够显著提升次优解的质量。
可扩展性：证明了次优算法能够解决比最优算法大 3 倍的地图（1500+ 单元格）和更多智能体（5+ 个）的问题。

4. 实验结果

状态空间缩减：在迷宫 (Maze) 和 Minecraft 风格地图上，CPD 方法将待覆盖单元格 $|U|$ 减少了 95.3% 和 89.0%。
运行时间对比：
- MWRP-CP3 在 32x32 迷宫地图上比 MWRP-A* 快 200 倍。
- 在 MWRP-A* 无法在 200 秒内解决的复杂实例上，MWRP-CP3 能够成功求解。
- 次优算法 (MxWA*, FS) 能够处理 1500+ 单元格和 5+ 智能体的大规模问题。
消融实验：
- 枢轴剪枝 (PP) 和平行启发式计算 (PHC) 均带来了显著加速，其中 PHC 的加速效果更稳定，而 PP 的效果随问题实例变化较大。
次优算法性能：
- 在权重 $w$ 较大时，MxWA* 比 FS 变体运行更快。
- Anytime 版本 (AMxWA*, AFS) 能随时间推移显著降低解的成本。
后处理效果：后处理框架仅增加了约 8% 的运行时间，但显著降低了路径成本。对于 MxWA* 生成的解，后处理效果最佳，甚至能接近最优解。

5. 意义与展望

实际意义：该研究解决了多智能体覆盖规划中“最优解计算不可行”的瓶颈，使得在真实世界的大规模环境（如灾难救援、消防巡逻）中实时或近实时地规划多智能体路径成为可能。
理论贡献：提出了针对 Makespan 目标的加权 A* 变体 (MxWA*) 和新的启发式策略，丰富了多智能体路径规划的理论体系。
未来工作：作者建议未来研究可探索更快的启发式函数、非网格图结构（如连续空间或复杂拓扑），以及考虑智能体间的碰撞和异构智能体场景。

总结：本文通过结合状态空间剪枝、启发式优化和次优搜索策略，成功地将多巡警路线问题从理论上的小规模求解推向了实际的大规模应用，为紧急响应和自动化巡检任务提供了强有力的算法支持。