Search by a metamorphic robotic system in a finite 2D square Grid

Abstract We consider search in an unknown finite 2D square grid by a metamorphic robotic system consisting of anonymous memory-less modules. Each module autonomously moves while executing a common distributed algorithm and the modules collectively form a robotic system by keeping connectivity. The number of shapes of the metamorphic robotic system grows as the number of modules increases, and a shape of the system serves as its memory and show its functionality. We present the minimum number of modules for search in a finite 2D square grid. We demonstrate that if the modules agree on the directions, i.e., they are equipped with the global compass, three modules are necessary and sufficient for search from an arbitrary initial shape, otherwise five modules are necessary and sufficient for search from limited initial shapes assuming that all modules share a common handedness.