TY - JOUR

T1 - Pattern formation by oblivious asynchronous mobile robots

AU - Fujinaga, Nao

AU - Yamauchi, Yukiko

AU - Ono, Hirotaka

AU - Kijima, Shuji

AU - Yamashita, Masafumi

N1 - Publisher Copyright:
© 2015 Society for Industrial and Applied Mathematics.

PY - 2015

Y1 - 2015

N2 - We investigate pattern formation, i.e., self-organization, by a swarm of mobile robots, which is closely related with the agreement problem in distributed computing. Consider a system of anonymous mobile robots in a 2-dimensional Euclidean space in which each robot repeatedly executes a "Look-Compute-Move" cycle, to observe the positions of all the robots, to compute a route to the next position using an algorithm, and then to trace the route, where the algorithm is common to all robots. The robots are said to be fully synchronous if their Look-Compute-Move cycles are completely synchronized, and the ith Look, Compute, and Move of all robots start and end simultaneously. They are said to be asynchronous if no assumptions are made on their synchrony. The robots are said to be oblivious if they have no memory to memorize the execution history and hence behave based only on the robots' positions observed during the immediately preceding Look. We show that the set of geometric patterns formable by oblivious asynchronous robots is exactly the set of those formable by nonoblivious fully synchronous robots, except for a point of multiplicity 2, i.e., gathering for two robots. In short, contrary to our intuition, synchrony and memory do not help in pattern formation, except for gathering. Specifically, we propose an algorithm for oblivious asynchronous robots that, given a geometric pattern as input, forms it, as long as it is formable by nonoblivious fully synchronous robots except for a point of multiplicity 2.

AB - We investigate pattern formation, i.e., self-organization, by a swarm of mobile robots, which is closely related with the agreement problem in distributed computing. Consider a system of anonymous mobile robots in a 2-dimensional Euclidean space in which each robot repeatedly executes a "Look-Compute-Move" cycle, to observe the positions of all the robots, to compute a route to the next position using an algorithm, and then to trace the route, where the algorithm is common to all robots. The robots are said to be fully synchronous if their Look-Compute-Move cycles are completely synchronized, and the ith Look, Compute, and Move of all robots start and end simultaneously. They are said to be asynchronous if no assumptions are made on their synchrony. The robots are said to be oblivious if they have no memory to memorize the execution history and hence behave based only on the robots' positions observed during the immediately preceding Look. We show that the set of geometric patterns formable by oblivious asynchronous robots is exactly the set of those formable by nonoblivious fully synchronous robots, except for a point of multiplicity 2, i.e., gathering for two robots. In short, contrary to our intuition, synchrony and memory do not help in pattern formation, except for gathering. Specifically, we propose an algorithm for oblivious asynchronous robots that, given a geometric pattern as input, forms it, as long as it is formable by nonoblivious fully synchronous robots except for a point of multiplicity 2.

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

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

U2 - 10.1137/140958682

DO - 10.1137/140958682

M3 - Article

AN - SCOPUS:84938082158

SN - 0097-5397

VL - 44

SP - 740

EP - 785

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -