TY - GEN
T1 - Pattern formation by mobile robots with limited visibility
AU - Yamauchi, Yukiko
AU - Yamashita, Masafumi
N1 - Funding Information:
This work is supported in part by JSPS Grant-in-Aid for Scientific Research on Innovative Areas “Molecular Robotics” (No. 24104003, and No. 24104519), and JSPS KAKENHI (No. 22300004, No. 24650008, and No. 23700019).
PY - 2013
Y1 - 2013
N2 - We investigate the pattern formation problem by mobile robots with limited visibility that can observe the positions of robots within limited distance. For robots with unlimited visibility, Fujinaga et al. (DISC 2012) showed that asynchronous oblivious robots have the same formation power as fully-synchronous non-oblivious robots, that is, starting from any initial configuration I , target pattern F is formable if and only if ρ(I) divides ρ(F) where ρ(•) is the geometric symmetricity. We first show that fully-synchronous oblivious robots with limited visibility cannot form F even when ρ(I) divides ρ(F). Hence, limited visibility substantially weakens the formation power of oblivious robots. Secondly, we show that despite limited visibility, semi-synchronous robots with rigid moves, and fully-synchronous robots with non-rigid moves have the same formation power as robots with unlimited visibility. Consequently, local memory is necessary and sufficient for these robots.
AB - We investigate the pattern formation problem by mobile robots with limited visibility that can observe the positions of robots within limited distance. For robots with unlimited visibility, Fujinaga et al. (DISC 2012) showed that asynchronous oblivious robots have the same formation power as fully-synchronous non-oblivious robots, that is, starting from any initial configuration I , target pattern F is formable if and only if ρ(I) divides ρ(F) where ρ(•) is the geometric symmetricity. We first show that fully-synchronous oblivious robots with limited visibility cannot form F even when ρ(I) divides ρ(F). Hence, limited visibility substantially weakens the formation power of oblivious robots. Secondly, we show that despite limited visibility, semi-synchronous robots with rigid moves, and fully-synchronous robots with non-rigid moves have the same formation power as robots with unlimited visibility. Consequently, local memory is necessary and sufficient for these robots.
UR - http://www.scopus.com/inward/record.url?scp=84892989101&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84892989101&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-03578-9_17
DO - 10.1007/978-3-319-03578-9_17
M3 - Conference contribution
AN - SCOPUS:84892989101
SN - 9783319035772
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 201
EP - 212
BT - Structural Information and Communication Complexity - 20th International Colloquium, SIROCCO 2013, Revised Selected Papers
T2 - 20th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2013
Y2 - 1 July 2013 through 3 July 2013
ER -