Local Strategies for Connecting Stations by Small Robotic Networks

摘要

Consider a group of m stations with fixed positions in the plane and a group of n mobile robots, called relays, aiming at building a communication network between the stations consisting of as few relays as possible. We present two strategies for dimensionless, identical (anonymous), oblivious and disoriented relays with limited viewing radius for constructing such a network. These strategies resemble natural strategies of swarms for maintaining formations. A relay does not communicate with others, its decision - whether to remove itself from the system, or where to move - consists only of the relative positions of its neighbors within its viewing radius. We provide a theoretical analysis of worst-case scenarios and upper and lower bounds for the number of relays used by the strategies. In addition, we show some preliminary experimental results.