Paralelización de problemas de búsqueda en grafos en una arquitectura tipo cluster

Abstract

Los problemas de optimización discreta, también conocidos como problemas combinatorios, surgen en diversas áreas y en general se resuelven utilizando técnicas que buscan una solución en el espacio de estados implícito del problema. Debido a la alta complejidad computacional de esta clase de problemas, las búsquedas exhaustivas se vuelven inaceptables, por lo cual se han desarrollado algoritmos heurísticos que utilizan funciones para evaluar el costo de los nodos y de este modo procesar primero los nodos que se estima están más cercanos al nodo “solución óptima”. Es de interés el desarrollo de heurísticas más potentes y algoritmos paralelos que resuelvan los problemas de optimización discreta de forma eficiente, con el fin de resolver instancias cada vez más grandes y dado que algunos problemas requieren soluciones en tiempo real, el paralelismo es en muchos casos la única forma de obtener el tiempo de respuesta esperado. En este marco, este trabajo toma como caso de estudio un problema de optimización clásico llamado Puzzle N<SUP>2</SUP>-1, y presenta una solución secuencial basada en el algoritmo A*. Se estudian variantes de la función heurística clásica (basadas en la Distancia de Manhattan) y se expone un trabajo experimental para analizar las mejoras en el rendimiento producidas, partiendo de diferentes configuraciones iniciales. Se propone una solución paralela al problema del Puzzle N<SUP>2</SUP>-1 sobre una arquitectura tipo cluster, y se analiza el speedup, la eficiencia, y la superlinealidad a medida que se escala el número de procesadores y el tamaño del problema (N). Se presenta además una generalización del problema para su aplicación a la planificación de movimientos de robots con múltiples objetivos.