Keeping in Touch: Maintaining Biconnected Structure by Homogeneous Robots

Abstract

For many distributed autonomous robotic systems, it is impor-tant to maintain communication connectivity among the robots. That is, each robot must be able to communicate with each other robot, perhaps through a series of other robots. Ideally, this prop-erty should be robust to the removal of any single robot from the system. In (Ahmadi & Stone 2006a) we define a property of a team’s communication graph that ensures this property, called biconnectivity. In that paper, a distributed algorithm to check if a team of robots is biconnected and its correctness proof are also presented. In this paper we provide distributed algorithms to add and remove robots to/from a multi-robot team while maintain-ing the biconnected property. These two algorithms are imple-mented and tested in the Player/Stage simulator.