Cálculo de eventos

Lenguaje para razonar y representar acontecimientos

El cálculo de eventos es una teoría lógica para representar y razonar sobre eventos y sobre la forma en que estos modifican el estado de un mundo real o artificial. Se ocupa tanto de eventos de acción, que son realizados por agentes, como de eventos externos, que están fuera del control de cualquier agente.

El cálculo de eventos representa el estado del mundo en cualquier momento mediante el conjunto de todos los hechos (llamados fluentes ) que se cumplen en ese momento. Los eventos inician y terminan los fluentes:

Un fluido se mantiene en un momento dado
si es iniciado por un evento que sucede en un momento anterior
y no es terminado por ningún evento que sucede mientras tanto. ^{[ cita requerida ]}

El cálculo de eventos se diferencia de la mayoría de los otros enfoques para razonar sobre el cambio al solidificar el tiempo, asociando los eventos con el momento en el que suceden y asociando los fluidos con los momentos en los que se mantienen.

La versión original del cálculo de eventos, introducida por Robert Kowalski y Marek Sergot en 1986, ^[1] fue formulada como un programa lógico y desarrollada para representar narrativas y actualizaciones de bases de datos. ^[2] Kave Eshghi mostró cómo utilizar el cálculo de eventos para la planificación, ^[3] utilizando la abducción para generar acciones hipotéticas para lograr un estado de cosas deseado.

Fue ampliada por Murray Shanahan y Rob Miller en la década de 1990 ^[4] y reformulada en lógica de primer orden con circunscripción . Estas y extensiones posteriores se han utilizado para formalizar acciones no deterministas, acciones concurrentes, acciones con efectos retardados, cambios graduales, acciones con duración, cambio continuo y fluidez no inercial.

Van Lambalgen y Hamm demostraron cómo una formulación del cálculo de eventos como un programa de lógica de restricciones puede usarse para dar una semántica algorítmica al tiempo y al aspecto en el lenguaje natural. ^[5]

Fluidos y eventos

En el cálculo de eventos, los fluidos se reifican . Esto significa que los fluidos se representan mediante términos . Por ejemplo, expresa que el está en el en el momento . Aquí hay un predicado, mientras que es un término. En general, la fórmula atómica ${\displaystyle {\mathit {holdsAt}}(on(green\_block,table),1)}$ ${\displaystyle {\mathit {green\_block}}}$ ${\displaystyle {\mathit {table}}}$ ${\displaystyle 1}$ ${\displaystyle {\mathit {holdsAt}}}$ ${\displaystyle {\mathit {on(green\_block,table)}}}$

${\displaystyle {\mathit {holdsAt}}(fluent,time)}$expresa que las bodegas en el ${\displaystyle {\mathit {fluent}}}$ ${\displaystyle {\mathit {time.}}}$

Los acontecimientos también se materializan y se representan mediante términos. Por ejemplo, expresa que el se traslada al momento . En general: ${\displaystyle {\mathit {happensAt}}(move(green\_block,red\_block),3)}$ ${\displaystyle {\mathit {green\_block}}}$ ${\displaystyle {\mathit {red\_block)}}}$ ${\displaystyle 3}$

${\displaystyle {\mathit {happensAt}}(event,time)}$expresa que sucede en el ${\displaystyle {\mathit {event}}}$ ${\displaystyle {\mathit {time.}}}$

Las relaciones entre los eventos y los fluidos que inician y terminan también están representadas por fórmulas atómicas:

${\displaystyle {\mathit {initiates}}(event,fluent,time)}$expresa que si sucede en entonces se vuelve verdadero después de . ${\displaystyle {\mathit {event}}}$ ${\displaystyle {\mathit {time}}}$ ${\displaystyle {\mathit {fluent}}}$ ${\displaystyle {\mathit {time}}}$

${\displaystyle {\mathit {terminates}}(event,fluent,time)}$expresa que si el sucede en el entonces el deja de ser verdadero después del . ${\displaystyle {\mathit {event}}}$ ${\displaystyle {\mathit {time}}}$ ${\displaystyle {\mathit {fluent}}}$ ${\displaystyle {\mathit {time}}}$

Axioma independiente del dominio

El cálculo de eventos fue desarrollado en parte como una alternativa al cálculo de situaciones , ^{[6] [7]} como una solución al problema del marco , de representar y razonar sobre la forma en que las acciones y otros eventos cambian el estado de algún mundo.

Existen muchas variantes del cálculo de eventos, pero el axioma central de una de las variantes más simples y útiles se puede expresar como un único axioma independiente del dominio:

${\displaystyle {\mathit {holdsAt}}(F,T2)\leftarrow }$

${\displaystyle [{\mathit {happensAt}}(E1,T1)\wedge {\mathit {initiates}}(E1,F,T1)\wedge (T1<T2)\wedge }$

${\displaystyle \neg \exists E2,T[{\mathit {happensAt}}(E2,T)\wedge {\mathit {terminates}}(E2,F,T)\wedge (T1\leq T<T2)]}$

El axioma establece que

Un fluido se sostiene a la vez si ${\displaystyle F}$ ${\displaystyle T2}$

Un evento sucede en un momento y ${\displaystyle E1}$ ${\displaystyle T1}$

${\displaystyle E1}$inicia en y ${\displaystyle F}$ ${\displaystyle T1}$

${\displaystyle T1}$es antes y ${\displaystyle T2}$

No es el caso que exista un acontecimiento y un tiempo tales que ${\displaystyle E2}$ ${\displaystyle T}$

${\displaystyle E2}$sucede en y ${\displaystyle T}$

${\displaystyle E2}$termina en y ${\displaystyle F}$ ${\displaystyle T}$

${\displaystyle T1}$es anterior o al mismo tiempo que y ${\displaystyle T}$

${\displaystyle T}$es antes . ${\displaystyle T2}$

El cálculo de eventos resuelve el problema del marco interpretando este axioma en una lógica no monótona , como la lógica de primer orden con circunscripción ^[8] o, como un programa lógico , en la lógica de cláusula de Horn con negación como fallo . ^[1] De hecho, la circunscripción es una de las varias semánticas que se pueden dar a la negación como fallo, ^[9] y está estrechamente relacionada con la semántica de completitud para programas lógicos ^[10] (que interpreta if como if y solo if ).

El axioma central del cálculo de eventos define el predicado en términos de los predicados , , y . Para aplicar el cálculo de eventos a un problema particular, también es necesario definir estos otros predicados. ${\displaystyle holdsAt}$ ${\displaystyle happensAt}$ ${\displaystyle initiates}$ ${\displaystyle terminates}$ ${\displaystyle <}$ ${\displaystyle \leq }$

El cálculo de eventos es compatible con diferentes definiciones de los predicados temporales y . En la mayoría de las aplicaciones, los tiempos se representan de forma discreta, mediante números naturales, o de forma continua, mediante números reales no negativos. Sin embargo, los tiempos también pueden ordenarse parcialmente. ${\displaystyle <}$ ${\displaystyle \leq }$

Axiomas dependientes del dominio

Para aplicar el cálculo de eventos en un dominio de problemas en particular, es necesario definir los predicados y para ese dominio. Por ejemplo, en el dominio del mundo de bloques , un evento de mover un objeto a un lugar inicia el fluent , que expresa que el objeto está en el lugar y termina el fluent , que expresa que el objeto está en un lugar diferente: ${\displaystyle initiates}$ ${\displaystyle terminates}$ ${\displaystyle move(Object,Place)}$ ${\displaystyle on(Object,Place)}$ ${\displaystyle on(Object,Place1)}$

${\displaystyle {\mathit {initiates}}(move(Object,Place),on(Object,Place),Time).}$

${\displaystyle {\mathit {terminates}}(move(Object,Place),on(Object,Place1),Time)\leftarrow different(Place1,Place).}$

Si queremos representar el hecho de que a se cumple en un estado inicial, digamos en el tiempo 1, entonces con el axioma básico simple anterior necesitamos un evento, digamos , que inicie en cualquier tiempo: ${\displaystyle Fluent}$ ${\displaystyle initialise(Fluent)}$ ${\displaystyle Fluent}$

${\displaystyle {\mathit {initiates}}(initialise(Fluent),Fluent,Time).}$

Axiomas dependientes del problema

Para aplicar el cálculo de eventos, dadas las definiciones de los predicados , , y , es necesario definir los predicados que describen el contexto específico del problema. ${\displaystyle holdsAt}$ ${\displaystyle initiates}$ ${\displaystyle terminates}$ ${\displaystyle <}$ ${\displaystyle \leq }$ ${\displaystyle happensAt}$

Por ejemplo, en el dominio del mundo de bloques, podríamos querer describir un estado inicial en el que hay dos bloques, un bloque rojo sobre un bloque verde sobre una mesa, como un semáforo de juguete, seguido de mover el bloque rojo a la mesa en el tiempo 1 y mover el bloque verde sobre el bloque rojo en el tiempo 3, poniendo el semáforo boca abajo:

${\displaystyle {\mathit {happensAt}}(initialise(on(red\_block,green\_block),0)}$

${\displaystyle {\mathit {happensAt}}(initialise(on(green\_block,table),0)}$

${\displaystyle {\mathit {happensAt}}(move(red\_block,table),1)}$

${\displaystyle {\mathit {happensAt}}(move(green\_block,red\_block),3)}$

Una implementación de Prolog

El cálculo de eventos tiene una implementación natural en Prolog puro (sin ninguna característica que no tenga una interpretación lógica). Por ejemplo, el escenario del mundo de bloques anterior se puede implementar (con modificaciones menores) mediante el programa:

sostieneEn ( Fluido ,  Hora2 )  :-  antes ( Hora1 ,  Hora2 ),  sucedeEn ( Evento ,  Hora1 ),  inicia ( Evento ,  Fluido ,  Hora1 ),  no ( recortado ( Fluido ,  Hora1 ,  Hora2 )). recortado ( Fluido ,  Tiempo1 ,  Tiempo2 )  :-  termina ( Evento ,  Fluido ,  Tiempo ),  sucedeEn ( Evento ,  Tiempo ),  antes ( Tiempo1 ,  Tiempo ),  antes ( Tiempo ,  Tiempo2 ).inicia ( inicializar ( Fluent ),  Fluent ,  Tiempo ). inicia ( mover ( Objeto ,  Lugar ),  en ( Objeto ,  Lugar ),  Tiempo ). termina ( mover ( Objeto ,  Lugar ),  en ( Objeto ,  Lugar1 ),  Tiempo ).sucedeEn ( inicializar ( en ( bloque_verde ,  tabla )),  0 ). sucedeEn ( inicializar ( en ( bloque_rojo ,  tabla )),  0 ). sucedeEn ( mover ( bloque_rojo ,  tabla ),  1 ). sucedeEn ( mover ( bloque_verde ,  tabla ),  3 ).

El programa Prolog se diferencia de la formalización anterior en los siguientes aspectos:

• Se ha reescrito el axioma central, utilizando un predicado auxiliar. Esta reescritura permite la eliminación de cuantificadores existenciales, de acuerdo con la convención de Prolog de que todas las variables están cuantificadas universalmente.clipped(Fact, Time1, Time2).
• Se ha cambiado el orden de las condiciones en el cuerpo de los axiomas centrales para generar respuestas a las consultas en orden temporal.
• La igualdad en la condición se ha eliminado de la condición correspondiente. Esto supone una suposición simplificadora de que los eventos no inician y terminan simultáneamente el mismo fluido. Como consecuencia, la definición del predicado se ha simplificado eliminando la condición de que . ${\displaystyle T1\leq T}$before(Time1, Time). ${\displaystyle terminates}$ ${\displaystyle different(Place1,Place)}$

Dada una definición apropiada ^{[nota 1]} del predicado, el programa Prolog genera todas las respuestas a la consulta ¿qué sucede y cuándo? en orden temporal:before(Time1, Time2),

?-  sostieneEn ( Fluido ,  Tiempo ). Fluido  =  en ( bloque_verde , mesa ),  Tiempo  =  1. Fluido  =  en ( bloque_rojo , bloque_verde ),  Tiempo  =  1. Fluido  =  en ( bloque_verde , mesa ),  Tiempo  =  2. Fluido  =  en ( bloque_rojo , mesa ),  Tiempo  =  2. Fluido  =  en ( bloque_verde , mesa ),  Tiempo  =  3. Fluido  =  en ( bloque_rojo , mesa ),  Tiempo  =  3. Fluido  =  en ( bloque_rojo , mesa ),  Tiempo  =  4. Fluido  =  en ( bloque_verde , bloque_rojo ),  Tiempo  =  4. Fluido  =  en ( bloque_rojo , mesa ),  Tiempo  =  5. Fluido  =  en ( bloque_verde , bloque_rojo ),  Tiempo  =  5.

El programa también puede responder a consultas negativas, como por ejemplo, ¿qué fluidos no se cumplen en qué momentos? Sin embargo, para que funcione correctamente, todas las variables en condiciones negativas deben instanciarse primero en términos que no contengan variables. Por ejemplo:

tiempoPunto ( 1 ). tiempoPunto ( 2 ). tiempoPunto ( 3 ). tiempoPunto ( 4 ). tiempoPunto ( 5 ).fluido ( en ( bloque_rojo ,  bloque_verde )). fluido ( en ( bloque_verde ,  bloque_rojo )). fluido ( en ( bloque_rojo ,  tabla )). fluido ( en ( bloque_verde ,  tabla )).?-  timePoint ( T ),  fluent ( F ),  not ( holdsAt ( F ,  T )). F  =  en ( bloque_verde , bloque_rojo ),  T  =  1. F  =  en ( bloque_rojo , tabla ),  T  =  1. F  =  en ( bloque_rojo , bloque_verde ),  T  =  2. F  =  en ( bloque_verde , bloque_rojo ),  T  =  2. F  =  en ( bloque_rojo , bloque_verde ),  T  =  3. F  =  en ( bloque_verde , bloque_rojo ),  T  =  3. F  =  en ( bloque_rojo , bloque_verde ),  T  =  4. F  =  en ( bloque_verde , tabla ),  T  =  4. F  =  en ( bloque_rojo , bloque_verde ),  T  =  5. F  =  en ( bloque_verde , tabla ),  T  =  5.

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:

• Planificadores de cálculo de eventos abductivos
• Razonador de cálculo de eventos discretos
• Conjunto de respuestas de cálculo de eventos Programación
• Cálculo de eventos reactivos
• Cálculo de eventos en tiempo de ejecución (RTEC)
• Cálculo probabilístico de eventos epistémicos (EPEC) ^[11]

Extensiones

Las extensiones notables del cálculo de eventos incluyen variantes basadas en redes lógicas de Markov ^[12] , probabilísticas ^[13] , epistémicas ^[14] y sus combinaciones. ^[15]

Véase también

• Lógica de primer orden
• Problema de marco
• Cálculo de situaciones

Referencias

1. Kowalski, Robert; Sergot, Marek (1986-03-01). "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. Kowalski, Robert (1 de enero de 1992). "Actualizaciones de bases de datos en el cálculo de eventos". The Journal of Logic Programming . 12 (1): 121–146. doi : 10.1016/0743-1066(92)90041-Z . ISSN  0743-1066.
3. Eshghi, Kave (1988). "Planificación abductiva con cálculo de eventos". Iclp/SLP : 562–579.
4. 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
5. Lambalgen, Hamm (2005). El tratamiento adecuado de los acontecimientos. Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7.OCLC 212129657  .
6. 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. Edinburgh University Press, 1969.
7. R. Reiter (1991). El problema del marco en el cálculo de situaciones: una solución simple (a veces) y un resultado de completitud 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.
8. Shanahan, M. (1997) Solución del problema del marco: una investigación matemática de la ley de inercia del sentido común . MIT Press.
9. Gelfond, M.; Przymusinska, H.; Przymusinski, T. (1989). "Sobre la relación entre la circunscripción y la negación como fracaso". Inteligencia artificial . 38 (1): 75–94. doi :10.1016/0004-3702(89)90068-4.
10. Clark, KL (1977). "La negación como fracaso". Lógica y bases de datos . Boston, MA: Springer US. págs. 293–322. doi :10.1007/978-1-4684-3384-5_11. ISBN . 978-1-4684-3386-9.
11. D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2024). "Una implementación basada en programación de conjuntos de respuestas del cálculo probabilístico de eventos epistémicos". Revista Internacional de Razonamiento Aproximado . 165 : 109101. doi :10.1016/j.ijar.2023.109101. ISSN  0888-613X.
12. 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". ACM Transactions on Computational Logic . 16 (2): 11:1–11:37. arXiv : 1207.3270 . doi :10.1145/2699916. ISSN  1529-3785. S2CID  6389629.
13. 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. arXiv : 1204.1851 . doi : 10.1017/S1471068413000690 . ISSN  1471-0684. S2CID  5701272.
14. 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, el presente y el futuro". Serie EPiC en Computación . 26 . EasyChair: 75–87. doi : 10.29007/zswj .
15. 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. S2CID  221521535.

Lectura adicional

• Brandano, S. (2001) "El cálculo de eventos evaluado", Simposio IEEE TIME : 7-12.
• R. Kowalski y F. Sadri (1995) "Variantes del cálculo de eventos", ICLP : 67-81.
• Mueller, Erik T. (2015). Commonsense Reasoning: An Event Calculus Based Approach (2.ª edición) . Waltham, MA: Morgan Kaufmann/Elsevier. ISBN 978-0128014165 . (Guía para utilizar el cálculo de eventos). 
• Shanahan, M. (1997) Solución del problema del marco: una investigación matemática de la ley de inercia del sentido común . MIT Press.
• Shanahan, M. (1999) "El cálculo de eventos explicado" Springer Verlag, LNAI (1600): 409-30.

Notas

1. Por ejemplo:

   antes ( Tiempo1 ,  Tiempo2 )  :-  línea de tiempo ( Eternidad ),  agregar ( Antes ,  [ Tiempo2  |  Después ],  Eternidad ),  miembro ( Tiempo1 ,  Antes ).línea de tiempo ([ 0 ,  1 ,  2 ,  3 ,  4 ,  5 ]).