El cálculo de situaciones 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 programación lógica. formulación.
Descripción general
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:
- Las acciones que se pueden realizar en el mundo
- Los fluidos que describen el estado del mundo
- Las situaciones
Un dominio se formaliza mediante una serie de fórmulas, a saber:
- Axiomas de condición previa de acción, uno para cada acción
- Axiomas de estado sucesor, uno para cada fluido
- Axiomas que describen el mundo en diversas situaciones.
- Los axiomas fundamentales del cálculo de situaciones
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 se presenta de acuerdo con una cuadrícula para que las ubicaciones se puedan especificar en términos decoordinar puntos. Es posible que el robot se mueva por el mundo y recoja y suelte elementos. Algunos elementos pueden ser demasiado pesados para que los recoja el robot o frágiles de modo que se rompan cuando se caen. El robot también tiene la capacidad de reparar cualquier artículo roto que tenga.
Elementos
Los elementos principales del cálculo de situaciones son las acciones, la fluidez y las situaciones. En la descripción del mundo también participan típicamente 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.
Comportamiento
Las acciones forman una especie de dominio. Se pueden utilizar variables de acción de clasificación. Las acciones se pueden cuantificar. En el ejemplo del mundo de los robots, los posibles términos de acción serían para modelar el robot que se mueve a una nueva ubicación , y para modelar el robot que recoge un objeto . Un predicado especial se utiliza para indicar cuándo una acción es ejecutable.
Situaciones
En el cálculo de situaciones, un mundo dinámico se modela como progresando a través de una serie de situaciones como resultado de diversas acciones que se realizan dentro del mundo. Una situación representa un historial de sucesos 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. Este punto ha sido resumido por Reiter de la siguiente manera:
- Una situación es una secuencia finita de acciones. Período. No es un estado, no es una instantánea, es una historia [1] .
La situación antes de que se haya realizado cualquier acción generalmente se denota y llamó a la 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(Algunas otras referencias [ ¿cuáles? ] También usan). 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 está 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 resultar en el mismo estado.
En el ejemplo del mundo de los robots, 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. Términos de situaciones como y denota las secuencias de acciones ejecutadas, y no la descripción del estado que resulta de la ejecución.
Fluidos
Los enunciados cuyo valor de verdad puede cambiar son modelados por fluidos relacionales , predicados que toman una situación como su 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, el fluido se puede utilizar para indicar que el robot lleva un objeto en particular en una situación particular. Si el robot inicialmente no lleva nada, es falso mientras es verdad. La ubicación del robot se puede modelar utilizando un fluido funcional que devuelve la ubicación del robot en una situación particular.
Fórmulas
La descripción de un mundo dinámico se codifica en lógicas 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.
Condiciones previas de acción
Es posible que algunas acciones no se puedan ejecutar en una situación determinada. Por ejemplo, es imposible dejar un objeto a menos que uno lo esté cargando. Las restricciones sobre la realización de acciones están modeladas por literales de la forma, dónde es una acción, una situación, y es un predicado binario especial que denota la ejecución de acciones. En el ejemplo, la condición de que dejar caer un objeto solo es posible cuando uno lo lleva está modelada por:
Como ejemplo más complejo, los siguientes modelos de que el robot puede transportar solo un objeto a la vez, y que algunos objetos son demasiado pesados para que el robot los levante (indicado por el predicado ):
Efectos de acción
Dado que una acción es posible en una situación, se deben especificar los efectos de esa acción en los fluidos. Esto se hace mediante los axiomas del efecto. Por ejemplo, el hecho de que levantar un objeto haga 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 de que algunos objetos son frágiles (indicado por el predicado) y dejarlos caer hace que se rompan (indicado por el fluido ):
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 .
El 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 levantar un objeto, la ubicación del robot permanece sin cambios. Esto requiere un llamado axioma de marco, una fórmula como:
La necesidad de especificar los axiomas del marco se ha reconocido desde hace mucho tiempo como un problema en la axiomatización de los mundos dinámicos, y se conoce como el problema del marco . Como generalmente hay un gran número de tales axiomas, es muy fácil para el diseñador omitir un axioma marco necesario u olvidarse de modificar todos los axiomas apropiados cuando se hace un cambio en la descripción del mundo.
Los axiomas del estado sucesor
Los axiomas del estado sucesor "resuelven" el problema del marco en el cálculo de situaciones. De acuerdo con 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 del efecto que afectan el valor de la fluidez se puede escribir en forma generalizada como un axioma de efecto positivo y negativo:
La formula describe las condiciones bajo las cuales la acción en situación hace que el fluido hacerse realidad en la situación del sucesor . Igualmente, describe las condiciones bajo las cuales realizar la acción en situación hace fluido falso en la situación del sucesor.
Si este par de axiomas describen todas las formas en que la fluidez pueden cambiar de valor, se pueden reescribir como un solo axioma:
En palabras, esta fórmula dice: "dado que es posible realizar una acción en situación , el fluido sería cierto en la situación resultante si y solo si realiza en lo haría verdad, o es verdad en una situación y actuando en no lo haría falso. "
A modo de ejemplo, el valor de la fluidez introducido anteriormente viene dado por el siguiente axioma de estado sucesor:
Estados
Las propiedades de la situación inicial o de cualquier otra situación se pueden especificar simplemente expresándolas 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 ). El siguiente modelo de declaraciones que inicialmente, el robot no lleva nada, está en la ubicación, y no hay objetos rotos:
Axiomas fundamentales
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 en situaciones.
Regresión
La regresión es un mecanismo para probar consecuencias en el cálculo de situaciones. Se basa en expresar una fórmula que contiene la situación. en términos de una fórmula que contiene la acción y la situacion , pero no la situación . Al iterar este procedimiento, uno puede terminar con una fórmula equivalente que contenga solo la situación inicial. Probar consecuencias es supuestamente más simple con esta fórmula que con la original.
GOLOG
GOLOG es un lenguaje de programación lógica basado en el cálculo de situaciones. [2] [3]
La versión original del cálculo de situaciones.
La principal diferencia entre el cálculo de situaciones original de McCarthy y Hayes y el que se usa hoy en día es la interpretación de situaciones. En la versión moderna del cálculo situacional, una situación es una secuencia de acciones. Originalmente, las situaciones se definieron como "el estado completo del universo en un instante de tiempo". Desde el principio quedó claro que tales situaciones no podían describirse por completo; la idea era simplemente dar algunas declaraciones sobre situaciones y derivar consecuencias de ellas. Esto también es diferente del enfoque adoptado por 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 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 una fluidez como una función que depende de la situación, pero luego procedieron siempre usando predicados para representar fluidez. Por ejemplo, el hecho de que esté lloviendo en un lugar en la situacion está representado por el literal . En la versión de 1986 del cálculo de situaciones de McCarthy, se utilizan fluidos funcionales. Por ejemplo, la posición de un objeto en la situacion está representado por el valor de , dónde es una función. Las declaraciones sobre tales funciones se pueden dar usando la igualdad: significa que la ubicación del objeto es igual en las dos situaciones y .
La ejecución de acciones está representada por la función : la ejecución de la acción en la situacion es la situacion . Los efectos de las acciones se expresan mediante fórmulas que relacionan fluidos 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á bloqueada está representado por:
Los predicados y 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á bloqueada en una situación, entonces la puerta se abre después de ejecutar la acción de apertura, esta acción está representada por la constante.
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 condiciones previas y efectos de las 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 sigue desde , que es lo que cabría esperar (la puerta no se cierra con llave abriéndola). Para que la inercia se mantenga, 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 se toman las situaciones como descripciones del mundo. Por ejemplo, para representar el escenario en el que se cerró la puerta pero no se bloqueó y la acción de abrirla se realiza se formaliza tomando una constante para referirse a la situación inicial y hacer declaraciones sobre ella (p. ej., ). Que la puerta esté abierta después del cambio se refleja en la fórmula.estar implicado. En cambio, la situación inicial 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 para el uso de fluidos funcionales (p. Ej., es un término que representa la posición de en la situacion ) y por un intento de utilizar la circunscripción para reemplazar los axiomas del marco.
El cálculo de situaciones como programa lógico
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í es un metapredicado y la variable va más allá de los fluidos. Los predicados, y corresponden a los predicados , , y respectivamente. La flecha izquierda es la mitad de la equivalencia . La otra mitad está implícita en la finalizació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 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.
Ver también
Referencias
- ^ McCarthy, John (1963). "Situaciones, acciones y leyes causales" (PDF) . Informe técnico de la Universidad de Stanford .
- ^ Lakemeyer, Gerhard. "El cálculo de la situación y Golog: un tutorial" (PDF) . www.hybrid-reasoning.org . Consultado el 16 de julio de 2014 .
- ^ "Publicaciones sobre GOLOG" . Consultado el 16 de julio de 2014 .
- J. McCarthy y P. Hayes (1969). Algunos problemas filosóficos desde el punto de vista de la inteligencia artificial . En B. Meltzer y D. Michie, editores, Machine Intelligence , 4: 463–502. Prensa de la Universidad de Edimburgo, 1969.
- R. Kowalski (1979). Lógica para la resolución de problemas - Elsevier North Holland.
- KR Apt y M. Bezem (1990). Programas acíclicos. En: VII Congreso Internacional de Programación Lógica. Prensa del MIT. Jerusalén, Israel.
- R. Reiter (1991). El problema del marco en el cálculo de situaciones: una solución simple (a veces) y un resultado completo para la regresión de objetivos. En Vladimir Lifshitz, editor, Inteligencia artificial y teoría matemática de la computación: artículos en honor a John McCarthy , páginas 359–380, San Diego, CA, EE. UU. Academic Press Professional, Inc. 1991.
- M. Shanahan (1997). Resolver el problema del marco: una investigación matemática de la ley de inercia del sentido común. Prensa del MIT.
- H. Levesque, F. Pirri y R. Reiter (1998). Fundamentos del cálculo de situaciones . Transacciones electrónicas sobre inteligencia artificial , 2 (3–4): 159-178.
- F. Pirri y R. Reiter (1999). Algunas aportaciones a la metateoría del Cálculo de Situaciones. Revista de la ACM , 46 (3): 325–361. doi : 10.1145 / 316542.316545
- R. Reiter (2001). Conocimiento en acción: fundamentos lógicos para especificar e implementar sistemas dinámicos. La prensa del MIT.