Inteligencia Artificial (Optativa 1º ciclo)
Práctica I
22-10-2000
La práctica consiste en adaptar el programa puzzle que
se puede encontrar en la página WWW de la asignatura a otros problemas
de búsqueda. En primer lugar debe estudiarse la solución
al problema del puzzle que se puede encontrar en:
http://www.dc.fi.udc.es/ai/~barreiro/iadocen/ialab.htm
y después se harán las modificaciones oportunas para adaptarlo
al nuevo problema. Para ello, será necesario:
-
Separar el programa puzzle de las interfaces gráficas curses y Tcl-Tk,
de tal manera que el programa pueda ser ejecutado directamente desde la
línea de comandos.
-
Adaptar el programa al problema de búsqueda definido.
El diseño del programa facilita esta labor ya que sólo
se necesitarán cambiar ciertos aspectos sin necesidad de modificar
los algoritmos de búsqueda
-
Cambiar el estado que define la situación actual del mundo
-
Definir una nueva lista de operadores y sus correspondientes funciones
aplicable
y aplicar
-
Definir nuevas heurísticas para la búsqueda A*
Antes de la implementación, se definirá el nuevo problema
de búsqueda. El diseño del problema será realizado
pensando en la eficiencia del programa, de tal manera que se decidirá:
-
La complejidad de los operadores.
Por ejemplo, en el 8-puzzle se puede pensar en mover el hueco 1 posición
a cada lado o mover varios bloques al mismo tiempo lo que equivaldría
a mover el hueco dos veces en la misma dirección.
-
La información contenida en el estado.
Por ejemplo, en el 8-puzzle, se incluyen las coordenadas del hueco
en el grid, que no son estrictamente necesarias, ya que el estado incluye
el grid como un array con todos los número y el hueco, sin embargo
hace más cómoda la labor de los operadores.
Defensa de la práctica
La práctica se defenderá en el laboratorio de prácticas
asignado a la asignatura. La defensa se realizará en las horas de
prácticas y atendiendo a la fecha límite que se indicará.
La defensa consistirá en la entrega de una breve memoria,
demostración de la práctica y contestación a las preguntas
del profesor. La memoria incluirá los siguientes puntos:
Para el análisis experimental se construirá una tabla de
resultados con una cabecera del tipo:
d numdeejs CBBA CBA*(h1) CBA*(h2) tA*(h1) tA*(h2)
donde para cada solución de longitud de camino d, se
han probado un número de ejemplos numdeejs,
CB mide el coste de la búsqueda por medio del
promedio de nodos generados,
y t es una medida del tiempo empleado en la búsqueda.
Para la búsqueda en anchura, el coste se calculará de forma teórica, para lo que se supondrá un factor de ramificación
promedio.
Problema a resolver
El juego del sokoban se desarrolla en un espacio de dos dimensiones
dividido en casillas, donde en cada casilla puede haber un obstáculo,
un robot o un bloque. El robot puede moverse por las casillas libres. Si
se mueve donde hay un bloque, empuja a éste a la siguiente casilla,
si está libre, sino, no cambia de posición. De esta forma
puede mover los bloques a diferentes posiciones. El objetivo es llevar
los bloques a unas posiciones concretas (indicadas con un punto).
En la definicion básica del problema, los operadores son
{norte,sur,este,oeste}, y el tipo de escenario básico
constará de un único bloque que el robot deberá llevar
a la posición final, sin embargo, la definición del problema
permitirá un número de bloques cualquiera, sin más
que cambiar una constante.
Cada grupo de prácticas podrá cambiar la definición
del problema con el fin de hacer que el programa resuelva escenarios
más complejos (más bloques, escenarios más grandes,
...).
Se creará un módulo en el programa para visualizar
la solución del problema paso a paso.
El estado inicial se leerá de un fichero inicio con
el formato arriba indicado. El estado final se indica con los puntos en
ciertas casillas.
Para el análisis experimental, se usará como escenario
básico el de la figura anterior.
Opcionalmente:
-
Se ampliará el análisis experimental variando el tamaño
del grid e incluso el número de bloques, para determinar cuál
es el factor más determinante para la complejidad de la búsqueda.
-
El programa determinará en qué casos no hay solución
para el problema para evitar búsquedas infructuosas.
