Diseño de un algoritmo de path planning para un drone acuático de superficie basado en grafos Eulerianos

Abstract

El objetivo de este trabajo es el diseño un algoritmo de path planning para un drone acuático de superficie autónomo que mida la calidad del agua en diferentes puntos del Lago Ypacaraí. Para este fin, se ha partido de un trabajo previo en el que se empleaban circuitos Hamiltonianos junto con Algoritmos Genéticos para la búsqueda del camino a realizar por el drone, adaptándose la forma en la que se genera la población inicial, de circuitos Hamiltonianos a Eulerianos. Para ello se ha creado un algoritmo con el que generar circuitos Eulerianos basándose en un grupo de balizas repartidas a lo largo del perímetro del lago. A partir de ese algoritmo se ha procedido a comparar los dos métodos planteados, y seguidamente a experimentar con diferentes parámetros para ver las diferencias de rendimiento del algoritmo. Finalmente, se ha podido comprobar que el nuevo algoritmo ha superado el rendimiento del método del que se partía.

The aim of this master thesis is the design of a path planning algorithm for an autonomous surface vessel to measure the quality of the water on the Ypacaraí Lake. For this purpose, a previous thesis has been taken as the starting point, where Hamiltonian circuits were used along with Genetic Algorithms for the search of a path for the drone to follow, adapting the way the initial population is generated, changing from Hamilonian to Eulerian circuits. To achieve that, an algorithm has been created that generates Eulerian circuits based on a group of beacons distributed along the perimeter of the lake. From that algorithm, a comparison has ben made between the two methods, and next variations of the parameters have been tried to examine the performance of the algorithm. Finally, it could be checked the better performance of the new algorithm compared to the previous one.