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.
Máquina con Linux o Windows XP y Mac OSX
en adelante
