変形ロボットシステムによる有限2次元正方グリッドの探索
Exploration of Finite 2D Square Grid by a Metamorphic Robotic System
匿名で記憶を持たないモジュールからなる変形ロボットシステムが、有限の2次元正方グリッドを探索するために必要な最小モジュール数を明らかにした。方位の合意がある場合は3個、ない場合は5個で探索可能であることを示した。
著者: Keisuke Doi, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita
分類: cs.DC, cs.RO
原文アブストラクト
We consider exploration of finite 2D square grid by a metamorphic robotic system consisting of anonymous oblivious modules. The number of possible shapes of a metamorphic robotic system grows as the number of modules increases. The shape of the system serves as its memory and shows its functionality. We consider the effect of global compass on the minimum number of modules necessary to explore a finite 2D square grid. We show that if the modules agree on the directions (north, south, east, and west), three modules are necessary and sufficient for exploration from an arbitrary initial configuration, otherwise five modules are necessary and sufficient for restricted initial configurations.
