Connectivity and stochastic robustness of synchronized multi-drone systems

A set of n drones with limited communication range is deployed to monitor a terrain partitioned into pairwise disjoint and closed convex trajectories, one per drone. There is exactly one communication link between two trajectories if they are close enough, and drones can communicate provided they visit the link at the same time. If each robot flies around an assigned area and shares information with the neighbors periodically the system is said to be synchronized. Over time, one or more drones may fail and the ability to survey, communicate, and stay connected decreases, thus the robustness against drone failure becomes crucial. In this paper we study various problems related to the proper functioning of a synchronized system under drone failure. First, we provide efficient algorithms, both centralized and decentralized, for determining the connected components induced by the set of surviving drones. Second, we study coverage, isolation, and connectivity under a probabilistic failure model and show that, in the case of grids, the system is quite robust in the sense that it can tolerate a large probability of failure before drones fail to completely cover the terrain, become isolated, or the system loses full connectivity.