Planning paths for covering environments with UAVs moving at discrete heights

The Coverage Path Planning (CPP) problem is the problem of determining a path that a robot has to follow in order to cover with its sensors all the points of a target area. The 3D CPP problem is the CPP problem in a 3D environment. The application scenarios of the 3D CPP are several: surveying, precision agriculture, structural inspections, covering of ocean floors, monitoring of external surfaces of buildings and of automotive parts. In this thesis we address the problem of covering a 2D area at the ground by solving multiple CPPs over 2D grids, that are obtained as the result of the intersection of the 3D environment with |H| horizontal planes at different heights h in H, where H denotes the set of discrete heights. Given the 2D grids, we can have tours at single fixed heights, or tours over two or more heights. We are interested in finding the minimum-cost tour, in terms of its length, that allows the robot to cover the target area on the ground. We consider two specific scenarios and we formulate two algorithms. The easier scenario considers the environments in which the area covered at a given height is always included in the area covered at a higher height. The other scenario includes the environments in which the area that can be covered at a given height is a subset of the area covered at any lower heights. Both the algorithms are based on a two-phase approach that first approximately solves an Art Gallery Problem (AGP) as a set cover problem in order to find a feasible set of covering points (from which the target area can be fully covered) and then solves a Travelling Salesman Problem (TSP) to connect them. Since both the AGP and TSP are NP-hard we reduce the search space considering only a subset of all the possible tours. In the easier scenario we formulate a theorem that reduces the search space to consider only tours over fixed heights without losing optimality. Instead, in the other scenario all the possible tours must be computed. So, the other algorithm computes tours over two or more heights with a hierarchical approach, starting from the highest grid and going down, to cover incrementally the uncovered area. We implement both algorithms using different FOVs (Field Of Views) for the robot's sensor and environments. We compare the costs and the computational times of the tours they find.

Il problema del Coverage Path Planning (CPP) consiste nel determinare un percorso che un robot deve seguire per coprire con i suoi sensori un'area di interesse evitando ostacoli. Il 3D CPP è la versione del problema del CPP in ambienti 3D. Il 3D CPP è un problema fondamentale in molte applicazioni, come la sorveglianza, la ricostruzione di strutture 3D, e il controllo delle semine in agricoltura. In questa tesi trattiamo il problema di copertura di un'area al suolo come una composizione di più problemi di copertura 2D, poiché suddividiamo l'ambiente 3D in |H| sezioni orizzontali a diverse altezze prestabilite h in H, dove H è l'insieme discreto delle altezze. L'obiettivo è di trovare il tour minimo, in termini di lunghezza, che permetta al robot di coprire l'area di intesse al suolo. Ci concentreremo su due scenari specifici e formuleremo due algoritmi. Nello scenario più semplice considereremo gli ambienti in cui l'area al suolo coperta da una data altezza è sempre inclusa nell'area coperta da un'altezza maggiore. Invece, nell'altro scenario considereremo gli ambienti in cui l'area al suolo coperta da una data altezza è un sottoinsieme dell'area coperta da un'altezza minore. Entrambi gli algoritmi sono basati su un approccio a due fasi. La prima fase consiste nel risolvere un Art Gallery Problem (AGP) come un problema di set cover per trovare un set di punti di copertura che coprano l'intera area di interesse, mentre la seconda fase consiste nel risolvere il Problema del Commesso Viaggiatore (TSP) per trovare un tour che connetta i punti di copertura individuati. Sia l'AGP che il TSP sono due problemi NP-hard, per cui ridurremo lo spazio di ricerca, per non considerare tutti i possibili tour, ma solo un sottoinsieme. Nello scenario più semplice formuleremo un teorema che ridurrà lo spazio di ricerca ai soli tour ad altezze fisse senza sacrificare l’ottimalità. Dunque, uno dei due algoritmi analizzerà solo i tour ad altezze fisse. Invece, nell'altro scenario, tutti i possibili tour devono essere presi in considerazione. Quindi l'altro algoritmo troverà tutti i tour a due o più altezze con un approccio gerarchico che, partendo dalla griglia più alta e scendendo, copre incrementalmente le zone dell'area di interesse al suolo non ancora coperte. Valuteremo i due algoritmi in diversi ambienti e con diversi campi visivi per il sensore del robot. Mostreremo i tour trovati e ne confronteremo i risultati in termini di costo e tempi di calcolo.