Inteligencia Artificial: evitar pensar dos veces

Posted on the junio 19th, 2007 under Inteligencia Artificial,Investigación,Programación Lógica by Nacho

Del trabajo práctico número 2 de Inteligencia Artificial, el cuál implementamos en Java el simulador y la inteligencia en SWI-Prolog usando JPL, surgieron varias cosas interesantes.

El modelar las reglas de inferencia y la base de conocimiento del Agente en Prolog, fue muy sencillo debido a que previamente habíamos hecho un buen diseño lógico de los axiomas de estado sucesor, reglas causales, etc. El mapeo de estas reglas formales a Prolog fue casi directo.

El Agente, era un Agente Pacman con un mundo estático, aleatorio, cerrado, parcialmente observable, con visión limitada a las celdas adyacentes (izquierda, derecha, arriba, abajo). Dado tal escenario, Pacman debía ir conociendo el mundo y aplicando sucesivas reglas de inferencia para saber como cumplir su objetivo realizando ciertas acciones. Pero nuestro agente pensaba las cosas dos veces antes de determinar una acción. Mejor dicho, pensaba demasiadas veces lo mismo 🙂 (detalles dentro del post).

En un principio habíamos definido los axiomas de estado sucesor, como reglas recursivas similares a la siguiente:

1
celda_vacia(X,Y,S1) :- S is S1 - 1, celda_vacia(X,Y,S).

Esta era una de las situaciones que se podía dar. Es decir: Una celda vacía en una Situación S seguirá estando vacía en la situación S + 1 (S1). Esto debido a la simplificación del escenario por supuesto.

Para saber que celdas estaban vacías en una situación S=5 bastaba con consultar por:

1
celda_vacia(X,Y,5).

Para saber si la celda X=1,Y=3 en la situacion 4 estaba vacía:

1
celda_vacia(1,3,4).

El problema surgió a medida que se avanzaba en las situaciones. Para una situación 6 había llamadas recursivas por cada consulta de una celda, si estaba vacía, si había enemigo, si había comida, etc. A esto había que sumarle que las percepciones recibidas podían estar generando duplicados, ya que una celda vacía de una situación anterior se podía estar percibiendo. El agente estaba deduciendo cosas que ya había deducido antes. Diseño elegante, pero muy ineficiente.

Quisimos modelar estos axiomas agregando una cláusula

1
assert(celda_vacia(X,Y,S))

al final de cada uno de los predicados, pero sólo terminamos teniendo más duplicados en la base de conocimiento, lo que enlentecía la búsqueda.

Seguramente hay soluciones más eficientes para resolver esto como la utilización de la familia de predicados

1
record(K,P)

pero lo resolvimos de la siguiente forma:

Definimos predicados

1
estado_sucesor(S1)

por cada posible desencadenante de una regla de estado sucesor, es decir, por cada pre-condición que podía llegar a determinar una celda vacía, una celda con enemigo, una celda con comida, etc. Cada uno de esto predicados, verificaba que la post-condición (es decir lo que se quería determinar), no se hubiese agregado antes a la base de conocimiento o no se conociera por inferencia de la percepción. Si pasaba este chequeo, entonces una vez garantidas las precondiciones, se hacía el assert(P) a la base de conocimiento.

Luego, desde Java, una vez pasada la percepción, se consultaba la base con el predicado

1
findall(_,estado_sucesor(S),_)

donde S era la situación en particular.

Lo que hace findall era encontrar todas las posibles soluciones para estado_sucesor, por lo que obteniamos el efecto deseado de ejecutar todos los assert sólo las veces que fueran necesarias.

Debajo dejo un ejemplo de un axioma de estado sucesor y su explicación:

1
2
3
estado_sucesor(S1):- S1 > 1,S is S1-1,vacia(X,Y,S),not(vacia(X,Y,S1)),asserta(vacia(X,Y,S1)).
estado_sucesor(S1):- S1 > 1,S is S1-1,posicion(X,Y,S),accionEjecutada(comer,S),asserta(vacia(X,Y,S1)).
estado_sucesor(S1):- S1 > 1,S is S1-1,posicion(X,Y,S),accionEjecutada(pelear,S),asserta(vacia(X,Y,S1)).

Una celda X,Y está vacía en la situación S+1 si:

está vacía en la situación S ó
el Agente está en la posición X,Y en la situación S y su acción ejecutada fue “comer” ó
el Agente está en la posición X,Y en la situación S y su acción ejecutada fue “pelear”

Notar que antes de hacer el asserta(P), me fijo que no se haya percibido como vacía. Para los 2 últimos casos no hace falta 😉

Apenas aprobemos el trabajo práctico vamos a liberar el código fuente de ambos (del primero implementado con búsqueda y del segundo implementado con lógica).

3 Responses to 'Inteligencia Artificial: evitar pensar dos veces'

  1. junio 20, 2007 a las 8:54 pm
    Juanjo
  2. junio 21, 2007 a las 12:11 am
    webmaster
  3. junio 21, 2007 a las 11:01 am
    webmaster

Leave a Reply




XHTML::
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>