Examinando por Autor "Contreras Leyton, Jean Luis"

Mostrando 1 - 1 de 1
  • Miniatura
    Ítem
    Windowed conflict-based search algorithm
    (Universidad Andrés Bello, 2020) Contreras Leyton, Jean Luis; Hernández, Carlos; Facultad de Ingeniería
    La búsqueda de rutas de múltiples agentes (MAPF) es el problema de encontrar rutas para varios agentes mientras evitan colisiones en un grafo. Uno de los algoritmos más fuertes en este campo es Conflict-Based Serach (CBS). CBS encuentra la ruta óptima para todos los agentes de manera offline. Esto significa que es necesario finalizar la búsqueda antes de que los agentes puedan avanzar hacia sus objetivos. Por otro lado, uno de los algoritmos online (intercala planificación y movimiento) más poderosos es Windowed Hierarchical Cooperative A* (WHCA*). WHCA* encuentra una ruta subóptima para todos los agentes y limita la profundidad de la búsqueda espacio-temporal a una ventana dinámica de tamaño fijo, reduciendo el cálculo computacional. En base a esto, presentamos un nuevo algoritmo online subóptimo llamado Windowed CBS (WCBS). WCBS se basa en CBS, pero incorpora las ventanas de WHCA*. Otra contribución menor que se presenta en el artículo, es una mejora al procedimiento de búsqueda de WHCA* llamada improved WHCA* (iWHCA*). En nuestros experimentos, WCBS supera a CBS en su tasa de éxito y tiempo de ejecución, pero tiene un rendimiento inferior en costo de solución. Por otro lado, WCBS supera a iWHCA* en costo de solución y tiempo de ejecución (para un bajo número de agentes y mapas con corredores o pasillos), pero tiene un rendimiento ligeramente inferior (para ventanas más grandes) en su tasa de éxito.