Espacios de estados

4.1 PROBLEMAS Y ESPACIOS DE ESTADOS

Muchos de los problemas que pueden ser resueltos aplicando técnicas de inteligencia artificial se modelan en forma simbólica y discreta definiendo las configuraciones posibles del universo estudiado. El problema se plantea entonces en términos de encontrar una configuración objetivo a partir de una configuración inicial dada, aplicando transformacionesválidas según el modelo del universo. 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 (son universos restringidos fáciles de modelar). En un juego, las configuraciones del universo corresponden directamente a las configuraciones del tablero. Cada configuraciónes 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 lastransiciones 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 grandespara 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.

Entonces un problema típico de la Inteligencia Artificial consiste en buscar un estado concreto entre un conjunto determinado, al que se le llama espacio de estados.

El primer pasopara diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema.

Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ejemplo el ajedrez). Otros problemas naturales, como por ejemplo la comprensión del lenguaje(¿Qué es?), no son tan sencillos de especificar.

Para producir una especificación formal de unproblema se deben definir:

*Espacios de estados
*Estado inicial del problema
*Estado objetivo o final
*Reglas que se puedan aplicar para pasar de un estado a otro.

CONCEPTOS ÚTILES

Problemas lógicos.- El hallazgo de la solución de un problema mediante un “espacio de estado” y los métodos de búsqueda en este espacio de solución.

Estado.- la representación de un problema en un instantedado

Espacio de estado.- se trata de definir el problema mediante estados posibles.

Operador.-convierte un estado en otro

Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todos los estados válidos, sino que es posible definirlo de manera más general.


1-Ejemplo de espacio de estados

Descripción del problema:
Un arriero se encuentra en elborde 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 pertenecias). 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...