El cálculo situacional 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 introducida por Ray Reiter en 1991. Le siguen secciones sobre la versión de McCarthy de 1986 y una formulación de programación lógica .
El cálculo de situaciones 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 de robots simple como ejemplo de ejecución. En este mundo hay un solo robot y varios objetos inanimados. El mundo está diseñado según una cuadrícula para que las ubicaciones se puedan especificar en términos de puntos de coordenadas. El robot puede moverse por el mundo y recoger y dejar caer objetos. Algunos objetos pueden ser demasiado pesados para que el robot los recoja o frágiles y se rompan al caer. El robot también tiene la capacidad de reparar cualquier objeto roto que esté sosteniendo.
Los elementos principales del cálculo de situaciones son las acciones, los fluidos y las situaciones. En la descripción del mundo también intervienen normalmente 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. Mientras que 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 tipo acción y también funciones cuyo resultado sea de tipo acción. Las acciones se pueden cuantificar. En el mundo de los robots de ejemplo, los términos de acción posibles 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 avanza a través de una serie de situaciones como resultado de varias acciones que se llevan a cabo dentro del mundo. Una situación representa una historia de ocurrencias de acciones. En la versión de Reiter del cálculo de situaciones que se describe aquí, 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 se denota típicamente como y se denomina situación inicial. La nueva situación resultante de la realización de una acción se denota utilizando el símbolo de función do (Algunas otras referencias [3] también utilizan result ). 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 ve reforzado por un axioma que establece que es igual a si y solo si y . Esta condición no tiene sentido si las situaciones fueran estados, ya que dos acciones diferentes ejecutadas en dos estados diferentes pueden dar como resultado el mismo estado.
En el mundo de los robots 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 situación como y denotan las secuencias de acciones ejecutadas, y no la descripción del estado que resulta de la ejecución.
Las afirmaciones cuyo valor de verdad puede cambiar se modelan mediante fluentes relacionales , predicados que toman una situación como argumento final. También son posibles los fluentes funcionales , funciones que toman una situación como argumento final y devuelven un valor dependiente de la situación. Los fluentes pueden considerarse como "propiedades del mundo".
En el ejemplo, el fluido se puede utilizar para indicar que el robot lleva un objeto particular en una situación particular. Si el robot no lleva nada inicialmente, 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 fundacionales.
Algunas acciones pueden no ser ejecutables en una situación dada. Por ejemplo, es imposible dejar un objeto a menos que uno lo esté llevando consigo. Las restricciones sobre la ejecució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 solo es posible cuando uno lo está llevando consigo 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 heavy ):
Dado que una acción es posible en una situación, se deben especificar los efectos de esa acción sobre los fluidos. Esto se hace mediante los axiomas de efecto. Por ejemplo, el hecho de que recoger un objeto haga que el robot lo lleve consigo se puede modelar como:
También es posible especificar efectos condicionales, que son efectos que dependen del estado actual. Los siguientes modelos indican que algunos objetos son frágiles (indicados por el predicado frágil ) y que al eliminarlos se rompen (indicado por el predicado fluido roto ):
Si bien esta fórmula describe correctamente el efecto de las acciones, no es suficiente para 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 se pueden usar para derivar los efectos no deseados de las acciones. Por ejemplo, no es posible deducir que después de recoger un objeto, la ubicación del robot permanece inalterada. Esto requiere un axioma de marco, una fórmula como la siguiente:
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 hay una gran cantidad de tales axiomas, es muy fácil que el diseñador omita un axioma de marco necesario u olvide modificar todos los axiomas apropiados cuando se realiza un cambio en la descripción del mundo.
Los axiomas de estado sucesor "resuelven" el problema del 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 en particular. Los axiomas de efecto que afectan el valor del fluido se pueden escribir en forma generalizada como un axioma de efecto positivo y uno negativo:
La fórmula describe las condiciones bajo las cuales la acción a en la situación s hace que la fluidez 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 la función F fluida puede cambiar de valor, pueden reescribirse 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 F fluida 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 a en s no la haría falsa".
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 enunciando las mismas en forma de 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 afirmaciones demuestran que, inicialmente, el robot no lleva nada, se encuentra 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 las situaciones.
La regresión [4] es un mecanismo para demostrar 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 iterar este procedimiento, se puede llegar a una fórmula equivalente que contiene solo la situación inicial S 0 . Demostrar consecuencias es supuestamente más simple a partir de esta fórmula que a partir de 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 situacional 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 las 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 situaciones, los fluentes no están cosificados. En otras palabras, las condiciones que pueden cambiar se representan mediante predicados y no mediante funciones. En realidad, McCarthy y Hayes definieron un fluente como una función que depende de la situación, pero luego procedieron siempre a utilizar predicados para representar fluentes. Por ejemplo, el hecho de que esté lloviendo en el lugar x en la situación s se representa mediante el literal . En la versión de 1986 del cálculo de situaciones de McCarthy, se utilizan fluentes funcionales. Por ejemplo, la posición de un objeto x en la situación s se representa mediante el valor de , donde la ubicación es una función. Se pueden dar enunciados sobre tales funciones utilizando la igualdad: significa que la ubicación del objeto x es la misma en las dos situaciones s y .
La ejecución de acciones se representa mediante la función result : 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 fluidos en la situación s y fluidos en las situaciones . Por ejemplo, que la acción de abrir la puerta dé como resultado que la puerta esté abierta si no está bloqueada se representa mediante:
Los predicados bloqueado y abierto representan las condiciones de que una puerta esté bloqueada y abierta, respectivamente. Como estas condiciones pueden variar, se representan mediante predicados con un argumento de situación. La fórmula dice que si la puerta no está bloqueada en una situación, entonces la puerta está abierta después de ejecutar la acción de abrir, acción que se representa mediante la constante opens .
Estas fórmulas no son suficientes para derivar todo lo que se considera plausible. De hecho, los fluidos en diferentes situaciones solo están relacionados si son precondiciones 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 sigue de , que es lo que uno esperaría (la puerta no se bloquea 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 situaciones, la situación inicial, posteriormente denotada por , no se identifica explícitamente. La situación inicial no es necesaria si las situaciones se toman como descripciones del mundo. Por ejemplo, para representar el escenario en el que la puerta estaba cerrada pero no bloqueada y se realiza la acción de abrirla se formaliza tomando una constante s para significar la situación inicial y haciendo afirmaciones sobre ella (por ejemplo, ). Que la puerta esté abierta después del cambio se refleja en la fórmula que se implica. La situación inicial, en cambio, es necesaria si, como en el cálculo de situaciones moderno, una situación se toma 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 situaciones 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 situaciones como un programa lógico:
Aquí Holds es un metapredicado y la variable f se extiende sobre los fluentes. 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 finalización del programa, en la que la negación se interpreta como negación como fracaso . Los axiomas de inducción también son implícitos y solo se necesitan para probar 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)\right)\right]}](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 reparar(o)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7da99e394ede67d8b8425ecc63db7d2dba81cd42)
