Suboptimally Solving the Watchman Route Problem on a Grid with Heuristic Search

Abstract

In the Watchman Route Problem (WRP) we are given a grid map with obstacles and the task is to (offline) find a (shortest) path through the grid such that all cells in the map can be visually seen by at least one cell on the path. WRP was recently formalized and optimally solved with heuristic search. In this paper we show how the previous optimal methods can be relaxed and modified to obtain suboptimal solvers that are much faster than the optimal solvers without sacrificing too much the quality of the solution. In particular, we present three methods that intelligently prune away large subtrees. We then derive bounded suboptimal solvers, suboptimal solvers without bounds and anytime variants of these. All these algorithms are backed up with experimental evidence that show their benefits compared to existing approaches.