TY - JOUR
T1 - Characterizing geometric patterns formable by oblivious anonymous mobile robots
AU - Yamashita, Masafumi
AU - Suzuki, Ichiro
N1 - Funding Information:
We would like to thank the anonymous referees and Nao Fujinaga for their helpful comments. The first author was supported in part by a Grant-in-Aid for Scientific Research from Japan Society for the Promotion Science. The second author was supported in part by the Global COE Program ‘‘Mathematics-for-Industry,’’ Ministry of Education, Culture, Sports, Science and Technology, Japan, and UWM Research Growth Initiative.
PY - 2010/6/6
Y1 - 2010/6/6
N2 - In a system in which anonymous mobile robots repeatedly execute a "Look-Compute-Move" cycle, a robot is said to be oblivious if it has no memory to store its observations in the past, and hence its move depends only on the current observation. This paper considers the pattern formation problem in such a system, and shows that oblivious robots can form any pattern that non-oblivious robots can form, except that two oblivious robots cannot form a point while two non-oblivious robots can. Therefore, memory does not help in forming a pattern, except for the case in which two robots attempt to form a point. Related results on the pattern convergence problem are also presented.
AB - In a system in which anonymous mobile robots repeatedly execute a "Look-Compute-Move" cycle, a robot is said to be oblivious if it has no memory to store its observations in the past, and hence its move depends only on the current observation. This paper considers the pattern formation problem in such a system, and shows that oblivious robots can form any pattern that non-oblivious robots can form, except that two oblivious robots cannot form a point while two non-oblivious robots can. Therefore, memory does not help in forming a pattern, except for the case in which two robots attempt to form a point. Related results on the pattern convergence problem are also presented.
UR - http://www.scopus.com/inward/record.url?scp=77953253903&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953253903&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2010.01.037
DO - 10.1016/j.tcs.2010.01.037
M3 - Article
AN - SCOPUS:77953253903
SN - 0304-3975
VL - 411
SP - 2433
EP - 2453
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 26-28
ER -