Nonredundant Information Collection in Rescue Applications via an Energy-Constrained UAV

Unmanned aerial vehicles (UAVs) are emerging as promising devices to provide valuable information in rescue applications, which can be dispatched to take photos for Points Of Interests (POIs) in disaster areas where humans are hard to approach. Most existing studies focused on the limited energy capacity issue of UAVs when they take photos, which however ignored an important fact, that is, the photos taken by the UAVs usually are highly redundant. In this paper we study a novel monitoring quality maximization problem to find a flying tour for an energy-constrained UAV, such that the amount of non-redundant information of the photos taken by the UAV in its tour is maximized. Due to NP-hardness of the problem, we first propose an approximation algorithm with a quasi-polynomial time complexity. We then devise a fast yet scalable heuristic algorithm for the problem. We finally evaluate the performance of the proposed algorithms via both a real dataset and extensive simulations. Experimental results show that the proposed algorithms are very promising. Especially, the amounts of non-redundant information by the proposed approximation and heuristic algorithms are about 11% and 8% larger than that by the state-of-the-art, respectively. To the best of our knowledge, we are the first to consider the novel problem of collecting non-redundant information with an energy-constrained UAV.