Cálculo de evento - Event calculus

O cálculo de eventos é uma linguagem lógica para representar e raciocinar sobre eventos e seus efeitos, apresentada pela primeira vez por Robert Kowalski e Marek Sergot em 1986. Ela foi ampliada por Murray Shanahan e Rob Miller na década de 1990. Semelhante a outras linguagens para raciocinar sobre mudanças, o cálculo de eventos representa os efeitos das ações nos fluentes . No entanto, os eventos também podem ser externos ao sistema. No cálculo de eventos, pode-se especificar o valor dos fluentes em alguns pontos de tempo dados, os eventos que ocorrem em pontos de tempo dados e seus efeitos.

Fluentes e eventos

No cálculo do evento, os fluentes são reificados . Isso significa que eles não são formalizados por meio de predicados, mas por meio de funções . Um predicado separado $HoldsAt$ é usado para dizer quais fluentes são mantidos em um determinado momento. Por exemplo, significa que a caixa está na mesa no momento $t$ ; nesta fórmula, $HoldsAt$ é um predicado enquanto $on$ é uma função. ${\ displaystyle {\ mathit {HoldsAt}} (on (caixa, tabela), t)}$

Os eventos também são representados como termos. Os efeitos dos eventos são dados usando os predicados $Iniciados$ e $Terminados$ . Em particular, significa que, se o evento representado pelo termo $e$ for executado no tempo $t$ , então o $f$ fluente será verdadeiro após $t$ . O predicado $Terminates$ tem um significado semelhante, com a única diferença sendo que $f$ será falso após $t$ . ${\ displaystyle {\ mathit {Iniciados}} (e, f, t)}$

Axiomas independentes de domínio

Como outras linguagens de representação de ações, o cálculo de eventos formaliza a evolução correta do fluente por meio de fórmulas que informam o valor de cada fluente após uma ação arbitrária ter sido realizada. O cálculo de evento resolve o problema do referencial de uma maneira que é semelhante aos axiomas de estado sucessor do cálculo de situação : um fluente é verdadeiro no tempo $t$ se e somente se foi tornado verdadeiro no passado e não foi tornado falso no entretanto.

{\ displaystyle {\ mathit {HoldsAt}} (f, t) \ leftarrow [{\ mathit {Acontece}} (e, t_ {1}) \ wedge {\ mathit {Iniciados}} (e, f, t_ {1 }) \ wedge (t_ {1} <t) \ wedge \ neg {\ mathit {Cortado}} (t_ {1}, f, t)]}

Esta fórmula significa que o fluente representado pelo termo $f$ é verdadeiro no tempo $t$ se:

um evento $e$ ocorreu :; ${\ displaystyle {\ mathit {Acontece}} (e, t_ {1})}$
isso aconteceu no passado :; ${\ displaystyle {\ mathit {t}} _ {1} <t}$
este evento tem o $f$ fluente como efeito :; ${\ displaystyle {\ mathit {Iniciados}} (e, f, t_ {1})}$
o fluente não se tornou falso nesse ínterim: ${\ displaystyle {\ mathit {Cortado}} (t_ {1}, f, t)}$

Uma fórmula semelhante é usada para formalizar o caso oposto em que um fluente é falso em um determinado momento. Outras fórmulas também são necessárias para formalizar corretamente os fluentes antes que tenham sido efeitos de um evento. Essas fórmulas são semelhantes às anteriores, mas foram substituídas por . ${\ displaystyle {\ mathit {Acontece}} (e, t_ {1}) \ wedge {\ mathit {Iniciados}} (e, f, t_ {1})}$ ${\ displaystyle {\ mathit {HoldsAt}} (f, t_ {1})}$

O predicado $Clipped$ , afirmando que um fluente foi tornado falso durante um intervalo, pode ser axiomatizado, ou simplesmente tomado como uma abreviação, como segue:

{\ displaystyle {\ mathit {Cortado}} (t_ {1}, f, t_ {2}) \ equiv \ existe e, t [{\ mathit {Acontece}} (e, t) \ wedge (t_ {1} \ leq t <t_ {2}) \ wedge {\ mathit {Termina}} (e, f, t)]}

Axiomas dependentes de domínio

Os axiomas acima relacionam o valor dos predicados $HoldsAt$ , $Initiates$ e $Terminates$ , mas não especificam quais fluentes são conhecidos como verdadeiros e quais eventos realmente tornam os fluentes verdadeiros ou falsos. Isso é feito usando um conjunto de axiomas dependentes de domínio. Os valores conhecidos de fluentes são declarados como literais simples . Os efeitos dos eventos são declarados por fórmulas que relacionam os efeitos dos eventos com suas pré-condições. Por exemplo, se o evento $open$ torna o $isopen$ fluente verdadeiro, mas apenas se $haskey$ for atualmente verdadeiro, a fórmula correspondente no cálculo do evento é: ${\ displaystyle {\ mathit {HoldsAt}} (f, t)}$

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

A expressão do lado direito dessa equivalência é composta de uma disjunção: para cada evento e fluente que pode ser tornado verdadeiro pelo evento, há um disjuntor dizendo que $e$ é realmente aquele evento, que $f$ é realmente aquele fluente e que o condição prévia do evento é atendida.

A fórmula acima especifica o valor verdadeiro de para cada evento possível e fluente. Como resultado, todos os efeitos de todos os eventos devem ser combinados em uma única fórmula. Isso é um problema, porque a adição de um novo evento requer a modificação de uma fórmula existente em vez de adicionar novas. Este problema pode ser resolvido pela aplicação da circunscrição a um conjunto de fórmulas, cada uma especificando um efeito de um evento: ${\ displaystyle {\ mathit {Iniciados}} (e, f, t)}$

{\ displaystyle {\ mathit {Initiates}} (abrir, isopen, t) \ leftarrow {\ mathit {HoldsAt}} (haskey, t)}

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

{\ displaystyle {\ mathit {Initiates}} (break, broken, t) \ leftarrow {\ mathit {HoldsAt}} (hashammer, t)}

Essas fórmulas são mais simples do que a fórmula acima, porque cada efeito de cada evento pode ser especificado separadamente. A única fórmula que diz quais eventos $e$ e fluentes $f$ tornam verdadeiros foi substituída por um conjunto de fórmulas menores, cada uma relatando o efeito de um evento em um fluente. ${\ displaystyle {\ mathit {Iniciados}} (e, f, t)}$

No entanto, essas fórmulas não são equivalentes à fórmula acima. Na verdade, eles apenas especificam condições suficientes para serem verdadeiros, o que deve ser completado pelo fato de que os $Iniciados$ são falsos em todos os outros casos. Este fato pode ser formalizado simplesmente circunscrevendo o predicado $Iniciados$ na fórmula acima. É importante notar que esta circunscrição é feita apenas nas fórmulas que especificam $Iniciados$ e não nos axiomas independentes de domínio. O predicado $Terminates$ pode ser especificado da mesma maneira que $Initiates$ . ${\ displaystyle {\ mathit {Iniciados}} (e, f, t)}$

Uma abordagem semelhante pode ser adotada para o predicado $Happens$ . A avaliação desse predicado pode ser imposta por fórmulas que especificam não apenas quando é verdadeiro e quando é falso:

{\ displaystyle {\ mathit {Acontece}} (e, t) \ equiv (e = abrir \ cunha t = 0) \ vee (e = sair \ cunha t = 1) \ vee \ cdots}

A circunscrição pode simplificar esta especificação, pois apenas as condições necessárias podem ser especificadas:

{\ displaystyle {\ mathit {Happens}} (aberto, 0)}

{\ displaystyle {\ mathit {Happens}} (sair, 1)}

Circunscrevendo o predicado $Happens$ , esse predicado será falso em todos os pontos nos quais não seja explicitamente especificado como verdadeiro. Esta circunscrição deve ser feita separadamente da circunscrição das outras fórmulas. Em outras palavras, se $F$ é o conjunto de fórmulas do tipo , $G$ é o conjunto de fórmulas e $H$ são os axiomas independentes de domínio, a formulação correta do domínio é: ${\ displaystyle {\ mathit {Initiates}} (e, f, t) \ leftarrow \ cdots}$ ${\ displaystyle {\ mathit {Acontece}} (e, t)}$

{\ displaystyle {\ mathit {Circ}} (F; {\ mathit {Iniciados}}, {\ mathit {Termina}}) \ wedge Circ (G; Acontece) \ wedge H}

O cálculo do evento como um programa lógico

O cálculo de evento foi originalmente formulado como um conjunto de cláusulas de Horn acrescidas de negação como falha e poderia ser executado como um programa Prolog . Na verdade, a circunscrição é uma das várias semânticas que podem ser atribuídas à negação como falha e está intimamente relacionada à semântica de completamento (na qual "se" é interpretado como "se e somente se" - ver programação lógica ).

Extensões e aplicativos

O artigo original de cálculo de eventos de Kowalski e Sergot focava em aplicativos para atualizações e narrativas de banco de dados. Extensões do cálculo de eventos também podem formalizar ações não determinísticas, ações concorrentes, ações com efeitos retardados, mudanças graduais, ações com duração, mudança contínua e fluentes não inerciais.

Kave Eshghi mostrou como o cálculo de eventos pode ser usado para planejamento, usando abdução para gerar eventos hipotéticos na programação lógica abdutiva . Van Lambalgen e Hamm mostraram como o cálculo de evento também pode ser usado para fornecer uma semântica algorítmica para tempo e aspecto em linguagem natural usando programação de lógica de restrição .

Outras extensões notáveis do Cálculo de Eventos incluem as variantes baseadas em Redes Lógicas de Markov, probabilísticas , epistêmicas e suas combinações.

Ferramentas de raciocínio

Além do Prolog e suas variantes, várias outras ferramentas para raciocinar usando o cálculo de evento também estão disponíveis:

Veja também

Referências

^ Kowalski, Robert; Sergot, Marek (1986-03-01). "Um cálculo de eventos baseado em lógica" . Computação de nova geração . 4 (1): 67–95. doi : 10.1007 / BF03037383 . ISSN 1882-7055 . S2CID 7584513 .
^ Miller, Rob; Shanahan, Murray (2002), Kakas, Antonis C .; Sadri, Fariba (eds.), "Some Alternative Formulations of the Event Calculus" , Computational Logic: Logic Programming and Beyond: Essays in Honor of Robert A. Kowalski Parte II , Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp . 452–490, doi : 10.1007 / 3-540-45632-5_17 , ISBN 978-3-540-45632-2, recuperado em 2020-10-05
^ Kowalski, Robert (01-01-1992). “Atualizações da base de dados no cálculo do evento” . The Journal of Logic Programming . 12 (1): 121–146. doi : 10.1016 / 0743-1066 (92) 90041-Z . ISSN 0743-1066 .
^ Eshghi, Kave (1988). "Planejamento abdutivo com cálculo de eventos" . Iclp / SLP : 562–579.
^ Lambalgen, Hamm (2005). O tratamento adequado dos eventos . Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC 212129657 .
^ Skarlatidis, Anastasios; Paliouras, Georgios; Artikis, Alexander; Vouros, George A. (17/02/2015). "Cálculo Probabilístico de Eventos para Reconhecimento 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 .
^ Skarlatidis, Anastasios; Artikis, Alexander; Filippou, Jason; Paliouras, Georgios (março de 2015). "Um cálculo de evento de programação lógica probabilística" . Teoria e Prática de Programação Lógica . 15 (2): 213–245. doi : 10.1017 / S1471068413000690 . ISSN 1471-0684 . S2CID 5701272 .
^ Ma, Jiefei; Miller, Rob; Morgenstern, Leora; Patkos, Theodore (28/07/2014). "Um cálculo de evento epistêmico para raciocínio baseado em ASP sobre o conhecimento do passado, presente e futuro" . EPiC Series in Computing . Poltrona. 26 : 75–87. doi : 10.29007 / zswj .
^ D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2020-10-01). "Raciocínio probabilístico sobre narrativas de ação epistêmica" . Inteligência Artificial . 287 : 103352. doi : 10.1016 / j.artint.2020.103352 . ISSN 0004-3702 .

Leitura adicional

Brandano, S. (2001) " The Event Calculus Assessed ," IEEE TIME Symposium : 7-12.
R. Kowalski e F. Sadri (1995) " Variants of the Event Calculus ", ICLP : 67-81.
Mueller, Erik T. (2015). Commonsense Reasoning: An Event Calculus Based Approach (2nd Ed.) . Waltham, MA: Morgan Kaufmann / Elsevier. ISBN 978-0128014165 . (Guia para usar o cálculo de evento)
Shanahan, M. (1997) Resolvendo o problema da moldura: Uma investigação matemática da lei da inércia do senso comum . MIT Press.
Shanahan, M. (1999) " The Event Calculus Explained " Springer Verlag, LNAI (1600): 409-30.

[1] Kowalski, Robert; Sergot, Marek (1986-03-01). "Um cálculo de eventos baseado em lógica" . Computação de nova geração . 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.), "Some Alternative Formulations of the Event Calculus" , Computational Logic: Logic Programming and Beyond: Essays in Honor of Robert A. Kowalski Parte II , Lecture Notes in Computer Science, Berlin, Heidelberg: Springer, pp . 452–490, doi : 10.1007 / 3-540-45632-5_17 , ISBN 978-3-540-45632-2, recuperado em 2020-10-05

[3] Kowalski, Robert (01-01-1992). “Atualizações da base de dados no cálculo do evento” . The Journal of Logic Programming . 12 (1): 121–146. doi : 10.1016 / 0743-1066 (92) 90041-Z . ISSN 0743-1066 .

[4] Eshghi, Kave (1988). "Planejamento abdutivo com cálculo de eventos" . Iclp / SLP : 562–579.

[5] Lambalgen, Hamm (2005). O tratamento adequado dos eventos . Malden, MA: Blackwell Pub. ISBN 978-0-470-75925-7. OCLC 212129657 .

[6] Skarlatidis, Anastasios; Paliouras, Georgios; Artikis, Alexander; Vouros, George A. (17/02/2015). "Cálculo Probabilístico de Eventos para Reconhecimento 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 .

[7] Skarlatidis, Anastasios; Artikis, Alexander; Filippou, Jason; Paliouras, Georgios (março de 2015). "Um cálculo de evento de programação lógica probabilística" . Teoria e Prática de Programação 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/07/2014). "Um cálculo de evento epistêmico para raciocínio baseado em ASP sobre o conhecimento do passado, presente e futuro" . EPiC Series in Computing . Poltrona. 26 : 75–87. doi : 10.29007 / zswj .

[9] D'Asaro, Fabio Aurelio; Bikakis, Antonis; Dickens, Luke; Miller, Rob (2020-10-01). "Raciocínio probabilístico sobre narrativas de ação epistêmica" . Inteligência Artificial . 287 : 103352. doi : 10.1016 / j.artint.2020.103352 . ISSN 0004-3702 .

Languages

In other projects