GRASP Metaheuristic for Energy-efficient Drone Coverage Path Planning
Bárbara Peixoto Nascimento Ferreira de Souza, Tarcísio Barroso Marques, José Elias Claudio Arroyo · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
In this study, the Coverage Path Planning (CPP) problem is addressed, which aims to find the best flight path for a unmanned aerial vehicle (drone) to completely cover a given area of interest. Arbitrary areas containing obstacles (e.g. buildings, towers, trees or hills) are considered. The CPP is modeled as a Traveling Salesman Problem, where the drone must visit all non-obstacle points of the area to be covered. Battery power is the main resource that limits a drone's flight time or distance. It is known that, battery consumption is higher when a drone makes turns and altitude changes. To minimize the drone's energy consumption, we consider minimizing the total distance traveled, altitude variations and direction changes made during its route. As the CPP problem is NP-hard, in this work we propose a heuristic based on the GRASP meta-heuristic. The GRASP heuristic repeatedly constructs a solution using the cheapest insertion algorithm and this solution is improved by a local search procedure. The solutions determined by the proposed GRASP are compared with solutions generated by the Mixed-Integer Linear Programming model (solved by GUROBI solver). The results show that the GRASP heuristic determines excellent quality solutions using significantly less CPU time than GUROBI.