Skip to content

Proyecto extraído de trimestres anteriores de la materia dictada por Blai Bonet

Notifications You must be signed in to change notification settings

LeoGCode/proyecto-1-ci5437

 
 

Repository files navigation

Introduccion

Proyecto 1 de la Asignatura Inteligencia Artificial I dictada por el profesor Carlos Infante durante el trimestre Abril Julio 2023. Este tiene como finalidad realizar estudios acerca de busquedas en espacios de estados mediante heuristicas tanto aditivas como no aditivas.

Equipo

  • Leonel Guerrero 18-10638
  • Eros Cedeño 16-10216

Objetivo

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.

Problemas

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

Árboles de búsqueda

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.

Heurísticas

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.

Algoritmos informados

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á").

Casos de prueba

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.

Cualquier trabajo extra (heurísticas o algoritmos extra implementados, otros métodos de eliminación de duplicados, etc...) contará para los puntos de participación.

About

Proyecto extraído de trimestres anteriores de la materia dictada por Blai Bonet

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 65.8%
  • Python 28.2%
  • Makefile 5.2%
  • CMake 0.8%