The classic Watchman Route Problem (WRP) seeks to compute a shortest tour in a polygonal domain that sees every point of the domain. We introduce and study a novel generalization of the WRP, the See-Through Watchman Route Problem (STWRP), in which, in addition to vision-blocking "walls" of an input domain, there are obstacles to motion that are not opaque to vision: the watchman can see through certain obstacles or portions of the boundary of a polygonal domain P. This setting is motivated by real-world situations that may include transparent barriers (e.g., glass walls), obstacles that obstruct movement but not vision (e.g., lakes, flowerbeds, or potholes), and robotic sensors with penetration capabilities (e.g., microwave imaging). To the best of our knowledge, this version of the problem is new to the algorithms community. Our main result is an FPTAS for the STWRP in the case that P is an opaque-walled simple polygon having within it a set of transparent obstacles. A closely related problem that arises in this setting is that of the Traveling Salesperson problem with neighborhoods (TSPN) on a set of lines in the plane, with obstacles. We give the first FPTAS for the Quota-TSPN on infinite lines with polygonal obstacles. Additionally, we show tightness of our FPTAS, in that the Quota-TSPN on infinite lines with obstacles is weakly NP-hard. In the case of the STWRP within a simple polygon P with portions of the boundary, ∂ P, being transparent, we prove that the problem is NP-hard to approximate within a factor better than O(log n).

Assume that a target is known to be present at an unknown point among a finite set of locations in the plane. We search for it using a mobile robot that has imperfect sensing capabilities. It takes time for the robot to move between locations and search a location; we have a total time budget within which to conduct the search. We study the problem of computing a search path/strategy for the robot that maximizes the probability of detection of the target. Considering non-uniform travel times between points (e.g., based on the distance between them) is crucial for search and rescue applications; such problems have been investigated to a limited extent due to their inherent complexity. In this paper, we describe fast algorithms with performance guarantees for this search problem and some variants, complement them with complexity results, and perform experiments to characterize their performance.