Target Searching and Exploration on Ring by Myopic Robots
摘要
In this paper, the solutions to the target searching problem on a ring by a swarm of anonymous, oblivious, asynchronous robots that are initially deployed over the ring randomly are addressed. A particular node in the ring is specified as the target node and the robots from their arbitrary initial distribution are required to find out the target node and gather at that location. In the proposed solution, apart from finally gathering at the target node, the robots collectively explore the complete ring within a finite amount of time. The ring nodes here are considered to have persistent memory, known as whiteboards, which may be used to store an integer that would finally indicate the distance of that node from the target node. In this work, the robots are considered to have the strongest possible myopia; they can see only up to their neighbouring nodes. However, a robot cannot modify the whiteboard marking of its neighbours. Two different algorithms are proposed in the paper. In the first solution, it is assumed that in the initial distribution at least one robot must be present either at the target node or at any one of its neighbours. However, in the second solution, the initial distribution is assumed to be completely random.