Multi-Covering a Point Set by $m$ Disks with Minimum Total Area

Abstract-- A common robotics sensing problem is to place sensors to robustly monitor a set of assets, where robustness is assured by requiring asset p to be monitored by at least κ (p) sensors. Given n assets that must be observed by m sensors, each with a disk-shaped sensing region, where should the sensors be placed to minimize the total area observed? W e provide and analyze a fast heuristic for this problem. Subsequently, we enforce separation constraints between the sensors by modifying the integer program formulation and by changing the disk candidate set. I. Introduction Coordinating different kinds of robotic assets is a natural challenge when it comes to problems of surveillance and guidance. As shown in Figure 1, this gives rise to scenarios in which a finite set of drones with downward communication links must maintain control of a finite set of ground assets [7], [15], choosing a set of different altitudes that balance safe separation between drones with reliable communication to the ground. The latter requires sufficient signal strength, so communication areas (and thus energy consumption) depend quadratically on the altitude.