TY - GEN
T1 - Plane formation by synchronous mobile robots in the three dimensional Euclidean space
AU - Yamauchi, Yukiko
AU - Uehara, Taichi
AU - Kijima, Shuji
AU - Yamashita, Masafumi
N1 - Funding Information:
This work was supported by a Grant-in-Aid for Scientific Research on Innovative Areas “Molecular Robotics” (No. No. 24104003 and No. 15H00821) of The Ministry of Education, Culture, Sports, Science, and Technology, Japan.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - 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, this paper investigates the plane formation problem that requires a swarm of robots moving in the three dimensional Euclidean space to reside in a common plane. The robots are fully synchronous and endowed with visual perception. But they have neither identifiers, access to the global coordinate system, any means of explicit communication with each other, nor memory of past. 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 paper presents a necessary and sufficient condition to solve the plane formation problem. 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 from every regular polyhedron (except a regular icosahedron), which consists of the same regular polygon faces and the robots on its vertices are “more” symmetric than semi-regular polyhedra.
AB - 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, this paper investigates the plane formation problem that requires a swarm of robots moving in the three dimensional Euclidean space to reside in a common plane. The robots are fully synchronous and endowed with visual perception. But they have neither identifiers, access to the global coordinate system, any means of explicit communication with each other, nor memory of past. 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 paper presents a necessary and sufficient condition to solve the plane formation problem. 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 from every regular polyhedron (except a regular icosahedron), which consists of the same regular polygon faces and the robots on its vertices are “more” symmetric than semi-regular polyhedra.
UR - http://www.scopus.com/inward/record.url?scp=84946042376&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84946042376&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-48653-5_7
DO - 10.1007/978-3-662-48653-5_7
M3 - Conference contribution
AN - SCOPUS:84946042376
SN - 9783662486528
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 92
EP - 106
BT - Distributed Computing - 29th International Symposium, DISC 2015, Proceedings
A2 - Moses, Yoram
PB - Springer Verlag
T2 - 29th International Symposium on Distributed Computing, DISC 2015
Y2 - 7 October 2015 through 9 October 2015
ER -