SISTEMAS INTELIGENTES

EJERCICIO 1

Enunciado | Código | Objetivos

Ejercicio 1: Búsqueda en árbol, no informada. Anchura y profundidad.

Dominio 1: Carreteras de Rumanía

Es un escenario extraído del [Russell&Norvig03] en el que tenemos un mapa de carreteras de Rumanía con las siguientes ciudades y distancias entre ellas por carretera:

Se trata de encontrar una ruta a Bucharest (preferentemente la más corta) partiendo de Arad.

Dominio 2: el 8-puzzle

Es la versión reducida de un puzzle muy conocido en el que tenemos una parrilla de 3 x 3 posiciones que contienen 8 piezas y un hueco. En cada situación podemos mover hacia el hueco alguna de sus piezas adyacentes. Para estas primeras pruebas tomaremos los siguientes estado inicial y estado meta:

1  2  3  4  5  6  7  8		4  1  3  7  2  5  8  6
Estado inicial		Estado meta

Codificaremos las posibles acciones como UP, DOWN, LEFT, RIGHT, dependiendo de cuál de las piezas movemos hacia el hueco.

Dominio 3: el mundo de los bloques

Se trata de un dominio de prueba muy conocido en Inteligencia Artificial. Tenemos un conjunto de N bloques numerados (de 0 a N-1). Cada bloque puede colocarse de uno en uno sobre la mesa (TABLE) o encima de otro bloque, formando torres. Sólo podemos mover bloques libres, que no tienen nada encima. En principio, en la versión más sencilla, la mesa tiene espacio suficiente para todos los bloques. Para estas primeras pruebas utilizaremos los siguientes estados inicial y estado meta.

Código a construir

Para cada dominio tendremos que completar dos archivos, domain.h y domain.c, que describimos a continuación.

• domain.h incluiremos ahí, como mínimo, la definición del tipo tState, un struct que contendrá la descripción de un estado del problema. Ahí incluiremos la información que consideremos necesaria. En el caso de las carreteras, en un estado basta con indicar la ciudad actual. En el 8-puzzle será un array de 3 x 3 junto con la posición (fila y columna) del hueco. En el mundo de bloques, un array con la posición donde reposa cada bloque (otro bloque o la mesa). En domain.h también incluiremos otras constantes que queramos usar. En el ejemplo romania.h, hemos incluído un nombre constante para cada ciudad (representada como número entero) del mapa de carreteras.
  
  
  
• domain.c contendrá todo el código para las siguientes funciones cuyas cabeceras están descritas en search.h:
  
  
  

  tState *loadDomain(char *); void freeDomain(); int goalTest(tState *s); int executable(unsigned op,tState *s); tState *successorState(unsigned op,tState *s); void freeState(tState *s); int cost(unsigned op,tState *s); void showOperator(unsigned op); void showState(tState *s);

  
  El archivo domain.c deberá contener los includes siguientes (en este orden):
  
  

  #include "domain.h" #include "search.h"

  
  
  La función loadDomain se encargará de construir el estado inicial de tipo tState, reservando espacio y devolviendo un puntero al mismo. Además, inicializará toda aquella información global de la búsqueda que necesitemos. En esa función deberemos establecer el valor de la variable global numOperators que indica el número de operadores. Por ejemplo, en el caso del mapa de carreteras, tendremos un operador por cada ciudad que indicará "moverse a la ciudad X". En el 8-puzzle tendremos 4 operadores (UP, DOWN, LEFT, RIGHT) mientras que en el mundo de bloques tendremos que usar un código entero para representar cada posible movimiento move(X,Y) donde X es un bloque (0..N-1) e Y una posición (cualquier bloque 0..N-1 o la mesa TABLE). El archivo romania.c contiene el ejemplo completo del mapa de carreteras.
  

• <algoritmo> puede ser búsqueda en árbol tree (por defecto) o búsqueda en grafo graph
• <tipodeinsercion> puede ser anchura breadth (por defecto) o profundidad depth
• <fichero> especifica un nombre de fichero que se le pasará a la función loadDomain, si nos interesa cargar el dominio a partir de un fichero
  

OBJETIVOS DEL EJERCICIO 1

1. Crear los dominios para el problema de 8-puzzle (ficheros 8puzzle.h y 8puzzle.c) y para el problema del Mundo de Bloques (ficheros blocks.h y blocks.h)
   
2. Experimentar con la búsqueda en anchura (la incluida por defecto en search.c) en los tres dominios: romania, 8puzzle y blocks.
   
   • ¿Cuántos nodos se expanden con búsqueda en árbol?
     
   • ¿y con búsqueda en grafo?
     
   • ¿la solución es óptima?
3. Cambiar a búsqueda en profundidad, insertando al principio de la frontera, en lugar de al final:
• ¿es necesario cambiar algo más en el algoritmo de búsqueda en árbol?
  
• ¿cuántos nodos se expanden?
• ¿la solución es óptima?