19
Il Situation Calculus Alberto Finzi Dipartimento di Informatica e Sistemistica Universit ` a di Roma “La Sapienza” Ingegneria della Conoscenza

Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

IlSitu

ation

Calcu

lus

Alberto

Finzi

Dip

artimen

tod

iInfo

rmatica

eS

istemistica

Un

iversitad

iRo

ma

“La

Sap

ienza”

Ingegneriadella

Conoscenza

Page 2: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

Do

min

ioD

inam

ico

Do

min

ioD

inam

ico:

dominio

soggettoa

cambiam

entidovutiadazioni,eventio

tempo.

Problem

adella

rappresentazionediun

dominio

dinamico.

Com

ecatturare

ilcambiam

ento?

(a)R

agionamento

sistemidiragionam

entonon

monotono

(beliefrevision)

(b)M

odelli�

���

logichedinam

iche:rappresentazione

diazioni(ocom

andi)(P

DL,S

it.C

alc.etc.)

logichetem

porali:rappresentazione

deltempo

(Logichetem

porali,EventC

alculusetc.)

Alberto

Finzi

Situation

Calculus

1

Page 3: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

Situ

ation

Calcu

lus:

on

tolo

gia

IlSituation

Calculus

[Hayes

McC

arthy’69][R

eiter’91]

eun

linguaggio(delsecondo

ordine)per

rappresentaredom

inidinamicam

entem

odificabilidaazioni:

tuttiicambiam

entideldominio

sonoconseguenza

diazioniesplicitamente

nominate

Lastoria

deicambiam

entiapportatialdominio

apartire

dauna

situazioneiniziale

euna

sequenzadiazioni.

Leproprieta

dipendonoda

sequenzediazioni.

Situ

azion

e:term

inedelprim

oordine

perrappresentare

sequenzediazioni.

Lasituazione

inizialee

rappresentatadalla

costante

��

Flu

ente:

predicato(

funzione)

cherappresenta

unaproprieta

(oggetto

)m

odificabilecon

l’esecuzionedelle

azioni.U

ltimo

argomento

riservatoad

unasituazione

�������

(������� ).

Alberto

Finzi

Situation

Calculus

2

Page 4: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

Situ

ation

Calcu

lus:

termin

i

SC

hatre

tipiditerminiazio

ni,situ

azion

i,og

getti:

azion

i:

�� ,�������

situazio

ni:

costruitecon

����

sit.iniziale

�� � ���

� �����

ela

sit.che

segue�

applicando�

(sono

situazioni�

,��� ��� �� ,��� ��� ��� ��� ��� ,���

)

og

getti:

tuttiglialtrioggettideldominio

Ad

esempio,���

�������

rapp.una

azione,�

ed�

rapp.oggetti.��

� ����� ����

� � ��

euna

situazione.

lasituazione:

��� ���� ����� �� � ��

� ����

� �� � ��� �� !�"�� �� � ����

descrivela

storia:

# �� !�"�� �� � ����

� �� ����� ����� ��$

Alberto

Finzi

Situation

Calculus

3

Page 5: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

Situ

ation

Calcu

lus:

flu

enti

Inun

dominio

dinamico

lerelazionie

lefunzionivariano

dasituazione

asituazione.

IlSituation

Calculus

permette

dirappresentare:

flu

entirelazio

nali:

letterepredicative

conultim

oargom

entoriservato

aduna

situazione

������ �

flu

entifu

nzio

nali:

simbolidifunzione

conultim

oargom

entoriservato

aduna

situazione

�������

.

Ad

esempio,se

sivuolerappresentare

undom

inioin

cuiunrobotopera

muovendo

oggettiil

fluenterelazionale

������

�� �� �

descriverailfatto

cheilrobotha

presol’oggetto

edil

fluentefunzionale

������� � �

indicheral’altezza

incuisitrova

l’oggetto

.

Alberto

Finzi

Situation

Calculus

4

Page 6: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

Situ

ation

Calcu

lus:

Actio

nT

heo

ry(1)

IlSituation

Calculus

permette

dirappresentareun

dominio

dinamico

come

unateoria

delle

azioni:A

ction

Th

eory.

Leazionisono

descrittein

terminidip

recon

dizio

nied

effetti.

Una

rappresentazioneidealizzata:

Basic

Th

eory

of

Actio

ns.

Azionideterm

inistiche.

Rappresentazione

completa

deldominio.

Azioniprim

itive(non

azionicomplesse,es.

programm

i).

Azioniche

modificano

ildominio

(es.non

azionipercettive).

Alberto

Finzi

Situation

Calculus

5

Page 7: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

Situ

ation

Calcu

lus:

Actio

nT

heo

ry(2)

LaB

asicT

heo

ryo

fA

ction

sprevede

iseguentiassiomi:

1.A

ssiomifondazionali:

indipendentidaldominio,perm

ettonol’interpretazione

correttadeiterm

inisituazione

2.A

ssiomistato

iniziale:descrizione

deldominio

nellodello

statoiniziale.

3.A

ssiomidiprecondizioni:

condizionidieseguibilitaper

ogniazione.

4.A

ssiomiche

descrivonoglieffetti:

rappresentazionedeglieffettidelle

azioni

Alberto

Finzi

Situation

Calculus

6

Page 8: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:A

ssiom

ifon

dazio

nali

Occorre

definireassiom

ipercatturare

imodelliche

interpretanocorrettam

entele

situazioni:le

situazioni

devonocorrispondere

asequenze

diazioni[PirriR

eiter’99].

����

� ������ ���

� ������ ��� ���

������� ��� ����

����� �

�# �� �� ��� ��

� ������$ �� ��� ��

� ����

����

� �������� �� ���

Alberto

Finzi

Situation

Calculus

7

Page 9: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:P

recon

dizio

nie

Qu

alificatio

nP

rob

lem

Leazionisono

applicabilisoloin

determinate

condizioni.

Siintroduce

ilpredicatospeciale��

����� :

������� :

“l’azione�

puoessere

eseguitanella

sit

Es. ��

� �

������ �� �������

������

�� � ��

Con

asserzionidiquestogenere

nonsipu

oderivare

l’eseguibilitadelle

azioni.O

ccorreuna

formula

deltipo:

� ������������������ ��

ma

difficilecatturare

“tutte”le

qualificazioni.

Qu

alificatio

nP

rob

lem:

occorredefinire

inm

odoesaustivo

tuttele

qualificazionidiunaazione.

So

luzio

ne

idealizzata:

siutilizzanoassiom

ideltipo���������� ����� ������

Alberto

Finzi

Situation

Calculus

8

Page 10: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:E

ffettieF

rame

Pro

blem

Glieffettidelle

azionisicatturanodescrivendo

quelloche

evero

dopol’esecuzione

delleazioni:

� ���

���� �

� �����

� ���

���� �

� �� ��� �

������ �

� �� ���

� ���

���� �

� �����

������

�� �

� �� ��� �

������ �

� �� ���

Per

avereuna

rapp.com

pletadello

statosuccessivo

nonbasta

rappresentarequello

checam

bia,

occorredescrivere

anchequello

cherim

aneinvariato:

� ���

���� �

� �����

� ���

���� �

� �� ��� �

������ �

� �� ���

��

����

�� �

� �� ���

������

�� �

� �� ��� � �

��� � ��� ���

Fram

eP

rob

lem:

problema

dirappresentarein

modo

sinteticole

proprietache

nonvariano

con

l’esecuzionedelle

azioni.

Ilframe

pro

blem

eproblem

atipico

dellerapp.

didominidinam

iciconlogiche

dinamiche.

Gliassiom

ichedescrivono

leproprieta

invariantisidiconofram

eaxio

ms.

Alberto

Finzi

Situation

Calculus

9

Page 11: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:u

na

solu

zion

ealfram

ep

rob

lem

Siconsideriper

ognifluentela

seguentecoppia

diassiomidieffetto� �� :

Positive

Norm

alForm

Axiom

forF

luent�

:

���� ����� ����� ������� ��� ������

Negative

Norm

alForm

Axiom

forF

luent�

:

���� ����� ����� �������

� ��� ������

Siconsidera

laseguente

ipotesidicompletezza:

dettiassiomidescrivono

tuttele

condizionipercui�

diventavera

(falsa

)nella

situazionesuccessiva.

Exp

lanatio

nC

losu

reA

xiom

s:(2)

�����������������

� ��� ������ �� �� ����� �����������

������������ ��� �� ��� �� �� ����� �����

Un

iqu

eN

ame

Axio

ms

for

Actio

ns:

����� � � ��� ���

����� �

� ���

Aquesto

puntosipuo

introdurreilseguente

risultato[R

eiter’91]:

Sia�

unateoria

delleazionialprim

o

ordineche

deriva �� � ��� ����� � �� ����� �� �� �� �� ����� �� �� ,in�

siderivache

gliassiomidichiusura

(2)e

dieffetto(2)

sonoequivalentialseguente:

������ ��� ������� � �� ����� ��������� �� ����

� ����������������

Alberto

Finzi

Situation

Calculus

10

Page 12: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:A

ssiom

ad

iStato

Su

ccessore

L’assioma

introdottoviene

detto:A

ssioma

diStato

Successore

perilfluente�

eperm

ettedidescrivere,

contemporaneam

ente,ilcambiam

entoe

l’invarianzadi�

conl’esecuzione

delleazioni.

Ad

esempio,per

descivereglieffettidelle

azionisulfluente������

siscriveraun

assioma

deltiposeguente:

���������� ��� �������

���������� �

���

� ������ �� �

��� ��� ����� �� ����� ��

� �� ��� �

������������������

��� � ����

L’Assiom

adiS

tatoS

uccessoreha

cioela

forma

seguente:

evero

nellasit.

succ.

# l’azionelo

rendevero�

eragia

veroe

l’azionenon

lorende

falso$

Glieffettidelle

azionipossonoessere

catturatidefinendoun

assioma

distatosucc.

incorrispondenza

diogni

predicatofluente.

Alberto

Finzi

Situation

Calculus

11

Page 13: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:S

olu

zion

ealfram

ep

rob

lem(R

iassun

to)

SS

AP

erognifluente

relazionale:

������ �������� �� ������� ������ ������� ����������� �

SS

Aper

ognifluentefunzionale:

������ ����������

��� ������ �� ���� �� �� ����� �� ���� ����������

Per

ogniazioneun

assioma

diprecondizione:

�������������� ������

Unique

Nam

eA

xioms

forA

ctions:

������ ��� �� ���������� ����� �

Alberto

Finzi

Situation

Calculus

12

Page 14: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:Stato

Iniziale

Lostato

inizialee

rappresentatodalle

proprietavere

nellasituazione

iniziale�� .S

ela

rappresentazionedello

statoiniziale

ecom

pletaallora,per

l’ipotesidideterminism

o,anchel’intero

dominio

dinamico

saracom

pletamente

specificato.

Lostato

inizialesara

definitoda

uninsiem

edifatti:

� ����� � �� ��� � �� ������� ����

Eda

regolestrutturali:���� ��

� �������� �� ���� �� �� � ����

Rappresentazione

completa�

ognifattoe

veroo

falso.

Se

nonrappresentazione

completa:

regolediventano

vincoli�

Ram

ificatio

nP

rob

lem

Alberto

Finzi

Situation

Calculus

13

Page 15: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:E

semp

io

Robotche

puom

uoversieprendere

oggetti(unoalla

volta)e

posarli.�

Actio

nP

recon

ditio

ns:

����� �� !�"����

� � ��� ��

� ���� �

�� �� ������

� � ���

� �� � ���

����� �

������� � ��

���� �

����� ��

Su

ccessor

State

Axio

ms:

���� �

����� ��� ������� ��

�� !�"����

������� �

����� �� �� ���������

����� ��� ������� ��

� ���

������ ������������

� ��

� ���

� ��

� ���� ��

����� � ��� ������� ������������ �� � ���

���� ���

� ������� ������� ��� !�"����

�� ��������� ��� ������� �������������� ��������� ����� ��� !�"����

Alberto

Finzi

Situation

Calculus

14

Page 16: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:E

semp

io(co

ntin

ua

...)

�S

ituazio

ne

Iniziale:

�� ������ �

� �� ��

���� �

�� �� �� ��

� ���� ��

� �� ��� ���� ��

�� � ���� ��

� �� ���� �

����� �� ���� ��������� ���

� ��� ����� �� � �� � � �� ���

��

� ��� ���� �

����� ����

���� �

�� � � �� ���

��� �

�����

� � ����

� ��

Un

iqu

eN

ame

Axio

ms:

�� !�"����

� ������ ��

�� !�"����

� �� ���

� ��

�������� �

� ���

� ��

�� !�"����

� ��� !�"�� �� ���

�������� ������ �� ���

�� ���

���� �

� ���

� �� ���

Alberto

Finzi

Situation

Calculus

15

Page 17: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:B

asicT

heo

ryo

fA

ction

s

Lateoria

delleazioni�

equindidella

seguenteform

a:

������� ���� ����� ���

Dove:

��

:assiom

ifondazionali.

����

:precondizionialle

azioni.

���� :

assiomidistato

successore.

�����

:assiom

idinome

unico.

���

:situazione

iniziale.

Defi

nizio

ne

Una

basictheory

ofactione

rapp.da

uninsiem

ediassiom

idellaform

adescritta

percuivalga

lafluentconsistency

property:sia

unfluente

funzionalecon

t.c.� ��� ��� �� ������ �� � ��� �� ��

allora

����� �� � �! ��� "� � � ���� � �� �� #!� ��%$& � � ���� � �� �� #� � ���� � �� �� '� ��%$(�

Teorem

aU

nabasic

theoryofaction

esoddisfacibile

sselo

e���� ���

Alberto

Finzi

Situation

Calculus

16

Page 18: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:R

egressio

ne

Meccanism

outilizzato

perfare

inferenzanelS

it.C

alc.

Per

provarese

unaproprieta

valein

unasituazione

sicercanole

proprietache

devonovalere

nellasituazione

iniziale.

Per

ognifluente�

sipuoconsiderare

che

������ �������� �

������ ���

Ingenerale,data

unaform

ula

�� ������ �� ,sipuo

ottenereuna

formula

� �� �

equivalente,ma

in

.La

procedurapuo

essereiterata

finoad

�� .

Ad

esempio,per

provareche:�

��

����� �

� �� ��� �

���� �� � ��� � �

��� ��� � �����

sipuo

applicarela

regressio

ne.

Alberto

Finzi

Situation

Calculus

17

Page 19: Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni, situazioni, og g etti: azioni: , situazioni: costr uite con , sit. iniziale ` e la

SC

:P

ianifi

cazion

eD

edu

ttiva

Inuna

teoriadelle

azionisipuoutilizzare

ilreasoningper

farepianificazione

automatica:

pian

ificazio

ne

ded

uttiva.

Sirappresenta

ilgoalcome

formula

�� �

esicerca

ladim

ostrazionedi

���� ����� � �

�� ��

(dove����� ��

indical’eseguibilita

dellasequenza

diazioni�

:ad

esempio����

� ��� �

� � ��� �

� � � ���

staper

����� �

� � � � #����� �

� � ��� �

� � � �� )

Se

laprova

ecostruttiva

vieneottenuto

come

sideeffectdella

dimostrazione.

Ilproblema

dellapianificazione

sipuotradurre

inun

problema

dideduzione(

pian

ificazio

ne

ded

uttiva

[Green

’69])

Alberto

Finzi

Situation

Calculus

18