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.

A multirobot path planner (MPP)should find an optimal (or near-optimal) collision-free path, optimal in terms of a particular criterion, from the starting position to the goal position in an environ ment with obstacles for each robot in the formation. Because of the MPP complexity, heuristic algorithms usually are used to find an optimal solution, specifically in complex environments with many robots. In this work, we present a multirobot path planning algorithm using a search method based on the Simple Genetic Algorithm (SGA). Given a graph of the working environment, the algorithm finds a path for a formation taking into account possible split of the formation and its consecutive merge. From an initial population of suboptimal feasible paths, a particular encoding of chromosomes and genetic operators specially designed for the MPP problem, the algorithm evolves through generations, to find the best so lution for the robots formation. Results from the simulations show that the algorithm performs well in environments with obstacles and multiple robots formatio