Kalkul událostí (Event Calculus)

transcript

Kalkul událostí (Event

Calculus)

Prezentaci vypracovala:Martina Číhalová

Úvod:

Formalismy pro reprezentaci akcí a

jejich důsledků, využívány v

databázových aplikacích.

Účel: rozhodování o provedení akce na

základě znalosti důsledků akcí.

Kalkul událostí (event calculus)

Situační kalkul (situation calculus)

calculus)

Poprvé uvedl: Robert Kowalski, Marek Sergot v roce 1986

Rozšíření: Murray Shanah, Rob Miller 90 léta 20. stol.

calculus)

Umožňuje časovou projekci, predikci - řešení deduktivních úloh

Umožňuje časovou explanaci, postdikci - řešení abduktivních úloh

Hledání teorie pro důsledky akcí- řešení induktivních úloh (učení)

Kalkul událostíÚvod

Umožňuje reprezentaci následujících typů akcí:

Akce s nepřímými důsledky Akce s nedeterministickými důsledky Složené akce Souběžné akce Nepřetržitá změna(?)

Kalkul událostí Formalismus

Založen na predikátové logice

prvního řádu

Speciální predikátové a funkční

symboly

Množina axiomů vymezující

požadovaný model

Kalkul událostí Základní

proměnné

AKCE (ACTIONS (EVENTS))

STAVY (FLUENTS) - pro representaci propozic, které se mění v čase; lze specifikovat jejich hodnotu pro určitý časový okamžik

ČASOVÉ OKAMŽIKY (TIME POINTS)

Kalkul událostí Predikáty

Pomocí příslušných predikátů vyjadřujeme:

Podmínku „co se stane, když“ Počáteční podmínku Důsledky (účinky) akcí Platnost stavu (fluent) v

příslušných časových okamžicích

Kalkul událostí Predikáty

FORMULA MEANINGInitiates(,β,τ) Stav (fluent) β počíná platit akcí po čase τ

Terminates(,β,τ) Stav (fluent) β přestává platit akcí po čase τ

InitiallyP(β) Stav (fluent) β platí od času 0

τ1 < τ2 Časový okamžik τ1 je před časovým okamžikem τ2

Happens(,τ) Akce je vykonána v čase τ

HoldsAt(β,τ) Stav (fluent) β platí v čase τ

Clipped(τ1, β,τ2) Stav (fluent) β je ukončen mezi čas. okamžiky τ1 a τ2

Kalkul událostí Fluents

Účinky akcí jsou dány pomocí predikátů:

INITIATES: jestliže je vykonána akce vyjádřená termem a v čase t, pak stav (fluent) bude po čase t pravdivý

TERMINATES: jestliže je vykonána akce vyjádřená termem a v čase t, pak stav (fluent) bude po čase t nepravdivý

Kalkul událostí Axiomy

(InitiallyP(f) Clipped(0,f,t)) HoldsAt(f,t) (SC1)

Happens(a,t1) Initiates(a,f,t1) t1 t2 Clipped(t1,f,t2) HoldsAt (f,t2) (SC2)

a,t Happens(a,t) t1 t t2 Terminates(a,f,t) Clipped(t1,f,t2) (SC3)

Kalkul událostí Axiomy

Dle výchozích axiomů (SC1, SC2) neplatí stav (fluent) v čase akce, která ho iniciovala, ale platí v čase akce, která ho ukončuje.

Tedy intervaly, které vyjadřují časovou platnost stavu (fluent) jsou zleva otevřené a zprava ostré.

Problém rámce (frame problem)

Technický problém umělé inteligence, spočívá v logice.

Formulován v r. 1969 Mc Carthym a Hayem (tzv. Yale shooting scenario)

Jde o problém toho, jak vyjádřit důsledky akcí, aniž by muselo být explicitně specifikováno, které stavy(fluents) nejsou příslušnou akcí ovlivněny.

Rámcový problém Yale Shooting

scenario Tři možné akce: nabít, odjistit, vystřelit Tři možné stavy (fluents) : nabito, živý,

mrtvý Důsledkem akce nabít je stav nabito Důsledkem akce vystřelit je stav mrtvý Akce odjistit nemá žádný důsledek Scénář se skládá z akce nabít,

následované akcí odjistit, následované akcí vystřelit

scenario

Formální specifikace:

Initiates(Load,Loaded,t) (Y1.1) HoldsAt(Loaded,t)

Initiates(Shoot,Dead,t)(Y1.2)

HoldsAt(Loaded,t) Terminates(Shoot,Alive,t) (Y1.3)

scenario

InitiallyP(Alive) (Y2.1) Happens(Load,T1) (Y2.2) Happens(Sneeze,T2) (Y2.3) Happens(Shoot,T3) (Y2.4) T1 T2 (Y2.5) T2 T3 (Y2.6) T3 T4 (Y2.7)

scenario

…konjunkce (Y1.1) až (Y1.3) …konjunkce (Y2.1) až (Y2.7) Tedy mělo by platit následující: SC l= HoldsAt(Dead,T4)

scenario

Tento úsudek je však neplatný! Neboť jsme explicitně neuvedli stavy,

které nejsou důsledkem příslušných akcí

Neboť nejsme například schopni říci, zda akce odjistit nezpůsobí to, že zbraň přestane být nabitá

scenario

Existuje model formulí SC, v němž: Terminates(Sneeze,Loaded,T2) je pravdivé Holds(Alive,T4) je pravdivé HoldsAt(DeadT4) je nepravdivé Tedy je nutné zavedením dalších pravidel

zohlednit další okolnosti, pokud chceme, aby závěr z předpokladů opravdu vyplýval.

Rámcový problém Řešení rámcového problému

Využitím nemonotónního formalismu,např. defaultní logiky (možnost vyjádření faktů typu: „něco je defaultně považováno za pravdivé“) (Reiter,1980)

Pomocí specifikace (McCarthy 1980), formalizace takzvaného common sense law of inertia (stav (fluent) je považován za stále platný, dokud není důvod věřit, že je tomu jinak)

Kalkul událostí Plná verze:

predikáty

FORMULA MEANINGReleases(,β,τ) Neplatí předpoklad netečnosti akce

ke stavu (fluent) β v čase τ

InitiallyN(β) Stav (fluent) β neplatí od času 0

Happens(,τ1,τ2) Platnost akce začíná v čase τ1 a končí v čase τ2

Declipped(τ1,β,τ2) Stav (fluent) β je iniciován mezi časy τ1 a τ2

axiomy

InitiallyP(f) Clipped(0,f,t) HoldsAt(f,t) (EC1)

Happens(a,t1,t2) Initiates(a,f,t2) t2 t3 Clipped(t1,f,t3) HoldsAt(f,t3) (EC2)

a,t1,t3 Happens(a,t1,t3) t1 t3 t2 t4 Terminates(a,f,t2) Releases (a,f,t2) Clipped(t1,f,t4) (EC3)

axiomy InitiallyN(f) Declipped(0,f,t) HoldsAt(f,t) (EC4)

Happens(a,t1,t2) Teminates(a,f,t1) t2<t3 Declipped(t1,f,t3) HoldsAt(f,t3) (EC5)

a,t2,t3Happens(a,t2,t3) t1<t3 t2<t4 Initiates(a,f,t2) Releases(a,f,t2) Declipped(t1,f,t4) (EC6)

Happens(a,t1,t2) t1 t2 (EC7)

Situační kalkul Jde o logický formalismus navržený

pro reprezentaci znalostí a rozhodování nad dynamickými doménami.

Využívá predikátovou logiku druhého řádu.

Představen roku 1963 J. McCarthym. Jeho základní verzi vyvinul roku 1991

Ray Reiter.

Situační kalkul:základní prvky

Akce (Actions) Stavy (Fluents) Situace (Situations): konečné sekvence

akcí Objekty (Objects): (cokoliv co není akce,

nebo situace)

Situační kalkul Axiomy

Axiomy udávající podmínky příslušných akcí, jeden pro každou akci

Axiomy udávající následníka stavu, jeden pro každý stav (fluent)

Axiomy popisující svět v různých situacích

Základní axiomy situačního kalkulu

Situační kalkul Základní

Jde o kalkul nad doménou tří typů entitních sort:

Akce, situace, objekty Stavy (fluents) jsou modelovány

pomocí predikátů nebo funkcí. Spec. Predikát pro vyjádření toho,

že je akce proveditelná Poss(action)

Situační kalkul Příklady formalizace

do(a,S) (akce) is_carrying(o,S) (stav) is_carrying(Ball,S0) is_carrying(Ball, do(pickup(Ball),S0))

situace

Situační kalkul Příklad

formalizace Poss(pickup(o),S)

(zis_carrying(z,S)) heavy(o)

Akci zvednout objekt v situaci S je možné provést jen tehdy a tehdy, když pro všechny objekty platí stav, že nejsou neseny v situaci S a nejsou těžké.

Kalkul událostí (Event Calculus)

Documents