Publication:1664133

DOI10.1007/978-3-662-48653-5_7zbMath1394.68150arXiv1505.04546OpenAlexW2734373235MaRDI QIDQ1664133

Yukiko Yamauchi, Masafumi Yamashita, Shuji Kijima, Taichi Uehara

Publication date: 24 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

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 paper 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 polyhedrdon.

Full work available at URL: https://arxiv.org/abs/1505.04546

zbMATH Keywords

rotation groupsymmetry breakingmobile robotsmobile robots in three-dimensional spaceplane formation

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distributed systems (68M14) Artificial intelligence for robotics (68T40)

Related Items (21)

TuringMobile: a Turing machine of oblivious mobile robots with limited visibility and its applications ⋮ Search by a metamorphic robotic system in a finite 2D square grid ⋮ On fast pattern formation by autonomous robots ⋮ Plane formation by synchronous mobile robots without chirality ⋮ Ring exploration of myopic luminous robots with visibility more than one ⋮ Asynchronous arbitrary pattern formation: the effects of a rigorous approach ⋮ Autonomous mobile robots with lights ⋮ Compatibility of convergence algorithms for autonomous mobile robots (extended abstract) ⋮ Team assembling problem for asynchronous heterogeneous mobile robots ⋮ Ring exploration of myopic luminous robots with visibility more than one ⋮ Gathering robots in graphs: the central role of synchronicity ⋮ Plane formation by semi-synchronous robots in the three dimensional Euclidean space ⋮ Unnamed Item ⋮ Gathering on a circle with limited visibility by anonymous oblivious robots ⋮ On the power of bounded asynchrony: convergence by autonomous robots with limited visibility ⋮ Gathering on a circle with limited visibility by anonymous oblivious robots ⋮ Arbitrary pattern formation on infinite grid by asynchronous oblivious robots ⋮ Fault-induced dynamics of oblivious robots on a line ⋮ Embedded pattern formation by asynchronous robots without chirality ⋮ On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis ⋮ Arbitrary pattern formation on infinite regular tessellation graphs

This page was built for publication: Plane formation by synchronous mobile robots in the three dimensional Euclidean space