Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem
Srikar Gouru, Ariel Felner, Jiaoyang Li · 2026
Read Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem by Srikar Gouru, Ariel Felner, Jiaoyang Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-15610.txt.
Introduction
Gouru, Felner, and Li tackle the Multiple Watchman Route Problem, finding paths for M watchmen so every map location falls under at least one watchman's view. Pruning areas guaranteed visible en route shrinks the search space, and their MWRP-CP3 optimal planner cuts it by more than 95 percent while running over 200 times faster than existing optimal methods. Suboptimal variants with quality bounds solve maps 3 times larger.
Catalog record
| CREATOR | Srikar Gouru, Ariel Felner, Jiaoyang Li |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42110 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.15610
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem Srikar Gouru, Ariel Felner, Jiaoyang Li Abstract In this paper, we tackle the Multiple Watchman Route Problem (MWRP), which aims to find a set of paths that M M watchmen can follow such that every location on the map can be seen by at least one watchman. First, we propose multiple methods to reduce the state space over which a search needs to be conducted by pruning map areas that are guaranteed to be seen en route to other areas. Next, we introduce MWRP-CP 3 , an efficient optimal planner that combines these methods with techniques that improve the quality and calculation time of existing heuristics. We present several suboptimal algorithms with bounds on solution quality, including MxWA * , a general variant of weighted A * for makespan problems. We also present anytime variations of our suboptimal algorithms, as well as techniques to improve an existing suboptimal solution by solving multiple decomposed sub-problems. We show that MWRP-CP 3 can reduce the search space by more than 95% and runs more than 200 × \times faster than existing optimal algorithms on 2D grid maps. We also show that our suboptimal algorithms solve maps 3 × \times larger than those solvable by MWRP-CP 3 . See mwrp-cp3.github.io for the open source codebase and video demonstrations. 1 Introduction Coverage Path Planning (CPP) is the task of computing a path that passes over every point in a given environment. CPP plays a vital role in emergency scenarios such as searching for survivors in disaster relief ( 6 ) and locating active wildfires ( 3 ) . Extensive research has been conducted for exploration in unknown environments including frontier-based ( 29 ) and sampling-based ( 26 ) algorithms. For CPP in known environments, methods such as cellular decomposition ( 11 ) and genetic algorithms ( 13 ) have been studied to compute optimal paths. However, these methods are designed for robots with a pre-determined coverage radius, such as lawnmowers and vacuums, rather than robots whose coverage may instead depend on visibility or line-of-sight. Specifically, we focus on the Watchman Route Problem (WRP) which requires a traveling agent, the watchman , to find the shortest path such that every point on the environment can be seen from at least one location on the path. WRP was first introduced by Chin and Ntafos, who presented an efficient solution for rectilinear polygons and proved that the problem was NP-hard in polygons with holes ( 5 ) . Since then, many problem variations have been introduced. The k -Watchman Route Problem ( k -WRP) ( 21 ) involves k traveling watchmen whose combined vision must encompass the entire environment, with the goal of minimizing either the longest watchman’s path ( min-max / makespan ) or the total path length ( min-sum ). Computing optimal paths for an arbitrary k watchmen was proven to be NP-hard for both the makespan ( 18 ) and min-sum ( 20 ) objectives in simple polygons. Moreover, WRP can be either anchored , in which the watchmen have predetermined starting locations, or floating , in which the watchman paths can start anywhere. Recently, a discrete variation of single-watchman WRP was introduced for arbitrary graphs, with a focus on 2D grid maps. Unlike the classic WRP and k -WRP problems, graph-based WRP works on an arbitrary Line-Of-Sight (LOS) function that determines which cells are visible from a given cell ( 25 ) . Additionally, graph-based WRP makes no prior assumptions on the environment geometry and the watchman’s LOS, allowing for complex problem instances to be modeled. The problem was proven to be NP-hard to solve optimally. Suboptimal algorithms have also been proposed ( 28 ) . Graph-based WRP has since been extended to the graph-based Multiple Watchman Route Problem (MWRP), in which every cell must be visible from at least one cell along at least one of the watchman paths ( 16 ) . A new variant of A * called MWRP-A * was introduced, which performs a joint-space heuristic search to compute an optimal set of paths for both the min-sum and makespan objectives. They were able to solve grids of up to 200 free cells and up to 6 agents in several seconds. However, MWRP-A * is infeasible for real-world scenarios where maps consist of thousands of cells. We focus on the makespan objective since most exploration problems are time-critical due to some emergency (i.e., disaster relief, firefighting). Our contributions are summarized as follows: 1. Optimal Search Algorithm: We present MWRP-CP 3 , which consists of methods for reducing the state space of the algorithm by determining that some cells in the map are strictly harder to see than others. Additionally, MWRP-CP 3 includes algorithmic enhancements that significantly improve heuristic quality and calculation time. 2. Bounded Suboptimal Search (BSS): We introduce Minimax Weighted A * (MxWA * ), a general variant of weighted A * ( 23 ) that efficiently computes bounded-quality solutions for makespan problems. Additionally, we introduce two heuristics that are used in conjunction with Focal Search ( 22 ) to solve the MWRP problem with makespan. We also formulate anytime variations for both algorithms. 3. Postprocessing Framework: We present a framework that efficiently improves the makespan of an existing suboptimal solution by partitioning the map into and solving fast, decomposed sub-problems for each agent. We show that MWRP-CP 3 can reduce the search space by more than 95% on complex maps and computes optimal paths more than 200 \times faster than existing baselines. We also show that our suboptimal algorithms scale in terms of map size (1,500+ grid cells) and agent count (5+ agents). 2 Background The WRP and MWRP problems can be represented as any graph structure ( 25 ; 16 ) , and all of our techniques and algorithms are generalizable to arbitrary graphs. For simplicity, we formulate the problem as a 2D grid graph composed of free and obstacle cells, a common approach in coverage-related problems. 2.1 Problem Formulation The MWRP problem is defined by the tuple (M,\mathcal{C},\mathcal{U},\mathcal{S},\mathcal{N},\mathcal{L},\mathcal{O}) , where M is the number of agents, \mathcal{C} is the set of free cells on the grid that the agents can be at, \mathcal{U}\subseteq\mathcal{C} is the set of cells that need to be seen by at least one of the agents, and \mathcal{S}=\{\mathcal{S}_{1},...,\mathcal{S}_{M}\} , where \mathcal{S}_{k}\in\mathcal{C} is the starting location of agent a_{k} . In general, \mathcal{U}=\mathcal{C} , however we separate these terms because we introduce certain subproblems where not every cell in \mathcal{C} needs to be explicitly seen. The neighbor function, \mathcal{N} , defines the cells that an agent can move to in a single action from a given cell, and the LOS function, \mathcal{L} , defines all cells visible to an agent from a given cell. Figure 1 (left) visualizes four-way movement , an example neighbor function, and Bresenham LOS , an example LOS function commonly used in computer graphics that simulates a continuous field-of-view in discrete maps ( 4 ) . We define the watchers function, \mathcal{W} , as the inverse of the LOS function, such that s_{2}\in\mathcal{L}(s_{1})\leftrightarrow s_{1}\in\mathcal{W}(s_{2})\,\forall\,s_{1},s_{2}\in\mathcal{C} . For many LOS functions, including Bresenham LOS, \mathcal{W} may not be symmetric,