Towards a Continuous Solution of the d-Visibility Watchman Route Problem in a Polygon with Holes

A new heuristic solution framework is proposed to address the challenging watchman route problem (WRP) in a polygonal domain, which can be viewed as an offline version of the robot exploration task. The solution is the shortest route from which the robot can visually inspect a known 2D environment. Our framework considers a circular robot with radius r equipped with an omnidirectional sensor with limited visibility range d. Instead of a standard decoupled solution, the framework generates a set of specifically constrained regions covering the domain and then solves the traveling salesman problem with continuous neighborhoods (TSPN) to obtain the solution route. The TSPN is solved by another proposed heuristic algorithm that finds a discretized solution first and then improves it back in the continuous domain. The whole framework is evaluated experimentally, compared to two approaches from the literature, and shown to provide the highest-quality solutions. The current version of the framework is one step from a fully continuous approach to the WRP that we will address in the future.