El cálculo de situación es un formalismo lógico diseñado para representar y razonar sobre dominios dinámicos. Fue introducido por primera vez por John McCarthy en 1963. [1] La versión principal del cálculo situacional que se presenta en este artículo se basa en la presentada por Ray Reiter en 1991. Le siguen secciones sobre la versión de McCarthy de 1986 y una programación lógica. formulación.
El cálculo de situación representa escenarios cambiantes como un conjunto de fórmulas lógicas de primer orden . Los elementos básicos del cálculo son:
Un dominio se formaliza mediante una serie de fórmulas, a saber:
Se modelará un mundo robótico sencillo como ejemplo en ejecución. En este mundo hay un solo robot y varios objetos inanimados. El mundo está dispuesto según una cuadrícula para que las ubicaciones se puedan especificar en términos de puntos de coordenadas. Es posible que el robot se mueva por el mundo y recoja y suelte objetos. Algunos artículos pueden ser demasiado pesados para que el robot los recoja o pueden ser tan frágiles que se rompan al caer. El robot también tiene la capacidad de reparar cualquier elemento roto que contenga.
Los elementos principales del cálculo de situación son las acciones, los flujos y las situaciones. En la descripción del mundo también suelen intervenir varios objetos. El cálculo de situaciones se basa en un dominio ordenado con tres tipos: acciones, situaciones y objetos, donde los objetos incluyen todo lo que no es una acción o una situación. Se pueden utilizar variables de cada tipo. Si bien las acciones, situaciones y objetos son elementos del dominio, los fluidos se modelan como predicados o funciones.
Las acciones forman una especie de dominio. Se pueden utilizar variables de acción de clasificación y también funciones cuyo resultado sea de acción de clasificación. Las acciones se pueden cuantificar. En el mundo de los robots de ejemplo, los posibles términos de acción serían modelar el robot moviéndose a una nueva ubicación y modelar el robot recogiendo un objeto o . Se utiliza un predicado especial Poss para indicar cuándo una acción es ejecutable.
En el cálculo de situaciones, se modela un mundo dinámico que progresa a través de una serie de situaciones como resultado de diversas acciones que se realizan dentro del mundo. Una situación representa una historia de acontecimientos de acción. En la versión de Reiter del cálculo de situación aquí descrita, una situación no representa un estado, contrariamente al significado literal del término y contrariamente a la definición original de McCarthy y Hayes . Reiter ha resumido este punto de la siguiente manera:
La situación anterior a la realización de cualquier acción generalmente se denota y se denomina situación inicial. La nueva situación resultante de la realización de una acción se denota mediante el símbolo de función do (algunas otras referencias [3] también utilizan resultado ). Este símbolo de función tiene una situación y una acción como argumentos, y una situación como resultado, siendo esta última la situación que resulta de realizar la acción dada en la situación dada.
El hecho de que las situaciones sean secuencias de acciones y no estados se refuerza mediante un axioma que establece que es igual a si y sólo si y . Esta condición no tiene sentido si las situaciones fueran estados, ya que dos acciones diferentes ejecutadas en dos estados diferentes pueden resultar en el mismo estado.
En el mundo del robot de ejemplo, si la primera acción del robot es moverse a la ubicación , la primera acción es y la situación resultante es . Si su siguiente acción es recoger la pelota, la situación resultante es . Los términos de situaciones como y denotan secuencias de acciones ejecutadas, y no la descripción del estado que resulta de la ejecución.
Los enunciados cuyo valor de verdad puede cambiar se modelan mediante fluidos relacionales , predicados que toman una situación como argumento final. También son posibles los fluidos funcionales , funciones que toman una situación como argumento final y devuelven un valor dependiente de la situación. Los fluidos pueden considerarse "propiedades del mundo".
En el ejemplo, la fluidez se puede utilizar para indicar que el robot lleva un objeto particular en una situación particular. Si el robot inicialmente no lleva nada, es falso mientras que es verdadero. La ubicación del robot se puede modelar utilizando un fluido funcional que devuelve la ubicación del robot en una situación particular.
La descripción de un mundo dinámico está codificada en lógica de segundo orden utilizando tres tipos de fórmulas: fórmulas sobre acciones (condiciones previas y efectos), fórmulas sobre el estado del mundo y axiomas fundamentales.
Es posible que algunas acciones no sean ejecutables en una situación determinada. Por ejemplo, es imposible dejar un objeto a menos que uno lo esté llevando. Las restricciones sobre la realización de acciones se modelan mediante literales de la forma , donde a es una acción, s una situación y Poss es un predicado binario especial que denota la ejecutabilidad de las acciones. En el ejemplo, la condición de que dejar caer un objeto sólo es posible cuando uno lo lleva se modela mediante:
Como ejemplo más complejo, los siguientes modelos muestran que el robot solo puede transportar un objeto a la vez y que algunos objetos son demasiado pesados para que el robot los levante (indicado por el predicado pesado ):
Dado que una acción es posible en una situación, hay que especificar los efectos de esa acción sobre los fluidos. Esto se hace mediante los axiomas del efecto. Por ejemplo, el hecho de que recoger un objeto hace que el robot lo lleve se puede modelar como:
También es posible especificar efectos condicionales, que son efectos que dependen del estado actual. Los siguientes modelos muestran que algunos objetos son frágiles (indicado por el predicado frágil ) y dejarlos caer provoca que se rompan (indicado por el fluido roto ):
Si bien esta fórmula describe correctamente el efecto de las acciones, no es suficiente describir correctamente la acción en lógica, debido al problema del marco .
Si bien las fórmulas anteriores parecen adecuadas para razonar sobre los efectos de las acciones, tienen una debilidad crítica: no pueden usarse para derivar los no efectos de las acciones. Por ejemplo, no es posible deducir que después de recoger un objeto, la ubicación del robot permanezca sin cambios. Esto requiere el llamado axioma del marco, una fórmula como:
La necesidad de especificar axiomas de marco se ha reconocido desde hace mucho tiempo como un problema en la axiomatización de mundos dinámicos, y se conoce como el problema del marco . Como generalmente existe un gran número de axiomas de este tipo, es muy fácil para el diseñador omitir un axioma de marco necesario u olvidarse de modificar todos los axiomas apropiados cuando se realiza un cambio en la descripción del mundo.
Los axiomas del estado sucesor "resuelven" el problema marco en el cálculo de situaciones. Según esta solución, el diseñador debe enumerar como axiomas de efecto todas las formas en que se puede cambiar el valor de un fluido particular. Los axiomas del efecto que afectan el valor de fluent se pueden escribir en forma generalizada como un axioma de efecto positivo y negativo:
La fórmula describe las condiciones bajo las cuales la acción a en la situación s hace que la fluida F se vuelva verdadera en la situación sucesora . Asimismo, describe las condiciones bajo las cuales realizar la acción a en la situación s hace que la fluidez F sea falsa en la situación sucesora.
Si este par de axiomas describe todas las formas en que F fluido puede cambiar de valor, se pueden reescribir como un solo axioma:
En palabras, esta fórmula establece: "dado que es posible realizar la acción a en la situación s , la fluidez F sería verdadera en la situación resultante si y sólo si realizar a en s la haría verdadera, o es verdadera en la situación s y realizar un in s no lo haría falso."
A modo de ejemplo, el valor del fluido roto introducido anteriormente viene dado por el siguiente axioma del estado sucesor:
Las propiedades de la situación inicial o de cualquier otra situación se pueden especificar simplemente enunciandolas como fórmulas. Por ejemplo, un hecho sobre el estado inicial se formaliza haciendo afirmaciones sobre (que no es un estado, sino una situación ). Las siguientes declaraciones modelan que inicialmente el robot no lleva nada, está en la ubicación y no hay objetos rotos:
Los axiomas fundamentales del cálculo de situaciones formalizan la idea de que las situaciones son historias al tener . También incluyen otras propiedades como la inducción de segundo orden sobre situaciones.
La regresión [4] es un mecanismo para probar consecuencias en el cálculo de situaciones. [5] Se basa en expresar una fórmula que contiene la situación en términos de una fórmula que contiene la acción a y la situación s , pero no la situación . Al repetir este procedimiento, se puede terminar con una fórmula equivalente que contenga sólo la situación inicial S 0 . Se supone que demostrar las consecuencias es más sencillo con esta fórmula que con la original.
GOLOG es un lenguaje de programación lógica basado en el cálculo de situaciones. [6] [7]
La principal diferencia entre el cálculo de situación original de McCarthy y Hayes y el que se utiliza hoy en día es la interpretación de las situaciones. En la versión moderna del cálculo situacional, una situación es una secuencia de acciones. Originalmente, las situaciones se definían como "el estado completo del universo en un instante de tiempo". Desde el principio quedó claro que tales situaciones no podían describirse completamente; la idea era simplemente dar algunas afirmaciones sobre situaciones y derivar consecuencias de ellas. Esto también es diferente del enfoque que adopta el cálculo fluido , donde un estado puede ser una colección de hechos conocidos, es decir, una descripción posiblemente incompleta del universo.
En la versión original del cálculo de situación, los fluidos no están cosificados. En otras palabras, las condiciones que pueden cambiar están representadas por predicados y no por funciones. En realidad, McCarthy y Hayes definieron un fluido como una función que depende de la situación, pero luego procedieron a utilizar siempre predicados para representar fluidos. Por ejemplo, el hecho de que esté lloviendo en el lugar x en la situación s se representa con el literal . En la versión de 1986 del cálculo de situación de McCarthy, se utilizan fluidos funcionales. Por ejemplo, la posición de un objeto x en la situación s está representada por el valor de , donde la ubicación es una función. Se pueden dar afirmaciones sobre tales funciones usando la igualdad: significa que la ubicación del objeto x es la misma en las dos situaciones s y .
La ejecución de acciones está representada por el resultado de la función : la ejecución de la acción a en la situación s es la situación . Los efectos de las acciones se expresan mediante fórmulas que relacionan fluidez en situaciones y fluidez en situaciones . Por ejemplo, que la acción de abrir la puerta da como resultado que la puerta se abra si no está cerrada se representa por:
Los predicados bloqueado y abierto representan las condiciones de una puerta cerrada y abierta, respectivamente. Dado que estas condiciones pueden variar, se representan mediante predicados con un argumento de situación. La fórmula dice que si la puerta no está cerrada con llave en una situación, entonces la puerta se abre luego de ejecutar la acción de apertura, estando representada esta acción por la constante abre .
Estas fórmulas no son suficientes para derivar todo lo que se considera plausible. De hecho, las fluidez en situaciones diferentes sólo están relacionadas si son condiciones previas y efectos de acciones; Si un fluido no se ve afectado por una acción, no hay forma de deducir que no cambió. Por ejemplo, la fórmula anterior no implica que se siga de , que es lo que uno esperaría (la puerta no se cierra con llave al abrirla). Para que se mantenga la inercia, se necesitan fórmulas llamadas axiomas de marco . Estas fórmulas especifican todos los no efectos de las acciones:
En la formulación original del cálculo de situación, la situación inicial, posteriormente denotada por , no se identifica explícitamente. La situación inicial no es necesaria si las situaciones se consideran descripciones del mundo. Por ejemplo, para representar el escenario en el que la puerta estaba cerrada pero no bloqueada y la acción de abrirla se realiza se formaliza tomando una constante s para significar la situación inicial y haciendo afirmaciones sobre ella (p. ej., ). Que la puerta esté abierta tras el cambio se refleja en la fórmula que conlleva. La situación inicial es, por el contrario, necesaria si, como en el cálculo de situaciones moderno, se toma una situación como una historia de acciones, ya que la situación inicial representa la secuencia vacía de acciones.
La versión del cálculo de situación introducida por McCarthy en 1986 difiere de la original por el uso de fluidos funcionales (por ejemplo, es un término que representa la posición de x en la situación s ) y por un intento de utilizar la circunscripción para reemplazar los axiomas del marco. .
También es posible (por ejemplo, Kowalski 1979, Apt y Bezem 1990, Shanahan 1997) escribir el cálculo de situación como un programa lógico:
Aquí Holds es un metapredicado y la variable f oscila sobre los fluidos. Los predicados Poss , Initiates y Terminates corresponden a los predicados Poss , y respectivamente. La flecha izquierda ← es la mitad de la equivalencia ↔. La otra mitad está implícita en la realización del programa, en el que la negación se interpreta como negación como fracaso . Los axiomas de inducción también están implícitos y sólo son necesarios para demostrar las propiedades del programa. El razonamiento hacia atrás como en la resolución SLD , que es el mecanismo habitual utilizado para ejecutar programas lógicos, implementa la regresión implícitamente.
![{\displaystyle Poss(a,s)\rightarrow \left[F({\overrightarrow {x}},do(a,s))\leftrightarrow \gamma _ {F}^{+}({\overrightarrow {x} },a,s)\vee \left(F({\overrightarrow {x}},s)\wedge \neg \gamma _ {F}^{-}({\overrightarrow {x}},a,s) \bien bien]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff11c2eddd8beef74445816539358b972d08dd8)
![{\displaystyle Poss(a,s)\rightarrow \left[roto(o,do(a,s))\leftrightarrow a=drop(o)\wedge frágil(o)\vee roto(o,s)\wedge a \neq reparación(o)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7da99e394ede67d8b8425ecc63db7d2dba81cd42)
