How simple robots benefit from looking back
Rights / licenseIn Copyright - Non-Commercial Use Permitted
We study the sensor and movement capabilities that simple robots need in order to create a map of an unknown polygon of size n, and to meet. We consider robots that can move from vertex to vertex, can backtrack movements, and see distant vertices in counter-clockwise order but have no means of visibly identifying them. We show that such robots can always solve the weak rendezvous problem and reconstruct the visibility graph, given an upper bound on n. Our results are tight: The strong rendezvous problem, in which robots need to gather at a common location, cannot be solved in general, and without a bound on n, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known Show more
Journal / seriesTechnical report
PublisherETH, Department of Computer Science
SubjectROBOTERSEHEN; AUTONOME ROBOTER; ROBOT VISION; AUTONOMOUS ROBOTS; ROBOTERNAVIGATION; ROBOT NAVIGATION
Organisational unit02150 - Departement Informatik / Department of Computer Science
NotesTechnical Reports D-INFK.
Weitere Autoren: Shantanu Das, Yann Disser, Matúš Mihalák, and Peter Widmayer.
MoreShow all metadata