Windowed conflict-based search algorithm
| dc.contributor.advisor | Hernández, Carlos | |
| dc.contributor.author | Contreras Leyton, Jean Luis | |
| dc.contributor.editor | Facultad de Ingeniería | |
| dc.date.accessioned | 2020-12-10T13:22:58Z | |
| dc.date.available | 2020-12-10T13:22:58Z | |
| dc.date.issued | 2020 | |
| dc.description | Tesis (Magíster en Ciencias de la Computación) | es |
| dc.description.abstract | 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. | es |
| dc.description.abstract | The Multi-agent pathfinding (MAPF), is the problem of finding paths for several agents avoiding collisions in a graph. One of the strongest algorithms in this field is Conflict-Based Search (CBS). CBS finds the optimal path for all agents in an offline manner. This means that its needed to finish the search before the agents can move to their goals. On the other hand, one of the strongest online algorithms (interleaves planning and movement) is Windowed Hierarchical Cooperative A* (WHCA*). WHCA* finds a suboptimal path for all agents and limits the space-time search depth to a dynamic window of fixed size, reducing computation. Because of this, we introduce a new suboptimal online algorithm called Windowed CBS (WCBS). WCBS is based on CBS, but incorporates the WHCA* windows. Another minor contribution presented in the article is an improvement to the WHCA* search procedure called improved WHCA* (iWHCA*). In our experiments, WCBS outperforms CBS in its success rate and execution time, but underperforms in solution cost. On the other hand, WCBS outperforms iWHCA* in solution cost and execution time (for a low number of agents and maps with corridors), but underperforms slightly (for bigger windows) in its success rate. | |
| dc.identifier.uri | http://repositorio.unab.cl/xmlui/handle/ria/16908 | |
| dc.language.iso | es | es |
| dc.publisher | Universidad Andrés Bello | es |
| dc.subject | Algoritmos Computacionales | es |
| dc.title | Windowed conflict-based search algorithm | es |
| dc.type | Tesis | es |
Archivos
Bloque original
1 - 1 de 1
No hay miniatura disponible
- Nombre:
- a130889_Contreras_J_Windowed_conflict_based_search_algorithm_2020_Tesis.pdf
- Tamaño:
- 1.29 MB
- Formato:
- Adobe Portable Document Format
- Descripción:
- TEXTO COMPLETO EN ESPAÑOL
Bloque de licencias
1 - 1 de 1
No hay miniatura disponible
- Nombre:
- license.txt
- Tamaño:
- 1.71 KB
- Formato:
- Item-specific license agreed upon to submission
- Descripción: