A localized algorithm for bi-connectivity of connected mobile robots

Teams of multiple mobile robots may communicate with each-other using a wireless ad-hoc network. Faulttolerance in communication can be achieved by making the communication network bi-connected. We present the first localized protocol for constructing a fault-tolerant biconnected robotic network topology from a connected network, in such a way that the total movement of robots is minimized. The proposed distributed algorithm uses p-hop neighbor information to identify critical head robots that can direct two neighbors to move toward each other and bi-connect their neighborhood. Simulation results show that the total distance of movement of robots decreases significantly (e.g. about 2.5 times for networks with density 10) with our localized algorithm when compared to the existing globalized one. Proposed localized algorithm does not guarantee bi-connectivity, may partition the network, and may even stop at connected but not bi-connected stage. However, our algorithm achieved 100% success on all networks with average degrees ≥ 10, and over 70% success on sparse networks with average degrees ≥ 5.