License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2017.13
URN: urn:nbn:de:0030-drops-86337
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8633/
Tomita, Yusaku ;
Yamauchi, Yukiko ;
Kijima, Shuji ;
Yamashita, Masafumi
Plane Formation by Synchronous Mobile Robots without Chirality
Abstract
We consider a distributed system consisting of autonomous mobile computing entities called robots moving in the three-dimensional space (3D-space). The robots are anonymous, oblivious, fully-synchronous and have neither any access to the global coordinate system nor any explicit communication medium. Each robot cooperates with other robots by observing the positions of other robots in its local coordinate system. One of the most fundamental agreement problems in 3D-space is the plane formation problem that requires the robots to land on a common plane, that is not predefined. This problem is not always solvable because of the impossibility of symmetry breaking. While existing results assume that the robots agree on the handedness of their local coordinate systems, we remove the assumption and consider the robots without chirality. The robots without chirality can never break the symmetry consisting of rotation symmetry and reflection symmetry. Such symmetry in 3D-space is fully described by 17 symmetry types each of which forms a group. We extend the notion of symmetricity [Suzuki and Yamashita, SIAM J. Compt. 1999] [Yamauchi et al., PODC 2016] to cover these 17 symmetry groups. Then we give a characterization of initial configurations from which the fully-synchronous robots without chirality can form a plane in terms of symmetricity.
BibTeX - Entry
@InProceedings{tomita_et_al:LIPIcs:2018:8633,
author = {Yusaku Tomita and Yukiko Yamauchi and Shuji Kijima and Masafumi Yamashita},
title = {{Plane Formation by Synchronous Mobile Robots without Chirality}},
booktitle = {21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
pages = {13:1--13:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-061-3},
ISSN = {1868-8969},
year = {2018},
volume = {95},
editor = {James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8633},
URN = {urn:nbn:de:0030-drops-86337},
doi = {10.4230/LIPIcs.OPODIS.2017.13},
annote = {Keywords: Autonomous mobile robots, plane formation problem, symmetry breaking, group theory}
}
|
Keywords: |
|
Autonomous mobile robots, plane formation problem, symmetry breaking, group theory |
|
Collection: |
|
21st International Conference on Principles of Distributed Systems (OPODIS 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
28.03.2018 |
