Planificación cualitativa de camino de robots móviles en entornos poligonales basada en la teoría de matroides orientadas

Abstract

La planificación de caminos es uno de los principales problemas de la robótica. En este proyecto fin de carrera se estudia la planificación del camino de uno o varios robots móviles, en el que cada uno tiene que moverse desde una posición inicial a una final, evitando los obstáculos. Los obstáculos se representan en el plano en que se mueven los robots, mediante polígonos. Las rectas soporte de las aristas de estos polígonos inducen una partición del plano en celdas. Este conjunto de celdas será el espacio de búsqueda de los caminos, que serán secuencias de celdas adyacentes que unen las celdas que contienen las posiciones iniciales y finales. Para representar el entorno en que los robots se mueven, se usará una estructura llamada matroide orientada, la cuál guarda propiedades combinatorias tales como el orden, la separación, convexidad de los vértices de los polígonos que representan obstáculos. Esta estructura proporcionará al robot información local y global para la planificación del camino, sin ser necesaria información métrica, como puedan ser las coordenadas de los vértices. Los robots se suponen de tipo uniciclo. Para resolver el problema se utilizará el Algoritmo A*.