El objetivo del proyecto es aprender sobre el modelo de espacio de estados y sobre los diferentes algoritmos de búsqueda heurística. No sólo se evaluará la correctitud de la implementación; es importante que los algoritmos sean eficientes y puedan resolver los problemas propuestos en los tiempos estipulados. También es importante su ánalisis de resultados en el informe.
Para el proyecto se usará el lenguaje declarativo PSVN, con su conjunto de herramientas y documentación que será entregada a los estudiantes. Se recomienda leer detenidamente los ejemplos, instrucciones y herramientas que vienen incluidas, recuerde que todo lo que se incluye es para facilitar el trabajo en el proyecto.
Será necesario utilizar C o C++ para trabajar con el API de PSVN y la implementación de algoritmos de búsqueda, para lo cuál también se incluyen ejemplos.
Consideramos los siguientes problemas:
- N-puzzles: 15-puzzle y 24-puzzle
- Cubo de Rubik: 3x3x3
- Top spin: 12-4, 14-4, y 17-4
- Torre de Hanoi con 4 astas: 12, 14, y 18 discos
Se requiere que incluya representaciones en PSVN para cada uno de los dominios. Para los N-Puzzle, es útil revisar las lecciones incluidas, pues encontrará ejemplos muy similares que ayudarán a realizar sus representaciones.
En el caso de los demás problemas, encontrará representaciones incluídas junto a PSVN, o en su defecto generadores para las mismas. Debe leer la información incluída para entender cómo funcionan estas representaciones.
Debe incluir como parte de la entrega las representaciones en PSVN utilizadas para cada problema, así como una breve explicación
Estudiar los árboles de búsqueda y su factor de ramificación sin eliminación de duplicados y con eliminación parcial de duplicados (poda de ancestros). Se deben crear tablas para cada problema donde se reporte el número de estados a cada profundidad en el árbol de búsqueda a partir del estado objetivo, hasta la profundidad máxima que se alcance en 15 minutos de ejecución.
Puede utilizar el código incluído con PSVN como ayuda para calcular esto.
Se deben implementar heurísticas PDBs para cada problema. Para los n-puzzles las PDBs deben ser aditivas. Para los otros problemas, se toma el máximo de varias PDBs. Leer el paper "Additive Pattern Databases" de Felner et al. que se incluye, y el paper sobre el Cubo de Rubik. Para el Cubo de Rubik, las PDBs estándar pueden tomar demasiado espacio; en ese caso, se pueden crear mas PDBs de menor tamaño.
En la documentación de PSVN hay secciones indicando como elaborar PDBs utilizando el lenguaje, así como ejemplos de ello. Deben incluir todos los archivos que utilicen para generarlos.
Estudiar la búsqueda de soluciones óptimas con algoritmos informados. Buscar soluciones para las instancias dadas en cada problema utilizando los algoritmos: A* con eliminación retardada de duplicados (DDD) e IDA* con eliminación parcial de duplicados. Para las heurísticas en cada problema:
- N-puzzles: distancia Manhattan (15-puzzle) y diferentes additive PDBs (15- y 24-puzzle)
- Cubo de Rubik: max de corner PDB y 2 edge PDBs (si son demasiado grandes, dividirlas en varias PDBs pequeñas)
- Top Spin: max de diferents PDBs
- Torre de Hanoi con 4 astas: max de diferentes PDBs
El tiempo máximo de ejecución lo deciden ustedes según los recursos que tengan a su disposición. Para A*, no permitan que el programa utilice memoria virtual (paginación sobre disco) ya que posiblemente correrá extremadamente lento y no podrán resolver el problema (y la máquina se les "congelará").
Se entregan casos de prueba para los n-puzzles y para el Cubo de Rubik. Para los problemas restantes deben generar casos de prueba con el programa global/generator.cc que se entrega en la distribución de PSVN. Leer el programa para entenderlo y poder ejecutarlo. Se deben generar casos de prueba fáciles y difíciles.
Deben entregar su implementación de la solución junto a un informe que explique las decisiones tomadas y los resultados de sus ejecuciones.