Inteligencia Artificial (Optativa 1º ciclo)

Problema a resolver

AVISO: Las representaciones usadas en la práctica 1 del curso 2001/2002 no pueden proponerse en la solución de este problema.

El juego de Bumper Cars se desarrolla en un espacio de dos dimensiones dividido en casillas, donde en cada casilla puede haber un obstáculo (la casilla es inaccesible), un coche verde , o un coche azul . Además entre algunas casillas existe un muro que las incomunica con otras casillas vecinas. Existe además un muro rodeando el espacio del juego que sólo tiene 2 salidas (una verde y una azul). El objetivo es sacar cada coche a la salida de su color. Los muros, obstáculos y salidas son fijos durante cada ejecución del juego.  (3).
 

El espacio del juego es un tablero 5x5 aunque la implementación deberá permitar cambiar a un tablero NxN sin mas que cambiar el valor de una constante. Puede suponerse un número máximo posible de obstáculos (N), muros horizontales (N) y muros verticales (N). Los obstáculos se definarán indicando sus coordenadas; (1,2), (2,3) y (3,1) en el ejemplo. De la misma manera se indicará las posición de los coches; (1,0) para el verde y (3,0) para el azul en el ejemplo.  Para las posiciones de los coches se permitarán valores de las coordenadas mayores que 4 o menores que 0 en función de la posición de las salidas; en el ejemplo la solución vendrá dada por una posición del coche verde en (1,5) y del coche azul en (3,5). Los muros interiores horizontales se representarán indicando las coordenadas de la celda que tienen por debajo; (0,0) y (4,2) en el ejemplo. Los muros interiores verticales se representarán indicando las coordenadas de la celda que tienen a la izquierda: (3,3) en el ejemplo. Ya que el tablero tiene que tener exactamente dos salidas no es necesario indicar explícitamente los muros exteriores; es más cómodo indicar las salidas. Para ello se indicará si hay salida en la cara norte y cual es su coordenada, y lo mismo con cada una de las otras caras.

Los operadores son {norte,sur,este,oeste}. Un coche sólo puede moverse a una casilla adyacente si ésta está libre. Al ejecutar cualquiera de estos operadores, avanzará un coche, los dos o ninguno, dependiendo de si el movimiento es posible para cada coche, es decir, si no hay obstáculos ni otro coche ni un muro.

Para simplificar el problema se tendrá en cuenta que una vez que un coche sale por alguna de las salidas, ya  no puede moverse más. Por tanto es posible que dos coches salgan por su salida en momentos diferentes.

Si los coches se encuentran en el siguiente estado:  AV,y se ejecuta el operador Oeste, sólo se puede mover el coche azul, ya que los movimientos deben ser simultáneos. No importa que al mover el coche verde, el coche azul podría moverse al oeste a continuación. Debe hacerse la misma consideración en los casos similares a este para todas las posibilidades de coches adyacentes.

El estado inicial se leerá de un fichero inicio con el formato arriba indicado. El estado final es el que se corresponde con el objetivo definido y por tanto viene dado por la posición de las salidas.

Una vez obtenida la solución se ideará alguna forma de visualizarla paso a paso.

Para el análisis experimental, se usaran cinco escenarios:

-el de la figura mostrada.
-el de la figura mostrada cambiando el coche verde a (4,3)
-el de la figura mostrada cambiando el coche azul a (1,1)
-el de la figura mostrada cambiando la salida azul a la cara oeste coordenada 2.
-el de la figura mostrada cambiando el obstáculo (2,3) a la posición (0,2)

Se utilizará en cada caso búsqueda primero en anchura y busqueda heurística A* con dos heurísticas distintas. Se medirá el coste de la búsqueda :

que se pueden obtener en el fichero generales.