Development of a multi-UAS coverage planning algorithm based on the Ant Colony optimization

This thesis focuses on the coverage planning problem with multiple UAVs (Unmanned aerial Vehicles), also called drone. The aim is to minimize the coverage time of an operational area with the presence of several obstacles. The strategy adopted divides the operational area to be covered into several regions, and, then, assigns them to the corresponding UAV. The choice for the optimization algorithm was made through a literature search of the different methods proposed at the state of the art, focusing on those peculiar to multi-drone aerial systems. The method adopted is based on the use of Voronoi diagram and Delaunay triangulation to decompose the operational area into regions. Thus, an algorithm based on the bio-inspired Ant Colony method provides an optimization by assigning the different regions to each UAV, as well as defining the order of visit each region, evaluating the parameters of drones, such as cruise speed and the field of view of the sensor used in the coverage application. For the subdivision of the area, two methods were mainly investigated. First, the Boustrophedon decomposition has been used, which involves the subdivision into regions based on the presence of obstacles in the operational area. Second, the Voronoi diagram is exploited by generating points (seeds) of the regions using a Conforming Constrained Delaunay Triangulation of the whole operations area. The resulting behavior of this strategy depends on the use of constraining parameters linked to the area definition for the correct tessellation. Several tests have been performed to select the best approach for the decomposition of the area, but the Voronoi-Delaunay combination allows a faster coverage and a more equitable division into regions and, then, assignment to the various drones. For the region assignment and order of visiting the Ant Colony has been adopted. It is a bio-inspired approach based on the natural behavior of ants that choose the best path between two destinations exploiting both the previous knowledge of the environment and the presence of pheromone left by the ants themselves. In fact, it is observed that the selected paths are gradually optimized by selecting the shortest one. This strategy is widely adopted by the state of the art for the path planning of autonomous vehicles, e.g. drones in this thesis. Specifically, the method involves the use of two parameters, heuristic and pheromonic that vary between the regions, until the solution converges to the best one between the different artificial ants. The proposed coverage planning strategy has been implemented using Python, used to generate the operational scenario (i.e. the map to be covered), decompose the operation area to regions and, then, assign the regions to drones that visit the assigned regions. The obtained results of the optimization demonstrate both the usefulness of the pheromone information for the ant colony algorithm and the best choice through the subdivision with Voronoi diagram.