Joint UAV Placement and Data Delivery in Aerial Inspection Under Uncertainties
Napat Ngoenriang, Stephen John Turner, Dusit Niyato, Sucha Supittayapornpong
Abstract
The advancements in Internet-connected drones and edge computing raise the possibility of an on-the-fly inspection service that can instantly report the results. Inspection of sites using a drone fleet requires planning to meet situational requirements while minimizing operational costs under uncertainties of inspection requests, the urgency of reports, and the availability of communication channels. In this work, with the restriction on drone flying time, we decompose the planning into two phases: 1) precomputing groups of sites and 2) three-stage stochastic programming. The former phase generates feasible groups of sites, each of which is served by a drone, and precomputes the minimum-cost flying path for each group. The latter phase, given the feasible groups, jointly optimizes drone placement and data delivery under the uncertainties. The two-phase approach allows the planning to scale up to a practical situation. The performance evaluations show that the overall cost can be saved even if uncertainties exist, and the proposed approach significantly outperforms other methods, which do not consider the uncertainties. For a larger problem size, a heuristic algorithm is proposed to trade a loss in the optimality of 1.05–1.09 times the cost with 3.67–483.97 times speed-up in computation time.