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