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

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...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2022-05, Vol.285, p.104695, Article 104695
Main Authors: Doi, Keisuke, Yamauchi, Yukiko, Kijima, Shuji, Yamashita, Masafumi
Format: Article
Language:English
Subjects:
Distributed system
Exploration
Metamorphic robotic system
Mobile computing entities
Search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 shows 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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2021.104695