LIPIcs.OPODIS.2017.13.pdf
- Filesize: 0.55 MB
- 17 pages
Document
Plane Formation by Synchronous Mobile Robots without Chirality
Authors
-
Part of:
Volume:
21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-03-28
Cite AsGet BibTex
Yusaku Tomita, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. Plane Formation by Synchronous Mobile Robots without Chirality. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.OPODIS.2017.13
https://doi.org/10.4230/LIPIcs.OPODIS.2017.13
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.
Keywords
- Autonomous mobile robots
- plane formation problem
- symmetry breaking
- group theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Dana Angluin, James Aspnes, Zoe Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. In Proceedings of the 23rd annual ACM symposium on Principles of distributed computing (PODC 2004), pages 290-299, 2004. URL: http://dx.doi.org/10.1145/1011767.1011810.
-
Mark A. Armstrong. Groups and symmetry. Springer-Verlag New York Inc., 1988.
- Aaron Becker, Erik D. Demaine, Sándor P. Fekete, Golnaz Habibi, and James McLurkin. Reconfiguring massive particle swarms with limited, global control. In Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013), pages 51-66, 2013. URL: http://dx.doi.org/10.1007/978-3-642-45346-5_5.
- Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Asynchronous embedded pattern formation without orientation. In Proceedings of the 30th International SymposiumDistributed on Computing (DISC 2016), pages 85-98, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53426-7_7.
- Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by mobile robots: gathering. SIAM Journal on Computing, 41(4):829-879, 2012. URL: http://dx.doi.org/10.1137/100796534.
-
Peter R. Cromwell. Polyhedra. University Press, 1997.
- Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: Amoebot - a new model for programmable matter. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, pages 220-222, 2014. URL: http://dx.doi.org/10.1145/2612669.2612712.
- Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Universal shape formation for programmable matter. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pages 289-299, 2016. URL: http://dx.doi.org/10.1145/2935764.2935784.
- Yoann Dieudonné, Franck Petit, and Vincent Villain. Leader election problem versus pattern formation problem. In Proceedings of the 24th International Symposium on Distributed Computing (DISC 2010), pages 267-281, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15763-9_26.
-
Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by oblivious mobile robots. Morgan &Claypool, 2012.
- Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Distributed computing by mobile robots: Solving the uniform circle formation problem. In Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS 2014), pages 217-232, 2014. URL: http://dx.doi.org/10.1007/978-3-319-14472-6_15.
- Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation by oblivious asynchronous mobile robots. SIAM Journal on Computing, 44(3):740-785, 2015. URL: http://dx.doi.org/10.1137/140958682.
-
Marcello Mamino and Giovanni Viglietta. Square formation by asynchronous oblivious robots. In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016), pages 1-6, 2016.
- Sheryl Manzoor, Samuel Sheckman, Jarrett Lonsford, Hoyeon Kim, Min Jun Kim, and Aaron T. Becker. Parallel self-assembly of polyominoes under uniform control inputs. IEEE Robotics and Automation Letters, 2(4):2040-2047, 2017. URL: http://dx.doi.org/10.1109/LRA.2017.2715402.
- Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. URL: http://dx.doi.org/10.1137/S009753979628292X.
- Taichi Uehara, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. Plane formation by semi-synchronous robots in the three dimensional euclidean space. In Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2016), pages 383-398, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49259-9_30.
- Masafumi Yamashita and Ichiro Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theoretical Computer Science, 411:2433-2453, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2010.01.037.
- Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, and Masafumi Yamashita. Plane formation by synchronous mobile robots in the three dimensional euclidean space. Journal of the ACM, 64(16), 2017. URL: http://dx.doi.org/10.1145/3060272.
- Yukiko Yamauchi, Taichi Uehara, and Masafumi Yamashita. Brief announcement: Pattern formation problem for synchronous mobile robots in the three dimensional euclidean space. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC 2016), pages 447-449, 2016. URL: http://dx.doi.org/10.1145/2933057.2933063.
- Yukiko Yamauchi and Masafumi Yamashita. Pattern formation by mobile robots with limited visibility. In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013), pages 201-212, 2013. URL: http://dx.doi.org/10.1007/978-3-319-03578-9_17.