La IA en la Solución de Problemas: Espacio de Estados



    
Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan definiendo las configuraciones posibles del problema estudiado. El problema se plantea en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformaciones válidas según el modelo del problema. La respuesta, es la secuencia de transformaciones cuya aplicación sucesiva lleva a la configuración deseada.

 

     Los ejemplos más característicos de esta categoría de problemas son los juegos. En un juego, las configuraciones del universo corresponden directamente a las configuraciones del tablero. Cada configuración, es un estado que puede ser esquematizado gráficamente y representado en forma simbólica. Las transformaciones permitidas corresponden a las reglas o movidas del juego, formalizadas como transiciones de estado.

 

     Entonces, para plantear formalmente un problema, se requiere precisar una representación simbólica de los estados y definir reglas del tipo condición - acción para cada una de las transiciones válidas dentro del universo modelado. La acción de una regla indica como modificar el estado actual para generar un nuevo estado. La condición impone restricciones sobre la aplicabilidad de la regla según el estado actual, el estado generado o la historia completa del proceso de solución.

 

      El espacio de estados de un juego es un grafo cuyos nodos representan las configuraciones alcanzables (los estados válidos) y cuyos arcos explicitan las movidas posibles (las transiciones de estado). En principio, se puede construir cualquier espacio de estados partiendo del estado inicial, aplicando cada una de las reglas para generar los sucesores inmediatos, y así sucesivamente con cada uno de los nuevos estados generados (en la práctica, los espacios de estados suelen ser demasiado grandes para explicitarlos por completo).

      Cuando un problema se puede representar mediante un espacio de estados, la solución computacional corresponde a encontrar un camino desde el estado inicial a un estado objetivo.

Ejemplo:

     Un arriero se encuentra en el borde de un rio llevando un puma, una cabra y una lechuga. Debe cruzar a la otra orilla por medio de un bote con capacidad para dos (el arriero y alguna de sus pertenencias). La dificultad es que si el puma se queda solo con la cabra la devorará, y lo mismo sucederá si la cabra se queda sola con la lechuga. ¿Cómo cruzar sin perder ninguna pertenencia?

 

Representación de las configuraciones del universo del problema:

     Basta precisar la situación antes o después de cruzar. El arriero y cada una de sus pertenencias tienen que estar en alguna de las dos orillas. La representación del estado debe entonces indicar en que lado se encuentra cada uno de ellos. Para esto se puede utilizar un término simbólico con la siguiente sintáxis: estado(A,P,C,L), en que A, P, C y L son variables que representan, respectivamente, la posición del arriero, el puma, la cabra y la lechuga. Las variables pueden tomar dos valores: i y d, que simbolizan respectivamente el borde izquierdo y el borde derecho del rio. Por convención se elige partir en el borde izquierdo. El estado inicial es entonces estado(i,i,i,i). El estado objetivo es estado(d,d,d,d).

 

Definición de las reglas de transición:

     El arriero tiene cuatro acciones posibles: cruzar solo, cruzar con el puma, cruzar con la cabra y cruzar con la lechuga. Estas acciones están condicionadas a que ambos pasajeros del bote estén en la misma orilla y a que no queden solos el puma con la cabra o la cabra con la lechuga. El estado resultante de una acción se determina intercambiando los valores i y d para los pasajeros del bote.

 

Generación del Espacio de Estados:

     En este ejemplo se puede explicitar todo el espacio de estados (el número de configuraciones está acotado por:

estado	movidas
	cruza solo	con puma	con cabra	con lechuga
estado(i,i,i,i)	problema	problema	estado(d,i,d,i)	problema
estado(d,i,d,i)	estado(i,i,d,i)	imposible	estado(i,i,i,i)	imposible
estado(i,i,d,i)	estado(d,i,d,i)	estado(d,d,d,i)	imposible	estado(d,i,d,d)
estado(d,d,d,i)	problema	estado(i,i,d,i)	estado(i,d,i,i)	imposible
estado(d,i,d,d)	problema	imposible	estado(i,i,i,d)	estado(i,i,d,i)
estado(i,d,i,i)	problema	imposible	estado(d,d,d,i)	estado(d,d,i,d)
estado(i,i,i,d)	problema	estado(d,d,i,d)	estado(d,i,d,d)	imposible
estado(d,d,i,d)	estado(i,d,i,d)	estado(i,i,i,d)	imposible	estado(i,d,i,i)
estado(i,d,i,d)	estado(d,d,i,d)	imposible	estado(d,d,d,d)	imposible
estado(d,d,d,d)	problema	problema	estado(i,d,i,d)	problema

Este espacio de estados también se puede representar mediante un grafo equivalente.

 

Solución del Problema:

     El camino que pasa por la siguiente secuencia de estados es una solución del problema:

estado(i,i,i,i)
cruza con cabra
estado(d,i,d,i)
cruza solo
estado(i,i,d,i)
cruza con puma
estado(d,d,d,i)
cruza con cabra
estado(i,d,i,i)
cruza con lechuga
estado(d,d,i,d)
cruza solo
estado(i,d,i,d)
cruza con cabra
estado(d,d,d,d)

Fuente: http://users.dcc.uchile.cl/~abassi/52a/material/c5.html