This paper solves the Watchman Route Problem (WRP) on a general discrete graph with Heuristic Search. Given a graph, a line-of-sight (LOS) function, and a start vertex, the task is to (offline) find a (shortest) path through the graph such that all vertices in the graph will be visually seen by at least one vertex on the path. WRP is reminiscent but different from graph covering and mapping problems, which are done online on an unknown graph. We formalize WRP as a heuristic search problem and solve it optimally with an A*-based algorithm. We develop a series of admissible heuristics with increasing difficulty and accuracy. Our heuristics abstract the underlying graph into a disjoint line-of-sight graph (GDLS) which is based on disjoint clusters of vertices such that vertices within the same cluster have LOS to the same specific vertex. We use solutions for the Minimum Spanning Tree (MST) and the Traveling Salesman Problem (TSP) of GDLS as admissible heuristics for WRP. We theoretically and empirically investigate these heuristics. Then, we show how the optimal methods can be modified (by intelligently pruning away large sub-trees) to obtain various suboptimal solvers with and without bound guarantees. These suboptimal solvers are much faster and expand fewer nodes than the optimal solver with only minor reduction in the quality of the solution.

It was not long before James and Skyler became close friends. The paternal-like connection between the two previous strangers surprised Acharya. James would often brag about Skyler in the mannerism of a proud father. Anchor was fond of James as well. She would run to him and leap in his arms while Data would bark frantically for her attention, hoping for those magic words: "Don't get me." After some coaxing, James agreed to fly with Skyler. Even with his limited flying time, James could tell Skyler was gifted. Moreover, Skyler enjoyed flying again since the death of his best friend. It was pouring all day on the North Shore as James and Acharya sat in James' office at the forest research center, watching the rain through the large window. The downpour was relaxing, and James loved the sound.