Coverage Planning for Multiple Unmanned Aerial Vehicles with Guaranteed Deadlines

The present work will present possible navigation algorithms for a fleet of UAVs inside a known region. After a series of consideration about the requirements necessary to achieve a satisfactory result, like for example the complete coverage and the warranty of covering the spots when their priority overcomes a certain value, a set of algorithms able to satisfy the requirements will be developed. In the following will be considered both centralized and decentralized algorithms. The work flow starts from a centralized approach, that will base its functioning on the search of the maximum value of the priority function at each step, in such a way to assure the visiting of them in the minor possible time. Since in this way the high priority spots in the vehicles neighborhood are considered only if one of them has in absolute the highest priority inside the region, creating an unwanted zig-zag trend and overpositions, two solutions will be proposed: the first is simply not consider just the greater value but a set of the high values (for example the n highest priorities) and among them choose the closest to the vehicle as next destination of the navigation. The second solution is to change entirely approach and to search for each step of the vehicle the position that minimizes a certain function that would take into account both the global state of the region and the local one, through a MPC-based algorithm. Considering the demands of a real-life application and the impossibility to have a constant connection, a decentralized algorithm will be developed. The region will be divided for this purpose in sub-regions of interest and a meeting will be imposed every period of time, in such a way to perform an update of the information. The navigation inside the respective sub-region in the time instants between the two meeting will be performable with the preferred navigation method, that in this case will be the maximum search algorithm described above.