Cálculo de eventos

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. Aborda tanto los eventos de acción, realizados por agentes, como los eventos externos, que escapan al 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 dan en ese momento. Los eventos inician y terminan los fluentes:

Un flujo se mantiene en un momento dado si se inicia por un evento que ocurre en un momento anterior y no se termina por ningún evento que ocurra mientras tanto.

El cálculo de eventos se diferencia de la mayoría de los demás enfoques para razonar sobre el cambio al reificar el tiempo, asociando los eventos con el momento en que ocurren y asociando los flujos con los momentos en que se mantienen.

La versión original del cálculo de eventos, introducida por Robert Kowalski y Marek Sergot en 1986, ^{[ 1 ]} se formuló como un programa lógico y se desarrolló para representar narrativas y actualizaciones de bases de datos. ^{[ 2 ]} Kave Eshghi mostró cómo usar el cálculo de eventos para la planificación, ^{[ 3 ]} mediante 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 posteriores extensiones se han utilizado para formalizar acciones no deterministas, acciones concurrentes, acciones con efectos retardados, cambios graduales, acciones con duración, cambio continuo y fluentes no inerciales.

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 ]}

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

${\displaystyle {\mathit {holdsAt}}(fluent,time)}$expresa que el${\displaystyle {\mathit {fluido}}}$se mantiene en el${\displaystyle {\mathit {tiempo.}}}$

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

${\displaystyle {\mathit {sucedeEn}}(evento,tiempo)}$expresa que el${\displaystyle {\mathit {evento}}}$sucede en el${\displaystyle {\mathit {tiempo.}}}$

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

${\displaystyle {\mathit {inicia}}(evento,fluido,tiempo)}$expresa que si el${\displaystyle {\mathit {evento}}}$sucede en el${\displaystyle {\mathit {tiempo}}}$entonces el${\displaystyle {\mathit {fluido}}}$se convierte en realidad después de la${\displaystyle {\mathit {tiempo}}}$.

${\displaystyle {\mathit {termina}}(evento,fluido,tiempo)}$expresa que si el${\displaystyle {\mathit {evento}}}$sucede en el${\displaystyle {\mathit {tiempo}}}$entonces el${\displaystyle {\mathit {fluido}}}$deja de ser cierto después de la${\displaystyle {\mathit {tiempo}}}$.

El cálculo de eventos se desarrolló 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 puede expresarse 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 afirma que

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

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

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

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

No es el caso que exista un evento${\displaystyle E2}$y un tiempo${\displaystyle T}$de tal manera que

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

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

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

${\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áusulas de Horn con la 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 only if ).

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

El cálculo de eventos es compatible con diferentes definiciones de los predicados temporales.${\displaystyle <}$y${\displaystyle \leq }$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 estar parcialmente ordenados.

Para aplicar el cálculo de eventos en un dominio de problemas particular, es necesario definir el${\displaystyle inicia}$y${\displaystyle termina}$predicados para ese dominio. Por ejemplo, en el dominio del mundo de los bloques , un evento${\displaystyle mover(Objeto,Lugar)}$El acto de mover un objeto a un lugar inicia la fluidez${\displaystyle on(Object,Place)}$, que expresa que el objeto está en el lugar y termina la fluidez${\displaystyle on(Object,Place1)}$, lo que indica que el objeto se encuentra en un lugar diferente:

${\displaystyle {\mathit {inicia}}(mover(Objeto,Lugar),en(Objeto,Lugar),Tiempo).}$

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

Si queremos representar el hecho de que un${\displaystyle Fluent}$se mantiene en un estado inicial, digamos en el tiempo 1, entonces con el axioma central simple anterior necesitamos un evento, digamos${\displaystyle inicializar (fluido)}$, que inicia el${\displaystyle Fluent}$en cualquier momento:

${\displaystyle {\mathit {inicia}}(inicializar(Fluido),Fluido,Tiempo).}$

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

Por ejemplo, en el dominio del mundo de los 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)}$

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 escenario del mundo de bloques anterior se puede implementar (con pequeñas modificaciones) mediante el programa:

holdsAt ( Fluent , Time2 ) :- before ( Time1 , Time2 ), happensAt ( Event , Time1 ), initiates ( Event , Fluent , Time1 ), not ( clipped ( Fluent , Time1 , Time2 )).recortado ( Fluent , Time1 , Time2 ) :- termina ( Event , Fluent , Time ), sucedeEn ( 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 ).happenAt ( initialise ( on ( green_block , table )), 0 ). happenAt ( initialise ( on ( red_block , green_block )), 0 ). happenAt ( move ( red_block , table ), 1 ). happenAt ( move ( green_block , red_block ), 3 ).

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

• El axioma central ha sido reescrito, utilizando un predicado auxiliar. Esta reescritura permite la eliminación de cuantificadores existenciales, conforme a 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 del axioma o axiomas centrales para generar respuestas a las consultas en orden temporal.
• La igualdad en la condición${\displaystyle T1\leq T}$se ha eliminado de la condición correspondiente Esto incorpora una suposición simplificadora de que los eventos no inician y terminan simultáneamente el mismo flujo. Como consecuencia, la definición de la before(Time1,Time).${\displaystyle terminates}$El predicado se ha simplificado eliminando la condición de que${\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 cuándo? en orden temporal:before(Time1,Time2),

?- holdsAt ( Fluent , Time ). Fluent = on ( green_block , table ), Time = 1. Fluent = on ( red_block , green_block ), Time = 1. Fluent = on ( green_block , table ), Time = 2. Fluent = on ( red_block , table ), Time = 2. Fluent = on ( green_block , table ), Time = 3. Fluent = on ( red_block , table ), Time = 3. Fluent = on ( red_block , table ), Time = 4. Fluent = on ( green_block , red_block ), Time = 4. Fluent = on ( red_block , table ), Time = 5. Fluent = on ( green_block , red_block ), Time = 5.

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

timePoint ( 1 ). timePoint ( 2 ). timePoint ( 3 ). timePoint ( 4 ). timePoint ( 5 ).fluent ( en ( bloque_rojo , bloque_verde )). fluent ( en ( bloque_verde , bloque_rojo )). fluent ( en ( bloque_rojo , tabla )). fluent ( en ( bloque_verde , tabla )).?- timePoint ( T ), fluent ( F ), not ( holdsAt ( F , T )). F = on ( green_block , red_block ), T = 1. F = on ( red_block , table ), T = 1. F = on ( red_block , green_block ), T = 2. F = on ( green_block , red_block ), T = 2. F = on ( red_block , green_block ), T = 3. F = on ( green_block , red_block ), T = 3. F = on ( red_block , green_block ), T = 4. F = on ( green_block , table ), T = 4. F = on ( red_block , green_block ), T = 5. F = on ( green_block , table ), T = 5.

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

• Planificadores de cálculo de eventos abductivos
• Razonador de cálculo de eventos discretos
• Programación de conjuntos de respuestas de 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 ]}

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

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

• Brandano, S. (2001) " Evaluación del cálculo de eventos ," 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 el uso del 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 . MIT Press.
• Shanahan, M. (1999) " El cálculo de eventos explicado " Springer Verlag, LNAI (1600): 409-30.