@inproceedings{f9206481e49a4392a122a74b69f415c7,

title = "Symmetry breaking in the plane: Rendezvous by robots with unknown attributes",

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.",

keywords = "Anonymous, Asymmetric clock, Chirality, Competitive ratio, Infinite plane, Mobile robot, Speed",

author = "Jurek Czyzowicz and Leszek Gasieniec and Ryan Killick and Evangelos Kranakis",

note = "Publisher Copyright: {\textcopyright} 2019 ACM. Copyright: Copyright 2019 Elsevier B.V., All rights reserved.; 38th ACM Symposium on Principles of Distributed Computing, PODC 2019 ; Conference date: 29-07-2019 Through 02-08-2019",

year = "2019",

month = jul,

day = "16",

doi = "10.1145/3293611.3331608",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "4--13",

booktitle = "PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing",

}