Deployment of Unmanned Aerial Vehicles for Anisotropic Monitoring Tasks

This paper considers the fundamental problem of deployment of Unmanned Aerial
V
eh
I
cles for ani
S
otropic mon
I
toring
T
asks (VISIT), that is, given a set of objects with determined coordinates and directions in 2D area, deploy a fixed number of UAVs by adjusting their coordinates and orientations such that the overall monitoring utility for all objects is maximized. We develop a theoretical framework to address VISIT problem. First, we establish monitoring model whose quality of monitoring (QoM is anisotropic with monitoring angle and varying with various monitoring distance. To the best of our knowledge, we are the first considering the anisotropy of monitoring angle. Then, we propose a framework consisting of area discretization and Monitoring Dominating Set (MDS) extraction to reduce the infinite solution space of VISIT to a limited one with performance bound. Finally, we model the reformulated problem as maximizing a monotone submodular function subject to a matroid constraint, and present a greedy algorithm with
$1-1/e-\epsilon$
approximation ratio. We conduct both simulations and field experiments to evaluate our framework, and the results show that our algorithm outperforms comparison algorithms by at least 41.3 percent.