부산대학교 도서관

Unmanned Aerial vehicles (UAVs) or Drones crash due to power failure, communication failure, mechanical malfunction, or Cyber-Physical attacks. This paper aims to study fault-tolerant covering by UAVs, i.e., in case of failure of some UAVs, other existing non-faulty UAVs cover up the job for the faulty UAVs. We consider two communication techniques to replace the faulty UAVs: (a) with local knowledge, i.e., non-faulty neighbors of the faulty UAVs communicate between themselves to find a suitable replacement and (b) with global knowledge, where the rest of the non-faulty UAVs communicate themselves via a satellite to find a suitable replacement. Here the objective of a suitable replacement is to minimize the cost of replacement. Let P be a set of n non-negative weighted points (ground users such as fire fighters or soldiers). Using a given set of m UAVs with equal covering capacities, the objective of the covering problem is to cover a subset of points on the 2D plane such that the total weight of the covered points is maximized. The objective of our fault-tolerant covering problem is to maximize the total weight covered by the UAVs in the presence of failure and replacement of UAVs at any point of time under the two communication techniques mentioned above. In the case of globally connected, we are using a variation of Hungarian algorithm for assignment problem while in locally connected, we are using a variation of Depth-First Search. We implement both the techniques and compare the performance of the two methods through a simulation study.