💻 computer science

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

This paper introduces MWRP-CP3, an efficient optimal planner that utilizes state-space pruning and improved heuristics to solve the Multiple Watchman Route Problem with over 200x speedup, alongside scalable suboptimal algorithms with provable optimality bounds capable of handling maps three times larger.

Original authors: Srikar Gouru, Ariel Felner, Jiaoyang Li

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Srikar Gouru, Ariel Felner, Jiaoyang Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a security team. You have a large, complex building (like a maze or a castle) with many hidden corners, and you need to deploy a team of watchmen to patrol it.

Your goal is simple: Every single inch of the building must be visible to at least one watchman at some point.

But there's a catch: You don't just want any solution; you want the fastest possible solution. You want to know the minimum amount of time it takes for the slowest watchman to finish their route. If one watchman has to walk 100 steps and the others only walk 10, your team isn't "done" until that one person finishes. This is called the Multiple Watchman Route Problem (MWRP).

This paper introduces a new set of tools to solve this puzzle much faster than before. Here is how they did it, explained with everyday analogies.

1. The Problem: Why is this so hard?

Think of the building as a giant grid of tiles. If you have 5 watchmen, the computer has to figure out where all five of them should be at the same time, step by step.

The Old Way: Imagine trying to solve a 5-dimensional Rubik's cube. The computer would try millions of combinations, checking if every corner is seen. It's like trying to find a needle in a haystack while the haystack keeps growing. For big maps, this takes forever.
The Goal: The authors wanted to make this search so fast that it could handle real-world emergencies, like finding survivors in a collapsed building or spotting wildfires.

2. The Solution: "MWRP-CP3" (The Smart Optimizer)

The authors built a super-smart planner called MWRP-CP3. Think of it as a genius tour guide who knows exactly which paths are useless before you even start walking. They used three main tricks to speed things up:

A. The "Shadow" Trick (State Space Reduction)

Imagine you are walking down a hallway. If you look left and see a dark corner, you automatically see the floor right next to it. You don't need to walk to that floor to see it; seeing the corner covers it.

The Trick: The algorithm realizes that some spots in the building are "dominated" by others. If you see Spot A, you automatically see Spot B.
The Result: The computer stops wasting time trying to figure out how to see Spot B. It just says, "If we see A, B is covered." This cuts the number of possibilities the computer has to check by 95%. It's like realizing you don't need to check every single grain of sand on a beach because if you check the top layer, you know the bottom is covered too.

B. The "Shortcut" Trick (Pivot Pruning)

When calculating the best route, the computer sometimes picks "checkpoints" (pivots) to ensure nothing is missed. Sometimes, it picks a checkpoint that actually makes the route longer because it forces a detour.

The Trick: The algorithm looks at these checkpoints and asks, "Does this checkpoint actually help, or is it just a detour?" If a checkpoint is just a shortcut that confuses the math, the algorithm removes it.
The Result: The computer stops trying to solve unnecessary detours, making the calculation much snappier.

C. The "Assembly Line" Trick (Parallel Heuristics)

Usually, a computer solves one problem, then the next, then the next.

The Trick: The authors made the computer work like a factory assembly line. While it is finishing the calculation for the current best path, it is already calculating the next 100 potential paths in the background.
The Result: The computer never sits idle. It's always working ahead, which makes the whole process incredibly fast.

The Bottom Line: Their new planner is 200 times faster than the old best method. It can solve maps that were previously impossible to solve in a reasonable time.

3. The "Good Enough" Solutions (Bounded Suboptimal Algorithms)

Sometimes, you don't need the perfect solution; you just need a very good one, and you need it right now.

The Analogy: Imagine you are late for a flight. You don't need the absolute shortest path to the gate; you just need a path that gets you there in 15 minutes instead of 20.
The Tool: They created "MxWA*" and "Focal Search." These are like a GPS that says, "I can't guarantee the absolute shortest route, but I promise the route I give you won't be more than 20% longer than the best one."
The Benefit: These algorithms can handle maps 3 times larger than the perfect planner can. They are the "speed demons" of the group.

4. The "Polish" (Postprocessing)

Imagine you have a team of runners. You've assigned them routes, but one guy is running way too far while the others are resting.

The Trick: The authors built a "polishing" tool. It looks at the finished plan, finds the person with the longest route, and asks, "Can we give you a shorter path without leaving any dark corners unlit?"
The Result: It takes a "good enough" plan and tweaks it to make it almost perfect, often in just a few seconds.

Summary

This paper is about teaching computers how to be smarter security guards.

Don't look at everything: Ignore the things you can see just by looking at something else (Cell Dominance).
Don't take detours: Remove unnecessary checkpoints (Pivot Pruning).
Work faster: Do many calculations at once (Parallelism).
Be flexible: If you can't find the perfect answer instantly, find a "very good" one quickly and polish it later.

Thanks to these methods, we can now plan complex security routes for huge areas in seconds, which is a huge step forward for emergency response, robotics, and exploration.

1. Problem Definition

The paper addresses the Multiple Watchman Route Problem (MWRP), a generalization of the classic Watchman Route Problem (WRP).

Objective: Find a set of paths for $M$ agents (watchmen) in a known environment (modeled as a 2D grid graph) such that every cell in a target set $U$ is visible from at least one cell along at least one agent's path.
Optimization Goal: The primary focus is the Makespan objective (min-max), which seeks to minimize the length of the longest path among all agents. This is critical for time-sensitive applications like disaster relief and firefighting.
Constraints:
- Visibility: Defined by a Line-of-Sight (LOS) function (e.g., Bresenham LOS), which determines which cells are visible from a given cell.
- Collisions: The paper assumes agents can occupy the same cell (no inter-agent collision constraints) to focus on the complexity of the coverage/visibility aspect.
- Complexity: The problem is proven to be NP-hard.

2. Methodology

The authors propose a suite of algorithms ranging from exact optimal solvers to bounded suboptimal methods and post-processing techniques.

A. Optimal Search: MWRP-CP3

The core contribution is MWRP-CP3, an enhanced optimal search algorithm based on the existing MWRP-A* (joint-space A*). It introduces four key innovations to drastically reduce search space and computation time:

State Space Reduction (Cell & Path Dominance):
- Cell Dominance (CD): Identifies cells $s_1$ and $s_2$ where the set of watchers for $s_1$ is a subset of the watchers for $s_2$ ( $W(s_1) \subseteq W(s_2)$ ). If $s_1$ is seen, $s_2$ is guaranteed to be seen. $s_2$ is pruned from the target set $U$ .
- Path Dominance (PD): Identifies cells $s_1$ and $s_2$ where any path to see $s_1$ necessarily passes through a location that sees $s_2$ . $s_2$ is pruned.
- Impact: These methods reduce the residual set $U$ (the set of cells needing coverage) by over 95% on structured maps, significantly shrinking the state space $O(|C|^M 2^{|U|})$ .
Pivot Pruning:
- The heuristic relies on solving a Multiple Traveling Salesman Problem (mTSP) on a graph of "pivots" (key cells to be seen).
- The authors introduce a greedy removal strategy to eliminate pivots that act as "shortcuts" in the mTSP graph. Removing these pivots often increases the heuristic value (making it more informative) without sacrificing admissibility, leading to faster convergence.
Parallel Heuristic Calculation:
- The mTSP heuristic calculation is the primary bottleneck. The authors implement Batch A, where the heuristic for the next $N$ nodes to be expanded is computed in parallel. This utilizes modern multi-core processors without changing the asymptotic complexity of A.

B. Bounded Suboptimal Search (BSS)

To scale to larger maps where optimal search is infeasible, the paper introduces algorithms that guarantee a solution within a factor $w$ of the optimal cost ( $C \le w \cdot C^*$ ).

Minimax Weighted A (MxWA):**
- A novel variant of Weighted A* tailored for the makespan objective.
- Instead of weighting the sum of costs, it calculates $f_{MxW}(n) = \max_k \{ g_k(n) + w \cdot h_k(n) \}$ , where $k$ represents each agent.
- This prioritizes agents with lower remaining search effort while maintaining the $w$ -suboptimality bound.
- Includes an Anytime version (AMxWA*) that iteratively improves the solution.
Focal Search (FS) with New Heuristics:
- Utilizes a secondary heuristic ( $h_{FOCAL}$ ) to select nodes from a "Focal" list.
- Proposes two new heuristics for MWRP: Sum of Remaining Costs (SORC) and Max of Remaining Costs (MORC) based on the mTSP path lengths.
- Also includes an Anytime variant (AFS).

C. Postprocessing Framework

Takes an existing suboptimal solution and decomposes the problem.
Identifies the agent with the longest path ( $a_{max}$ ) and calculates the "minimum responsibility" (cells only visible to $a_{max}$ in the current solution).
Re-solves a single-agent optimal path for $a_{max}$ restricted to these specific cells.
Iterates until no further improvement is found. This significantly improves solution quality with minimal runtime overhead.

3. Key Contributions

MWRP-CP3: The first optimal solver capable of handling complex MWRP instances on maps with thousands of cells, running 200× faster than previous baselines (MWRP-A*).
MxWA:* The first application of Weighted A* specifically adapted for the makespan objective in joint-space search, providing provable bounded suboptimality.
Scalability: Demonstrated ability to solve maps with 1,500+ grid cells and 5+ agents, whereas previous optimal methods were limited to ~200 cells.
Efficiency Techniques: Validated that Cell/Path Dominance and Pivot Pruning are critical for reducing the search space, while Parallel Heuristic Calculation addresses the computational bottleneck.

4. Experimental Results

State Space Reduction: On structured maps (Mazes, Minecraft-inspired), Cell and Path Dominance reduced the target set $U$ by 95.3% and 89.0% respectively.
Runtime Performance:
- MWRP-CP3 solved instances 200× faster than MWRP-A*.
- It solved complex instances that MWRP-A* failed to solve within a 200-second time limit.
Suboptimal Scaling:
- MxWA* and Focal Search variants solved maps 3× larger than what MWRP-CP3 could handle.
- MxWA* generally outperformed Focal Search on larger agent counts due to the overhead of managing the Focal list in high-dimensional joint spaces.
Postprocessing: Improved solution costs significantly (e.g., reducing MxWA* cost from 124 to 93 on a test case) with only an 8% increase in total runtime.
Anytime Behavior: All anytime variants (AMxWA*, AFS) showed rapid initial solution generation followed by steady quality improvement.

5. Significance

This work bridges the gap between theoretical optimality and practical scalability for multi-agent coverage problems.

Real-World Applicability: By enabling the solution of large-scale maps (thousands of cells) in seconds, the algorithms make optimal or near-optimal planning feasible for real-time emergency scenarios (e.g., search and rescue, wildfire monitoring).
Theoretical Advancement: The introduction of MxWA* extends the applicability of weighted search heuristics to min-max objectives, a domain where standard Weighted A* is not directly applicable.
Open Source: The authors provide a public codebase and video demonstrations, facilitating further research and adoption in the robotics and AI communities.

In summary, the paper presents a comprehensive framework that combines mathematical pruning, algorithmic enhancements, and parallel computing to solve a notoriously hard NP-hard problem at a scale previously unattainable.