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 photographs for points of interests in disaster areas where humans are hard to approach. Most existing studies focused on the limited energy capacity issue of UAVs when they take photographs, which however ignored an important fact, that is, the photographs 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 nonredundant information of the photographs 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 nonredundant 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 nonredundant information with an energy-constrained UAV.