TY - GEN

T1 - Plane formation by synchronous mobile robots without chirality

AU - Tomita, Yusaku

AU - Yamauchi, Yukiko

AU - Kijima, Shuji

AU - Yamashita, Masafumi

N1 - Funding Information:
∗ This work was partially supported by a Grant-in-Aid for Scientific Research on Innovative Areas “Molecular Robotics” (No.24104003 and No.15H00821) of MEXT and MEXT/JSPS KAKENHI Grant Numbers JP15K15938, JP17K19982, JP15H02666, and JP15K11987. † A full version of the paper is available at https://arxiv.org/abs/1705.06521
Publisher Copyright:
© 2017 Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita.

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85045654749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045654749&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.OPODIS.2017.13

DO - 10.4230/LIPIcs.OPODIS.2017.13

M3 - Conference contribution

AN - SCOPUS:85045654749

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 21st International Conference on Principles of Distributed Systems, OPODIS 2017

A2 - Aspnes, James

A2 - Leitao, Joao

A2 - Bessani, Alysson

A2 - Felber, Pascal

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 21st International Conference on Principles of Distributed Systems, OPODIS 2017

Y2 - 18 December 2017 through 20 December 2017

ER -