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

Un planificador de caminos para multiples robots (MPP, del ingles Multirobot Path Planning) debe encontrar el conjunto de caminos libre de colisiones, optimo (o casi-optimo) en terminos de algun criterio en particular, desde una posicion inicial a una posicion final en un entorno con obstaculos. Dada la complejidad del problema de MPP, usualmente se utilizan algoritmos heuristicos para encontrar una solucion optima, especialmente en entornos complejos y con un numero elevado de robots. En este trabajo se presenta un algoritmo de planificacion de caminos para sistemas multirobots el cual utiliza como metodo de exploracion el conocido Algoritmo Genetico Simple (AGS). Dado un grafo representativo del espacio de busqueda el algoritmo encuentra los caminos de una formacion de robots teniendo en cuenta la posibilidad de separacion de la formacion y su posterior reunion. Partiendo de una poblacion inicial con gran diversidad de individuos y utilizando una codificacion de cromosomas y operadores evolutivos especialmente disenados para el problema de multiples robots, el algoritmo evoluciona generacion tras generacion devolviendo los mejores caminos para la formacion de robots. Los resultados de las simulaciones demuestran que el algoritmo es apto para ser utilizado en entornos con obstaculos y para una formacion de decenas de robots.