Calcul d'événement - Event calculus

Le calcul des événements est un langage logique pour représenter et raisonner sur les événements et leurs effets présenté pour la première fois par Robert Kowalski et Marek Sergot en 1986. Il a été étendu par Murray Shanahan et Rob Miller dans les années 1990. Semblable à d'autres langages pour raisonner sur le changement, le calcul d'événement représente les effets des actions sur les fluents . Cependant, les événements peuvent également être externes au système. Dans le calcul des événements, on peut spécifier la valeur des fluents à certains moments donnés, les événements qui ont lieu à des moments donnés et leurs effets.

Courants et événements

Dans le calcul des événements, les fluents sont réifiés . Cela signifie qu'ils ne sont pas formalisés au moyen de prédicats mais au moyen de fonctions . Un prédicat séparé HoldsAt est utilisé pour indiquer quels fluents sont valables à un moment donné. Par exemple, signifie que la boîte est sur la table à l'instant t ; dans cette formule, HoldsAt est un prédicat tandis que on est une fonction. ${\displaystyle {\mathit {HoldsAt}}(on(box,table),t)}$

Les événements sont également représentés sous forme de termes. Les effets des événements sont donnés à l'aide des prédicats Initie et Termine . En particulier, signifie que, si l'événement représenté par le terme e est exécuté à l'instant t , alors le fluent f sera vrai après t . Le prédicat Termine a une signification similaire, la seule différence étant que f sera faux après t . ${\displaystyle {\mathit {Initiés}}(e,f,t)}$

Axiomes indépendants du domaine

Comme d'autres langages de représentation d'actions, le calcul d'événements formalise l'évolution correcte du fluent via des formules indiquant la valeur de chaque fluent après qu'une action arbitraire a été effectuée. Le calcul d'événement résout le problème du cadre d'une manière similaire aux axiomes d'état successeur du calcul de situation : un fluent est vrai à l'instant t si et seulement s'il a été rendu vrai dans le passé et n'a pas été rendu faux dans le entre temps.

${\displaystyle {\mathit {HoldsAt}}(f,t)\leftarrow [{\mathit {Happens}}(e,t_{1})\wedge {\mathit {Initie}}(e,f,t_{1 })\coin (t_{1}<t)\coin \neg {\mathit {Coupe}}(t_{1},f,t)]}$

Cette formule signifie que le fluent représenté par le terme f est vrai à l'instant t si :

1. un événement e a eu lieu : ;${\displaystyle {\mathit {Happens}}(e,t_{1})}$
2. cela a eu lieu dans le passé : ;${\displaystyle {\mathit {t}}_{1}<t}$
3. cet événement a pour effet le fluent f : ;${\displaystyle {\mathit {Initiés}}(e,f,t_{1})}$
4. le fluent n'a pas été rendu faux entre-temps : ${\displaystyle {\mathit {Clippé}}(t_{1},f,t)}$

Une formule similaire est utilisée pour formaliser le cas inverse dans lequel un fluent est faux à un instant donné. D'autres formules sont également nécessaires pour formaliser correctement les fluents avant qu'ils n'aient été les effets d'un événement. Ces formules sont similaires à celles ci-dessus, mais sont remplacées par . ${\displaystyle {\mathit {Happens}}(e,t_{1})\wedge {\mathit {Initiates}}(e,f,t_{1})}$${\displaystyle {\mathit {HoldsAt}}(f,t_{1})}$

Le prédicat Clipped , indiquant qu'un fluent a été rendu faux pendant un intervalle, peut être axiomatisé, ou simplement pris comme un raccourci, comme suit :

${\displaystyle {\mathit {Clippé}}(t_{1},f,t_{2})\equiv \exists e,t[{\mathit {Happens}}(e,t)\wedge (t_{1} \leq t<t_{2})\wedge {\mathit {Termine}}(e,f,t)]}$

Axiomes dépendant du domaine

Les axiomes ci-dessus concernent la valeur des prédicats HoldsAt , Initiates et Terminates , mais ne spécifient pas quels fluents sont connus pour être vrais et quels événements rendent réellement les fluents vrais ou faux. Ceci est fait en utilisant un ensemble d'axiomes dépendant du domaine. Les valeurs connues des fluents sont exprimées sous forme de simples littéraux . Les effets des événements sont énoncés par des formules reliant les effets des événements à leurs conditions préalables. Par exemple, si l'événement open rend le fluent isopen vrai, mais seulement si haskey est actuellement vrai, la formule correspondante dans le calcul de l'événement est : ${\displaystyle {\mathit {HoldsAt}}(f,t)}$

${\displaystyle {\mathit {Initiés}}(e,f,t)\equiv [e=open\wedge f=isopen\wedge {\mathit {HoldsAt}}(haskey,t)]\vee \cdots }$

L'expression de droite de cette équivalence est composée d'une disjonction : pour chaque événement et fluence qui peut être rendu vrai par l'événement, il y a une disjonction disant que e est en fait cet événement, que f est en fait cette fluence, et que le la condition préalable de l'événement est remplie.

La formule ci-dessus spécifie la valeur de vérité de pour chaque événement possible et fluide. En conséquence, tous les effets de tous les événements doivent être combinés dans une seule formule. C'est un problème, car l'ajout d'un nouvel événement nécessite de modifier une formule existante plutôt que d'en ajouter de nouvelles. Ce problème peut être résolu par l'application de la circonscription à un ensemble de formules spécifiant chacune un effet d'un événement : ${\displaystyle {\mathit {Initiés}}(e,f,t)}$

${\displaystyle {\mathit {Initie}}(open,isopen,t)\leftarrow {\mathit {HoldsAt}}(haskey,t)}$

${\displaystyle {\mathit {Initie}}(break,isopen,t)\leftarrow {\mathit {HoldsAt}}(hashammer,t)}$

${\displaystyle {\mathit {Initie}}(break,breaké,t)\leftarrow {\mathit {HoldsAt}}(hashammer,t)}$

Ces formules sont plus simples que la formule ci-dessus, car chaque effet de chaque événement peut être spécifié séparément. La formule unique indiquant quels événements e et fluents f rendent vrais a été remplacée par un ensemble de formules plus petites, chacune indiquant l'effet d'un événement sur un fluent. ${\displaystyle {\mathit {Initiés}}(e,f,t)}$

Cependant, ces formules ne sont pas équivalentes à la formule ci-dessus. En effet, elles ne précisent que des conditions suffisantes pour être vraies, qui doivent être complétées par le fait qu'Initiés est fausse dans tous les autres cas. Ce fait peut être formalisé en circonscrivant simplement le prédicat Initié dans la formule ci-dessus. Il est important de noter que cette circonscription se fait uniquement sur les formules spécifiant les Initiés et non sur les axiomes indépendants du domaine. Le prédicat Terminas peut être spécifié de la même manière que Initiates . ${\displaystyle {\mathit {Initiés}}(e,f,t)}$

Une approche similaire peut être adoptée pour le prédicat Happens . L'évaluation de ce prédicat peut être imposée par des formules spécifiant non seulement quand il est vrai et quand il est faux :

${\displaystyle {\mathit {Happens}}(e,t)\equiv (e=open\wedge t=0)\vee (e=exit\wedge t=1)\vee \cdots }$

La circonscription peut simplifier cette spécification, car seules les conditions nécessaires peuvent être spécifiées :

${\displaystyle {\mathit {Happens}}(open,0)}$

${\displaystyle {\mathit {Happens}}(exit,1)}$

En circonscrivant le prédicat Happens , ce prédicat sera faux à tous les points où il n'est pas explicitement spécifié comme étant vrai. Cette circonscription doit se faire séparément de la circonscription des autres formules. En d'autres termes, si F est l'ensemble des formules du genre , G est l'ensemble des formules et H sont les axiomes indépendants du domaine, la formulation correcte du domaine est : ${\displaystyle {\mathit {Initiés}}(e,f,t)\leftarrow \cdots }$${\displaystyle {\mathit {Happens}}(e,t)}$

${\displaystyle {\mathit {Circ}}(F ;{\mathit {Initie}},{\mathit {Termine}})\wedge Circ(G ; se produit)\wedge H}$

Le calcul des événements en tant que programme logique

Le calcul d'événement a été initialement formulé comme un ensemble de clauses Horn augmentées d'une négation en tant qu'échec et pouvait être exécuté comme un programme Prolog . En fait, la circonscription est l'une des nombreuses sémantiques qui peuvent être attribuées à la négation comme un échec, et est étroitement liée à la sémantique d'achèvement (dans laquelle "si" est interprété comme "si et seulement si" - voir programmation logique ).

Extensions et applications

L'article original sur le calcul des événements de Kowalski et Sergot se concentrait sur les applications aux mises à jour de bases de données et aux récits. Les extensions du calcul des événements peuvent également formaliser des actions non déterministes, des actions concurrentes, des actions à effets retardés, des changements graduels, des actions avec durée, des changements continus et des fluents non inertiels.

Kave Eshghi a montré comment le calcul des événements peut être utilisé pour la planification, en utilisant l' abduction pour générer des événements hypothétiques dans la programmation logique abductive . Van Lambalgen et Hamm ont montré comment le calcul d'événements peut également être utilisé pour donner une sémantique algorithmique au temps et à l'aspect en langage naturel en utilisant la programmation logique par contraintes .

D'autres extensions notables du calcul des événements incluent les variantes épistémiques probabilistes , basées sur les réseaux logiques de Markov et leurs combinaisons.

Outils de raisonnement

En plus de Prolog et de ses variantes, plusieurs autres outils de raisonnement utilisant le calcul d'événements sont également disponibles :

• Planificateurs de calculs d'événements abductifs
• Raisonneur de calcul d'événement discret
• Programmation d'ensembles de réponses au calcul d'événements
• Calcul d'événement réactif
• Calcul d'événement d'exécution (RTEC)

Voir également

• Logique du premier ordre
• Problème de cadre
• Calcul de situation

Les références

Lectures complémentaires

• Brandano, S. (2001) " The Event Calculus Assessed ", Symposium IEEE TIME : 7-12.
• R. Kowalski et F. Sadri (1995) " Variantes du calcul des événements ", ICLP : 67-81.
• Mueller, Erik T. (2015). Raisonnement de bon sens : une approche basée sur le calcul des événements (2e éd.) . Waltham, Massachusetts : Morgan Kaufmann/Elsevier. ISBN  978-0128014165 . (Guide d'utilisation du calcul d'événement)
• Shanahan, M. (1997) Résoudre le problème du cadre: Une enquête mathématique sur la loi d'inertie du sens commun . Presse MIT.
• Shanahan, M. (1999) " The Event Calculus Explained " Springer Verlag, LNAI (1600): 409-30.