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 cambian el estado de algún 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 fluidos:

Un fluido se mantiene en un momento
si es iniciado por un evento que ocurre en un momento anterior
y no termina por ningún evento que suceda mientras tanto. ^{[ cita necesaria ]}

El cálculo de eventos difiere de la mayoría de los otros enfoques para razonar sobre el cambio cosificando el tiempo, asociando eventos con el momento en que ocurren y asociando flujos con los momentos en que se llevan a cabo.

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 desarrollado 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 ampliado por Murray Shanahan y Rob Miller en la década de 1990 ^[4] y reformulado 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, cambios continuos y flujos no inerciales.

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

Fluidos y eventos

En el caso del cálculo, los fluidos están cosificados . Esto significa que los fluidos están representados por términos . Por ejemplo, expresa que está 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 son cosificados y representados por términos. Por ejemplo, expresa que 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 lo 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 el entonces se vuelve verdadero después del . ${\displaystyle {\mathit {event}}}$ ${\displaystyle {\mathit {time}}}$ ${\displaystyle {\mathit {fluent}}}$ ${\displaystyle {\mathit {time}}}$

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

Axioma independiente del dominio

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

Hay 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 axioma único e 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 evento y un tiempo tal que ${\displaystyle E2}$ ${\displaystyle T}$

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

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

${\displaystyle T1}$es antes 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 programa lógico , en la lógica de cláusulas de Horn con negación como fracaso . ^[1] De hecho, la circunscripción es una de las varias semánticas que se le pueden dar a la negación como fracaso, ^[9] y está estrechamente relacionada con la semántica de compleción 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 discretamente mediante números naturales o continuamente mediante números reales no negativos. Sin embargo, los tiempos también se pueden ordenar parcialmente. ${\displaystyle <}$ ${\displaystyle \leq }$

Axiomas dependientes del dominio

Para aplicar el cálculo de eventos en un dominio de problema 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 fluido , que expresa que el objeto está en el lugar y termina el fluido , 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 mantiene en un estado inicial, digamos en el momento 1, entonces con el axioma central simple anterior necesitamos un evento, digamos , que inicie en cualquier momento: ${\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 mundial 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 momento 1 y moviendo el bloque verde al bloque rojo en el momento 3, poniendo el semáforo al revés:

${\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 prólogo

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

HoldsAt ( Fluent ,  Time2 )  : -  antes ( Time1 ,  Time2 ),  sucedeAt ( Event ,  Time1 ),  inicia ( Event ,  Fluent ,  Time1 ),  no ( recortado ( Fluent ,  Time1 ,  Time2 )). recortado ( Fluent ,  Time1 ,  Time2 )  : -  termina ( Evento ,  Fluent ,  Time ),  sucede en ( Event ,  Time ),  antes ( Time1 ,  Time ),  antes ( Time ,  Time2 ).inicia ( inicializar ( fluido ),  fluido ,  tiempo ). inicia ( mover ( Objeto ,  Lugar ),  en ( Objeto ,  Lugar ),  Tiempo ). termina ( mover ( Objeto ,  Lugar ),  en ( Objeto ,  Lugar1 ),  Tiempo ).sucede en ( inicializar ( en ( green_block ,  tabla )),  0 ). sucede en ( inicializar ( en ( bloque_rojo ,  bloque_verde )),  0 ). sucede en ( mover ( red_block ,  tabla ),  1 ). sucede en ( mover ( bloque_verde ,  bloque_rojo ),  3 ).

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

• El axioma central se ha reescrito utilizando un predicado auxiliar. Esta reescritura permite la eliminación de cuantificadores existenciales, conforme a la convención Prolog de que todas las variables se cuantifican 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 ha sido eliminada de la condición correspondiente. Esto construye una suposición simplificadora de que los eventos no inician y terminan simultáneamente el mismo fluido. Como consecuencia, se ha simplificado la definición del predicado 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é se cumple cuando? en orden temporal:before(Time1, Time2),

?-  mantiene At ( Fluido ,  Tiempo ). Fluent  =  activado ( bloque_verde , tabla ),  Tiempo  =  1. Fluent  =  activado ( bloque_rojo , bloque_verde ),  Tiempo  =  1. Fluent  =  activado ( bloque_verde , tabla ),  Tiempo  =  2. Fluent  =  activado ( bloque_rojo , tabla ),  Tiempo  =  2. Fluent  =  activado ( bloque_verde , tabla ),  Tiempo  =  3. Fluent  =  activado ( bloque_rojo , tabla ),  Tiempo  =  3. Fluent  =  activado ( bloque_rojo , tabla ),  Tiempo  =  4. Fluent  =  activado ( bloque_verde , bloque_rojo ),  Tiempo  =  4. Fluido  =  activado ( bloque_rojo , tabla ),  Tiempo  =  5. Fluido  =  activado ( bloque_verde , bloque_rojo ),  Tiempo  =  5.

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

punto de tiempo ( 1 ). punto de tiempo ( 2 ). punto de tiempo ( 3 ). Punto de tiempo ( 4 ). Punto de tiempo ( 5 ).fluido ( en ( red_block ,  green_block )). fluido ( en ( bloque_verde ,  bloque_rojo )). fluido ( en ( red_block ,  tabla )). fluido ( en ( green_block ,  tabla )).?-  timePoint ( T ),  fluido ( F ),  no ( holdsAt ( F ,  T )). F  =  encendido ( bloque_verde , bloque_rojo ),  T  =  1. F  =  encendido ( bloque_rojo , tabla ),  T  =  1. F  =  encendido ( bloque_rojo , bloque_verde ),  T  =  2. F  =  encendido ( bloque_verde , bloque_rojo ),  T  =  2. F  =  activado ( bloque_rojo , bloque_verde ),  T  =  3. F  =  activado ( bloque_verde , bloque_rojo ),  T  =  3. F  =  activado ( bloque_rojo , bloque_verde ),  T  =  4. F  =  activado ( bloque_verde , tabla ),  T  =  4. F  =  activado ( bloque_rojo , bloque_verde ),  T  =  5. F  =  activado ( 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
• Programación del conjunto de respuestas del cálculo de eventos
• Cálculo de eventos reactivos
• Cálculo de eventos en tiempo de ejecución (RTEC)
• Cálculo de eventos probabilísticos epistémicos (EPEC) ^[11]

Extensiones

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]

Ver también

• Lógica de primer orden
• Problema de marco
• Cálculo de situació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. Kowalski, Robert (1 de enero de 1992). "Actualizaciones de bases de datos en el cálculo de eventos". La revista de programación lógica . 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. Molinero, Rob; Shanahan, Murray (2002), Kakás, 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 , Apuntes de conferencias sobre informática, Berlín, Heidelberg: Springer, págs. 452–490, dirección : 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: Pub Blackwell. 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. Prensa de la Universidad de Edimburgo, 1969.
7. R. Reiter (1991). El problema marco en el cálculo de situaciones: una solución simple (a veces) y un resultado completo para la regresión objetivo. 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. Profesional de prensa académica, Inc. 1991.
8. Shanahan, M. (1997) Resolución del problema del marco: una investigación matemática de la ley de inercia del sentido común . Prensa del MIT.
9. Gelfond, M.; Przymusinska, H.; Przymusinski, T. (1989). "Sobre la relación entre circunscripción y 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 EE. UU. 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, Lucas; Molinero, Rob (2024). "Una implementación basada en programación de conjuntos de respuestas del cálculo de eventos probabilísticos 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, Alejandro; Vouros, George A. (17 de febrero de 2015). "Cálculo de eventos probabilísticos para el reconocimiento de eventos". Transacciones ACM sobre lógica computacional . 16 (2): 11:1–11:37. arXiv : 1207.3270 . doi :10.1145/2699916. ISSN  1529-3785. S2CID  6389629.
13. Skarlatidis, Anastasios; Artikis, Alejandro; 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. Mamá, Jiefei; Molinero, 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 Computación . 26 . Sillón: 75–87. doi : 10.29007/zswj .
15. D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Lucas; Molinero, 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.

Otras lecturas

• 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). Razonamiento de sentido común: un enfoque basado en el cálculo de eventos (2ª ed.) . Waltham, MA: Morgan Kaufmann/Elsevier. ISBN 978-0128014165 . (Guía para utilizar el cálculo de eventos) 
• Shanahan, M. (1997) Resolviendo el problema del marco: una investigación matemática de la ley de inercia del sentido común . Prensa del MIT.
• Shanahan, M. (1999) "Explicación del cálculo de eventos" 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 ]).