Yukiko Yamauchi
Abstract
Creating a swarm of mobile computing entities, frequently called robots, agents, or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation problem that requires a swarm of robots moving in the three-dimensional Euclidean space to land on a common plane. The robots are fully synchronous and endowed with visual perception. But they do not have identifiers, nor access to the global coordinate system, nor any means of explicit communication with each other. Though there are plenty of results on the agreement problem for robots in the two-dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three-dimensional space. This article presents a necessary and sufficient condition for fully synchronous robots to solve the plane formation problem that does not depend on obliviousness, i.e., the availability of local memory at robots. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can form a plane from every regular polyhedron (except a regular icosahedron), whose symmetry is usually considered to be higher than any semi-regular polyhedron.
- Noa Agmon and David Peleg. 2006. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36, 1 (2006), 56--82. Google Scholar
Digital Library
- Hideki Ando, Yoshinobu Oasa, Ichiro Suzuki, and Masafumi Yamashita. 1999. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Automat. 15, 5 (1999), 818--828.Google ScholarCross Ref
- Mark A. Armstrong. 1988. Groups and Symmetry. Springer-Verlag, New York.Google Scholar
- Zohir Bouzid, Maria Gradinariu Potop-Butucaru, and Sébastien Tixeuil. 2010. Optimal byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci. 411 (2010), 3154--3168. Google ScholarDigital Library
- Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2012. Distributed computing by mobile robots: Gathering. SIAM J. Comput. 41, 4 (2012), 829--879.Google ScholarDigital Library
- Reuven Cohen and David Peleg. 2005. Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 6 (2005), 1516--1528. Google ScholarDigital Library
- Reuven Cohen and David Peleg. 2008. Convergence of autonomous mobile robots with inaccurate sensors and movements. SIAM J. Comput. 38, 1 (2008), 276--302. Google ScholarDigital Library
- Harold Scott MacDonald Coxeter. 1973. Regular Polytopes. Dover Publications.Google Scholar
- Peter R. Cromwell. 1997. Polyhedra. Cambridge University Press.Google Scholar
- Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Masafumi Yamashita. 2016. Autonomous mobile robots with lights. Theor. Comput. Sci. 609 (2016), 171--184. Google ScholarDigital Library
- Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita. 2015. Forming sequence of geometric patterns with oblivious mobile robots. Distrib. Comput. 28 (2015), 131--145. Google ScholarDigital Library
- Edsger W. Dijkstra. 1974. Self-stabilizing systems in spite of distributed control. Comm. ACM 17, 11 (1974), 643--644. Google ScholarDigital Library
- Asaf Efrima and David Peleg. 2009. Distributed algorithms for partitioning a swarm of autonomous mobile robots. Theor. Comput. Sci. 410 (2009), 1355--1368. Google ScholarDigital Library
- Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2012. Distributed Computing by Oblivious Mobile Robots. Morgan 8 Claypool. Google ScholarDigital Library
- Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. 2014. Distributed computing by mobile robots: Solving the uniform circle formation problem. In Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS’14). Springer International Publishing, 217--232.Google ScholarCross Ref
- Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. 2005. Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337 (2005), 147--168. Google ScholarDigital Library
- Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. 2008. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407 (2008), 412--447. Google ScholarDigital Library
- Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. 2015. Pattern formation by oblivious asynchronous mobile robots. SIAM J. Comput. 44, 3 (2015), 740--785.Google ScholarDigital Library
- Tomoko Izumi, Sayaka Kamei, and Yukiko Yamauchi. 2014. Approximation algorithms for the set cover formation by oblivious mobile robots. In Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS’14). Springer International Publishing, 233--247.Google ScholarCross Ref
- Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada, and Masafumi Yamashita. 2012. The gathering problem for two oblivious robots with unreliable compasses. SIAM J. Comput. 41, 1 (2012), 26--46. Google ScholarDigital Library
- David Peleg. 2005. Distributed coordination algorithms for mobile robot swarms: New directions and challenges. In Proceedings of the 7th International Workshop on Distributed Computing (IWDC’04). Springer Berlin, 1--12. Google ScholarDigital Library
- Samia Souissi, Xavier Défago, and Masafumi Yamashita. 2009. Using eventually consistent compasses to gather memory-less mobile robots with limited visibility. ACM Trans. Auton. Adapt. Syst. 4, 1 (2009), 9:1--9:27. Google ScholarDigital Library
- Ichiro Suzuki and Masafumi Yamashita. 1999. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28, 4 (1999), 1347--1363. Google ScholarDigital Library
- Taichi Uehara, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita. 2016. 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’16). Springer International Publishing, 383--398.Google ScholarCross Ref
- Masafumi Yamashita and Tsunehiko Kameda. 1996. Computing on anonymous networks: Part I-Characterizing the solvable cases. IEEE Trans. Parallel Distrib. Syst. 7, 1 (1996), 69--89. Google ScholarDigital Library
- Masafumi Yamashita and Ichiro Suzuki. 2010. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci. 411 (2010), 2433--2453. Google ScholarDigital Library
- Yukiko Yamauchi, Taichi Uehara, and Masafumi Yamashita. 2016. Brief announcement: Pattern formation problem for synchronous mobile robots in the three dimensional euclidean space. In Proceedings of the 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC’16). ACM New York, 447--449. Google ScholarDigital Library
- Yukiko Yamauchi and Masafumi Yamashita. 2013. Pattern formation by mobile robots with limited visibility. In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO’13). Springer International Publishing, 201--212.Google ScholarCross Ref
- Yukiko Yamauchi and Masafumi Yamashita. 2014. Randomized pattern formation algorithm for asynchronous oblivious mobile robots. In Proceedings of the 28th International Symposium on Distributed Computing (DISC’14). Springer Berlin, 137--151.Google ScholarCross Ref
Index Terms
- Plane Formation by Synchronous Mobile Robots in the Three-Dimensional Euclidean Space
Recommendations
Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed ComputingWe investigate the pattern formation problem that requires a swarm of autonomous mobile robots to form a given target pattern in the three-dimensional Euclidean space. We show a necessary and sufficient condition for synchronous robots to form a given ...
Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space
DISC 2015: Proceedings of the 29th International Symposium on Distributed Computing - Volume 9363Creating a swarm of mobile computing entities frequently called robots, agents or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, this paper investigates the plane formation problem ...
Collision-free path planning for nonholonomic mobile robots using a new obstacle representation in the velocity space
This paper presents a collision-free path planner for mobile robot navigation in an unknown environment subject to nonholonomic constraints. This planner is well adapted for use with embarked sensors, because it uses only the distance information ...
Comments