Automatic gas source localization with UAV: a graph-based approach

In this master's thesis, we implemented an algorithm that autonomously enables a drone to locate a gas leak in an unknown map, possibly containing obstacles, in the shortest possible time. After a literature review to understand the techniques used in this context, we decided to implement an Entrotaxis approach, where the decision-making logic is based on estimating the gradient of the gas distribution. For navigation, the GBEAM algorithm was successfully migrated to ROS~2 for compatibility with the latest software packages for future deployment in drone hardware. This algorithm manages navigation and mapping by creating an obstacle-free graph, dividing nodes into 'reachable' nodes for navigation and 'obstacle' nodes for environmental mapping. The main contribution of this thesis is the extension of GBEAM to include gas source localization logic. This recursive approach uses three sampling points positioned as the vertices of a triangle to approximate the gas distribution (assumed to be Gaussian). By interpolating a plane over these three points, the algorithm estimates the gradient, which indicates the direction to follow to reach the leak location (assumed to be the peak of the function). A specific stopping criterion is formulated, and sensitivity tests validate the algorithm's performance in terms of execution time, accuracy in estimating the leak location on the map, and quality of the gas concentration estimation. These tests cover scenarios with and without obstacles and with and without noise in the measurements, assuming a single peak in the distribution. Finally, an extension of the algorithm is proposed for more realistic scenarios, where obstacles influence the gas distribution, creating accumulation zones where concentration levels increase and may generate multiple local maxima in the distribution. In such cases, an Entrotaxis approach (which relies solely on following the concentration gradient) could encounter difficulties.

In questa tesi magistrale, abbiamo implementato un algoritmo che permette autonomamente a un drone di localizzare una fuoriuscita di gas all'interno di una mappa sconosciuta, possibilmente con ostacoli, nel minor tempo possibile. Dopo una ricerca bibliografica per comprendere le tecniche utilizzate in questo contesto, abbiamo deciso di implementare un approccio di Entrotaxis, in cui la logica decisionale è basata sulla stima del gradiente della distribuzione di gas. Per la navigazione, l’algoritmo GBEAM è stato efficacemente migrato alla seconda versione di ROS per poterlo implementare in controllori più recenti. Questo algoritmo gestisce la navigazione e la mappatura creando un grafo privo di ostacoli, dove i nodi sono suddivisi in nodi "raggiungibili" per la navigazione e nodi "ostacolo" per la mappatura ambientale. Il principale contributo di questa tesi è l'estensione di GBEAM per includere la logica di localizzazione della fonte di gas. Questo approccio ricorsivo utilizza tre punti di campionamento posizionati come i vertici di un triangolo per approssimare la distribuzione di gas (considerata come Gaussiana). Interpolando un piano su questi tre punti, l'algoritmo stima il gradiente, che indica la direzione da seguire per raggiungere la posizione della perdita (assunta come il picco della funzione). Un criterio di arresto specifico è formulato, e i test di sensitività validano le prestazioni dell'algoritmo in termini di tempo di esecuzione, accuratezza nella stima della posizione della perdita sulla mappa e qualità della stima della concentrazione di gas. Questi test coprono scenari in presenza e assenza di ostacoli e in presesenza e assenza di rumore sulle misurazioni, assumendo un solo picco nella distribuzione. Infine, è formulata un'estensione dell'algoritmo per scenari più realistici, in cui gli ostacoli influenzano la distribuzione del gas, creando zone di accumulo dove i livelli di concentrazione aumentano e possono generarsi vari massimi locali nella distribuzione. In tali casi, un approccio di Entrotaxis (che si basa esclusivamente sul seguire il gradiente di concentrazione) potrebbe incontrare difficoltà.