DARPA: Deployment of UAVs for Polygonal Sizable Object Surveillance

Unmanned aerial vehicle (UAV) has attracted much attention due to its excellent ability to collect visual information of surroundings. In this paper, we investigate a new monitoring model to focus on sizes and shapes of objects, and occlusion between objects, and then study the placement of a set of UAVs to monitor polygonal sizable objects. Our aim is to maximize the overall monitoring utility of all objects by determining the positions and orientations of UAVs, given a set of polygonal sizable objects with fixed coordinates and shapes on a
$2\mathbf{D}$
plane. We study two typical scenarios of the problem: the former stipulates that a line segment is effectively monitored only when it is completely monitored by a single UAV, and the latter allows multiple UAVs to cooperatively monitor a line segment and then integrate their image information. The problem is proved to be NP-hard with infinite continuous solution space. For the first scenario, we propose a
$(1-1/e)$
-approximation algorithm. For the second one, we first propose a 1/2-approximation algorithm to address its simple version, and then propose a heuristic solution. Numerical evaluations validate the effectiveness of our proposed algorithms.