Energy-Efficient Min-Max Planning of Heterogeneous Tasks with Multiple UAVs

Unmanned Aerial Vehicles (UAVs) have been widely used in various applications such as inspection, security surveillance, and aerial photography, in which the cooperation of multiple UAVs is significantly important for better accomplishing complex tasks due to the limited capability for individual UAV s. Task planning is the primary issue for the cooperation of multiple UAV s, and has attracted extensive research interests. However, most research fails to account adequately for limited energy on each UAV, which involves in many factors such as different operations for performing a task and various movement patterns besides the distance and turns that have been commonly considered. By contrast, we conduct a series of experiments to obtain the energy model of UAV s. Furthermore, we focus on the energy-efficient min-max task planning (E2M2TP) problem by considering the heterogeneity of tasks and integrating various energy factors, which is beneficial for balancing the workload and energy consumption among UAV s and thus reducing the number of required UAVs. We show that E2M2TP is NP-hard, and propose an energy-aware variable neighbor search (EVNS) algorithm to iteratively optimize both task allocation and path planning. Extensive simulations are conducted to validate that EVNS outperforms the other state-of-the-art algorithms.