Agentes lógicos y planificación

Un agente basado en conocimientos actúa a partir de una descripción de su mundo. Su base de conocimientos (KB) contiene enunciados formales: hechos y reglas iniciales, llamados axiomas, e información añadida durante el funcionamiento. La inferencia conecta esos enunciados con conclusiones que el agente nunca ha observado directamente.

Conecta la percepción con la acción

TELL añade un enunciado a la KB. ASK solicita una respuesta respaldada por ella, ya sea almacenada o derivada. En cada paso de tiempo, el agente registra su percepción, pregunta qué acción debe realizar, registra la acción elegida y la ejecuta. Registrar las acciones importa porque el razonamiento posterior necesita saber cómo ha cambiado el mundo.

En el nivel de conocimiento, podríamos decir que un robot sabe que un pasillo está bloqueado y quiere llegar a una zona de almacenamiento. En el nivel de implementación, describimos estructuras de datos y procedimientos de inferencia. Un diseño declarativo proporciona hechos y reglas; un diseño procedimental escribe el comportamiento directamente en código. Un agente en funcionamiento puede combinar ambos.

Interpreta el mundo del wumpus

El mundo del wumpus es una cuadrícula de 4 × 4. Las coordenadas son [columna, fila]; el agente empieza en [1, 1] mirando a la derecha. Hay un wumpus, una pieza de oro y una probabilidad de 0,2 de que haya un pozo en cada casilla salvo la inicial. Los pozos y el wumpus permanecen en su lugar. El mundo es discreto, determinista y de un solo agente, pero parcialmente observable: la disposición está oculta.

Una brisa señala un pozo en una casilla directamente adyacente; un hedor señala al wumpus en una de ellas. Las casillas diagonales no cuentan. Un destello indica oro en la casilla actual, un golpe informa de una pared y un grito informa de la muerte del wumpus en cualquier lugar de la cueva. Las acciones son Forward, TurnLeft, TurnRight, Grab, Shoot y Climb. El agente tiene una flecha; Climb solo permite salir desde [1, 1]. Salir con el oro da 1000 puntos, morir resta 1000, cada acción cuesta 1 y disparar cuesta otros 10.

Combina observaciones

En [1, 1], la ausencia de brisa descarta pozos en [1, 2] y [2, 1]; la ausencia de hedor descarta al wumpus allí. Ambas casillas son seguras. En [2, 1], una brisa sitúa un pozo en [2, 2] o [3, 1], porque la casilla inicial no tiene ninguno. La ausencia de hedor descarta al wumpus en [2, 2] y [3, 1].

El agente visita después [1, 2]. La ausencia de brisa descarta un pozo en [2, 2], así que la disyunción anterior obliga a que haya un pozo en [3, 1]. Un hedor en [1, 2] sitúa al wumpus en [1, 3] o [2, 2]. La observación anterior de ausencia de hedor descarta [2, 2], por lo que queda [1, 3]. El agente ha establecido que [2, 2] no contiene ninguno de los dos peligros sin entrar en ella.

Este razonamiento depende tanto de las percepciones como de las reglas que las relacionan con los peligros. Una casilla no explorada es desconocida cuando la KB no respalda ni que sea segura ni que sea peligrosa. No poder derivar que es peligrosa no basta para afirmar que es segura. Elegir entrar en una casilla así requiere una decisión sobre el riesgo, más allá de las consecuencias lógicas por sí solas.

La lógica proposicional proporciona a un agente reglas precisas para combinar afirmaciones que pueden ser verdaderas o falsas. Un símbolo atómico nombra una afirmación completa, como P₁₂ para «hay un pozo en [1, 2]». Un literal es un átomo o su negación. Los enunciados más complejos los combinan con ¬, ∧, ∨, ⇒ y ⇔.

Evalúa las conectivas

Un modelo asigna verdadero o falso a cada símbolo. Con n símbolos hay 2ⁿ asignaciones. La negación invierte un valor de verdad; una conjunción necesita que ambos lados sean verdaderos; una disyunción inclusiva necesita al menos uno. Una implicación es falsa solo cuando la premisa es verdadera y la conclusión es falsa. Un bicondicional necesita valores de verdad iguales en ambos lados.

El orden de precedencia es ¬, ∧, ∨, ⇒, ⇔. Así, ¬A ∧ B ⇒ C significa ((¬A) ∧ B) ⇒ C. Usa paréntesis cuando la agrupación pretendida pueda resultar poco clara. Con A verdadero, B falso y C verdadero, (A ∨ B) ⇒ C es verdadero, mientras que A ⇒ (B ∧ C) es falso.

La implicación lógica establece una restricción sobre los valores de verdad, no una causa. Una premisa falsa hace verdadera la implicación. Tampoco permite invertir la dirección: de «si la batería está descargada, el robot se detiene», el mero hecho de que se detenga no permite establecer que la batería esté descargada.

Codifica ambas direcciones de una regla

La regla de la brisa en la casilla inicial es B₁₁ ⇔ (P₁₂ ∨ P₂₁). Dice que hay brisa exactamente cuando existe un pozo en una casilla vecina. La dirección B₁₁ ⇒ (P₁₂ ∨ P₂₁) permite detectar un peligro a partir de una brisa. La dirección inversa permite descartar pozos a partir de la ausencia de brisa. Omitirla impide la inferencia de ¬B₁₁ a ¬P₁₂ ∧ ¬P₂₁.

Cada casilla necesita su propia regla proposicional. Codificar que hay exactamente un wumpus entre 16 casillas necesita una disyunción que indique que hay al menos uno, más una restricción que indique que hay como máximo uno para cada par. Hay 16 × 15 / 2 = 120 pares distintos. Los símbolos proposicionales no pueden cuantificar sobre casillas, así que las reglas generales se convierten en muchos enunciados separados.

Representa el cambio sin perder la persistencia

Un fluente es un hecho cuya verdad puede cambiar. Un superíndice de tiempo distingue sus valores: L₁₁⁰ registra la ubicación en el tiempo 0. Un axioma de efecto puede decir que moverse a la derecha desde [1, 1] produce la ubicación [2, 1] en el tiempo 1 y elimina la ubicación anterior. Deja sin especificar qué ocurre con los hechos no relacionados, como la posesión de la flecha. Describir todos estos hechos que no cambian es el problema del marco.

Un axioma de estado sucesor proporciona una regla completa de actualización por fluente: Fᵗ⁺¹ ⇔ (una acción hace verdadero F) ∨ (Fᵗ ∧ ninguna acción hace falso F). Para la flecha, HaveArrowᵗ⁺¹ ⇔ (HaveArrowᵗ ∧ ¬Shootᵗ). Como ninguna acción proporciona otra flecha, el agente la conserva hasta disparar y después sigue sin ella.

Un agente necesita un criterio para determinar si una conclusión está justificada. La consecuencia lógica, escrita KB ⊨ α, significa que α es verdadero en todos los modelos que satisfacen la KB. Un solo mundo compatible en el que α sea falso invalida la consecuencia lógica.

Conserva exactamente los modelos compatibles

La comprobación de modelos enumera las asignaciones, descarta las que hacen falso algún enunciado de la KB y comprueba la consulta en las restantes. Supón que la KB contiene A ∨ B y ¬A. De las cuatro asignaciones a A y B, solo A falso, B verdadero satisface ambos enunciados. De la KB se siguen B y ¬A. A no se sigue porque el modelo que queda hace falso A.

En la KB del wumpus, ¬P₁₁, B₁₁ ⇔ (P₁₂ ∨ P₂₁), B₂₁ ⇔ (P₁₁ ∨ P₂₂ ∨ P₃₁), ¬B₁₁ y B₂₁ usan siete símbolos. Hay 128 asignaciones. Exactamente tres satisfacen la KB: P₁₂ y P₂₁ son falsos, mientras que P₂₂ y P₃₁ son, respectivamente, verdadero/falso, falso/verdadero o verdadero/verdadero. Por tanto, ¬P₁₂ es una consecuencia lógica. P₂₂ varía entre los tres modelos, así que no se sigue ni P₂₂ ni ¬P₂₂. Estas reglas sobre pozos por sí solas establecen la ausencia de un pozo, no la ausencia del wumpus.

Distingue las principales comprobaciones lógicas

P ∨ ¬P es válido; P ∧ ¬P es insatisfacible. P ⇒ Q y ¬P ∨ Q son equivalentes. La equivalencia exige consecuencia lógica en ambas direcciones. De A ∧ B se sigue A, pero A permite modelos con B falso, así que la consecuencia inversa no se cumple.

Convierte una consulta en una prueba de contradicción

KB ⊨ α exactamente cuando KB ∧ ¬α es insatisfacible. Añadir la consulta negada busca un mundo donde se cumpla la KB y falle la consulta. No encontrar ninguno demuestra la consecuencia lógica; encontrar uno proporciona un contramodelo. De forma equivalente, α ⊨ β exactamente cuando α ⇒ β es válido. La validez de α puede comprobarse, a su vez, determinando si ¬α es insatisfacible.

La conectiva ⇒ pertenece al interior de un enunciado. El símbolo ⊨ describe una relación entre enunciados y sus modelos. Del mismo modo, «no se sigue» puede significar que la consulta está descartada o que sigue siendo desconocida. Comprueba si su negación se sigue antes de elegir entre ambas posibilidades.

La enumeración es correcta y completa para la lógica proposicional porque comprueba exhaustivamente un conjunto finito. La enumeración en profundidad necesita O(2ⁿ) de tiempo y O(n) de memoria; 50 símbolos ya producen aproximadamente 1,13 × 10¹⁵ asignaciones. Determinar la consecuencia lógica proposicional es co-NP-completo. Comprueba también la consistencia: de una KB sin modelos se sigue cualquier enunciado, porque no tiene ningún modelo compatible que pueda incumplir una consulta.

Una demostración deriva una consulta aplicando reglas a enunciados ya conocidos. KB ⊢ α indica una derivación; KB ⊨ α indica una garantía semántica sobre los modelos. Un procedimiento de demostración correcto los conecta: toda conclusión que deriva realmente se sigue de la KB. Un procedimiento completo puede derivar toda conclusión que sea consecuencia lógica dentro del lenguaje al que se aplica.

Aplica reglas a sus premisas

Modus ponens permite obtener Q a partir de P ⇒ Q y P. La eliminación de la conjunción permite obtener cualquiera de los dos términos de P ∧ Q. Si se conocen SensorOn ∧ Calibrated y SensorOn ⇒ ReadingAvailable, la eliminación de la conjunción da SensorOn y después Modus ponens da ReadingAvailable. Cada línea indica la información y la regla que la justifican.

Estas reglas preservan la verdad, pero su vocabulario restringido hace que sean incompletas como sistema de demostración completo. De P se sigue semánticamente P ∨ Q, pero ninguna de las dos reglas introduce ∨. Un conjunto de reglas correctas puede aun así dejar sin obtener conclusiones válidas.

Reescribe sin cambiar el significado

Las equivalencias útiles pueden aplicarse en ambas direcciones:

• Doble negación: ¬¬P ≡ P.
• Implicación: P ⇒ Q ≡ ¬P ∨ Q.
• Contraposición: P ⇒ Q ≡ ¬Q ⇒ ¬P.
• Bicondicional: P ⇔ Q ≡ (P ⇒ Q) ∧ (Q ⇒ P).
• De Morgan: ¬(P ∨ Q) ≡ ¬P ∧ ¬Q, y ¬(P ∧ Q) ≡ ¬P ∨ ¬Q.
• Distribución: P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R), con la ley dual para ∧ sobre ∨.

La conjunción y la disyunción también permiten reagrupar y cambiar el orden. Estas reescrituras muestran la estructura útil de un enunciado sin añadir un nuevo supuesto sobre los hechos.

Para B₁₁ ⇔ (P₁₂ ∨ P₂₁) y ¬B₁₁, separa el bicondicional y selecciona (P₁₂ ∨ P₂₁) ⇒ B₁₁. La contraposición da ¬B₁₁ ⇒ ¬(P₁₂ ∨ P₂₁). Modus ponens da ¬(P₁₂ ∨ P₂₁); De Morgan da ¬P₁₂ ∧ ¬P₂₁. La eliminación de la conjunción demuestra entonces ¬P₁₂. La demostración nunca necesita enumerar todas las disposiciones posibles de la cueva.

Comprueba un atajo inválido

De P ⇒ Q y Q, inferir P es afirmar el consecuente. De P ⇒ Q y ¬P, inferir ¬Q es negar el antecedente. Ambos fallan en el modelo P falso, Q verdadero. Una caída del servidor puede impedir que cargue una página, pero un fallo de carga tiene otras posibles causas; la ausencia de una caída tampoco garantiza que cargue.

Encontrar una demostración es un problema de búsqueda. El estado inicial contiene la KB; una acción aplica una regla de inferencia y añade su conclusión; el estado objetivo contiene la consulta. La longitud de la demostración puede servir como costo del camino. Seleccionar enunciados relevantes evita dedicar esfuerzo a cadenas que no están relacionadas. La lógica clásica es monótona: añadir premisas preserva las consecuencias lógicas anteriores. Las reglas por defecto con excepciones necesitan otro tratamiento porque la información posterior puede retirar una conclusión por defecto anterior.

La resolución demuestra la consecuencia lógica buscando una contradicción. Su entrada está en forma normal conjuntiva (CNF): una conjunción de cláusulas, cada una de ellas una disyunción de literales. Una cláusula de un solo literal es una cláusula unitaria. La cláusula vacía no tiene ningún literal que pueda ser verdadero y representa la falsedad.

Convierte enunciados en cláusulas

Primero elimina ⇔ y ⇒. Después desplaza las negaciones hacia el interior con las leyes de De Morgan y la eliminación de la doble negación. Por último, distribuye ∨ sobre ∧. Un bicondicional puede crear así varias cláusulas.

Para B₁₁ ⇔ (P₁₂ ∨ P₂₁), la primera dirección da ¬B₁₁ ∨ P₁₂ ∨ P₂₁. La inversa da ¬(P₁₂ ∨ P₂₁) ∨ B₁₁. Al desplazar la negación hacia el interior y distribuir se obtienen ¬P₁₂ ∨ B₁₁ y ¬P₂₁ ∨ B₁₁. Se necesitan las tres cláusulas para expresar el bicondicional completo.

Resuelve un par complementario

De P ∨ A y ¬P ∨ B, la resolución deriva A ∨ B. Sea cual sea el valor de P, al menos una de las partes restantes debe cumplirse. La resolución unitaria usa una cláusula de un solo literal: P con ¬P ∨ B da B. Los literales duplicados se eliminan mediante factorización, así que resolver A ∨ B con A ∨ ¬B da A.

Resuelve exactamente un par complementario cada vez. A ∨ B y ¬A ∨ ¬B son satisfacibles conjuntamente cuando A es verdadero y B es falso. Eliminar ambos pares daría incorrectamente la cláusula vacía. Resolver solo sobre A produce B ∨ ¬B, una tautología que no añade ninguna restricción.

Refuta la consulta negada

Para demostrar KB ⊨ α, añade ¬α, convierte el enunciado combinado a CNF y deriva nuevas cláusulas resolventes. Llegar a la cláusula vacía demuestra que no existe ningún contramodelo.

Para la consulta sobre el pozo ¬P₁₂, añade P₁₂. Resuélvelo con ¬P₁₂ ∨ B₁₁ para obtener B₁₁. Resuelve eso con el ¬B₁₁ observado para llegar a la cláusula vacía. La demostración establece la ausencia del pozo, no su presencia: el literal positivo del pozo era una consulta negada temporal.

Un segundo ejemplo usa R ⇒ C, (C ∨ I) ⇒ G y R. Las cláusulas CNF son ¬R ∨ C, ¬C ∨ G, ¬I ∨ G y R. Añade ¬G. Se resuelve con ¬C ∨ G para dar ¬C, que da ¬R usando la primera cláusula. Resolver ¬R con R cierra la refutación. No se necesitó ningún hecho sobre I.

La resolución proposicional es correcta y completa por refutación. Termina porque un número finito de símbolos permite un número finito de cláusulas distintas. Si el cierre exhaustivo no produce ninguna cláusula nueva ni contradicción, la consulta no es una consecuencia lógica. No tiene por qué derivar directamente todos los enunciados que son consecuencia lógica: a partir de A por sí solo, la resolución no construye A ∨ B.

La distribución puede ampliar la CNF de forma exponencial. Una codificación de Tseitin introduce símbolos para las subfórmulas y produce una CNF de tamaño lineal. El nuevo enunciado es equisatisfacible con el original; no tiene por qué ser lógicamente equivalente sobre el vocabulario ampliado. Preservar la satisfacibilidad basta para las pruebas de contradicción basadas en SAT.

Las reglas con una sola conclusión positiva permiten un procedimiento de inferencia más sencillo que la resolución general. Una cláusula definida tiene exactamente un literal positivo; ¬A ∨ ¬B ∨ C se escribe A ∧ B ⇒ C. Un hecho tiene un cuerpo vacío. Una cláusula de Horn tiene como máximo un literal positivo, lo que incluye una cláusula objetivo sin ninguno, como A ∧ B ⇒ Falso.

Deja que los hechos dirijan las reglas

El encadenamiento hacia delante empieza con los hechos conocidos. Cuando se conocen todas las premisas de una regla, añade su cabeza. Continúa hasta que aparezca la consulta o se llegue a un punto fijo en el que no se añada nada. Las implementaciones eficientes mantienen una agenda de hechos nuevos y un contador de premisas no satisfechas por regla.

Toma PowerOn, FanSpinning y LoadLow como hechos. Las reglas son PowerOn ∧ FanSpinning ⇒ Cooling; Cooling ∧ LoadLow ⇒ TempNormal; PowerOn ⇒ LedLit; LedLit ∧ TempNormal ⇒ SystemOK; FanSpinning ⇒ NoiseHeard. Procesar PowerOn permite obtener LedLit y satisface parcialmente la regla de enfriamiento. FanSpinning permite obtener Cooling y NoiseHeard. Cooling junto con LoadLow da TempNormal, y después TempNormal junto con LedLit da SystemOK. NoiseHeard es una conclusión adicional válida aunque la consulta no la necesitara.

Deja que una consulta elija las reglas

El encadenamiento hacia atrás empieza con SystemOK. Su regla requiere LedLit y TempNormal. LedLit se reduce al hecho conocido PowerOn. TempNormal requiere Cooling y LoadLow; Cooling requiere PowerOn y FanSpinning. Todas las hojas son hechos, así que la consulta tiene éxito. La regla del ruido nunca se examina.

Para KB de cláusulas definidas y consultas atómicas, ambos métodos son correctos y completos con un control adecuado de la búsqueda. El encadenamiento proposicional hacia delante puede ejecutarse en tiempo lineal respecto al tamaño de la KB. En su punto fijo, asignar verdadero a los símbolos derivados y falso a todos los demás da un modelo de las cláusulas definidas.

Gestiona los ciclos sin perder respuestas

A ⇒ B y B ⇒ A producen un ciclo infinito en un procedimiento ingenuo hacia atrás. Una rama puede detenerse cuando su objetivo ya está en la pila de objetivos activos. Los subobjetivos demostrados pueden almacenarse, pero un fallo causado por un ciclo es temporal. Con B ⇒ A, A ⇒ B, C ⇒ A y el hecho C, un intento temprano de demostrar B mientras A está activo puede fallar. Después de demostrar A a partir de C, volver a intentar B tiene éxito. Guardar permanentemente ese primer fallo perdería la demostración. La tabulación de respuestas hace seguimiento de los objetivos dependientes y vuelve a examinarlos cuando aparecen respuestas.

El encadenamiento depende de la forma de las reglas. A ∨ B tiene dos literales positivos, así que no es una cláusula de Horn. Junto con A ⇒ C y B ⇒ C, implica C al considerar ambas alternativas. Ninguna regla definida se activa a partir de la disyunción por sí sola. La resolución general puede demostrar esta conclusión aunque el encadenamiento sencillo se estanque.

Un resolvedor SAT busca una asignación que satisfaga todas las cláusulas de un enunciado en CNF. Un modelo devuelto puede comprobarse directamente. Un resultado insatisfacible descarta todas las asignaciones. SAT es NP-completo, pero las instancias estructuradas suelen admitir soluciones mucho más rápidas que la enumeración exhaustiva mediante tablas de verdad.

Reduce la búsqueda con DPLL

DPLL es un retroceso en profundidad con tres atajos. Un literal verdadero satisface toda su cláusula, mientras que una cláusula completamente falsa termina la rama. Un símbolo puro aparece con un solo signo entre las cláusulas no satisfechas, así que puede asignarse para satisfacer esas apariciones. Una cláusula unitaria solo tiene un literal restante que puede ser verdadero, al que debe asignarse verdadero. Repetir estas elecciones forzadas es la propagación unitaria.

Considera (A), (¬A ∨ B), (¬B ∨ C ∨ D), (¬C ∨ ¬D), (D ∨ E). E es puro, así que asígnale verdadero. La cláusula unitaria A obliga a que A sea verdadero, lo que obliga a que B sea verdadero. La restricción restante C ∨ D y la cláusula ¬C ∨ ¬D requieren que exactamente uno de C y D sea verdadero. Ramifica con C verdadero; la propagación obliga a que D sea falso. A, B, C y E verdaderos con D falso satisfacen todas las cláusulas.

Para (A ∨ B), (A ∨ ¬B), (¬A ∨ C), (¬A ∨ ¬C), ramifica sobre A. A falso obliga a que se cumplan tanto B como ¬B; A verdadero obliga a que se cumplan tanto C como ¬C. Ambas ramas entran en conflicto, así que todo el enunciado es insatisfacible.

Aprende de los conflictos

El aprendizaje de cláusulas dirigido por conflictos (CDCL) amplía esta búsqueda. Una cláusula aprendida bloquea una combinación responsable de un conflicto. El retroceso por saltos omite elecciones irrelevantes; la actividad de las variables guía la ramificación; los reinicios cambian el recorrido de búsqueda; los literales vigilados aceleran la propagación. Las cláusulas aprendidas están justificadas por la fórmula, así que preservan sus posibles soluciones.

Busca cambiando una asignación completa

WalkSAT empieza con una asignación completa aleatoria. Elige una cláusula no satisfecha e invierte una variable de ella, unas veces al azar y otras para dejar satisfechas el mayor número de cláusulas. Los movimientos aleatorios ayudan a escapar de trampas locales. Empezar con los cinco símbolos falsos en el ejemplo anterior deja falsos (A) y (D ∨ E). Invertir A corrige (A), pero deja de satisfacer (¬A ∨ B). Un movimiento puede reparar una cláusula y perjudicar otra.

Para comprobar la consecuencia lógica, proporciona KB ∧ ¬α. La insatisfacibilidad demuestra α; un modelo es un contraejemplo. Si WalkSAT agota el tiempo, ambas posibilidades siguen abiertas. En fórmulas 3-CNF aleatorias grandes, la proporción de cláusulas por variable tiene una transición estimada cerca de 4,26, y las instancias difíciles suelen estar cerca de ella. Es un patrón del conjunto, no un umbral que decida una fórmula individual. La estructura de las cláusulas y la estrategia del resolvedor también afectan a la dificultad.

La lógica de primer orden describe objetos y sus relaciones. En lugar de dar a cada casilla un símbolo independiente, puede expresar una regla para todas las casillas: ∀s (Breezy(s) ⇔ ∃r (Adjacent(r, s) ∧ Pit(r))). Los cuantificadores hacen que la generalidad forme parte del lenguaje.

Separa los objetos de las afirmaciones

Una constante nombra un objeto, como Ada. Una variable, como x, recorre los objetos. Una función asigna un objeto a objetos: MotherOf(Ada) es un término que se refiere a alguien. Un predicado forma una afirmación: Owns(Ada, Atlas) es verdadero o falso. Un término puede ser una constante, una variable o una función aplicada a términos.

Book(x) es un enunciado, no un objeto, así que Owns(Ada, Book(x)) coloca un tipo de expresión incorrecto en la posición de un argumento. La igualdad compara aquello a lo que se refieren los términos: MotherOf(Ada) = Clara dice que ambos términos denotan el mismo objeto.

Evalúa un enunciado en un modelo

Un modelo de primer orden proporciona un dominio no vacío y una interpretación. Las constantes denotan objetos del dominio, los predicados denotan relaciones y las funciones dan resultados para cada tupla adecuada de objetos del dominio. Un enunciado cuantificado universalmente debe cumplirse para cada posible valor de su variable; un enunciado existencial necesita al menos un testigo.

Sea el dominio {a, b, k}; Ada nombra a a, Ben nombra a b y Atlas nombra a k. Person contiene a y b, Book contiene k y Owns contiene solo (a, k). Owns(Ada, Atlas) es verdadero. ∃x (Book(x) ∧ Owns(Ben, x)) es falso porque Ben no posee ningún objeto. ∀x (Person(x) ⇒ ∃y (Book(y) ∧ Owns(x, y))) es falso porque Ben es un contraejemplo. Sin embargo, todo libro tiene propietario: se cumple ∀x (Book(x) ⇒ ∃y Owns(y, x)).

Explicita los supuestos de modelado

La lógica de primer orden estándar no impone estos supuestos de bases de datos. Book(Atlas), Book(Beowulf), Owns(Ada, Atlas) y Owns(Ada, Beowulf) dejan sin determinar si los dos nombres denotan el mismo libro y si Ada posee más libros. Con la semántica de bases de datos, describen exactamente dos libros que posee Ada.

Para obtener esa afirmación exacta en la semántica estándar, conserva los cuatro hechos y añade ¬(Atlas = Beowulf) y ∀x ((Book(x) ∧ Owns(Ada, x)) ⇒ (x = Atlas ∨ x = Beowulf)). La desigualdad establece que hay dos libros distintos; la restricción universal excluye otros libros que Ada posea.

Los modelos de primer orden pueden tener dominios de tamaño arbitrariamente grande, así que el método de enumeración finita de los modelos proposicionales no proporciona aquí un procedimiento general de decisión. Los métodos de demostración trabajan, en cambio, con la estructura de los enunciados. Una variable libre necesita una asignación para su evaluación; vincula las variables cuando escribas una afirmación cerrada para la KB.

La traducción empieza por determinar qué afirma el enunciado sobre cada objeto. El ámbito de los cuantificadores, la dirección de la implicación y la igualdad determinan el significado; los nombres de los predicados por sí solos no lo fijan. Los paréntesis hacen visible el ámbito pretendido.

Usa la conectiva adecuada con un cuantificador

«Todos los gatos son mamíferos» se convierte en ∀x (Cat(x) ⇒ Mammal(x)). Un objeto que no pertenece a la categoría satisface la implicación sin ser un gato. Escribir ∀x (Cat(x) ∧ Mammal(x)) hace incorrectamente que todo sea un gato.

«Algún gato es negro» se convierte en ∃x (Cat(x) ∧ Black(x)). El testigo debe satisfacer ambas propiedades. Con ∃x (Cat(x) ⇒ Black(x)), cualquier objeto que no sea un gato ya es un testigo, incluso en un mundo sin gatos negros. Las reglas universales sobre categorías suelen usar implicación; las afirmaciones existenciales sobre categorías suelen usar conjunción.

Comprueba quién puede depender de quién

∀x ∃y Loves(x, y) permite que cada x ame a una persona distinta. ∃y ∀x Loves(x, y) requiere una persona amada por todo el mundo. En un mundo de dos personas donde cada una ama solo a la otra, el primero se cumple y el segundo falla. Intercambiar cuantificadores de distintos tipos puede cambiar una afirmación; intercambiar dos cuantificadores universales adyacentes o dos existenciales adyacentes la preserva.

La negación intercambia los cuantificadores: ¬∀x P(x) ≡ ∃x ¬P(x), y ¬∃x P(x) ≡ ∀x ¬P(x). Por tanto, «No todos los estudiantes aprobaron» significa ∃x (Student(x) ∧ ¬Passed(x)). Requiere un estudiante que no aprobó; no afirma que todos los estudiantes hayan reprobado.

Expresa dirección y número

«Solo los miembros toman prestado» significa ∀x (Borrows(x) ⇒ Member(x)). Tomar prestado basta para establecer la pertenencia, mientras que pertenecer por sí solo no dice nada sobre tomar prestado. «Ningún reptil es mamífero» significa ∀x (Reptile(x) ⇒ ¬Mammal(x)).

Para expresar que Ada posee al menos dos libros, escribe ∃x ∃y (Book(x) ∧ Book(y) ∧ Owns(Ada, x) ∧ Owns(Ada, y) ∧ ¬(x = y)). La desigualdad importa: dos nombres de variable pueden referirse al mismo objeto. Para exactamente uno se usa un testigo más unicidad: ∃x (Book(x) ∧ Owns(Ada, x) ∧ ∀y ((Book(y) ∧ Owns(Ada, y)) ⇒ y = x)).

Da a las definiciones ambas direcciones

Una definición de hermanos puede ser ∀x ∀y (Sibling(x, y) ⇔ (¬(x = y) ∧ ∃p (Parent(p, x) ∧ Parent(p, y)))). La primera dirección impone condiciones a los hermanos; la inversa permite que los hechos sobre un progenitor compartido establezcan que son hermanos. Una implicación en una sola dirección aporta solo la mitad de ese significado.

En el dominio de un agente, las reglas diagnósticas van de las observaciones a las posibles causas, mientras que las reglas causales van de las causas a los efectos. «Toda casilla con brisa tiene un pozo adyacente» es diagnóstica. «Todo pozo hace que haya brisa en todas las casillas adyacentes» es causal. Juntas respaldan el bicondicional completo de la brisa. Termina una traducción comprobando la vinculación de cada variable y probando un mundo pequeño donde la afirmación en lenguaje natural debería ser falsa.

Construir una base de conocimientos útil es una tarea de modelado. La notación formal solo ayuda una vez elegidos las preguntas, los objetos y las relaciones pertinentes. La ingeniería del conocimiento convierte esas elecciones en axiomas que pueden comprobarse frente a los ejemplos previstos.

Construye a partir de las preguntas

Una secuencia práctica consiste en identificar la tarea, recopilar los conocimientos pertinentes, elegir un vocabulario, escribir axiomas generales, añadir hechos de la instancia, plantear consultas y depurar los resultados. Empieza con preguntas concretas como «¿Puede este estudiante inscribirse en este curso?». Esa pregunta determina lo que la representación debe permitir.

Para la inscripción, usa Student(s), Course(c), Prereq(p, c), Passed(s, c) y CanEnroll(s, c). Prereq(p, c) significa que p debe aprobarse antes de c; invertir sus argumentos invertiría la dependencia. Una regla es ∀s ∀c ((Student(s) ∧ Course(c) ∧ ∀p (Prereq(p, c) ⇒ Passed(s, p))) ⇒ CanEnroll(s, c)). Exige todos los requisitos previos, no solo uno.

Separa las reglas reutilizables de una instancia

Supón que los hechos son Student(Mia), Course(AI), Prereq(Logic, AI), Prereq(Programming, AI), Passed(Mia, Logic) y Passed(Mia, Programming). La regla general puede reutilizarse para otros estudiantes y cursos, mientras que estos hechos de la instancia describen un caso.

En la lógica de primer orden estándar, estos hechos dejan abierta la posibilidad de que haya requisitos previos adicionales para AI. Un modelo compatible podría incluir un tercer requisito previo no aprobado, así que CanEnroll(Mia, AI) aún no es una consecuencia lógica. Añade ∀p (Prereq(p, AI) ⇔ (p = Logic ∨ p = Programming)) para completar la lista. Ahora cada requisito previo es uno de los dos cursos aprobados y se aplica la regla de inscripción. Una base de datos de mundo cerrado puede obtener la misma respuesta tratando como falsos los hechos ausentes sobre requisitos previos.

Elige qué se convierte en objeto

Una ontología es el vocabulario y sus supuestos estructurales. Red(x) trata el rojo como una propiedad. Color(x, Red) convierte Red en un objeto, lo que permite que ∃c (Color(x, c) ∧ Color(y, c)) exprese un color compartido. Este paso es la reificación: permite que el lenguaje hable de una propiedad o categoría como algo por derecho propio.

ASK puede preguntar si se sigue CanEnroll(Mia, AI). ASKVARS puede solicitar vinculaciones para CanEnroll(x, AI), devolviendo una sustitución como {x/Mia}. La misma KB permite tanto preguntas de verdad como consultas sobre objetos que coinciden.

Depura el significado, no solo la sintaxis

Un axioma ausente puede impedir una consecuencia lógica deseada; un axioma incorrecto puede respaldar una no deseada. Prueba ejemplos positivos, negativos y casos límite. La regla ∀c (Course(c) ⇒ ∃t Teaches(t, c)) es demasiado fuerte si algunos cursos aún no tienen profesor. La regla ∀p ∀c (Prereq(p, c) ⇒ Passed(Mia, p)) es demasiado fuerte porque atribuye a Mia la aprobación de todos los requisitos previos de todos los cursos.

Los nombres de los predicados son etiquetas para el sistema de razonamiento. Llamar Prereq a una relación no proporciona por sí solo ninguna política de inscripción. Las reglas deben conectar los hechos sobre requisitos previos, los cursos aprobados y la posibilidad de inscripción en la dirección pretendida.

La inferencia de primer orden trabaja con patrones que contienen variables. La sustitución reemplaza variables por términos; la unificación encuentra reemplazos que hacen idénticas dos expresiones. Juntas permiten que una regla general sirva para muchos hechos concretos sin generar antes todas las instancias posibles.

Instancia con cuidado los enunciados cuantificados

La instanciación universal sustituye una variable vinculada universalmente por cualquier término sin variables. De ∀x (Cat(x) ⇒ Mammal(x)), deriva Cat(Tom) ⇒ Mammal(Tom), o la instancia correspondiente con MotherOf(Tom). Un término sin variables no contiene ninguna variable.

La instanciación existencial introduce un nombre nuevo para un testigo. De ∃x (Crown(x) ∧ OnHead(x, John)), introduce una constante nueva C₁ y añade Crown(C₁) y OnHead(C₁, John). Nombrar en cambio a Ben como testigo identificaría incorrectamente un objeto no especificado con uno existente. La KB ampliada preserva la satisfacibilidad, no la equivalencia en el vocabulario ampliado.

La proposicionalización genera instancias sin variables y después usa razonamiento proposicional. Los símbolos de función pueden producir infinitos términos: Ada, MotherOf(Ada), MotherOf(MotherOf(Ada)), y así sucesivamente. Las consultas de primer orden que son consecuencia lógica tienen demostraciones finitas, pero un demostrador general puede ejecutarse indefinidamente cuando la consulta no lo es. Esto es la semidecidibilidad.

Encuentra una sustitución consistente

Para unificar Knows(Ana, x) con Knows(y, Bo), comprueba primero que coincidan el predicado y la aridad. Los primeros argumentos requieren y = Ana; los segundos requieren x = Bo. La sustitución {y/Ana, x/Bo} convierte ambas expresiones en Knows(Ana, Bo).

Knows(Ana, x) y Knows(y, MotherOf(y)) dan en cambio {y/Ana, x/MotherOf(Ana)}. Una vinculación debe propagarse por los demás términos. Si la misma variable x aparece en ambas expresiones Knows(Ana, x) y Knows(x, Bo), tendría que convertirse tanto en Ana como en Bo, así que la unificación sintáctica falla.

Las variables de enunciados cuantificados por separado son independientes. El renombrado de variables para evitar coincidencias cambia sus nombres antes de combinar enunciados. Renombrar la segunda x como z en ese último par permite {z/Ana, x/Bo}. Esto preserva la independencia prevista de las variables locales de dos reglas.

Un unificador más general (MGU) no impone vinculaciones innecesarias. Knows(Ana, x) y Knows(y, z) se unifican con {y/Ana, x/z}; asignar también Ana a z haría el resultado más específico sin necesidad. La comprobación de ocurrencias rechaza x = MotherOf(x), ya que un término finito no puede contenerse a sí mismo. La unificación ordinaria de Prolog puede permitir términos cíclicos, así que hay que prestar atención a su comportamiento cuando se pretende usar lógica de primer orden con términos finitos.

Aplica la regla que coincide

El Modus ponens generalizado hace coincidir todas las premisas con una única sustitución consistente. Owns(Ada, Atlas) y Book(Atlas) coinciden con Owns(x, y) ∧ Book(y) ⇒ Reader(x) mediante {x/Ada, y/Atlas}, lo que da Reader(Ada). Hacer coincidir una premisa con y = Atlas y otra con y = Beowulf no justificaría activar la regla: las variables compartidas obligan a usar los mismos objetos.

Una cláusula definida de primer orden tiene premisas atómicas y una conclusión atómica, y se entiende que sus variables están cuantificadas universalmente. El encadenamiento hacia delante y hacia atrás usa la unificación para aplicar estas reglas a objetos nombrados. Datalog conserva esta forma de regla y excluye los símbolos de función, lo que da un espacio finito de posibles hechos sin variables en el marco habitual de bases de datos finitas.

Deriva ubicaciones alcanzables

Toma Link(A, B), Link(B, C) y Link(C, D). Usa Link(x, y) ⇒ Reach(x, y), y Link(x, y) ∧ Reach(y, z) ⇒ Reach(x, z). En rondas síncronas, cada regla lee los hechos disponibles antes de esa ronda.

La ronda 1 deriva Reach(A, B), Reach(B, C) y Reach(C, D). La ronda 2 añade Reach(A, C) y Reach(B, D). La ronda 3 añade Reach(A, D). La ronda 4 no añade nada. Hay seis hechos Reach en el punto fijo. Una implementación que reutiliza inmediatamente los hechos nuevos puede encontrarlos en otro orden, pero llega al mismo cierre.

Con n constantes y predicados de aridad como máximo k, solo es posible un número finito de tuplas; una cota superior es p · nᵏ para p predicados. En cambio, NatNum(0) y NatNum(n) ⇒ NatNum(S(n)) generan términos de profundidad creciente sin fin. Los símbolos de función eliminan la garantía de un dominio finito.

Hacer coincidir una regla de varias premisas es un problema de restricciones. Una premisa selectiva puede reducir mucho las sustituciones consideradas a continuación. El encadenamiento hacia delante incremental se centra en las reglas afectadas por los hechos recién añadidos. Las redes Rete conservan coincidencias parciales entre actualizaciones, lo que evita repetir trabajo en los sistemas de reglas de producción.

Trabaja hacia atrás con vinculaciones

Para demostrar Reach(A, D), prueba la regla de enlace directo, que requiere el hecho ausente Link(A, D). La regla recursiva requiere en cambio Link(A, y) y Reach(y, D). La primera vincula y con B. Continuar por B y C lleva al hecho conocido Link(C, D). La consulta Reach(A, w) tiene tres respuestas: w = B, C o D.

Prolog escribe las reglas con la cabeza primero y usa variables en mayúscula y constantes en minúscula:

reach(X, Y) :- link(X, Y).
reach(X, Z) :- link(X, Y), reach(Y, Z).

Prueba las cláusulas de arriba abajo y las premisas de izquierda a derecha mediante encadenamiento hacia atrás en profundidad. La aritmética puede usar N is M + 1. La negación por fallo, escrita \+ p, tiene éxito si el intento de demostrar p falla en un número finito de pasos. Es una comprobación operativa del fallo, no una demostración general de negación clásica.

Evita que la recursión atrape la búsqueda

Poner reach(X, Y) primero en el cuerpo recursivo puede llamar inmediatamente otra vez al mismo objetivo sin resolver. Ayudan las cláusulas base primero y una recursión que consume un enlace, pero los ciclos aún pueden atrapar búsquedas sin éxito. La tabulación de respuestas registra las respuestas a los subobjetivos y gestiona las dependencias repetidas. El encadenamiento hacia delante es completo para Datalog finito; la búsqueda ingenua hacia atrás en profundidad necesita este tipo de control para evitar que se pierdan respuestas alcanzables tras ramas infinitas.

La resolución de primer orden amplía el razonamiento con cláusulas mediante la unificación. Puede demostrar conclusiones que implican objetos sin nombre porque los términos de Skolem conservan las dependencias de los testigos existenciales. Como en la refutación proposicional, empieza con la KB y la negación de la consulta.

Prepara cláusulas de primer orden

Elimina ⇔ y ⇒, desplaza las negaciones hacia el interior, renombra las variables vinculadas para evitar coincidencias, Skolemiza las variables existenciales, elimina los cuantificadores universales y después distribuye ∨ sobre ∧. Es importante desplazar primero la negación porque ¬∀x P(x) se convierte en ∃x ¬P(x), lo que cambia el tipo de testigo necesario.

Para «Todo curso tiene un profesor», ∀c (Course(c) ⇒ ∃t Teaches(t, c)), el profesor existencial puede depender de c. Introduce una función nueva T(c) para obtener ¬Course(c) ∨ Teaches(T(c), c). Una sola constante impondría un profesor compartido, algo que el enunciado original no exige. Para ∃t ∀c (Course(c) ⇒ Teaches(t, c)), una constante nueva es adecuada porque el testigo precede al cuantificador universal.

«No todas las aves vuelan» se convierte en ∃x (Bird(x) ∧ ¬Flies(x)), y después en Bird(B₁) y ¬Flies(B₁). Ambas cláusulas usan el mismo testigo nuevo. La Skolemización preserva la satisfacibilidad; no es una equivalencia ordinaria sobre el vocabulario ampliado.

Aplica un unificador a toda la resolvente

Renombra las variables de las dos cláusulas para evitar coincidencias. Encuentra literales complementarios que se unifiquen, elimínalos y aplica su MGU a cada literal restante. La factorización también fusiona literales unificables dentro de una cláusula. La resolución con factorización es completa por refutación para cláusulas de primer orden.

Toma ¬Course(c) ∨ Teaches(T(c), c), ¬Teaches(u, v) ∨ Staff(u) y Course(Logic). La consulta es ∃w Staff(w); su negación da ¬Staff(w), cuantificado universalmente. Resuelve el hecho del curso con la primera cláusula para obtener Teaches(T(Logic), Logic). Resuelve con la segunda mediante {u/T(Logic), v/Logic}, lo que da Staff(T(Logic)). Resuelve con ¬Staff(w) mediante {w/T(Logic)} para llegar a la cláusula vacía. Existe un miembro del personal aunque la KB nunca dé a esa persona un nombre ordinario.

Controla la búsqueda de cláusulas

La preferencia por cláusulas unitarias elige primero las cláusulas cortas. El conjunto de soporte requiere una cláusula progenitora procedente de la consulta negada o de sus descendientes y preserva la completitud cuando el resto de la KB es satisfacible. La resolución de entrada requiere una cláusula progenitora original en cada paso y es completa para KB de Horn. La subsunción elimina una cláusula más débil ya cubierta por una más fuerte y general, como eliminar P(Ana) ∨ Q(Bo) cuando se conoce P(x).

La igualdad necesita un tratamiento específico: axiomas de igualdad, reescritura mediante ecuaciones por demodulación o inferencias como la paramodulación. La resolución puramente sintáctica por sí sola no recoge todos los significados de la igualdad. Una búsqueda completa y equitativa encuentra una contradicción para todo conjunto insatisfacible de cláusulas de primer orden, pero puede ejecutarse indefinidamente en otros casos. Entre los demostradores basados en resolución están Vampire y E; EQP demostró la conjetura de Robbins en 1996.

Una ontología organiza las categorías, los objetos, las relaciones y los supuestos de un dominio. Una ontología de nivel superior proporciona ideas generales como objetos, sucesos y tiempo; una ontología de dominio proporciona las distinciones útiles en un campo particular. Las ontologías clínicas y biológicas ilustran por qué un vocabulario compartido útil suele servir a una comunidad específica.

Mantén separadas la pertenencia y la relación de subclase

Una categoría puede aparecer como predicado, Laptop(x), o como objeto, Laptops. La pertenencia x ∈ Laptops dice que un individuo pertenece a ella. Laptops ⊂ Computers dice que toda computadora portátil es una computadora. Una taxonomía organiza estas relaciones de subclase en una jerarquía. Si toda computadora tiene un procesador, las computadoras portátiles heredan esa propiedad.

La relación de subclase es transitiva: Penguins ⊂ Birds y Birds ⊂ Animals dan Penguins ⊂ Animals. La pertenencia no es transitiva. Pingu ∈ Penguins y Penguins ∈ Species no hacen que Pingu sea una especie. Un enunciado se refiere a un ave individual; el otro se refiere a una categoría tratada como objeto.

Las categorías son disjuntas cuando no comparten miembros. Una descomposición exhaustiva cubre todos los miembros de la categoría superior. Una partición cumple ambas condiciones: los enteros negativos, el cero y los enteros positivos forman una partición de los enteros. La exhaustividad permite solapamientos a menos que también se indique que las categorías son disjuntas.

Representa partes, sucesos y valores heredados

PartOf describe composición, no pertenencia a una categoría. PartOf es transitiva: un radio que pertenece a una rueda que pertenece a una bicicleta es parte de la bicicleta. Eso no convierte a una bicicleta en un tipo de rueda. Los sucesos también pueden ser objetos: Happens(e, t), Initiates(e, f, t) y HoldsAt(f, t) conectan sucesos con fluentes cambiantes. Encender una lámpara inicia un fluente que persiste hasta que un suceso lo termina.

Una red semántica representa objetos y categorías como nodos con relaciones etiquetadas. En una red con valores por defecto, «las aves normalmente vuelan» puede proporcionar un valor heredado por las aves ordinarias, mientras que una categoría más específica de pingüinos lo sustituye. Esto es distinto de afirmar el axioma clásico sin excepciones ∀x (Bird(x) ⇒ Flies(x)), que también se aplicaría a los pingüinos.

Elige el lenguaje de razonamiento

Las lógicas descriptivas permiten comprobar la subsunción, la clasificación y la consistencia. Una definición puede clasificar a una persona con al menos tres hijos en una categoría adecuada. Estas lógicas son la base de los lenguajes de lógica descriptiva de OWL.

El razonamiento por defecto es no monótono: saber que un ave es un pingüino puede retirar la conclusión por defecto de que vuela. La circunscripción minimiza los casos anómalos en reglas como Bird(x) ∧ ¬Abnormal(x) ⇒ Flies(x). La lógica por defecto permite conclusiones mientras sigan siendo consistentes con los conocimientos. Los sistemas de mantenimiento de la verdad registran el soporte para que puedan eliminarse las conclusiones que dependen de una creencia retirada.

Un grafo de conocimiento almacena entidades y sus relaciones como un grafo dirigido. Una arista sencilla se convierte en una tripleta: sujeto, predicado, objeto. Por ejemplo, (Ada, worksAt, Lab) corresponde a WorksAt(Ada, Lab); (Ada, type, Researcher) expresa la pertenencia a una categoría. Un esquema da a estas etiquetas un significado compartido y permite realizar más inferencias.

Distingue los estándares web

RDF representa grafos como tripletas. Los sujetos son IRI o nodos en blanco, los predicados son IRI y los objetos también pueden ser valores literales. Los IRI identifican recursos entre conjuntos de datos; un nodo en blanco representa un recurso sin darle un identificador global. RDFS añade clases, relaciones de subclase y el dominio y rango de las propiedades. OWL proporciona definiciones de ontologías más ricas. SPARQL hace coincidir patrones de grafos para devolver vinculaciones de variables. Los grafos de propiedades ofrecen otro modelo con propiedades de clave–valor en nodos y aristas; Cypher y GQL son lenguajes de consulta para esa familia.

Si Ada está clasificada como Researcher y Researcher es una subclase de Scientist, una regla de subclase deriva que Ada es Scientist. Esto es encadenamiento hacia delante de primer orden sobre Member(x, c) ∧ Subset(c, d) ⇒ Member(x, d). Un motor de consultas de grafos necesita soporte para la consecuencia lógica pertinente o conclusiones materializadas para mostrar este hecho inferido.

Haz coincidir una consulta y conserva los detalles

Con ex: declarado como prefijo de IRI, una consulta puede ser:

SELECT ?p WHERE {
  ?p a ex:Researcher .
  ?p ex:worksAt ex:Lab .
}

El mismo ?p debe satisfacer ambos patrones. Es una combinación, no dos búsquedas independientes. Los resultados son vinculaciones como ?p = ex:Ada, similares a las sustituciones en consultas lógicas.

Una arista binaria no puede expresar por sí sola todos los papeles de un suceso fechado. Para un premio, crea un nodo de suceso o enunciado y conéctalo con el destinatario, el premio y el año. Esto mantiene juntos los detalles de un premio y evita asociar accidentalmente la fecha a todos los premios de ese tipo. Wikidata admite calificadores de enunciados para estos detalles.

Separa los enlaces ausentes, inferidos y predichos

RDF y OWL usan una interpretación de mundo abierto: una arista ausente sobre el cónyuge deja la relación como desconocida. Las aplicaciones de mundo cerrado toman una decisión distinta sobre los hechos ausentes. Un resultado vacío informa de que no hay coincidencias con esa configuración de consulta; por sí solo no establece un hecho negativo universal.

Wikidata, DBpedia, el Knowledge Graph de Google y los grafos internos de organizaciones permiten realizar consultas sobre hechos, vincular registros, apoyar recomendaciones y recuperar información para sistemas generativos. Sus hechos pueden ser incompletos o estar desactualizados. La resolución de entidades identifica registros que se refieren a lo mismo incluso cuando los identificadores son distintos.

Las representaciones vectoriales asignan vectores a entidades y relaciones. En TransE, la suma del vector de cabeza y el vector de relación se entrena para que esté cerca del vector de cola. Una puntuación alta sugiere un enlace ausente; es una predicción estadística. La inferencia lógica deriva una consecuencia a partir de hechos y reglas expresados. Mantén visible esta diferencia al decidir si una nueva arista pertenece a los hechos verificados.

La planificación clásica busca acciones que lleven un estado inicial conocido hasta un objetivo. El modelo es completamente observable, determinista, discreto y de un solo agente; el mundo cambia mediante las acciones modeladas. Una representación factorizada describe cada estado mediante fluentes, de modo que un planificador puede razonar sobre lo que cambia cada acción.

Escribe el estado y los esquemas de acción

En el fragmento básico de PDDL de estilo STRIPS, un estado enumera los fluentes atómicos verdaderos sin variables. Los fluentes no enumerados son falsos según el supuesto de mundo cerrado. El dominio reutilizable declara predicados y esquemas de acción; el problema declara objetos, el estado inicial y un objetivo. PDDL se presentó para la competición de planificación de 1998, basándose en STRIPS.

Un esquema de acción tiene parámetros, una precondición y efectos. Go(r, from, to) requiere At(r, from) y Connected(from, to); añade At(r, to) y elimina At(r, from). Pick(r, p, l) requiere At(r, l), In(p, l) y HandEmpty(r); añade Holding(r, p) y elimina In(p, l) y HandEmpty(r). Drop requiere ubicación y posesión; añade la ubicación del paquete y una mano vacía, y elimina la posesión.

Una acción sin variables solo se aplica cuando se cumplen sus precondiciones. Su actualización es RESULT(s, a) = (s − DEL(a)) ∪ ADD(a). Los demás fluentes persisten, incluidos los hechos estáticos Connected. Esta persistencia implícita gestiona el problema del marco sin un axioma separado para cada fluente que no se ve afectado.

Sigue una entrega de cuatro acciones

Inicialmente R está en Dock, Box está en Shelf y la mano de R está vacía. Los enlaces Connected unen Dock con Shelf y Shelf con Packing en ambas direcciones. El objetivo es In(Box, Packing).

1. Go(R, Dock, Shelf) cambia la ubicación de R y conserva los hechos sobre la caja y la mano.
2. Pick(R, Box, Shelf) retira la caja del estante y hace que R la sostenga.
3. Go(R, Shelf, Packing) mueve a R mientras conserva Holding(R, Box).
4. Drop(R, Box, Packing) coloca la caja en Packing y libera la mano.

El objetivo deja sin especificar la ubicación final del robot salvo donde las acciones la requieren. En general, los objetivos describen muchos estados aceptables, no un único estado completo.

Interpreta y comprueba un esquema

(:action pick
 :parameters (?r ?p ?l)
 :precondition (and (at ?r ?l) (in ?p ?l) (hand-empty ?r))
 :effect (and (holding ?r ?p)
              (not (in ?p ?l)) (not (hand-empty ?r))))

Omitir un efecto de eliminación puede dejar a un robot en dos lugares o a un paquete sostenido y en un estante a la vez. Poner una condición necesaria solo en un efecto hace que la acción la cree en lugar de comprobarla.

En el mundo de los bloques, mover un bloque libre b desde x hasta encima de un bloque libre y requiere On(b, x), Clear(b), Clear(y), Block(b), Block(y) y ¬(b = y). Añade On(b, y) y Clear(x), y elimina On(b, x) y Clear(y). Las comprobaciones de que son distintos y de que son bloques impiden apilar un bloque sobre sí mismo y tratar la mesa como un solo bloque. Una acción MoveToTable separada mantiene la mesa disponible para otros bloques.

Un modelo de planificación define un espacio de búsqueda, pero elegir acciones útiles sigue siendo difícil. La progresión busca hacia delante entre estados completos. La regresión busca hacia atrás entre las condiciones que debe satisfacer un estado anterior. Ambas pueden reutilizar métodos generales de búsqueda y aprovechar la estructura de las acciones.

Busca desde cualquiera de los dos extremos

La progresión empieza en el estado inicial y aplica acciones sin variables que sean aplicables. Puede malgastar esfuerzo en acciones irrelevantes: un robot, 20 cajas y 10 ubicaciones ya dan 200 combinaciones Pick posibles sin variables antes de filtrar por aplicabilidad.

La regresión considera una acción que logra un literal del objetivo sin negar otro. Regresa un conjunto objetivo g a través de a eliminando los literales logrados y añadiendo las precondiciones: g′ = (g − EFFECT(a)) ∪ PRECOND(a). EFFECT incluye literales positivos y negativos con su signo. Rechaza un resultado inconsistente que contenga un literal y su negación.

Para In(Box, Packing) ∧ At(R, Dock), regresar a través de Drop(R, Box, Packing) da Holding(R, Box) ∧ At(R, Packing) ∧ At(R, Dock). Estas condiciones entran en conflicto con el invariante previsto de una sola ubicación. Un plan válido debe entregar la caja antes del regreso final del robot. Regresar en cambio a través de Go(R, Shelf, Dock) da In(Box, Packing) ∧ At(R, Shelf) ∧ Connected(Shelf, Dock), que conserva la entrega del paquete.

Estima la distancia mediante problemas más sencillos

Una heurística es admisible cuando nunca sobreestima el costo óptimo restante. A* con una heurística admisible encuentra un plan óptimo. Contar los objetivos no satisfechos no siempre es admisible: una sola acción podría lograr varios.

Ignorar las precondiciones hace que todas las acciones puedan usarse de inmediato. Ignorar los efectos de eliminación hace permanente el progreso, para problemas expresados con precondiciones y objetivos positivos. Las condiciones negativas deben convertirse primero en fluentes positivos mantenidos explícitamente. La longitud óptima del plan relajado h⁺ es una cota inferior de la longitud del plan real, pero calcularla es NP-difícil. FF encuentra rápidamente un plan relajado sin garantizar su optimalidad; su longitud puede sobreestimar h⁺ y no está garantizado que sea admisible.

Para el objetivo de entrega en el almacén más el regreso, el plan real más corto tiene seis acciones: ir a Shelf, recoger, ir a Packing, soltar, volver a Shelf y volver a Dock. La relajación por omisión de efectos negativos solo necesita las primeras cuatro porque At(R, Dock) sigue siendo verdadero después de partir. Así, h⁺ = 4 mientras que el costo real es 6. El conteo de objetivos no satisfechos empieza en solo 1 y no refleja la mayor parte de ese trabajo.

Combina estimaciones sin contar dos veces

Un grafo de planificación alterna niveles de posibles fluentes y acciones, con enlaces de exclusión mutua que marcan pares incompatibles. La primera aparición de un objetivo da una estimación de nivel. Tomar el máximo de los niveles de los objetivos individuales es admisible; sumarlos puede contar repetidamente el trabajo compartido. La abstracción de estados elimina algunos fluentes para reducir el espacio de estados. La descomposición en subobjetivos también se beneficia de comprobar las acciones compartidas: el máximo de los costos admisibles de los subobjetivos es seguro, mientras que su suma necesita justificación adicional.

Los métodos de planificación difieren en aquello sobre lo que buscan: estados, asignaciones de valores de verdad, restricciones de orden o refinamientos de procedimientos expertos. Su utilidad depende de la interacción entre subobjetivos y de los supuestos que hace el modelo sobre la ejecución.

Reconoce los subobjetivos que interactúan

En la anomalía de Sussman, C está sobre A, con A y B sobre la mesa. El objetivo es On(A, B) ∧ On(B, C). Completar primero el subobjetivo de colocar A sobre B bloquea la posterior colocación de B. Colocar B sobre C inmediatamente deja A debajo. Un plan más corto libera primero A y después construye la pila desde abajo: mueve C a la mesa, mueve B sobre C y después mueve A sobre B. Los tres movimientos intercalan la preparación y el logro de los objetivos.

Codifica un plan acotado como SAT

SATPlan elige un horizonte T. Afirma los fluentes iniciales en el tiempo 0, los fluentes del objetivo en T, las precondiciones de las acciones, las restricciones de estado sucesor y las exclusiones de acciones incompatibles. Una asignación satisfactoria selecciona acciones que forman un plan. Un resultado insatisfacible descarta planes dentro de esa codificación y ese horizonte.

Probar horizontes en orden encuentra el menor horizonte satisfacible. Con acciones paralelas, esto minimiza las capas, no necesariamente el número total de acciones. Se necesita una cota de parada para que los sucesivos horizontes insatisfacibles permitan concluir que no existe un plan.

Mantén solo el orden necesario

La planificación de orden parcial registra acciones, restricciones de orden y enlaces causales. Un enlace de A a B etiquetado con p dice que A establece la precondición p para B. Una acción C que podría eliminar p entre ellas es una amenaza. La degradación sitúa C antes de A; la promoción la sitúa después de B. Las acciones no relacionadas pueden permanecer sin ordenar hasta la ejecución, siguiendo el principio de mínimo compromiso.

La planificación HTN refina tareas de alto nivel mediante una biblioteca de métodos. DeliverBox puede convertirse en desplazarse hasta la caja, recogerla, desplazarse hasta el destino y soltarla. Estos métodos codifican procedimientos expertos, así que la búsqueda puede centrarse en refinamientos útiles en lugar de considerar cada acción primitiva en cada punto.

Ajusta el modelo al mundo

La existencia de un plan para STRIPS proposicional general es PSPACE-completa. El mundo de los bloques tiene un problema de existencia más fácil para disposiciones posibles: despejar los bloques llevándolos a la mesa y reconstruir, usando como máximo 2n movimientos para n bloques. Encontrar un plan más corto para el mundo de los bloques sigue siendo NP-difícil.

Los modelos clásicos excluyen resultados inciertos, estados ocultos y duraciones de acciones. Los planes conformantes funcionan sin observaciones, los planes contingentes se ramifican según las observaciones, la replanificación en línea responde a diferencias durante la ejecución y la programación de tareas gestiona tiempos y recursos. Una precondición ausente sobre la batería puede hacer que un plan válido en el modelo falle físicamente. La supervisión de la ejecución comprueba esta diferencia. La planificación automatizada ha llegado a sistemas reales, incluido el Remote Agent de la NASA en Deep Space 1 en 1999.