Biconnected Structure for Multi-Robot Systems∗

Many applications of distributed autonomous robotic sys-tems can benefit from, or even may require, the team of robots staying within communication connectivity. For ex-ample, consider the problem of multirobot surveillance (Ah-madi & Stone 2006), in which a team of robots must col-laboratively patrol a given area. If any two robots can di-rectly communicate at all times, the robots can coordinate for efficient behavior. This condition holds trivially in en-vironments that are smaller than the robots ’ communica-tion range. However in larger environments, the robots must actively maintain physical locations such that any two robots can communicate — possibly through a series of other robots. Otherwise, the robots may lose track of each others ’ activities and become miscoordinated. Furthermore