Paper deep dive
Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem
Srikar Gouru, Ariel Felner, Jiaoyang Li
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 97%
Last extracted: 6/21/2026, 11:48:30 AM
Summary
The paper presents MWRP-CP3, an efficient optimal planner for the Multiple Watchman Route Problem (MWRP), which aims to find paths for M watchmen to cover all locations on a map. The authors introduce state-space reduction techniques including Cell Dominance (CD) and Path Dominance (PD) to prune unnecessary cells. They also introduce MWRP-CP3, which incorporates these methods with pivot pruning and parallel heuristic calculation to significantly outperform existing algorithms. The paper also presents MxWA*, a bounded suboptimal algorithm for the makespan objective, and a postprocessing framework to improve suboptimal solutions.
Entities (7)
Relation Signals (4)
MWRP-CP3 → implements → Cell Dominance
confidence 100% · MWRP-CP3, which is MWRP-A* with Cell and Path dominance, Pivot pruning, and Parallel heuristic calculation.
MWRP-CP3 → implements → Path Dominance
confidence 100% · MWRP-CP3, which is MWRP-A* with Cell and Path dominance, Pivot pruning, and Parallel heuristic calculation.
MxWA* → solves → makespan
confidence 100% · including MxWA*, a general variant of weighted A* for makespan problems.
MWRP-A* → solves → Multiple Watchman Route Problem
confidence 100% · A new variant of A* called MWRP-A* was introduced, which performs a joint-space heuristic search to compute an optimal set of paths
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In this paper, we tackle the Multiple Watchman Route Problem (MWRP), which aims to find a set of paths that 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-CP3, 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-CP3 can reduce the search space by more than 95% and runs more than 200x faster than existing optimal algorithms on 2D grid maps. We also show that our suboptimal algorithms solve maps 3x larger than those solvable by MWRP-CP3. See this http URL for the open source codebase and video demonstrations.
Tags
Links
- Source: https://arxiv.org/abs/2604.15610v1
- Canonical: https://arxiv.org/abs/2604.15610v1
Trouble viewing inline? Open PDF directly →
Full Text
49,900 characters extracted from source content.
Expand or collapse full text
Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem Srikar Gouru1, Ariel Felner2, Jiaoyang Li1 Abstract In this paper, we tackle the Multiple Watchman Route Problem (MWRP), which aims to find a set of paths that 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-CP3, 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-CP3 can reduce the search space by more than 95% and runs more than 200× faster than existing optimal algorithms on 2D grid maps. We also show that our suboptimal algorithms solve maps 3× larger than those solvable by MWRP-CP3. 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 (Cho et al. 2021) and locating active wildfires (Bezas et al. 2022). Extensive research has been conducted for exploration in unknown environments including frontier-based (Yamauchi 1997) and sampling-based (Steinbrink et al. 2021) algorithms. For CPP in known environments, methods such as cellular decomposition (Huang 2001) and genetic algorithms (Jimenez et al. 2007) 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 (Chin and Ntafos 1988). Since then, many problem variations have been introduced. The k-Watchman Route Problem (k-WRP) (Packer 2008) 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 (Mitchell and Wynters 1991) and min-sum (Nilsson 1995) 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 (Seiref et al. 2020). 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 (Yaffe et al. 2021). 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 (Livne et al. 2023). 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-CP3, 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-CP3 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* (Pohl 1970) that efficiently computes bounded-quality solutions for makespan problems. Additionally, we introduce two heuristics that are used in conjunction with Focal Search (Pearl and Kim 1982) 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-CP3 can reduce the search space by more than 95% on complex maps and computes optimal paths more than 200× 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 (Seiref et al. 2020; Livne et al. 2023), 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,,,,,ℒ,)(M,C,U,S,N,L,O), where M is the number of agents, C is the set of free cells on the grid that the agents can be at, ⊆U is the set of cells that need to be seen by at least one of the agents, and =1,…,MS=\S_1,...,S_M\, where k∈S_k is the starting location of agent aka_k. In general, =U=C, however we separate these terms because we introduce certain subproblems where not every cell in C needs to be explicitly seen. The neighbor function, N, defines the cells that an agent can move to in a single action from a given cell, and the LOS function, ℒ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 (Bresenham 1965). We define the watchers function, W, as the inverse of the LOS function, such that s2∈ℒ(s1)↔s1∈(s2)∀s1,s2∈s_2 (s_1) s_1 (s_2)\,∀\,s_1,s_2 . For many LOS functions, including Bresenham LOS, W may not be symmetric, meaning there is no guarantee that (s)=ℒ(s)W(s)=L(s). We define d(s1,s2)d(s_1,s_2) as the length of the shortest traversable path between s1s_1 and s2s_2. A solution to the MWRP problem must be a set of paths =π1,…,πM π=\ _1,..., _M\, where each path πk _k is a list of cells that agent aka_k traverses starting at kS_k and following the movement constraints defined by N. A set of paths, π, is a solution to the problem if every cell in U is seen during at least one agent’s path. That is, defining the function ()=⋃πkP( π)= \, _k, π is a solution if (s)∩()≠∅W(s)\, ( π)≠ for every cell s∈s . The cost of a path is its length, defined as c(πk)=|πk|c( _k)=| _k|. O is the makespan objective function, defined as ()=maxπk∈c(πk)O( π)= _ _k∈ πc( _k). Figure 1: Examples of four-way movement (top left), Bresenham LOS (bottom left), an MWRP problem with the optimal makespan solution (middle), an example scenario for the mTSP heuristic (top right), and its corresponding G_DLS (bottom right). The legend applies to all figures in this paper. Because exploration problems generally require few agents searching over a large area, we assume that each cell s∈s can hold all M agents, and thus we do not consider agent-agent collisions for our solution. This assumption was also used in previous work (Livne et al. 2023). The problem is solved once offline, and we assume perfect information regarding the map structure and agent starting locations. Figure 1 (middle) shows an example problem and a makespan-optimal solution on a 32×32 Maze map with 3 agents. 2.2 MWRP-A* Algorithm In this section we summarize the MWRP-A* algorithm by Livne et al., a variation of joint-space A* that optimally solves the MWRP problem (Livne et al. 2023). Node: Each node in the search tree consists of a list of tuples, (sk,ck)(s_k,c_k), representing the current location and the cumulative cost for agent aka_k. Additionally, each node keeps track of its residual set R⊆R , which is the set of residual (or remaining) cells that need to be seen. The cost of the node is maxkck _k\c_k\. Root node: The tuples are (k,0)(S_k,0) for each agent aka_k, and the residual set, R=∖⋃ℒ(Sk)R=U\ (S_k), represents the residual cells not visible from any agent’s starting location. Goal node: Any node where R=∅R= is considered a goal node. Successors Successor nodes are generated using a joint-space expansion. To avoid generating nodes where agents do not see any new cells, MWRP-A* utilizes the Expanding Borders mechanism, which finds nearby cells for each agent that have LOS to a previously unseen residual cell. These new cells, along with the cumulative cost to reach them, are the successor states of the agent. Each agent also has the option to terminate, which removes it from the set of agents in the successor node. The successor nodes are the Cartesian product of the successor states for each agent. In each successor node, R is computed by copying R from the parent node and removing cells that the agents have LOS to from their new locations. Node Dominance To avoid unnecessary re-expansions, dominated nodes are pruned out during the search. Node n dominates node n′n if (1) all of their agent locations are equal (n.sk=n′.skn.s_k=n .s_k), (2) the residual set for node n is a subset of the residual set for node n′n (n.R⊆n′.Rn.R n .R), and (3) the cumulative cost for each agent in node n is less than or equal to the cumulative cost in node n′n (n.ck≤n′.ckn.c_k≤ n .c_k). Lazy Heuristic Evaluation Nodes are initially inserted into the OPEN list with their f-value calculated using the Singleton heuristic. If a node is popped from OPEN for the first time, a more informed f-value is calculated using the multiple Traveling Salesman Problem (mTSP) heuristic, and the node is re-inserted into OPEN with its new f-value. When a node is popped from OPEN for the second time, it is expanded and successors are generated. Singleton Heuristic The Singleton heuristic defines fs=minkck+ws,kf_s= _k\c_k+w_s,k\ as the lowest agent cost at which cell s can be seen, where ws,kw_s,k is the minimum cost for agent aka_k to reach a watcher of s. Since every cell in R must be seen, the admissible Singleton f-value is maxfs \f_s\ among all s∈Rs∈ R. mTSP Heuristic First, a set of pivots is selected from R such that no two pivots share any watchers. Next, a graph G_DLS is constructed, where each vertex vpv_p in G_DLS corresponds to pivot p, and each vertex vav_a corresponds to agent a. Since any solution requires all pivots to be seen by at least one agent, the heuristic is computed by solving mTSP on the graph G_DLS, where each vertex vpv_p must be reached by at least one agent, with the agents starting at vav_a. For the heuristic to be admissible, edges in G_DLS are calculated with underestimated costs. Edge costs from agent vertices vav_a to pivot vertices vpv_p are calculated as the minimum distance between agent a and any watcher of pivot w∈(p)w (p). Edge costs from pivot vertices vpiv_p_i to other pivot vertices vpjv_p_j are calculated as the minimum distance between any watcher wi∈(pi)w_i (p_i) and any watcher wj∈(pj)w_j (p_j), as a lower bound on the travel distance to go from seeing pivot pip_i to pivot pjp_j. Figure 1 (top right) shows an example search node with a single agent a, pivots p1p_1 and p2p_2, and the corresponding G_DLS (bottom right). The closest distance from agent a to a watcher of p1p_1 (labeled w1w_1) is 5, and the closest distance from agent a to a watcher of p2p_2 (labeled w2w_2) is 7. Additionally, the closest distance from any watcher of p1p_1 to any watcher of p2p_2 is 2 (the distance from w1w_1 to w2w_2), thus resulting in the G_DLS graph shown in Figure 1 (bottom right). Defining hkh_k as the path length of each agent aka_k on G_DLS, solving mTSP to minimize minck+hk \c_k+h_k\ (Gavish 1976) results in an admissible f-value. However, this f-value is not consistent, so we utilize the pathmax technique to ensure consistency by setting f(n)=maxf(n),f(np)f(n)= \f(n),f(n_p)\, where npn_p is node n’s parent during the A* search (Mero 1984). 3 MWRP-CP3 This section describes our optimal search algorithm, MWRP-CP3, which is MWRP-A* with Cell and Path dominance, Pivot pruning, and Parallel heuristic calculation. We first introduce cell and path dominance, two methods for reducing the algorithm’s state space. Then, we introduce pivot pruning and parallel heuristic calculation, two enhancements that directly speed up the original MWRP-A* algorithm. 3.1 State Space Reduction Each node in the search space is uniquely defined by the location of each agent, which is a cell in C, and the residual set R, which is a subset of U. Thus, the state space is O(||M2||)O(|C|^M2^|U|). We introduce cell and path dominance, two methods to reduce U by identifying cells that can be ignored during the search, a process that we call cell pruning. We prove that both methods do not alter the set of possible solutions, thus preserving the algorithm’s optimality guarantees. Cell Dominance (a) (b) (c) Figure 2: Figures(a) and (b) show the watchers (yellow) of cells s1s_1 and s2s_2 (purple), respectively. The cells are also watchers of themselves. Figure(c) shows an example with an agent (green) where s3s_3 is along the agent’s path to s4s_4. The first method, cell dominance (CD), stems from the observation that some cells are guaranteed to be seen when an agent sees other cells, no matter where the agent is. Intuitively, looking at the example shown in Figure 2(a) and (b), it is impossible to see s1s_1 without also seeing s2s_2. Formally, this is because the watchers of s1s_1 are a subset of the watchers of s2s_2. Thus, no matter what watcher of s1s_1 an agent sees the cell from, it simultaneously sees s2s_2. We refer to this property as cell dominance, specifically that s1s_1 dominates s2s_2. During our search, we ignore s2s_2, since seeing s1s_1 must also result in seeing s2s_2. Theorem 1 proves that cell dominance does not sacrifice optimality. Theorem 1. Given a cell sj∈s_j , if there exists another cell si∈s_i such that (si)⊆(sj)W(s_i) (s_j), then any solution π that sees ∖sjU \s_j\ also sees U. Proof. Let π be any solution that sees every cell in ∖sjU\, \,\s_j\. Since si∈∖sjs_i \s_j\, the solution must include a watcher of sis_i, so there exists a cell k∈()∩(si)k ( π)\,∩\,W(s_i). Since (si)⊆(sj)W(s_i) (s_j), it must be that k∈(sj)k (s_j), thus π sees sjs_j. ∎ Algorithm 1 Cell Dominance (CD) Input: ,W,U Output: Updated U with dominated cells pruned 1: for si∈s_i do 2: for sj∈∖sis_j \s_i\ do 13: if (si)⊆(sj)W(s_i) (s_j) then =∖sjU=U \s_j\; 4: return U; In Algorithm 1, we loop through every pair of unseen cells (lines 1-2) and prune one of them if it is dominated by the other (line 3). Since each cell has at most |||C| watchers, the runtime complexity of CD is O(||||2)O(|C||U|^2). CD is executed once per problem instance to compute the updated U prior to running the A* algorithm discussed in Section 2.2. Path Dominance The second method, path dominance (PD), stems from the idea that given the starting locations of the agents, the agents are guaranteed to see some cells on the way to seeing other cells. In the example shown in Figure 2(c), s3s_3 lies on the agent’s path to seeing s4s_4, and it is impossible to see s4s_4 without seeing s3s_3 first. Thus, for any pair of distinct cells sis_i and sjs_j in U, if all the paths to seeing sis_i require the agent to also see sjs_j, then we can safely ignore sjs_j during our search, since any solution that sees sis_i is guaranteed to also see sjs_j. We call this behavior path dominance, specifically that sis_i dominates sjs_j. For a cell sj∈s_j , we determine if another cell si∈s_i dominates it by performing a multi-source breadth-first search (BFS), starting at S, to find all cells that can be reached by at least one agent without seeing sjs_j. If there is some cell sis_i such that no watcher of sis_i is in , then sis_i dominates sjs_j. Theorem 2 proves that path dominance does not sacrifice optimality. Theorem 2. Given a cell sj∈s_j , we define Π as the set of all paths that originate at the starting location of an agent and do not see sjs_j from any cell along the path. We also define =⋃πi∈Ππi = _ _i∈ _i as the set of cells that is in at least one path in Π . If there exists a cell si≠sjs_i≠ s_j such that (si)∩=∅W(s_i)\,∩\, = , then any solution π that sees ∖sjU \s_j\ also sees U. Proof. Let π be any solution that sees every cell in ∖sjU \s_j\. Since si∈∖sjs_i \s_j\, there exists a watcher k∈(si)k (s_i) that was visited by at least one agent, so k∈πak∈ _a for some πa∈ _a∈ π. Since (si)∩=∅W(s_i)\,∩\, = , we know k∉k∉ . This means that πa∉Π _a∉ , so πa _a must have seen sjs_j along its path. ∎ Algorithm 2 subgraphBFS Input: ,,′S,N,C Output: containing all reachable cells within ′C 1: Q=Q=S; 2: =∅ = ; 3: while Q≠∅Q≠ do 4: s=Q.pop()s=Q.pop(); 25: if s∈s∈ or s∉′s then continue ; 6: =∪s = ∪ s; 37: for n∈(s)n (s) do Q=Q∪nQ=Q∪ n; 8: return ; Algorithm 3 Path Dominance (PD) Input: ,,,W,N,U,S Output: Updated U with dominated cells pruned 1: for sj∈s_j do 2: ′=∖(sj)C =C (s_j); 3: = = subgraphBFS(,,′S,N,C ); 4: for si∈∖sjs_i \s_j\ do 5: if (si)∩=∅W(s_i)∩ = then 6: =∖sjU=U \s_j\; 7: break; 8: return U; First, we introduce subgraphBFS (Algorithm 2), a modified floodfill algorithm that only expands cells within a given cell set ′C (line 5). The method returns all cells in ′C reachable from S and has a runtime complexity of O(|′|)O(|C |). In Algorithm 3 we describe the PD algorithm, in which we loop through all cells sj∈s_j to determine if sjs_j is path dominated by any other cell sis_i. First, we compute ′C , the subset of C with all watchers of sjs_j removed (line 2). Then we call subgraphBFS on ′C to compute , the set of cells that an agent can reach while avoiding LOS to sjs_j (line 3). If there is a cell sis_i that has no watchers in , then sis_i dominates sjs_j, so sjs_j is pruned (lines 4-6). The runtime complexity for this check is O(||||)O(|C||U|), which dominates the O(||)O(|C|) runtime of the subgraphBFS algorithm. Thus, like CD, the runtime complexity of the PD algorithm is O(||||2)O(|C||U|^2). PD is run once per problem instance to compute the updated U prior to running the A* algorithm discussed in Section 2.2. Figure 3: Comparison of state space reduction showing cells removed by cell dominance (orange only) and path dominance (orange + blue) on a Maze map (top left) (Stern et al. 2019), a randomized map (bottom left), and a Minecraft-inspired map (right) (Chong et al. 2024). We also note that the set of cells pruned by CD is a subset of those pruned by PD. If sis_i dominates sjs_j in CD, then there exists no cell from which we can see sis_i without also seeing sjs_j, thus sis_i dominates sjs_j in PD as well. Figure 3 visualizes the cells dominated by CD and PD. Our experiments show that CD generally runs faster than PD due to time-intensive BFS computation in PD. Thus, we first run CD followed by PD, reducing the cells that PD needs to loop through. We call this method cell and path dominance (CPD). 3.2 Pivot Pruning (a) (b) (c) (d) (e) (f) Figure 4: Examples where pivot pruning improves (top) and worsens (bottom) the heuristic. In Figures(b) and (e), the top graph corresponds to the left Figures(a/d), and the bottom graph corresponds to right Figures(c/f). Next, we describe an algorithmic enhancement to MWRP-A*. When computing the mTSP heuristic, we know that any set of pivots, where no two pivots share watchers, results in an admissible mTSP heuristic. MWRP-A* greedily uses as many pivots as possible. However, consider the example shown in Figure 4(a). From agent a, the closest watcher of p1p_1 is w1w_1, 15 cells away, and the closest watcher of p2p_2 is w3w_3 5 cells away. Additionally, the closest watchers between p1p_1 and p2p_2, w1w_1 and w2w_2, are 2 cells apart. This results in the graph G_DLS shown in Figure 4(b) (top graph). The mTSP heuristic solved on G_DLS results in the path a→p2→p1a→ p_2→ p_1, with a heuristic value of 5+2=75+2=7. However, if we remove p2p_2 (Figure 4(c)), then the only edge is a→p1a→ p_1 (Figure 4(b), bottom graph), and solving mTSP gives a heuristic value of 1515. We call this behavior shortcut removal, since p2p_2 provides a shortcut between a and p1p_1. To maximize the admissible heuristic value, we greedily remove pivots that may provide shortcuts in the mTSP solution. The shortcut that pivot pip_i provides between agent aka_k and pivot pjp_j is s(pi,pj,ak)=e(ak,pj)−(e(ak,pi)+e(pi,pj))s(p_i,p_j,a_k)=e(a_k,p_j)-(e(a_k,p_i)+e(p_i,p_j)), where e is the distance between two vertices in G_DLS. We use a while loop to repeatedly prune out the pivot that provides the largest shortcut between agents and other pivots until no more pivots provide a positive shortcut. Pivot pruning has a runtime complexity of O(MP3)O(MP^3) where P is the number of pivots. Pivot pruning is run for every mTSP heuristic calculation prior to running the mTSP solver. Pivot pruning is not guaranteed to increase the heuristic value, and in some cases may even reduce the informativeness of the heuristic. An example is shown in Figure 4(d-f), where removing pivot p3p_3, which provides a shortcut from a to p2p_2, worsens the overall mTSP heuristic from 1111 to 99. However, our experiments show that it provides a significant speedup. 3.3 Parallel Heuristic Calculation Despite using lazy heuristic evaluation for A* expansions, the majority of the time overhead in MWRP-A* comes from the mTSP heuristic calculation. Parallelization algorithms for lazy heuristics have been explored for large-scale multiprocessing (Mukherjee et al. 2022), however these methods require constantly running asynchronous processes. Instead, we use Batch A* (Li et al. 2022; Agostinelli et al. 2019), which is often used to parallelize the calculation of neural network heuristics. During each expansion cycle of A*, we first check if the next node to be popped has had its mTSP heuristic computed. If not, we parallelize the computation by looping through the next N nodes that are going to be popped from OPEN and accumulating the nodes that have not yet had their mTSP heuristic computed into a batch. We then compute the mTSP heuristic for the batch in parallel and update each node’s f-value in OPEN. Since N is a constant, the runtime complexity of A* is not changed. Larger N values will parallelize more heuristic calculations, but may execute more unnecessary computations, since there is no guarantee that all of these nodes would have been expanded. We use N=100N=100 in our experiments. As proven above, MWRP-CP3 is guaranteed to return an optimal solution. Notably, while our focus is the makespan objective, MWRP-CP3 makes no assumptions on the objective function and is thus optimal for graph-based WRP and MWRP with either the sum-of-costs or makespan objective. 4 Bounded Suboptimal Methods Bounded Suboptimal Search (BSS) algorithms are a class of search methods that, given a weight w≥1w≥ 1, guarantee a solution with cost C≤C∗⋅wC≤ C^*· w, where C∗C^* is the cost of the optimal solution. We present two BSS algorithms that are used to scale MWRP-CP3 to larger maps and agent counts. 4.1 Minimax Weighted A* (MxWA*) A popular BSS variant of A* is weighted A* (WA*) (Pohl 1970). In WA*, the f-value is altered to fw(n)=g(n)+w⋅h(n)f_w(n)=g(n)+w· h(n), where g(n)g(n) is the cost to reach node n and h(n)h(n) is an admissible heuristic. WA* has previously been applied to the graph-based WRP problem with WRP-A* (Yaffe et al. 2021). To our knowledge, WA* has not been applied to makespan problems with joint-space search. Figure 5: Two example search nodes, each with the agent costs (gkg_k) and estimates on the remaining search efforts (hkh_k). We propose Minimax Weighted A* (MxWA*), a WA* variant specifically for the makespan objective. The goal is to prioritize agents with lower search effort while ensuring that the solution found is still bounded suboptimal. MxWA* first obtains a weighted fkf_k-value for each agent aka_k. Then, the maximum of these fkf_k-values is used as the w-admissible f-value during the search. That is, MxWA* performs the A* search with the f-value fMxW(n)=maxkgk+w⋅hkf_MxW(n)= _k\g_k+w· h_k\. For example, consider nodes a and b shown in Figure 5. Node a has g(a)=maxg1,g2=50g(a)= \g_1,g_2\=50 and admissible f(a)=maxg1+h1,g2+h2=50f(a)= \g_1+h_1,g_2+h_2\=50. Similarly, node b has g(b)=maxg1,g2=45g(b)= \g_1,g_2\=45 and admissible f(b)=maxg1+h1,g2+h2=55f(b)= \g_1+h_1,g_2+h_2\=55. In A*, node a is expanded first since it has a lower f-value. However, using MxWA*, we generate f(a)=max50+w⋅0,10+w⋅40=10+w⋅40f_MxW(a)= \50+w· 0,10+w· 40\=10+w· 40 and f(b)=max35+w⋅5,45+w⋅10=45+w⋅10f_MxW(b)= \35+w· 5,45+w· 10\=45+w· 10. Thus, with w≥1.2w≥ 1.2, node b would be expanded first, which is preferred since it has lower h-values and thus has a lower remaining search effort. We now prove that MxWA* is w-suboptimal. Theorem 3. Given agent costs gk(n)g_k(n) and estimates of agent cost-to-go of hk(n)h_k(n), performing A* search with f(n)=maxigk()+w⋅hk(n)f_MxW(n)= _i\g_k()+w· h_k(n)\ returns a solution with cost C≤w⋅C∗C≤ w· C^*, where C∗C^* is the cost of the optimal solution. Proof. We define the last node expanded during the search as node G with solution cost C. Let P∗P^* be the optimal search path with cost C∗C^*, and let n be the last node on P∗P^* that is in OPEN. Since G was expanded before n, we know that f(G)≤f(n)f_MxW(G)≤ f_MxW(n), and since hk(G)=0h_k(G)=0 for each agent aka_k, f(G)=g(G)f_MxW(G)=g(G), so g(G)≤f(n)=maxkgk(n)+w⋅hk(n)≤maxkw⋅gk(n)+w⋅hk(n)=w⋅f(n)g(G)≤ f_MxW(n)= _k\g_k(n)+w· h_k(n)\≤ _k\w· g_k(n)+w· h_k(n)\=w· f(n). This means g(G)≤w⋅f(n)g(G)≤ w· f(n). Since f(n)f(n) is admissible and n is on P∗P^*, we know f(n)≤C∗f(n)≤ C^*, meaning g(G)=C≤w⋅C∗g(G)=C≤ w· C^*. ∎ In each node, gkg_k is the cumulative cost of agent aka_k. For the Singleton heuristic, hs,kh_s,k is the distance from agent aka_k to the nearest watcher of s. Using MxWA*, fs,MxW=minkgk+w⋅hs,kf_s,MxW= _k\g_k+w· h_s,k\ is a w-admissible f-value, so fMxW=maxsfs,MxWf_MxW= _s\f_s,MxW\. For the mTSP f-value, hkh_k is agent aka_k’s path length along G_DLS, so we compute f_MxW by minimizing maxkgk+w⋅hk _k\g_k+w· h_k\ as the mTSP objective function. In the single-agent case, MxWA* is identical to WA*. Additionally, following techniques from Anytime Weighted A* (Hansen and Zhou 2007), we extend MxWA* to Anytime MxWA* (AMxWA*). AMxWA* continues to search for better solutions even after an initial solution was found. If B is the cost of the best solution found by the search thus far, then AMxWA* prunes nodes n with maxf(n)w,g(n)≥B \ f_MxW(n)w,g(n)\≥ B, since f(n)w f_MxW(n)w is guaranteed to be admissible. This forces future solutions to improve on the current best solution. 4.2 Focal Search The second BSS method utilizes Focal Search (FS), which uses both an admissible heuristic h(n)h(n) and a second, not necessarily admissible, heuristic h(n)h_FOCAL(n) that serves as a better estimate of search effort (Pearl and Kim 1982). FS maintains the OPEN list from A* as well as a separate FOCAL list. FOCAL contains the subset of nodes n in OPEN with f(n)≤w⋅fminf(n)≤ w· f_min, where fminf_min is the current minimum f-value in OPEN. Each iteration, the node with the lowest h(n)h_FOCAL(n) value from FOCAL is expanded. Since we use lazy heuristic evaluation in OPEN, we need to recompute the heuristic of some nodes before inserting them into FOCAL. Each A* expansion cycle, all nodes n in OPEN that were inserted with the Singleton f-value f(n)≤w⋅fminf(n)≤ w· f_min are popped and reinserted into OPEN with the mTSP f-value. FOCAL contains the subset of nodes n in OPEN with an mTSP f-value of f(n)≤w⋅fminf(n)≤ w· f_min. We propose two different h_FOCAL heuristics, both of which estimate the remaining search effort based on the paths produced by mTSP. The Sum Of Remaining Costs (SORC) heuristic calculates ∑khkΣ _kh_k, and the Max Of Remaining Costs (MORC) heuristic calculates maxkhk _kh_k. We also utilize these heuristics with Anytime Focal Search (AFS) (Cohen et al. 2018). Defining B as the cost of the best solution found thus far, AFS limits the nodes in FOCAL to nodes with f(n)<minB,w⋅fminf(n)< \B,w· f_min\ to force future solutions to improve on the current best solution. 5 Postprocessing Framework Postprocessing is utilized in planning algorithms to quickly improve the solution quality of an existing suboptimal solution. We propose a postprocessing framework that decomposes the problem into several single-agent searches that are each run on a separate subset of the map. Naturally, to improve the makespan of an existing suboptimal solution, π, we look to improve the path of the agent with the highest path cost while ensuring that the resulting set of paths is still a solution. Defining agent amaxa_max as the agent with the largest path cost, we want to replace πa _a, the path of amaxa_max, with πa′ _a where (1) c(πa′)<c(πa)c( _a )<c( _a) and (2) the resulting set of paths still has line-of-sight to every cell in U. To ensure that the new set of paths has line-of-sight to every cell in U, we need to ensure that πa′ _a sees all cells in U that no other agent sees. Thus, defining − π^- as the paths of all agents other than amaxa_max, we extract the minimum responsibility (r) of amaxa_max as r=∖⋃s∈(−)ℒ(s)r=U _s ( π^-)L(s). Here, r represents the cells that only amaxa_max sees in the original solution, and thus must see in any improved solution. We utilize MWRP-CP3 to optimally solve a single-agent subproblem for agent amaxa_max with =rU=r (Figure 6). Formally, we solve the problem tuple (1,,r,amax,,ℒ,)(1,C,r,\S_a_max\,N,L,O). Figure 6: Visualization of the initial joint-space solution, decomposed agent sub-problems, and postprocessed solution. Once a new path πa′ _a is computed, we update πa=πa′ _a= _a . We repeat this process until the agent with the largest cost among π has already had its path optimized in this decomposed manner (Figure 6). Since the agent responsibilities (r) may not be optimally partitioned, the postprocessing framework cannot guarantee a globally optimal solution. 6 Experimental Results Figure 7: From left to right, Den101d, Lak105d, Den202d (Stern et al. 2019), and an example Room map. We conduct experiments with varying map types, map sizes, and agent counts to measure the performance of MWRP-CP3, our BSS algorithms, and our postprocessing framework. For all of our experiments, we use four-way movement as the neighbor function and BresenhamLOS as the LOS function (Figure 1). All algorithms, including the original MWRP-A* algorithm, are implemented in C++. The mTSP heuristic is implemented as an integer linear programming formulation (Bektas 2006) using CPLEX (12). All experiments were run on a Legion 5i Gen 10 with 32 Intel Core Ultra 255Hx processors (4.50 GHz) and 32GB of RAM. We ran experiments on four different map styles (Figures 3 and 7): (1) Maze maps, (2) Room maps consisting of 3×33× 3 rooms, (3) Random maps with 20% obstacles, and (4) Game-inspired maps (Figures 3 and 7). Room and random maps were custom-generated; the others were taken from the Moving AI MAPF Benchmark (Stern et al. 2019), previous work on MWRP (Livne et al. 2023), and previous work on multi-agent planning and task assignment (Chong et al. 2024). For all experiments, to simulate real-world scenarios where exploration requires entering an environment from the outside, we generate agent starting points by selecting random cells along the map border. 6.1 State Space Reduction First, we compare the state space reduction and execution runtime of CD, PD, and CPD on three distinct map architectures (visualized in Figure 3). Averages were computed over 50 runs per agent count, from 1-5 agents, on each map. As shown in Table 1, PD and CPD were able to reduce |||U| by more than 95% on some maps. CD and PD both pruned more cells in structured maps with long corridors, which are less prominent in Random maps and more prominent in Maze maps. CPD executed 1.25× faster than PD. Map Random Maze Minecraft Average initial size of ||| U| ||=|U|= 175.3 ||=|U|= 598.9 ||=|U|= 1279.5 CD % Reduction 0.8 ± 0.6 69.9 ± 1.2 18.5 ± 2.3 Runtime 2 ± 0 4 ± 0 45 ± 1 PD % Reduction 56.6 ± 19.8 95.3 ± 1.1 89.0 ± 3.8 Runtime 8 ± 0 28 ± 1 205 ± 3 CPD % Reduction 56.6 ± 19.8 95.3 ± 1.1 89.0 ± 3.8 Runtime 6 ± 1 8 ± 0 160 ± 2 Table 1: Comparison of CD, PD, and CPD on three distinct maps (shown in Figure 3). The % reduction in the size of U, as well as the CPU runtime (ms), are measured. The initial U is C minus the initial LOS of each agent. 6.2 Search Algorithm Runtime Comparison Figure 8: Runtime comparison of search algorithms with respect to map size (top) and agent counts (bottom). Suboptimal methods used w=2w=2. Algorithms were subject to a 200s time limit, and only those solving 80%+ of the instances are shown. To our knowledge, MWRP-A* is the only existing optimal algorithm for solving MWRP, and there are no bounded suboptimal algorithms. We compare runtime performance between MWRP-A*, MWRP-A* with CPD, MWRP-CP3, MxWA*, FS with SORC, and FS with MORC. The runtime measurements are averaged over 20 instances, each with randomly generated agent starting locations. CPD runtime was included in the total runtime. As shown in Figure 8, MWRP-CP3 is the fastest optimal solver, running 200× faster than MWRP-A*, and solving complex problem instances that MWRP-A* failed to solve within a 200s time limit. The runtime improvement is significantly lower on Random maps, as CPD is less effective (Table 1). Figure 8 also demonstrates the scalability of our suboptimal solvers with respect to increasing map sizes and agent counts. For larger agent counts, MxWA* performs better than both FS algorithms, likely because the size of FOCAL increases with a larger joint-space, resulting in more mTSP heuristic calculations. 6.3 Ablation Study 32×32 Maze Den101d M=1M=1 M=3M=3 M=1M=1 M=3M=3 P 3.21 ± 1.26 8.18 ± 6.35 1.38 ± 0.19 4.99 ± 2.15 PHC 2.03 ± 0.13 5.59 ± 2.00 1.76 ± 0.30 2.33 ± 0.83 Table 2: Ablation tests with M agents measuring the scalar factor increase in runtime after removing either P or PHC. We also performed an ablation study to measure the individual improvement of the Pivot Pruning (P) and Parallel Heuristic Calculation (PHC) techniques. Table 2 shows the slowdown caused by removing P or PHC, each averaged over 20 different problem instances. Both methods provide a speedup in all test cases, and both provide a larger benefit on problems with more agents. PHC has low variances in its slowdown factor, indicating that its speedup is consistent regardless of the problem. P, however, has high variances, meaning its speedup varies from problem to problem. 6.4 Comparison of Suboptimal Variants (a) (b) Figure 9: Figure(a) shows runtime (lines) and solution cost (bars) at different w values. Figure(b) shows the cost improvement over time of the anytime variations. As shown in Figure 9(a), we measured the performance of all three suboptimal methods at different weight values by running the algorithms on the same problem instance, a 32×32 Maze Map with 6 agents, at varying w values. The runtime and solution cost were averaged over 10 iterations. All three algorithms have increasing solution costs increasing and decreasing runtimes with larger w values. At lower w values, all three algorithms perform similarly in terms of runtime and solution cost. At higher w values, MxWA* is able to achieve faster runtimes than either FS. We also empirically tested the anytime behavior of AMxWA*, AFS with SORC heuristic, and AFS with MORC heuristic, as shown in Figure 9(b). All three algorithms were run on the Minecraft-inspired map with 2 agents. The algorithms were run only once, since the improvement over time cannot be averaged over several runs. We can see that all three algorithms improve their costs significantly over the course of the runtime. AFS with the SORC heuristic takes longer than AMxWA* to generate an initial solution (for w=3w=3), but is able to quickly improve its solution much faster than AMxWA* and AFS with the MORC heuristic. These results demonstrate that all three algorithms are effective depending on the specific scenario and w value. 6.5 Impact of Postprocessing Framework w BSS Algorithm Postprocessing Runtime Cost Runtime Cost MWRP-CP3 1 7,379 92 0 92 MxWA* 2 1,277 124 164 93 5 1,154 129 146 109 FS (SORC) 2 1,121 162 168 125 5 1,105 162 182 125 FS (MORC) 2 1,074 127 156 107 5 1,091 127 166 107 Table 3: Impact of postprocessing architecture on BSS algorithms. The BSS runtime (ms), cost of the initial BSS solution, postprocessing runtime (ms), and improved solution cost are shown. We also show MWRP-CP3 as a reference. The postprocessing framework was tested on a 32×32 Maze with 3 agents. As shown in Table 3, for each algorithm, the postprocessing framework increased overall runtime by only 8% while improving the solution cost significantly, with MxWA* achieving a near-optimal postprocessed solution. In general, the postprocessing framework is best suited for MxWA* since its solution better distributes the paths throughout the map, which helps create even partitions. 7 Conclusion In this work, we introduced MWRP-CP3, which optimally solves MWRP by utilizing cell and path dominance, pivot pruning, and parallel heuristic computation, and computes optimal paths 200× faster than existing baselines. We also introduced MxWA*, a variation of WA* for the makespan objective function, and SORC and MORC, two heuristics used in conjunction with Focal Search. Additionally, we presented anytime variations for our BSS algorithms, as well as a postprocessing framework, both of which significantly improve the quality of the suboptimal solution. Future work should (1) investigate faster heuristics (Ren et al. 2024), (2) experiment on non-grid graphs (Kavraki and Latombe 1994), and (3) expand the problem scope (i.e. considering inter-agent collisions or heterogeneous agents). Acknowledgments The research at Carnegie Mellon University was partially supported by the National Science Foundation under grants #2328671 and #2441629. Ariel Felner was supported by Israel Science Foundation (ISF) Grant #909/23 and by a grant from the Israeli Ministry of Science and Technology (MOST). References F. Agostinelli, S. McAleer, A. Shmakov, and P. Baldi (2019) Solving the rubik’s cube with deep reinforcement learning and search. Nature Machine Intelligence 1 (8), p. 356–363. Cited by: §3.3. T. Bektas (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34 (3), p. 209–219. Cited by: §6. K. Bezas, G. Tsoumanis, C. T. Angelis, and K. Oikonomou (2022) Coverage path planning and point-of-interest detection using autonomous drone swarms. Sensors 22 (19), p. 7551. Cited by: §1. J. E. Bresenham (1965) Algorithm for computer control of a digital plotter. IBM Systems Journal 4 (1), p. 25–30. Cited by: §2.1. W. Chin and S. Ntafos (1988) Optimum watchman routes. Information Processing Letters 28 (1), p. 39–44. Cited by: §1. S. W. Cho, H. J. Park, H. Lee, D. H. Shim, and S. Kim (2021) Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations. Computers and Industrial Engineering 161, p. 107612. Cited by: §1. Y. Q. Chong, J. Li, and K. Sycara (2024) Optimal task assignment and path planning using conflict-based search with precedence and temporal constraints. arXiv preprint arXiv:2402.08772. Cited by: Figure 3, §6. L. Cohen, M. Greco, H. Ma, C. Hernandez, A. Felner, T. K. S. Kumar, and S. Koenig (2018) Anytime focal search with applications. In Proceedings of the International Joint Conference on Artificial Intelligence, p. 1434–1441. Cited by: §4.2. B. Gavish (1976) Note—a note on “the formulation of the m-salesman traveling salesman problem”. Management Science 22 (6), p. 704–705. Cited by: §2.2. E. A. Hansen and R. Zhou (2007) Anytime heuristic search. Journal of Artificial Intelligence Research 28, p. 267–297. Cited by: §4.1. W. H. Huang (2001) Optimal line-sweep-based decompositions for coverage algorithms. In Proceedings of the International Conference on Robotics and Automation, Vol. 1, p. 27–32. Cited by: §1. [12] (2021) IBM ilog cplex optimization studio. International Business Machines Corporation. Cited by: §6. P. A. Jimenez, B. Shirinzadeh, A. Nicholson, and G. Alici (2007) Optimal area covering using genetic algorithms. In Proceedings of the International Conference on Advanced Intelligent Mechatronics, p. 1–5. Cited by: §1. L. Kavraki and J.-C. Latombe (1994) Randomized preprocessing of configuration for fast path planning. In Proceedings of the International Conference on Robotics and Automation, p. 2138–2145. Cited by: §7. T. Li, R. Chen, B. Mavrin, N. R. Sturtevant, D. Nadav, and A. Felner (2022) Optimal search with neural networks: challenges and approaches. In Proceedings of the International Symposium on Combinatorial Search, p. 109–117. Cited by: §3.3. Y. Livne, D. Atzmon, S. Skyler, E. Boyarski, A. Shapiro, and A. Felner (2023) Optimally solving the multiple watchman route problem with heuristic search. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, p. 905–913. Cited by: §1, §2.1, §2.2, §2, §6. L. Mero (1984) A heuristic search algorithm with modifiable estimate. Artificial Intelligence 23 (1), p. 13–27. Cited by: §2.2. J. S. Mitchell and E. Wynters (1991) Watchman routes for multiple guards. In Proceedings of the Canadian Conference on Computational Geometry, p. 126–129. Cited by: §1. S. Mukherjee, S. Aine, and M. Likhachev (2022) MPLP: massively parallelized lazy planning. IEEE Robotics and Automation Letters 7 (3), p. 6067–6074. Cited by: §3.3. B. Nilsson (1995) Guarding art galleries - methods for mobile guards. Ph.D. Thesis, Lund University. Cited by: §1. E. Packer (2008) Computing multiple watchman routes. In International Workshop on Experimental and Efficient Algorithms, p. 114–128. Cited by: §1. J. Pearl and J. H. Kim (1982) Studies in semi-admissible heuristics. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-4 (4), p. 392–399. Cited by: item 2, §4.2. I. Pohl (1970) Heuristic search viewed as path finding in a graph. Artificial Intelligence 1 (3-4), p. 193–204. Cited by: item 2, §4.1. Z. Ren, S. Rathinam, and H. Choset (2024) A bounded sub-optimal approach for multi-agent combinatorial path finding. IEEE Transactions on Automation Science and Engineering 22, p. 7590–7605. Cited by: §7. S. Seiref, T. Jaffey, M. Lopatin, and A. Felner (2020) Solving the watchman route problem on a grid with heuristic search. In Proceedings of the International Conference on Automated Planning and Scheduling, p. 249–257. Cited by: §1, §2. M. Steinbrink, P. Koch, B. Jung, and S. May (2021) Rapidly-exploring random graph next-best view exploration for ground vehicles. In 2021 European Conference on Mobile Robots (ECMR), p. 1–7. Cited by: §1. R. Stern, N. R. Sturtevant, A. Felner, S. Koenig, H. Ma, T. T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Bartak (2019) Multi-agent pathfinding: definitions, variants, and benchmarks. In Proceedings of the International Symposium on Combinatorial Search, p. 151–158. Cited by: Figure 3, Figure 7, §6. T. Yaffe, S. Skyler, and A. Felner (2021) Suboptimally solving the watchman route problem on a grid with heuristic search. In Proceedings of the International Symposium on Combinatorial Search, p. 106–114. Cited by: §1, §4.1. B. Yamauchi (1997) A frontier-based approach for autonomous exploration. In Proceedings of the International Symposium on Computational Intelligence in Robotics and Automation, p. 146–151. Cited by: §1.