Título: SokoGAS

Marco de Trabajo: Curso Algoritmos Evolutivos

Área de desarrollo: Inteligencia Artificial

Autor: Roger Abelenda, Isabel Gabard

Contacto: rabelenda@gmail.com

Día: LUNES

Hora: 15:30

Palabras Claves: Sokoban, Algoritmos Evolutivos

Resumen:
Sokoban es un juego de origen japonés muy conocido. El problema fundamental consiste en arrastrar cajas desde sus orígenes a posiciones de destino. El juego a cobrado especial interés en el ambiente académico (más específicamente en el área de inteligencia artificial), para el estudio de búsquedas complicadas de soluciones como la requerida en el juego. El problema es un problema NP-complejo para los cuales los algoritmos evolutivos son utilizados ampliamente. El presente proyecto trata la problemática de encontrar soluciones al juego Sokoban mediante el uso de algoritmos evolutivos. Dentro de los temas abarcados se encuentran el estudio de la complejidad del problema y de sus soluciones para distintos niveles del juego. Como se sabe, los problemas NP-complejos no pueden ser resueltos de forma eficiente utilizando algoritmos exactos, por lo tanto el uso de algoritmos genéticos es una buena aproximación para atacar el problema planteado. Los algoritmos genéticos se basan, a grandes rasgos, en la búsqueda de soluciones a partir de búsquedas locales y globales haciendo uso de heurísticas específicas para el problema que mejoran las posibles soluciones hasta encontrar una que esté suficientemente cerca del óptimo global. En el proyecto se plantean algunas formas de resolver el problema haciendo uso de algoritmos evolutivos y se dan algunas bases para seguir con el estudio del mismo. Para la solución se implementaron las funcionalidades específicas del juego en un simulador y un algoritmo genético (implementado en base a la librería GAlib) que depende de este simulador para su funcionamiento. Para atacar el problema el simulador representa al escenario con sus cajas y el robot y realiza cálculos que tienen en cuenta variables interesantes, como las posiciones deadlocks (posiciones de las cuales una caja no puede salir), posiciones reachables (posiciones alcanzables por el robot), validación de secuencia de movimientos de cajas, listado de todos los posibles movimientos de las cajas dado un escenario, cantidad de movimientos del robot para ir hacia una posición, etc. La solución alcanzada no resultó ser tan buena como se esperaba en un inicio, pero igualmente se plantean mejoras a realizar al algoritmo, y otras formas de encarar el problema. El proyecto resulta interesante como primer aproximación para atacar el problema haciendo uso de algoritmos evolutivos.