INTELIGENCIA ARTIFICIAL
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.
EJEMPLO
Por ejemplo, en el problema de jugar al ajedrez:- el espacio
de estados son la totalidad de tableros que se puede generar en un juego de ajedrez;-
el estado inicial es el tablero de 8 x 8 donde cada celda contiene un símbolo
de acuerdo a las piezas situadas;- el objetivo o estado final se define como
cualquier posición de tablero en la que el contrario no puede realizar ningún
movimiento legal y su rey esté amenazado;- las reglas son los movimientos
legales, que pueden describirse mediante una parte patrón para ser contrastado
con la posición actual de tablero y otra parte que describe el cambio que debe
producirse en el tablero.
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
definirlo 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).
REPRESENTACIÓN 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í:
