Algoritmos de resolución de laberintos en robótica y su aplicación a la navegación de drones en interiores

Abstract

[ES] Este Trabajo de Fin de Máster investiga, implementa y compara diversos métodos de resolución de laberintos con el fin de evaluar su aplicación en la navegación autónoma de drones en interiores. Tras una revisión bibliográfica de técnicas clásicas y avanzadas como las basadas en teoría de grafos y el aprendizaje por refuerzo así como otras técnicas de localización como el SLAM, se han implementado en MATLAB los métodos de resolución en entornos laberínticos generados aleatoriamente y simulados con CoppeliaSim. Entre las pruebas realizadas, en primer lugar se encuentran las llevadas a cabo con algoritmos que no requieren de un conocimiento previo del laberinto, en segundo lugar con aquellos que sí lo requieren y lo obtienen mediante un dron sobrevolando y tomando imágenes del laberinto y por último las realizadas proponiendo un control continuo del que se centre de forma autónoma en el pasillo mediante visión por computador. Los resultados demuestran que en general los algoritmos clásicos no son muy útiles para su extrapolación a la navegación de drones ya que su rendimiento depende en gran medida de la estructura a recorrer, por otro lado, en caso de tener un conocimiento previo del entorno el algoritmo A* es el más eficiente y por último, el aprendizaje por refuerzo resulta menos eficiente en este caso de estudio y requiere de un mayor conocimiento para su aplicación. En conclusión, el trabajo ha probado las diferentes técnicas de resolución, entre ellas algunas novedosas basadas en inteligencia artificial, ha aplicado con éxito la visión por computador y ha evaluado la viabilidad de las mismas para la navegación de drones en interiores, con sugerencias para futuras investigaciones de incluir la técnica de SLAM y los algoritmos genéticos.

[EN] This Master's Thesis studies, implements and compares different maze solving methods in order to evaluate their application to autonomous indoor drone navigation. After a literature review of classical and advanced techniques such as those based on graph theory and reinforcement learning as well as other localization techniques such as SLAM, the maze solving methods have been implemented in MATLAB in maze environments randomly generated and simulated with CoppeliaSim. The tests conducted included firstly algorithms that do not require prior knowledge of the maze, secondly those that do require prior knowledge, which was obtained by a drone flying over the maze and taking images, and finally those carried out with a continuous control of a drone that autonomously centres itself in the corridor using computer vision. The results show that the classical algorithms are generally not very useful for their extrapolation to drone navigation as their performance depends largely on the structure to be traversed. On the other hand, when prior knowledge of the environment is available, the A* algorithm is the most efficient and finally, reinforcement learning is less efficient in this case study and requires more knowledge for its application. In conclusion, the work has tested different maze solving techniques, including some novel ones based on artificial intelligence, has successfully applied computer vision and has evaluated their feasibility for indoor drone navigation, with suggestions for future research to include the SLAM technique and genetic algorithms.