A randomized art-gallery algorithm for sensor placement

ABSTRACT

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).

REFERENCES

• 1: J.E. Banta, Y. Zhien, X.Z. Wang, G. Zhang, M.T. Smith, and M.A. Abidi. A "next-best-view" algorithm for three-dimensional scene reconstruction using range images. In SPIE, volume 2588, pages 418-29, 1995.
• 2: Marshall Bern, Triangulations, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 3: H. Br.onnimann, B. Chazelle, and J. Matousek. Product range spaces, sensitive sampling, and derandomization. In Proc. of 34th IEEE Symposium on Foundations of Computer Science, pages 400-409, 1993.
• 4: H. Bronnimann and M.T. Goodrich. Almost optimal set covers in finite vc-dimension. Discrete and Computational Geometry, 14:463-479, 1995.
• 5: C. I. Conolly. The determination of next best views. In IEEE Int. Conf. on Robotics and Automation, pages 432-435, 1985.
• 6: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 7: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 8: T. Danner and L. Kavraki. Randomized planning for short inspection paths. In Proc. 2000 IEEE Int'l Conf. Robotics & and Automation, pages 971-976, April 2000.
• 9: H. Gonzalez-Banos, A. Efrat, J.C. Latombe, E. Mao, and T.M. Murali. Planning robot motion strategies for efficient model construction. In J. Hollerbach and D. Koditschek, editors, Robotics Research - The Ninth Int. Symp., Salt Lake City, UT, 1999. Springer-Verlag.
• 10: Marc Levoy , Pat Hanrahan, Light field rendering, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.31-42, August 1996 [doi>10.1145/237170.237199]
• 11: J. Maver , R. Bajcsy, Occlusions as a Guide for Planning the Next View, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.5, p.417-433, May 1993 [doi>10.1109/34.211463]
• 12: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 13: Joseph O'Rourke, Visibility, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 14: R. Pito. A solution to the next best view problem for automated cad model acquisition of free-form objects using range cameras. Technical Report 95-23, GRASP Lab, University ofPennsylvania, May 1995.
• 15: T. Shermer. Recent results in art galleries. Proc. IEEE, 80(9):1384-1399, September 1992.
• 16: Petr Slavík, A tight analysis of the greedy algorithm for set cover, Journal of Algorithms, v.25 n.2, p.237-254, Nov. 1997 [doi>10.1006/jagm.1997.0887]
• 17: Jack Snoeyink, Point location, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 18: Greg Turk , Marc Levoy, Zippered polygon meshes from range images, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.311-318, July 1994 [doi>10.1145/192161.192241]
• 19: Jorge Urrutia. Art gallery and illumination problems. In J. R. Sack and J. Urrutia, editors, Hanbook on Computational Geometry, pages 387-434. Elsevier Science Publishers, 1997.
• 20: L. Wixson. Viewpoint selection for visual search. In Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pages 800-805, 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Theory