Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem
For robotics and surveillance planning, this work provides significantly faster optimal and suboptimal solutions to a known NP-hard problem, enabling larger-scale applications.
The authors tackle the Multiple Watchman Route Problem (MWRP), introducing MWRP-CP3, an optimal planner that reduces search space by over 95% and runs more than 200x faster than existing optimal algorithms on 2D grid maps. They also present suboptimal algorithms that solve maps 3x larger than those solvable by MWRP-CP3.
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 mwrp-cp3.github.io for the open source codebase and video demonstrations.