Comparison of exact and approximate approaches to UAVs mission contingency planning in dynamic environments

This paper presents a novel approach to the joint proactive and reactive planning of deliveries by an unmanned aerial vehicle (UAV) fleet. We develop a receding horizon-based approach to contingency planning for the UAV fleet's mission. We considered the delivery of goods to spatially dispersed customers, over an assumed time horizon. In order to take into account forecasted weather changes that affect the energy consumption of UAVs and limit their range, we propose a set of reaction rules that can be encountered during delivery in a highly dynamic and unpredictable environment. These rules are used in the course of designing the contingency plans related to the need to implement an emergency return of the UAV to the base or handling of ad hoc ordered deliveries. Due to the nonlinearity of the environment's characteristics, both constraint programming and genetic algorithm paradigms have been implemented. Because of the NP-difficult nature of the considered planning problem, conditions have been developed that allow for the acceleration of calculations. The multiple computer experiments carried out allow for comparison representatives of the approximate and exact methods so as to judge which approach is faster for which size of the selected instance of the UAV mission planning problem.