a randomized art-gallery algorithm for sensor placement
This paper descirbes a placement strategy to compute a set of good locations where visual sensing will be most effective. Throughout this paper it is assumed that a {\em polygonal 2-D map} of a workspace is given as input. This polygonal map --- also known as a {\em floor plan} of {\em layout} --- is used to compute a set of locations where expensive sensing tasks (such as 3-D image acquisition) could be executed. A map-building robot, for example, can visit these locations in order to build a full 3-D model of the workspace. The sensor placement strategy relies on a randomized algorithm that solves a variant of the {\em art-gallery problem}-\cite{Oro87, She92, Urr97} : Find the minimum set of guards inside a polygonal workspace from which the entire workspace boundary is visibe. To better take into account the limitations of physical sensors, the algorithm computes a set of guards that satisfies incidence and range constraints. Although the computed set of guards is not guaranteed to have minimum size, the algorithm does compute with high probability a set whose size is at most a factor $\big0{ (n + h) \cot \log(c \ (n + h) )$ from the optimal size$c$, where $n$ is the number of edges in the input polygonal map and $n$ the number of obstacles in its interior (holes).
randomization algorithm sensor senses placement paper strategies computation locatability visualization effect input image robotics examples order model randomized algorithm account physical constraint size probability factor optimality art