PROBLEMAS Y ESPACIO DE ESTADOS

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. Imaginemos, por ejemplo, una habitación con estantes en la que hay un libro. Un robot se desea desplazar por la habitación con el fin de llegar a dicho libro. ¿De qué manera lo hará? En este punto es donde entran en juego las estrategias y los algoritmos de búsqueda.

El primer paso para diseñar un programa que resuelva un problema es crear una descripción formal y manejable del propio problema. Sería adecuado contar con programas que produzcan descripciones formales a partir de descripciones informales, proceso denominado operacionalización. Dado que por ahora no se conoce la forma de construir estos programas este proceso debe hacerse manualmente. Hay problemas que por ser artificiales y estructurados son fáciles de especificar (por ej. el ajedrez, el problema de las jarras de agua, etc.).

Otros problemas naturales, como por ej. la comprensión del lenguaje, no son tan sencillos de especificar. Para producir una especificación formal de un problema se deben definir:- espacio de estados;- estado inicial del problema;- estado objetivo o final;- reglas que se pueden aplicar para pasar de un estado a otro.

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 instante dado.

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

Es necesario hacer cambios en el espacio de estado para que pase a otro estado (movimiento), el cual también sufrirá nuevas transformaciones. Por lo cual hay que definir una serie de operadores.

Operador: convierte un estado en otro.

Pero hace falta definir el conjunto de acciones para llevar a cabo las transformaciones entre estados.

No todos los estados son admisibles a partir del estado inicial. Debe existir un conjunto de transferencias que lleve al estado final:

E0 ~ E1 ~ E2 ~......En

Al conjunto de transferencias también se le llaman reglas del tipo: Antecedente y Acción. Que sirven para realizar todos los estados.

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

Así uno de los métodos de búsqueda de soluciones para problemas poco estructurados (no existe un algoritmo bien definido), son los espacios de estado

Su estructura se corresponde con la resolución de problemas porque:-permite definir formalmente el problema, mediante la necesidad de convertir una situación dada en una situación deseada mediante un conjunto de operaciones permitidas; -permite definir el proceso de resolución de un problema como una combinación de técnicas conocidas y búsqueda (la técnica general de exploración del espacio intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).

REPRESENTACION DE ESPACIO DE ESTADOS

En el mencionado problema del robot en la habitación el conjunto de estados que el agente (en nuestro ejemplo, el robot) debe recorrer, generalmente se representa mediante un grafo, aunque en algunos casos concretos se usan árboles. Cada nodo del grafo representará a uno de los estantes de la habitación, y dos nodos serán adyacentes si también lo son sus estantes correspondientes. El grafo del dibujo en la parte inferior representa el tablero de manera parcial, y cada nodo es identificado por un número. Suponemos que la posición inicial del robot es el estante marcado con el número 1. En este grafo se aplica una correspondencia entre los nodos del mismo y los estantes numerados de igual forma. Como se puede observar en el tablero, por ejemplo, el estante 1 es adyacente al 2 y al 5, así :

Espacios de estados Determinísticos y espacios no determinístico

Como se mencionó en el tema anterior, el espacio de estados es la representación de un problema que abarca todas las posibles situaciones que se pueden presentar en la solución del problema

Los espacios de estados pueden clasificar en dos tipos: los implícitos y los explícitos, como se muestra en el diagrama siguiente

Los espacios de estados implícitos normalmente utilizan un sistema de producción para generar sobre la marcha los posibles estados siguientes de un estado dado. Los juegos suelen crear un espacio de estados implícito ya que un juego puede variar dependiendo de las reglas que lo describen.

Los espacios de estados explícitos son aquellos en los se define, previo al inicio de la búsqueda, todos los estados posibles y las conexiones entre ellos.

La representación de los espacios de estados explícitos se puede dar o no determinísticamente, esto es, que el espacio de estados determinísticos contienen un único estado inicial y seguir la secuencia de estados para la solución, mientras que el no determinístico contiene un amplio número de estados iniciales y sigue la secuencia de estados perteneciente al estado inicial del espacio.

Los espacios de estados determinísticos son usados por los sistemas expertos, mientras que los no determinísticos son usados por sistemas de lógica difusa.