Planificación de Caminos para Múltiples Robots Basado en Algoritmo Genético

Abstract

Un planificador de caminos para múltiples robots (MPP, del inglés Multirobot Path Planning) debe encontrar el conjunto de caminos libre de colisiones, óptimo (o casi-óptimo) en términos de algún criterio en particular, desde una posición inicial a una posición final en un entorno con obstáculos. Dada la complejidad del problema de MPP, usualmente se utilizan algoritmos heurísticos para encontrar una solución óptima, especialmente en entornos complejos y con un número elevado de robots. En este trabajo se presenta un algoritmo de planificación de caminos para sistemas multirobots el cual utiliza como método de exploración el conocido Algoritmo Genético Simple (AGS). Dado un grafo representativo del espacio de búsqueda el algoritmo encuentra los caminos de una formación de robots teniendo en cuenta la posibilidad de separación de la formación y su posterior reunión. Partiendo de una población inicial con gran diversidad de individuos y utilizando una codificación de cromosomas y operadores evolutivos especialmente diseñados para el problema de múltiples robots, el algoritmo evoluciona generación tras generación devolviendo los mejores caminos para la formación de robots. Los resultados de las simulaciones demuestran que el algoritmo es apto para ser utilizado en entornos con obstáculos y para una formación de decenas de robots.