Grid Based approach (GBA): a new approach based on the grid-clustering algorithm to solve a CPP type problem for air surveillance using UAVs

Air surveillance over large area using UAVs (Unmanned Aerial Vehicles) -also called drones- requires good planning. This kind of problem is classified as a CPP (Coverage Path Planing) problem which aims at finding a mission plan for the UAVs to cover the zone of interest. This type of problem is difficult because it relates to contradictory or combinatorial optimization problems. Therefor we need to find a heuristic solution. This zone is too large for one drone in a mission to reach and scan, thus it must be partitioned to small parts. This partitioning task must maximize each little part while respecting the performance constraints of the UAV. In this article we discuss a new approach called GBA (Grid Based Approach) different from the PGA (Point Gathering Approach) that we proposed in an earlier work. The GBA approach models the mission environment in a grid of points, each point is defined by its longitude, altitude and the obligation to reach that point expressed by a priority value limited between 0 and 100. Then it uses the grid-clustering algorithm to divide the whole zone in such a way to maximize the sum of the priorities of each partition (referred as gain). Finally we will compare the GBA and PGA approaches. In terms of time consumption, the GPA gives better results than PGA.