Agente Híbrido de Lógica Proposicional y Estado Lógico

Prerrequisito: Mundo Wumpus en Inteligencia Artificial

Para crear un agente híbrido para el mundo wumpus, la capacidad de deducir varios aspectos del estado del mundo puede integrarse de manera bastante simple con las reglas de condición-acción y los algoritmos de resolución de problemas. El programa del agente mantiene una base de conocimientos y una estrategia actualizada. Los axiomas atemporales, aquellos que no dependen de  , como el axioma que conecta la brisa de los cuadrados con la presencia de hoyos, se incluyen en la base de conocimiento inicial. La nueva frase de percepción se agrega en cada paso de tiempo, junto con todos los axiomas que dependen de  , como los axiomas de estado sucesor. (El agente no necesita axiomas para futuraspasos de tiempo, como se explica en la siguiente sección). Luego, el agente utiliza la inferencia lógica para determinar qué casillas son seguras y cuáles aún no se han visitado mediante   consultas de la base de conocimiento.

El cuerpo principal del programa de agente crea un plan basado en una prioridad decreciente de objetivos. Si hay un destello, el programa primero diseña una estrategia para agarrar el oro, regresar al lugar original y salir de la cueva. De lo contrario, si no existe un plan actual, el software traza una ruta hacia la casilla segura más cercana que aún no ha visitado, asegurándose de que la ruta pase solo por casillas seguras. Se utiliza una búsqueda ^* , no una  , para planificar una ruta. Si el agente todavía tiene una flecha y no hay casillas seguras para investigar, el siguiente paso es intentar hacer una casilla segura disparando a uno de los puntos wumpus disponibles. Estos se encuentran preguntando dónde   es falso, es decir, cuando se desconoce si hay o no un wumpus.  es utilizado por la función  (no se muestra) para planificar una secuencia de operaciones que alinearán esta toma. Si esto no funciona, el programa busca un cuadrado para explorar que no sea probablemente inseguro, es decir, uno para el que   devuelve falso. Si no existe tal cuadrado, la misión será imposible y el agente se retirará   y saldrá de la cueva.

Estados lógicos

El programa del agente funciona admirablemente, pero tiene un defecto fundamental: el costo computacional de las llamadas   crece exponencialmente con el tiempo. Esto se debe al hecho de que las conclusiones requeridas deben retroceder en el tiempo e involucrar un número creciente de símbolos de proposición. Obviamente, esto es insostenible: ¡no podemos tener un agente cuyo tiempo de procesamiento para cada percepción crezca al mismo ritmo que su vida útil! Realmente necesitamos un tiempo de actualización constante, es decir, uno que sea independiente de . La solución aparente es guardar, o almacenar en caché, los resultados de la inferencia para que el proceso de inferencia en el siguiente paso de tiempo pueda basarse en los resultados de las etapas anteriores en lugar de tener que reiniciarlo nuevamente. El estado de creencia, es decir, alguna representación del conjunto de todos los estados actuales concebibles del mundo, puede reemplazar la historia previa de las percepciones y todas sus repercusiones.

La estimación del estado es el proceso de actualizar el estado de creencia a medida que llegan nuevas percepciones. Podemos emplear una declaración lógica que involucre los símbolos de proposición asociados con el paso de tiempo actual, así como los símbolos atemporales, en lugar de una lista explícita de estados como en la Sección 4.4. Por ejemplo, considere la oración lógica.

describe el conjunto de todas las situaciones en el tiempo 1 en las que el wumpus está vivo, el agente está en  , el cuadrado está ventoso y hay un pozo en   o  en o en ambos.

Resulta que mantener un estado de creencia preciso como fórmula lógica no es sencillo. Hay 2 ⁿ estados potenciales, es decir, asignaciones de valores de verdad a esos símbolos, si hay n símbolos fluidos para el tiempo t. El conjunto de potencia (todos los subconjuntos) del conjunto de estados físicos es ahora el conjunto de estados de creencias. Hay   estados de creencias ya que hay 2 ⁿ estados físicos. Necesitaríamos números enteros con   bits para designar el estado de creencia actual incluso si empleáramos la codificación más pequeña posible de fórmulas lógicas, con cada estado de creencia representado por un número binario distinto. Para decirlo de otra manera, la estimación correcta del estado puede necesitar fórmulas lógicas de un tamaño proporcional al número de símbolos.

La representación de los estados de creencias como conjunciones de literales, es decir, fórmulas 1-CNF, es un método muy común y natural para la estimación aproximada del estado. Dado el estado de creencia en t 1, el programa del agente simplemente intenta probar   y   para cada símbolo   (así como para cada símbolo atemporal cuyo valor de verdad se desconoce). El nuevo estado de creencia está formado por la conjunción de literales verificables, y el estado de creencia anterior   se descarta.

Es vital tener en cuenta que a medida que pasa el tiempo, esta técnica puede perder algo de información. Si la ecuación anterior fuera el verdadero estado de creencia, ni   ni   serían demostrables por separado, y tampoco aparecerían en el estado de creencia 1-CNF . Por otro lado, sabemos que todo el estado de creencia de 1-CNF debe ser verdadero porque cada literal en él se prueba a partir del estado de creencia anterior, y el estado de creencia original es una declaración verdadera. Como resultado, el conjunto de posibles estados representados por el 1-CNFEl estado de creencia abarca todos los estados que de hecho son factibles cuando se tiene en cuenta toda la historia de la percepción. El estado de creencia CNF sirve como un sobre exterior básico, o una aproximación conservadora, al estado de creencia exacto. El concepto de aproximaciones cautelosas a conjuntos complicados parece ser un tema recurrente en varios campos de la IA.