Symmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes



Czyzowicz, Jurek, Gasieniec, Leszek ORCID: 0000-0003-1809-9814, Killick, Ryan and Kranakis, Evangelos
(2019) Symmetry Breaking in the Plane: Rendezvous by Robots with Unknown Attributes. In: PODC '19: ACM Symposium on Principles of Distributed Computing.

[img] Text
elements.pdf - Author Accepted Manuscript

Download (343kB) | Preview

Abstract

We study a fundamental question related to the feasibility of deterministic symmetry breaking in the infinite Euclidean plane for two robots that have minimal or no knowledge of the respective capabilities and "measuring instruments'' of themselves and each other. Assume that two anonymous mobile robots are placed at different locations at unknown distance d from each other on the infinite Euclidean plane. Each robot knows neither the location of itself nor of the other robot. The robots cannot communicate wirelessly, but have a certain nonzero visibility radius r (with range r unknown to the robots). By rendezvous we mean that they are brought at distance at most r of each other by executing symmetric (identical) mobility algorithms. The robots are moving with unknown and constant but not necessarily identical speeds, their clocks and pedometers may be asymmetric, and their chirality inconsistent. We demonstrate that rendezvous for two robots is feasible under the studied model iff the robots have either: different speeds; or different clocks; or different orientations but equal chiralities. When the rendezvous is feasible, we provide a universal algorithm which always solves rendezvous despite the fact that the robots have no knowledge of which among their respective parameters may be different.

Item Type: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: anonymous, asymmetric clock, chirality, competitive ratio, infinite plane, rendezvous, mobile robot, speed
Depositing User: Symplectic Admin
Date Deposited: 09 Sep 2019 11:52
Last Modified: 25 Nov 2023 08:03
DOI: 10.1145/3293611.3331608
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3053990