PROBLEMAS Y ESPACIO DE ESTADOS

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.

Un problema se define por:

ü  Estado inicial, conjunto de operadores, predicado meta, función de coste del camino

 Solución:

ü  Camino del estado inicial a un estado que satisface el predicado meta.

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 operaciónalizació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.

·         Espacio de estados;- estado inicial del problema.

·         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).

Existen diferentes formas de representar problemas para resolverlos de manera automática.

·         Representaciones generales

ü  Espacio de estados: un problema se divide en un conjunto de pasos de resolución desde el inicio hasta el objetivo.

·         Reducción a subproblemas: un problema se puede descomponer en una jerarquía de subproblemas.

·         Representaciones para problemas específicos.

ü  Resolución de juegos.

ESPACIOS DE ESTADOS:

ü  Espacio de Estados: Conjunto de todos los estados alcanzables desde el estado inicial por cualquier secuencia de operadores.

·   Los estados y su relación de accesibilidad conforman lo que se denomina espacio de estados.

·         Representa todos los caminos que hay entre todos los estados posibles de un problema.

·         Podría asimilarse con un mapa de carreteras de un problema.

·         La solución de nuestro problema está dentro de ese mapa.

·     Solución: Secuencia de pasos que llevan del estado inicial al final (secuencia de operadores) o también el estado final

·         Tipos de solución: una cualquiera, la mejor, todas

·         Coste de una solución: Gasto en recursos de la aplicación de los operadores a los estados. Puede ser importante o no según el problema y que tipo de solución busquemos.

v  Descripción de un problema en Espacio de Estados.

·         Definir el conjunto de estados del problema (explícita o implícitamente)

·         Especificar el estado inicial.

·         Especificar el estado final o las condiciones que cumple.

·         Especificar los operadores de cambio de estado (condiciones de aplicabilidad y función de transformación).

·         Especificar el tipo de solución:

ü  La secuencia de operadores o el estado final.

ü  Una solución cualquiera, la mejor (definición de coste).

Espacios de estados es un modelo matemático de un sistema físico descrito mediante un conjunto de entradas, salidas y variables de estado relacionadas por ecuaciones diferenciales de primer orden que se combinan en una ecuación diferencial matricial de primer orden.

 La representación de espacios de estado (también conocida como aproximación en el dominio del tiempo) provee un modo compacto y conveniente de modelar y analizar sistemas con múltiples entradas y salidas. Con P entradas y Q salidas, tendríamos que escribir Q*P veces la transformada de Laplace para procesar toda la información del sistema.