Cálculo de eventos - Event calculus

El cálculo de eventos es un lenguaje lógico para representar y razonar sobre eventos y sus efectos presentado por primera vez por Robert Kowalski y Marek Sergot en 1986. Murray Shanahan y Rob Miller lo ampliaron en la década de 1990. Al igual que en otros lenguajes para razonar sobre el cambio, el cálculo de eventos representa los efectos de las acciones en los fluidos . Sin embargo, los eventos también pueden ser externos al sistema. En el cálculo de eventos, se puede especificar el valor de los fluidos en algunos puntos de tiempo dados, los eventos que tienen lugar en puntos de tiempo dados y sus efectos.

Fluidos y eventos

En el caso de cálculo, los fluidos se cosifican . Esto significa que no se formalizan mediante predicados sino mediante funciones . Se utiliza un predicado independiente HoldsAt para indicar qué fluidos se mantienen en un momento determinado. Por ejemplo, significa que la caja está sobre la mesa en el momento t ; en esta fórmula, HoldsAt es un predicado mientras que on es una función.

Los eventos también se representan como términos. Los efectos de los eventos se dan utilizando los predicados Inicia y Termina . En particular, significa que, si el evento representado por el término e se ejecuta en el tiempo t , entonces la fluidez f será verdadera después de t . El predicado Terminates tiene un significado similar, con la única diferencia de que f será falsa después de t .

Axiomas independientes del dominio

Como otros lenguajes para representar acciones, el cálculo de eventos formaliza la correcta evolución de la fluidez a través de fórmulas que indican el valor de cada fluidez después de que se ha realizado una acción arbitraria. El cálculo de eventos resuelve el problema del marco de una manera similar a los axiomas de estado sucesor del cálculo de situaciones : un fluido es verdadero en el tiempo t si y solo si se ha hecho verdadero en el pasado y no se ha hecho falso en el tiempo t. mientras tanto.

Esta fórmula significa que el fluido representado por el término f es verdadero en el tiempo t si:

  1. un evento de correo ha tenido lugar: ;
  2. esto tuvo lugar en el pasado :;
  3. este evento tiene la fluidez f como efecto :;
  4. el fluido no se ha hecho falso mientras tanto:

Se utiliza una fórmula similar para formalizar el caso contrario en el que un fluido es falso en un momento dado. También se necesitan otras fórmulas para formalizar correctamente los fluidos antes de que hayan sido efectos de un evento. Estas fórmulas son similares a las anteriores, pero se reemplazan por .

El predicado recortado , que indica que un fluido se ha hecho falso durante un intervalo, puede axiomatizarse, o simplemente tomarse como una abreviatura, de la siguiente manera:

Axiomas dependientes del dominio

Los axiomas anteriores relacionan el valor de los predicados HoldsAt , Initiates y Terminates , pero no especifican qué fluidos se sabe que son verdaderos y qué eventos realmente hacen que los fluidos sean verdaderos o falsos. Esto se hace mediante el uso de un conjunto de axiomas dependientes del dominio. Los valores conocidos de fluidos se expresan como literales simples . Los efectos de los eventos se expresan mediante fórmulas que relacionan los efectos de los eventos con sus condiciones previas. Por ejemplo, si el evento open hace que el fluido isopen sea verdadero, pero solo si haskey es verdadero actualmente, la fórmula correspondiente en el cálculo de eventos es:

La expresión de la derecha de esta equivalencia se compone de una disyunción: para cada evento y fluidez que el evento puede hacer verdadero, hay una disyunción que dice que e es en realidad ese evento, que f es realmente así de fluida, y que el se cumple la condición previa del evento.

La fórmula anterior especifica el valor de verdad de para cada evento posible y fluido. Como resultado, todos los efectos de todos los eventos deben combinarse en una única fórmula. Esto es un problema, porque la adición de un nuevo evento requiere modificar una fórmula existente en lugar de agregar nuevas. Este problema puede resolverse mediante la aplicación de la circunscripción a un conjunto de fórmulas, cada una de las cuales especifica un efecto de un evento:

Estas fórmulas son más simples que la fórmula anterior, porque cada efecto de cada evento se puede especificar por separado. La fórmula única que dice qué eventos ey fluentes f se hacen verdaderos ha sido reemplazada por un conjunto de fórmulas más pequeñas, cada una de las cuales dice el efecto de un evento en un fluido.

Sin embargo, estas fórmulas no son equivalentes a la fórmula anterior. De hecho, solo especifican condiciones suficientes para ser verdaderas, lo que debe completarse con el hecho de que Iniciados es falso en todos los demás casos. Este hecho puede formalizarse simplemente circunscribiendo el predicado Iniciados en la fórmula anterior. Es importante notar que esta circunscripción se hace solo en las fórmulas que especifican Iniciados y no en los axiomas independientes del dominio. El predicado Terminates se puede especificar de la misma forma que Initiates .

Se puede adoptar un enfoque similar para el predicado Happens . La evaluación de este predicado se puede aplicar mediante fórmulas que especifiquen no solo cuándo es verdadero y cuándo es falso:

La circunscripción puede simplificar esta especificación, ya que solo se pueden especificar las condiciones necesarias:

Circunscribiendo el predicado Sucede , este predicado será falso en todos los puntos en los que no se especifique explícitamente que sea verdadero. Esta circunscripción debe hacerse por separado de la circunscripción de las otras fórmulas. En otras palabras, si F es el conjunto de fórmulas del tipo , G es el conjunto de fórmulas y H son los axiomas independientes del dominio, la formulación correcta del dominio es:

El cálculo de eventos como programa lógico

El cálculo de eventos se formuló originalmente como un conjunto de cláusulas de Horn aumentadas con negación como falla y podría ejecutarse como un programa Prolog . De hecho, la circunscripción es una de las varias semánticas que se le puede dar a la negación como falla, y está estrechamente relacionada con la semántica de terminación (en la que "si" se interpreta como "si y sólo si" - ver programación lógica ).

Extensiones y aplicaciones

El documento de cálculo de eventos original de Kowalski y Sergot se centró en aplicaciones para actualizaciones de bases de datos y narrativas. Las extensiones del cálculo de eventos también pueden formalizar acciones no deterministas, acciones concurrentes, acciones con efectos retardados, cambios graduales, acciones con duración, cambio continuo y fluidos no inerciales.

Kave Eshghi mostró cómo el cálculo de eventos se puede utilizar para la planificación, utilizando la abducción para generar eventos hipotéticos en la programación lógica abductiva . Van Lambalgen y Hamm mostraron cómo el cálculo de eventos también se puede utilizar para dar una semántica algorítmica al tiempo y aspecto en lenguaje natural utilizando la programación lógica de restricciones .

Otras extensiones notables del cálculo de eventos incluyen variantes epistémicas probabilísticas basadas en redes lógicas de Markov y sus combinaciones.

Herramientas de razonamiento

Además de Prolog y sus variantes, también están disponibles otras herramientas para razonar utilizando el cálculo de eventos:

Ver también

Referencias

  1. ^ Kowalski, Robert; Sergot, Marek (1 de marzo de 1986). "Un cálculo de eventos basado en la lógica" . Computación de nueva generación . 4 (1): 67–95. doi : 10.1007 / BF03037383 . ISSN  1882-7055 . S2CID  7584513 .
  2. ^ Miller, Rob; Shanahan, Murray (2002), Kakas, Antonis C .; Sadri, Fariba (eds.), "Algunas formulaciones alternativas del cálculo de eventos" , Lógica computacional: Programación lógica y más allá: Ensayos en honor a Robert A. Kowalski Parte II , Lecture Notes in Computer Science, Berlín, Heidelberg: Springer, págs. . 452–490, doi : 10.1007 / 3-540-45632-5_17 , ISBN 978-3-540-45632-2, consultado el 5 de octubre de 2020
  3. Kowalski, Robert (1 de enero de 1992). "Actualizaciones de la base de datos en el cálculo de eventos" . El diario de programación lógica . 12 (1): 121-146. doi : 10.1016 / 0743-1066 (92) 90041-Z . ISSN  0743-1066 .
  4. ^ Eshghi, Kave (1988). "Planificación abductiva con cálculo de eventos" . Iclp / SLP : 562–579.
  5. ^ Lambalgen, Hamm (2005). El tratamiento adecuado de los eventos . Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC  212129657 .
  6. ^ Skarlatidis, Anastasios; Paliouras, Georgios; Artikis, Alexander; Vouros, George A. (17 de febrero de 2015). "Cálculo probabilístico de eventos para el reconocimiento de eventos" . Transacciones ACM en lógica computacional . 16 (2): 11: 1–11: 37. arXiv : 1207.3270 . doi : 10.1145 / 2699916 . ISSN  1529-3785 . S2CID  6389629 .
  7. ^ Skarlatidis, Anastasios; Artikis, Alexander; Filippou, Jason; Paliouras, Georgios (marzo de 2015). "Un cálculo de eventos de programación lógica probabilística" . Teoría y práctica de la programación lógica . 15 (2): 213–245. doi : 10.1017 / S1471068413000690 . ISSN  1471-0684 . S2CID  5701272 .
  8. ^ Ma, Jiefei; Miller, Rob; Morgenstern, Leora; Patkos, Theodore (28 de julio de 2014). "Un cálculo de eventos epistémicos para el razonamiento basado en ASP sobre el conocimiento del pasado, presente y futuro" . Serie EPiC en Informática . Silla fácil. 26 : 75–87. doi : 10.29007 / zswj .
  9. ^ D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (1 de octubre de 2020). "Razonamiento probabilístico sobre narrativas de acción epistémica" . Inteligencia artificial . 287 : 103352. doi : 10.1016 / j.artint.2020.103352 . ISSN  0004-3702 .

Otras lecturas