Paper by Erik D. Demaine
- Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro, “Robot Localization without Depth Perception”, in Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT 2002), Lecture Notes in Computer Science, volume 2368, Turku, Finland, July 3–5, 2002, pages 249–259.
Consider the problem of placing reflectors in a 2-D environment in such a way
that a robot equipped with a basic laser can always determine its current
location. The robot is allowed to swivel at its current location, using the
laser to detect at what angles some reflectors are visible, but no distance
information is obtained. A polygonal map of the environment and reflectors is
available to the robot. We show that there is always a placement of reflectors
that allows the robot to localize itself from any point in the environment, and
that such a reflector placement can be computed in polynomial time on a real
RAM. This result improves over previous techniques which have up to a
quadratic number of ambiguous points at which the robot cannot determine
its location [1, 9]. Further, we show that the problem of optimal reflector
placement is equivalent to an art-gallery problem within a constant factor.
- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2368/23680249.pdf.
- The paper is \copyright Springer-Verlag.
- The paper is 10 pages.
- The paper is available in PostScript (498k), gzipped PostScript (247k), and PDF (173k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated February 10, 2020 by