Exploration of a Grid with Blocked Nodes Using a Swarm of Autonomous Robots
摘要
This paper studies the terminating exploration of a finite grid where k autonomous robots traverse the grid such that each node is visited at least once and robots eventually stop when the task is completed. Practically, there may exist nodes that are either not reachable or considered to be insignificant for exploration, denoted as blocked nodes. We study the exploration of a grid that has one or more blocked nodes using oblivious, non-communicating and fully-synchronous robots that have unlimited visibility and follow the look-compute-move model. Each node has a limited amount of space called whiteboard where robots can read and write some information. The proposed algorithm enables robots to collectively explore all the non-blocked nodes of the grid in finite time. During exploration, though a node may be visited more than once, the algorithm ensures that all visits to a particular node are made by the same robot.