PPS: Energy-Aware Grid-Based Coverage Path Planning for UAVs Using Area Partitioning in the Presence of NFZs

Area monitoring and surveillance are some of the main applications for Unmanned Aerial Vehicle (UAV) networks. The scientific problem that arises from this application concerns the way the area must be covered to fulfill the mission requirements. One of the main challenges is to determine the paths for the UAVs that optimize the usage of resources while minimizing the mission time. Different approaches rely on area partitioning strategies. Depending on the size and complexity of the area to monitor, it is possible to decompose it exactly or approximately. This paper proposes a partitioning method called Parallel Partitioning along a Side (PPS). In the proposed method, grid-mapping and grid-subdivision of the area, as well as area partitioning are performed to plan the UAVs path. An extra challenge, also tackled in this work, is the presence of non-flying zones (NFZs). These zones are areas that UAVs must not cover or pass over it. The proposal is extensively evaluated, in comparison with existing approaches, to show that it enables UAVs to plan paths with minimum energy consumption, number of turns and completion time while at the same time increases the quality of coverage.