Il Situation Calculuspirri/sitcalc/l2.pdf · Calculus: termini SC ha tre tipi di ter mini azioni,...

Preview:

Citation preview

IlSitu

ation

Calcu

lus

Alberto

Finzi

Dip

artimen

tod

iInfo

rmatica

eS

istemistica

Un

iversitad

iRo

ma

“La

Sap

ienza”

Ingegneriadella

Conoscenza

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SC

:E

semp

io(co

ntin

ua

...)

�S

ituazio

ne

Iniziale:

�� ������ �

� �� ��

���� �

�� �� �� ��

� ���� ��

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

�� � ���� ��

� �� ���� �

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

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

��

� ��� ���� �

����� ����

���� �

�� � � �� ���

��� �

�����

� � ����

� ��

Un

iqu

eN

ame

Axio

ms:

�� !�"����

� ������ ��

�� !�"����

� �� ���

� ��

�������� �

� ���

� ��

�� !�"����

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

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

�� ���

���� �

� ���

� �� ���

Alberto

Finzi

Situation

Calculus

15

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

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

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

Recommended