Inteligencia Artificial

Práctica 1 (obligatoria)

1. Enunciado

La práctica consiste en la resolución de un determinado tipo de problemas de enrutamiento para diseño de circuitos integrados. Las posiciones válidas en el circuito se determinan mediante una rejilla de puntos rectangular de dimensiones ROWS filas x COLS columnas. Sobre esa rejilla, nos especifican un número PATHS de pares de puntos a conectar, así como una serie de posiciones no válidas (obstáculos) que no se pueden utilizar. Se desea obtener el trazado de líneas de cable que conecte entre sí cada par de puntos, evitando tanto las posiciones obstáculo como, por supuesto, las líneas de los restantes pares.

Cuando el problema de enrutamiento tenga solución, se desea además conocer cuál es el trazado mínimo en términos de tramos de cable utilizados.

2. Ejemplo

Supongamos que tenemos 2 pares de puntos (el par p0 y el par p1) distribuidos en una rejilla de 7 filas x 7 columnas como la siguiente:

Ejemplo 1.
dos posibles soluciones a este problema serían:


Solución A
           
Solución B

La solución A consume 19 tramos de cable (13 para el par p0 + 6 para el par p1) y de hecho es óptima para el problema planteado, mientras que la solución B consume 25 tramos de cable (17 para el par p0 + 8 para el par p1).

3. Representación del problema

La búsqueda se realizará imaginando que "movemos" el cable de cada par de puntos avanzando desde uno cualquiera de ellos (el que llamaremos inicial) hasta el otro (que llamaremos final). La elección de cuál es el punto inicial y el final de cada par es arbitraria e irrelevante. En cada paso, haremos "avanzar" el cable evitando caer en un obstáculo o en una posición ya ocupada por cable (ya sea del par actual, o de otro par).

Estados

La información a almacenar en cada estado incluye un array llamado cells de ROWS filas x COLS columnas. Para cada posición cells[i][j], el valor -1 indicará que está vacía, el -2 que hay un obstáculo y un valor i entre 0 y PATHS-1 indicará que esa posición ha sido ocupada por el path i. En realidad, sería suficiente con indicar que está ocupada, pero almacenamos también el número de par a efectos de visualización.

Como ejemplo, la situación inicial del Ejemplo 1 se representaría con el array

     0  1  2  3  4  5  6

0   -1  0 -1 -1 -1 -1 -1
1
   -1 -1 -1 -1 -1 -1 -1
2   -1 -1  1 -1 -1 -2 -2
3   -1 -2 -2 -1 -1 -2 -2
4   -1 -2 -2 -1 -1 -1 -1
5   -1 -1 -1 -1 -1 -1 -1
6   -1 -1 -1 -1 -1 -1 -1

En este caso, hemos tomado como puntos iniciales el (0,1) para el par p0 y el (2,2) para el par p1. Como segundo ejemplo, si hacemos avanzar ambos cables 2 posiciones a la derecha, tendríamos el array:

     0  1  2  3  4  5  6

0   -1  0 
0  0 -1 -1 -1
1
   -1 -1 -1 -1 -1 -1 -1
2   -1 -1  1 
1  1 -2 -2
3   -1 -2 -2 -1 -1 -2 -2
4   -1 -2 -2 -1 -1 -1 -1
5   -1 -1 -1 -1 -1 -1 -1
6   -1 -1 -1 -1 -1 -1 -1

Nótese que los extremos finales no aparecen marcados. Usaremos un array constante endpoints de PATHS puntos, tal que endpoints[i].r y endpoints[i].c indican la fila y la columna de la posición final para el par pi. Como el array endpoints no varía, se puede almacenar como una variable general y no es necesario repetirlo en cada estado.

Para terminar, necesitaremos también indicar de algún modo el extremo actual de cada cable que hemos trazado, para saber por dónde continuar. Esto se hará manteniendo un array last[i] de modo que last[i].r y last[i].c indican la fila y la columna del extremo actual del cable pi.

Acciones

En cada paso vamos a trazar un tramo de cable para cada par de puntos. Los movimientos a realizar serán, para cada cable, uno de los 5 posibles: NOP (-), UP (u), DOWN (d), RIGHT (r) y LEFT (l). El movimiento NOP significa que no movemos el cable y se reserva exclusivamente para el caso en el que un cable concreto haya alcanzado su destino (esto es, cuando last[i] y endpoints[i] coinciden). Cuando eso sucede, en ese cable sólo se puede ejecutar NOP, mientras que si el cable no ha alcanzado el destino, nunca se puede ejecutar NOP. Para los movimientos usaremos las constantes:
#define NOP 0
#define UP 1
#define DOWN 2
#define LEFT 3
#define RIGHT 4

Como en cada paso de búsqueda movemos todos los cables, si PATHS=3 el aspecto de una acción sería, por ejemplo, una tupla como (r,u,-), indicando que trazamos un tramo de cable desde last[0] a la derecha, un tramo de cable desde last[1] hacia arriba y dejamos sin mover el cable 2. El número total de acciones posibles será por tanto: 5PATHS, esto es, 25 para PATHS=2, 125 para PATHS=3, etc. Para codificarlas usamos un valor entre 0 y 5PATHS-1. La siguiente función permite obtener un array ops[PATHS] con el movimiento correspondiente para cada cable a partir de un código de acción op:

void getOpsVector(int op,int ops[]) {
  int i;

  for (i=PATHS-1;i>=0;i--, op /= 5)
    ops[i]=op % 5;
}

Como ejemplo, si PATHS=3, el código de acción 113 devuelve el array {4,2,3} que corresponde a la acción conjunta (r,d,l).

4. Código disponible

Los ficheros fuente se proporcionan total o parcialmente:
Como se puede ver, el código para la obtención del estado inicial ya nos la facilitan. La función initialState construye un estado inicial a partir de un array de strings llamado settings. Para el Ejemplo 1, ese array tendría el aspecto:

char *setting[ROWS] = {
".0....1",
".......",
"..1..XX",
".XX..XX",
".XX...0",
".....XX",
".....XX"
};

donde '.' indica libre, 'X' indica un obstáculo y los dígitos son los pares a conectar. En principio, almacenamos el array settings en el fichero goal.h, de modo que cambiando ese fichero, podemos cambiar el dominio del problema a resolver. Estos son algunos ejemplos: goal0.h, goal1.h, goal2.h, goal3.h, goal4.h, goal5.h.

NOTA: al cambiar de dominio, podremos necesitar también cambiar el valor de las constantes ROWS, COLS y PATHS, definidas en routing.h.

Como último comentario, nótese que en routing.c, la función successorState también está prefijada. La idea es que el cálculo del estado siguiente se realizará simultáneamente con la comprobación de si una acción es ejecutable (executable), para evitar duplicar esfuerzos. De este modo, executable trabajará sobre un estado auxiliar aux, (ya declarado en routing.c) de forma que después, successorState devuelve una copia de ese estado. Este esquema funciona gracias a que siempre se llama a successorState justo después de comprobar si un estado es ejecutable.

5. Entrega

La práctica es individual y su plazo es el lunes 10 de enero. La forma de entrega por defecto es durante el desarrollo de las clases de laboratorio, aunque también es posible usar el horario de tutorías.