Energy-Efficient UAV Flight Planning for a General PoI-Visiting Problem with a Practical Energy Model

Unmanned aerial vehicles (UAVs) are being widely exploited for various applications, e.g., traverse to collect data from ground sensors, patrol to monitor key facilities, move to aid mobile edge computing. We summarize these UAV applications and formulate an abstract problem, namely the general waypoint-based PoI-visiting problem, aiming at minimizing flight energy consumption, which is critical due to its limited onboard storage capacity. In our problem, we pay special attention to the energy consumption for turning and switching operations on flight planning, which is usually ignored in the literature but plays an important role in practical UAV flights. We propose a novel method that uses specially designed graph parts to model the turning and switching cost and thus transfer the problem into a classic graph problem, i.e., traveling salesman problem, which can be efficiently solved. Finally, we evaluate our proposed algorithm by simulations. The results show it costs less than 107% of the optimal minimum energy consumption for small scale problem and costs only half as much energy as a naive algorithm for large scale problem.