Tema 4

Encadenamiento hacia adelante y hacia atras

Un grupo de múltiples reglas de inferencia que contiene un problema con su solución se llama cadena.

Una cadena que realiza una búsqueda o camino desde el problema a la solución se llama una cadena hacia adelante.

Este tipo de cadena va desde los hechos hsta las conclusiones que siguen a partir de los hechos.

Una cadena que transita hacia atrás desde una hipótesis hasta los hechos que soportan tal hipótesis se llama una cadena hacia atrás. Otra forma de definirla es en términos de una meta que puede estar formada por submetas que se han cumplido.

El encadenamiento se puede expresar con cierta facilidad en términos de inferencia si suponemos que tenemos reglas del tipo Modus-poner.

p->q
p
_____________
:. q 		conejo(x)->mamifero(x)
mamifero(x)->animal(x)
Por tanto una cadena causal de encadenamiento hacia adelante se representa mediante una secuencia de enlaces que conectan el consecuente de una regla con el antecedente de la siguiente.

Ejemplo:

conejo(Bugs Bunny)
conejo(x)->mamifero(x)
mamifero(x)->animal(x)
aminal(Bugs Bunny)

Un enlace, por otra parte también indica la unificación de variables a hechos. Por ejemplo la variable x en el predicaco conejo(x) debe ser unificada en el primer lugar con el hecho conejo(Bugs Bunny) antes de que la regla conejo se pueda aplicar, por lo que la cadena causal será en realidad una sucesión de implicaciones y unificaciones

En el encadenamiento hacia atrás el proceso es el inverso: queremos probar la hipótesis de animal(Bugs-Bunny). El problema central del encadenamiento hacia atrás es encontrar una cadena de enlace entre la evidencia y la hipótesis.

El hecho conejo(Bugs Bunny>) se llama la evidencia en el encadenamiento hacia atrás, para indicar que se usará para sostener la hipótesis, siendo esta evidencia usada para probar dicha hipótesis. Tenemos una estructura de claúsulas.

Los encadenamientos hacia adelante y hacia atrás son en realidad caminos a través de un espacio de estados de un problema. En este espacio de estados del problema los estados intermedios se corresponden con hipótesis intermedias bajo el encadenamiento hacia atrás o conclusiones intermedias bajo el encadenamiento hacia adelante.

Características comunes

Conozco más el encadenamiento hacia atrás ya que conozco el pasado, pero el futuro no.

En un sistema basado en reglas tenemos el siguiente grafico:

Encadenamiento hacia atrás:

En el encadenamiento hacia atrás, el orden a probar la hipótesis h deberá de probarse al menos una de las hipótesis intermedias. Se observa que el diagrama, en este caso se describe como un diagrama AND/OR para indicar que en algún caso, tal como h2 todas las hiótesis de nivel inferior deben estar presentes para sostener h2.

En otros casos, tal como la hipótesis de nivel superior h solo es necesario una hipótesis de nivel inferior para que se verifique.

En el encadenamiento hacia atrás, el sistemas, por lo general, obtendrá evidencia del usuario, con el fin de probar o no la hipótesis, lo que contrasta con el sistema de encadenamiento hacia adelante, en el que todos los hechos relevantes se conocen por lo general con antelación.

Encadenamiento hacia atrás, desde la hipótesis a la evidencia. Busca lo profundo
Encadenamiento hacia adelante, desde los hechos hasta la conclusión

Describir una serie de representaciones o de agentes basados en objetos se llama un representante de resolución de problemas. Este representante o agente decide que hacer para encontrar secuencias de oraciones que conduzcan a un determinado estado.

El tipo de problema que resulta del proceso de formulación del mismo dependerá del conocimiento disponible por el representante o agente, en especial si conoce el estado actual y las salidas de las acciones podremos entonces definir con más precisión los elementos que constituyen el problema y sus soluciones.

Resolución de problemas: Los agentes se supone que actúan de forma tal que a través del entorno transita a través de una secuencia de estados de forma tal que se maximice una medida de rendimiento. Consideraremos en primer lugar que una meta es un conjunto de estados del problema y donde esta meta es la primera etapa a definir en la resolución del problema y que se formula en base a la situación actual del mismo.

Las acciones se pueden considerar como la causa de la transición entre los estados del problema. Así el agente se encontrará con acciones que le lleven a un estado meta u objeto, siendo previo que acciones y estados debemos de considerar en el problema. A esta fase se le llama formulación

En general, por tanto, un agente con varias acciones inmediatas examinará primero las distintas secuencias de acciones que le llevará a estados de valor conocido y entonces deberá elegir cual es la mejor de esas opciones. Al procedimiento de mirar tal secuencia de acciones se le llama búsqueda.

Un algoritmo de búsqueda tiene un problema como entrada y devuelve una solución en forma de una secuencia de acciones (Rich 2 y 3). Si se encuentra esa solución, las acciones recomendadas se realizan, tenemos la fase de ejecución. La estructura de lo que vamos a ver es lo siguiente:

funcion agente_de_soluciones_de_un_problema(p) return una_oración_simple
inputs: p, una percepción
structic: s, secuencia de acciones, inicialmente vacía,
estado, descripción del estado actual del mundo
g, una meta, inicialmente nula
problema, una formulación del problema
estado <- cambio_estado(estado, p)
if s esta vacio then
g <- FORMULACIÓN_DE_LA_META(estado)
problema <- FORMULACION_DE_LA_META(estado, g)
s <- BUSQUEDA(problema)
acción <- RECOMENDACION(s, estado)
s <- RESTANTE(s, estado)
return accion

Formulación de problemas

En primer lugar veremos el conocimiento que un determinado agente puede tener respecto de sus acciones y del estadoen el que está. Esto dependerá de como este conectado el agente a su entorno a través de sus percepciones y acciones. Por tanto, en general, se conocerá 4 tipos de problemas:
Problemas de estado sencillo
:
Consiste en suponer que los sensores o las percepciones del representante dan suficiente información para decirle exactamente en que estado está, es decir, el mundo es accesible. También suponemos que sabe exactamente lo que cada una de sus acciones hace. Es el caso más simple
Problemas de estado múltiple
:
Suponemos que el agente conoce todos los efectos de sus accioens, pero tiene un acceso limitado al estado del mundo, por ello que en este caso el agente solo puede razonar acerca de un conjunto de estados que él puede obtener en vez de estados simples de un elemento de un conjunto .......
Problemas de contingencia
:
El agente necesita para resolver el problema una cierta información adicional durante la fase de ejecución, por lo que el agente calgçcula un árbol completo de acciones en vez de una sola secuencia de acciones. En general, cada rama del árbol está relacionada con las posibles contingencias que puedan presentarse. Por esta razón se le llama problema de contingencia.
Problemas de exploración
:
Podemos considerar problemas relacionados con lo que es la busqueda y ejecución, de los que su expresión más sencilla son los juegos bipersonales.

Problemas bien definidos y soluciones

Un problema es en realidad una colección de información que el agente usará para decidir qué hacer:

Información necesaria para definir un problema de estados simple:
  1. El estado inicial que el agente conoce por sí mismo
  2. Conjunto de posibles acciones para el agente y donde definiremos el concepto de operadores para definir la descripción de una acción en términos de que estado será alcancado llevando la acción desde un estado particular. Una fórmula final alternativa usa una función de sucesiones s(x) en donde dado el estado particular x, devuelve el conjunto de estados alcanzables desde x mediante una acción simple.
Si tenemos los dos puntos anteriores, tenemos definido el espacio de estados del problema. Este es el conjunto de todos los estados alcanzables desde el estado inicial, mediante una suceción de acciones. Un camino en el espacio de estados es una secuencia de acciones que parte de un estado a otro

.......elemento de un problema bien definido es el contraste de meta, el cual se aplica a un determinado agente asociado a una descripción de un determinado estado para determinar si es un estado meta. Si existe un conjunto explícito de estados metas, el contraste simplemente chequea para ver si hemos alcanzado uno de ellos. Pero si los estados meta se representan por una propiedad abstracta, el contraste deberá determinar si se cumple la propiedad

Es posible que una solución sea preferible a otra, aún cuando ambas sean metas, pero es posible que se quieran caminos con menos acciones o con un coste menor. Es por ello que se necesita un cuarto elemento: función de coste de camino; es una función que asigna un coste al camino en donde se considera que el coste del camino es la suma de los costes de las acciones individuales a lo largo del camino.

Podemos definir un tipo de dato llamado problema:

tipo-de-dato PROBLEMA
componentes ESTADO-INICIAL, OPERADORES, CONTRASTE-META, FUNCION-COSTE-CAMINO

Elementos de este tipo de dato son las entradas a nuestro algoritmo de búsqueda

Las salidas de un algoritmo de búsqueda son una solución, esto es, un camino que va desde el estado inicial a un estado que satisface el contraste de meta

Debemos hacer una modificación para los problemas de estado múltiple, puesto que tenemos un estado inicial como un conjunto, mientras que los operadores serán también un conjunto de operadores que van a especificar para cada acción el conjunto de estados posibles desde cualquier estado dado, además de un contraste de meta y una función de coste de camino. Por tanto, ahora un operador se aplica a un conjunto de estados reuniéndose los resultados de aplicar el operador a cada estado del conjunto

Un camino conectará ahora conjuntos de estados y una solución es ahora un camino que permite a un conjunto de estados conectar con todos aquellos que son estados meta, por lo que el espacio de estados se reemplaza por el espacio de conjuntos de estados.

Ejemplo 1: Caso del puzzle de 8 piezas

En el caso del puzzle de 8 piezas y 9 casillas, la definición de estado especifica la localización de cada una de las ocho fichas en uno de los 9 cuadrados. Por eficiencia, es útil incluir también la localización del blanco.

Operadores: del blanco se mueve a izquierda, derecha, arriba o abajo
Contraste de meta: el estado meta es aquel que tiene una determinada configuración particular
Coste del camino: cada etapa tiene un coste unidad de forma tal que el coste del camino es justamente su longitud

Ejemplo 2: Misioneros y Caníbales

Consiste en que tres misioneros y tres caníbales deben cruzar el río solo con una canoa que puede llevar a dos personas. No puede haber nunca más caníbales de misioneros

Estados: Consiste en una sucesión ordenada de tres números que representan el número de misioneros, el número de caníbales y el de canoas en el lado del río donde empieza. Entonces el estado inicial será (3,3,1).
Operadores: tomar(un misionero)(un canibal)(dos misioneros)(dos caníbales)(uno de cada), para cruzar el río con la canoa. Tenemos por tanto como máximo 5 operadores, aunque en la mayoría de estados se tienen menos porque es necesario evitar estados ilegales. Observamos que si distinguimos entre personas individuales (6 personas), entonces el número de operadores pasa de 5 a 27.
Contrasde de meta: será alcanzar el estado (0,0,0).
Coste del camino: será el número de cruces.

El espacio de estados es bastante pequeño y se puede resolver en principio mediante un algoritmo de búsqueda pero tiene problemas derivados de las restricciones que se plantean de que en cada lado del río no puede haber más caníbales que misioneros.

Búsqueda de soluciones

La idea en la búsqueda de soluciones es mantener y extender un conjunto de sucesiones parciales y por tanto, la forma de generar esas sucesiones y mantenerla mediante estructuras de datos será fundamental.

Generación de sucesiones de acciones

El proceso de búsqueda es en realidad la construcción de un algoritmo de búsqueda en árbol que está superpuesto sobre el espacio de estado donde la raiz del árbol de búsqueda es un nodo que se corresponde con el estado inicial.

Estructura de un algoritmo general de búsqueda

funcion: BUSQUEDA_GENERAL(problema, estrategia) return solución o fallo
inicializar el arbol con un estado inicial del problema
loop do
if no existe candidato para la expansión then return fallo
elegir un nodo u hoja para extenderse de acuerdo a la estrategia
if el nodo contiene un estado metan then return solucion
else extender el nodo y añadir los nodos resultados al arbol de busqueda
end