The Coverage Path Planning (CPP) problem is the problem of determining a path that a robot, in our case an UAV (Unmanned Aerial Vehicle), must follow in order to cover with its sensors all the points of a target area. In general, 3D CPP problem is a CPP problem in a 3D environment. The application scenarios of the 3D CPP are several: surveying, precision agriculture, structural inspections, covering of ocean floors.CPP problems are known to be NP-hard. Due to this, optimal solutions are approximated using various methods.In particular, the problem addressed in this thesis is to cover 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 ∈ H, where H denotes the set of discrete heights. The UAV uses a sensor with a conic FOV (Field Of View) that is used to cover the ground. Our main goal is to reduce the computational cost in a CPP problem. To do this, we adopt a divide-et-impera approach. In computer science, divide-et-impera is a method that consists in dividing the initial problem into two or more simple sub-problems. After that, the solutions of the sub-problems must be combined to obtain the final result. In our case, we divide the entire environment in smaller sections that are covered separately through the 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 the Travel Salesman Problem (TSP) to connect them. After the paths over all the zones are produced, a merge algorithm obtains the final single path that covers the entire target surface. We introduce two different merge algorithms. The first one solves the problem more rapidly in terms of computational time but generally produces high cost paths, vice versa the second one produces paths with less cost than the first algorithm at the expense of a higher computational time. We implement these algorithms in three different environments and with different FOVs (Field Of Views) of the UAV sensor. Then we compare the results obtained with the results obtained without a divide-et-impera approach.

Il problema del Coverage Path Planning (CPP) consiste nel determinare un percorso che un robot, nel nostro caso un UAV (Unmanned Aerial Vehicle), deve seguire per coprire con i suoi sensori tutti i punti di interesse evitando ostacoli. Il 3D CPP `e la versione del problema del CPP in ambienti 3D. Il 3D CPP `e fondamentale in molte applicazioni, come la sorveglianza, la ricostruzione di strutture 3D, e il controllo delle semine in agricoltura. Il problema del CPP `e NP-hard, per questo motivo vengono proposte soluzioni che approssimano il risultato ottimo. In questa tesi trattiamo il problema di copertura di un’area al suolo come una composizione di pi`u problemi di copertura 2D, poich´e suddividiamo l’ambiente 3D in |H| sezioni orizzontali a diverse altezze prestabilite h ∈ H, dove H `e l’insieme discreto delle altezze. L’UAV utilizza un sensore con un FOV (Field Of Viewe) conico usato per coprire il terreno. Il nostro obiettivo principale `e quello di ridurre il costo computazionale nei problemi di CPP. Per fare questo utiliazziamo un approccio divide-et-impera. In informatica, tale approccio prevede la suddivisione del problema iniziale in uno o pi`u sottoproblemi pi`u semplici. Successivamente, le soluzioni dei sottoproblemi devono essere combinate a formare la soluzione del problema iniziale. Nel nostro caso, dividiamo l’intera mappa in diverse zone pi`u piccole che vengono coperte separatamente. Nel nostro caso, la copertura viene effettuata da un Art Gallery Problem (AGP), un problema di set cover il cui obiettivo `e quello di trovare un insieme di punti di copertura che coprano l’intera area di interesse. Successivamente, il Problema del Commesso Viaggiatore (TSP) viene utilizzato per trovare un tour che connetta i punti di copertura individuati. Dopo aver ottenuto i percorsi di copertura di tutte le zone, un algoritmo di unione produce il risultato finale. Due algoritmi di unione vengono proposti nella tesi. Il primo produce risultati con un minore tempo computazionale ma generalmente produce percorsi costosi per quanto riguarda la distanza, viceversa, il secondo algoritmo ha con un costo computazionale pi`u elevato ma minori costi di distanza. Implementiamo questi due algoritmi di unione su diversi ambienti e con differenti FOV (Field Of View) del sensore dell’UAV. Infine analizziamo e compariamo i risultati ottenuti mettendoli a confronto con i risultati ottenuti senza un approccio divide-et-impera.

A divide-et-impera approach to path planning for ground covering with an UAV

BIANCHI, SIMONE
2018/2019

Abstract

The Coverage Path Planning (CPP) problem is the problem of determining a path that a robot, in our case an UAV (Unmanned Aerial Vehicle), must follow in order to cover with its sensors all the points of a target area. In general, 3D CPP problem is a CPP problem in a 3D environment. The application scenarios of the 3D CPP are several: surveying, precision agriculture, structural inspections, covering of ocean floors.CPP problems are known to be NP-hard. Due to this, optimal solutions are approximated using various methods.In particular, the problem addressed in this thesis is to cover 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 ∈ H, where H denotes the set of discrete heights. The UAV uses a sensor with a conic FOV (Field Of View) that is used to cover the ground. Our main goal is to reduce the computational cost in a CPP problem. To do this, we adopt a divide-et-impera approach. In computer science, divide-et-impera is a method that consists in dividing the initial problem into two or more simple sub-problems. After that, the solutions of the sub-problems must be combined to obtain the final result. In our case, we divide the entire environment in smaller sections that are covered separately through the 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 the Travel Salesman Problem (TSP) to connect them. After the paths over all the zones are produced, a merge algorithm obtains the final single path that covers the entire target surface. We introduce two different merge algorithms. The first one solves the problem more rapidly in terms of computational time but generally produces high cost paths, vice versa the second one produces paths with less cost than the first algorithm at the expense of a higher computational time. We implement these algorithms in three different environments and with different FOVs (Field Of Views) of the UAV sensor. Then we compare the results obtained with the results obtained without a divide-et-impera approach.
ING - Scuola di Ingegneria Industriale e dell'Informazione
18-dic-2019
2018/2019
Il problema del Coverage Path Planning (CPP) consiste nel determinare un percorso che un robot, nel nostro caso un UAV (Unmanned Aerial Vehicle), deve seguire per coprire con i suoi sensori tutti i punti di interesse evitando ostacoli. Il 3D CPP `e la versione del problema del CPP in ambienti 3D. Il 3D CPP `e fondamentale in molte applicazioni, come la sorveglianza, la ricostruzione di strutture 3D, e il controllo delle semine in agricoltura. Il problema del CPP `e NP-hard, per questo motivo vengono proposte soluzioni che approssimano il risultato ottimo. In questa tesi trattiamo il problema di copertura di un’area al suolo come una composizione di pi`u problemi di copertura 2D, poich´e suddividiamo l’ambiente 3D in |H| sezioni orizzontali a diverse altezze prestabilite h ∈ H, dove H `e l’insieme discreto delle altezze. L’UAV utilizza un sensore con un FOV (Field Of Viewe) conico usato per coprire il terreno. Il nostro obiettivo principale `e quello di ridurre il costo computazionale nei problemi di CPP. Per fare questo utiliazziamo un approccio divide-et-impera. In informatica, tale approccio prevede la suddivisione del problema iniziale in uno o pi`u sottoproblemi pi`u semplici. Successivamente, le soluzioni dei sottoproblemi devono essere combinate a formare la soluzione del problema iniziale. Nel nostro caso, dividiamo l’intera mappa in diverse zone pi`u piccole che vengono coperte separatamente. Nel nostro caso, la copertura viene effettuata da un Art Gallery Problem (AGP), un problema di set cover il cui obiettivo `e quello di trovare un insieme di punti di copertura che coprano l’intera area di interesse. Successivamente, il Problema del Commesso Viaggiatore (TSP) viene utilizzato per trovare un tour che connetta i punti di copertura individuati. Dopo aver ottenuto i percorsi di copertura di tutte le zone, un algoritmo di unione produce il risultato finale. Due algoritmi di unione vengono proposti nella tesi. Il primo produce risultati con un minore tempo computazionale ma generalmente produce percorsi costosi per quanto riguarda la distanza, viceversa, il secondo algoritmo ha con un costo computazionale pi`u elevato ma minori costi di distanza. Implementiamo questi due algoritmi di unione su diversi ambienti e con differenti FOV (Field Of View) del sensore dell’UAV. Infine analizziamo e compariamo i risultati ottenuti mettendoli a confronto con i risultati ottenuti senza un approccio divide-et-impera.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
tesi.pdf

accessibile in internet per tutti

Descrizione: Tesi senza contro relatore
Dimensione 7.04 MB
Formato Adobe PDF
7.04 MB Adobe PDF Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/152127