Generazione ed adattamento di piani attraverso grafi di pianificazione: sviluppo e sperimentazione di algoritmi basati su ricerca locale e backtracking

2 1.1 - Alcuni Concetti Basemente inuenzato il settore a cui si collega il lavoro proposto in questa tesi. Il restodell'introduzione é così organizzato: nella prima parte esporremo alcuni concettibase, esamineremo poi Graphplan e le sue recenti estensioni; successivamente analiz-zeremo le tecniche di compilazione di un problema di pianicazione in un problemaSAT. Inne verrà introdotto il problema dell'adattamento di un piano, illustrandobrevemente le principali tecniche esistenti.1.1 Alcuni Concetti BaseUn generico problema di pianicazione  é costituito da una quadrupla hL;I;G;Oidove:1. L é un linguaggio di pianicazione per descrivere stati, operatori e goal (adesempio STRIPS [28]);2. I é la descrizione dello stato iniziale del mondo attraverso L;3. G é una descrizione dei goal dell'agente attraverso L;4. O é una descrizione attraverso L delle possibili azioni (operatori) che possonoessere eseguite.Una soluzione di un problema di generazione di piani é un insieme di azioni ordinate,le quali, se eseguite a partire da qualche stato del mondo che soddis la descrizionedello stato iniziale, consentono di raggiungere uno stato del mondo in cui i goal diG sono veri. Si noti che questa formulazione del problema di pianicazione é piut-tosto astratta, in quanto specica in realtà una classe di problemi di pianicazioneparametrizzata dal linguaggio usato per rappresentare il mondo, i goal e le azioni.Uno dei primi linguaggi di rappresentazione dei problemi di pianicazione é cono-sciuto come linguaggio STRIPS [28]. Questo linguaggio modella le azioni come ope-razioni su una base di dati la quale registra l'attuale stato del mondo. La semplicitàdi STRIPS ed il fatto che sia sucientemente espressivo per rappresentare dei do-mini complessi sono le principali ragioni della sua vasta popolarità nella comunitàscientica internazionale che si occupa di pianicazione.Nel linguaggio STRIPS gli stati del mondo ed i goal dell'agente sono descritti dainsiemi di predicati ground (o fatti), i cui termini sono simboli di costanti chedenotano oggetti del dominio. Si noti che, mentre la descrizione dello stato inizialeI solitamente contiene solo predicati positivi, la descrizione di G può contenere anchepredicati negativi; inoltre, la descrizione di I può essere parziale, tuttavia moltisistemi di pianicazione adottano la convenzione (nota come assunzione del mondochiuso [81]) secondo cui, se la descrizione non comprende un fatto, allora si puòassumere che il fatto stesso sia falso.
Capitolo 1 - Introduzione 3
In STRIPS ogni operatore  di O consiste di tre elementi: Nome dell'operatore - É una lista di simboli, OpName(t1,t2, ...), do-ve il primo simbolo indica il nome dell'operatore, ed i successivi sono varia-bili e costanti che compaiono nella descrizione delle precondizioni ed eettidell'operatore; Precondizioni di  - É un insieme di predicati del primo ordine che deni-scono quali fatti devono essere veri immediatamente prima che l'operatore siaapplicato; le precondizioni di  sono indicate come Prec(); Eetti di  - Si esprimono come una congiunzioni di predicati del primo ordinee deniscono come cambia il mondo quando l'operatore é applicato; possiamodistinguere:- eetti positivi [ADD()], che determinano un insieme di fatti che risultanoveri dopo che l'operatore é stato applicato;- eetti negativi [DEL()], che individuano un insieme di fatti che risultanofalsi dopo che l'operatore é stato applicato.Nella gura 1.1 riportiamo un esempio degli operatori nel dominio Rocketworld [98].Un operatore contiene un insieme di variabili e quando queste vengono istanziaterisulta denita una azione. Diciamo che un'azione a é applicabile in uno stato Sse ognuna delle sue precondizioni é vera in S, cioè se Prec(a)  S. Nello statoS 0 risultante dall'applicazione di a in S tutti i letterali in ADD(a) sono soddisfattimentre quelli in DEL(a) sono resi falsi da a, cioè ADD(a)S0 e DEL(a)\S0 = Ø.Rappresentazione dei pianiUn piano può essere denito da una struttura dati che consiste di: un insieme di azioni A; un insieme di vincoli di ordinamento tra le azioni; ciascuno dei quali imponeche una certa azione ai in A venga eseguita prima di un'altra azione aj in A,cioè ai  aj .Un pianicatore che possa rappresentare piani in cui alcune azioni sono ordinatereciprocamente mentre altre non sono ordinate é detto pianicatore con ordina-mento parziale [8]. L'alternativa é un pianicate con ordinamento totale, incui le azioni sono completamente ordinate. Un piano totalmente ordinato derivatoda un piano parzialmente ordinato  aggiungendo vincoli di ordinamento é dettolinearizzazione di .
4 1.1 - Alcuni Concetti Base
Il dominio Rocketworld [98] ha quattro operatori: load, unload, move e refuel. Unoggetto può essere caricato in un rocket se é nella sua stessa locazione, un rocket puòmuoversi se ha carburante e quando si muove lo utilizza tutto. In STRIPS, gli operatori sono:
load(?object,?rocket,?place):v ?object cargo ?rocket rocket ?place place:p at(?rocket,?place) at(?object,?place):e ADD in(?object,?rocket)DEL at(?object,?place).unload(?object,?rocket,?place):v ?object cargo ?rocket rocket ?place place:p at(?rocket,?place) in(?object,?rocket):e ADD at(?object,?place)DEL in(?object,?rocket).move(?rocket,?from,?to):v ?rocket rocket ?from place ?to place:p has-fuel(?rocket) at(?rocket,?from):e ADD at(?rocket,?to) no-fuel(?rocket)DEL has-fuel(?rocket) at(?rocket,?from).refuel(?rocket):v ?rocket rocket:p no-fuel(?rocket):e ADD has-fuel(?rocket)DEL no-fuel(?rocket).Figura 1.1: Operatori del dominio Rocketworld.
Capitolo 1 - Introduzione 5SoluzioniUna soluzione ad un problema di pianicazione  é un piano che garantisce il rag-giungimento dei goal G partendo dallo stato iniziale I; corrisponde cioè ad un insiemeordinato (parzialmente o completamente) di azioni che deniscono un piano completoe consistente.In un piano completo i goal G e le precondizioni di ogni azione sono supportatidallo stato iniziale o da un'azione del piano. Un'azione ai supporta una precon-dizione c dell'azione aj se (1) ai  aj e c 2 ADD(ai); (2) non esiste nessuna azioneak tale che c 2 DEL(ak) dove ai  ak  aj in qualche linearizzazione del piano.2Considerando i goal come precondizioni di un'azione ttizia aG che segue tutte lealtre azioni del piano, si ottiene una denizione analoga per goal supportato da un'a-zione. Analogamente possiamo denire il concetto di stato iniziale che supporta unaprecondizione o goal; é suciente considerare i fatti che deniscono I come eetti diun'azione ttizia aI che precedete tutte le altre azioni del piano.In un piano consistente non esiste alcuna contraddizione nell'ordinamento nei vin-coli o nei legami delle variabili. Una contraddizione nei legami di variabile si vericaquando, ad esempio, per una coppia di azioni ai, aj sono validi sia ai  aj cheaj  ai.1.1.1 Assunzioni STRIPS e complessità della pianicazioneLa pianicazione STRIPS, spesso chiamata pianicazione classica, utilizza alcuneassunzioni che consentono di semplicare il problema trattato. In particolare sisuppone che:1. il tempo sia discreto e le azioni siano istantanee;2. gli eetti delle azioni siano deterministici (quindi quando viene eseguita unaazione si é in grado di predire esattamente lo stato risultante);3. nessun evento esogeno possa modicare imprevedibilmente lo stato corrente delmondo.Nonostante queste ipotesi siano molto forti, lo spazio di ricerca è in generale espo-nenziale rispetto ai parametri di ingresso (la dimensione dello stato iniziale, deigoal e degli operatori); infatti, il problema di individuare un piano utilizzando unadescrizione STRIPS risulta essere PSPACE-completo [13, 23]. É possibile denire lacomplessità dei problemi di pianicazione STRIPS considerando il numero ed il tipodi precondizioni ed eetti degli operatori [13]. La gura 1.2 illustra quali problemi2Consideriamo per semplicità precondizioni di azioni e goal non negativi, tuttavia la denizionepuò essere facilmente estesa per considerare anche questi casi.
6 1.1 - Alcuni Concetti Base
* precondizioni
* effetti
1 precondizioni
* effetti
k goals
* precondizioni
1 effetto
* precondizioni
* +effetti
1 precondizione
1 +effetto
1 +precondizione
2 effetti
2 +precondizioni
2 effetti
0 precondizioni
* effetti
* +precondizioni
1 effetto
1 precondizione
* effetti
PSPACE-completo
NP-hard
NP-completo
PolinomialeFigura 1.2: Dierenti livelli di complessità per la pianicazione STRIPS.  indica un nume-ro qualsiasi di precondizioni od eetti, + indica precondizioni od eetti positivi[13].
Capitolo 1 - Introduzione 7di pianicazione sono PSPACE-completi, quali NP-hard, quali NP-completi e qualipolinomiali. In particolare si ha che la pianicazione STRIPS é: PSPACE-completa nel caso generale; PSPACE-completa anche se gli operatori sono limitati ad un unico eetto;oppure se ogni operatore é limitato a due precondizioni (non negate) e dueeetti; NP-hard se ogni operatore ha un'unica precondizione (non negata) e due eetti; NP-completa se gli eetti degli operatori sono unicamente positivi; NP-completa se si limita la lunghezza massima del piano ad una funzionepolinomiale rispetto ai parametri di ingresso [24]; Polinomiale se ogni operatore é ristretto a precondizioni non negate ed un unicoeetto; Polinomiale se ogni operatore ha una precondizione ed il numero di goal élimitato da una costante; Polinomiale se gli operatori non hanno precondizioni.Nonostante le ipotesi sopra descritte e la dicoltà computazionale dei problemi con-siderati, la pianicazione di tipo STRIPS resta un settore di centrale interesse nellaricerca in Intelligenza Articiale. Ciò é dovuto in parte al fatto che:- esistono domini di pianicazione che sono approssimativamente classici, incui cioè le ipotesi precedentemente descritte sono in gran parte vericate;- é possibile gestire domini piú complessi di quelli rappresentati in STRIPS ef-fettuando ripianicazioni qualora sussistano eventi imprevisti che invalidanoil piano formulato;- lo studio di tecniche ecienti per la pianicazione classica costituisce il puntodi partenza per successive estensioni in cui una o piú assunzioni di tipo STRIPSvengono rilassate;1.2 Pianicazione Mediante Analisi di Gra di Piani-cazioneIn questo paragrafo introdurremo in dettaglio la metodologia di pianicazione basatasu Gra di Pianicazione (o Planning Graph), che costituisce la base delle tecniche
8 1.2 - Pianicazione Mediante Analisi di Gra di Pianicazione
n
o
o
p
n
o
o
p
G
o
a
l
 
L
e
v
e
l
G
o
a
l
s
:
 
a
t
(
a
,
 
D
)
a
t
(
b
,
 
D
)
a
t
(
a
,
 
S
)
 
 
a
t
(
b
,
 
S
)
a
t
(
R
,
 
S
)
 
 
f
u
e
l
(
R
)
a
t
(
b
,
S
)
a
t
(
R
,
S
)
f
u
e
l
(
R
)
l
o
a
d
(
b
,
R
,
S
)
l
o
a
d
(
a
,
R
,
S
)
n
o
o
p
n
o
o
p
n
o
o
p
a
t
(
R
,
D
)
i
n
(
b
,
R
)
i
n
(
a
,
R
)
a
t
(
R
,
D
)
i
n
(
b
,
R
)
i
n
(
a
,
R
)
u
n
l
o
a
d
(
b
,
R
,
D
)
u
n
l
o
a
d
(
a
,
R
,
D
)
n
o
o
p
n
o
o
p
n
o
o
p
n
o
o
p
n
o
o
p
n
o
o
p
a
t
(
R
,
 
S
)
f
u
e
l
(
R
)
a
t
(
b
,
 
S
)
a
t
(
R
,
 
S
)
f
u
e
l
(
R
)
a
t
(
a
,
 
S
)
a
t
(
b
,
 
S
)
m
o
v
e
(
R
,
S
,
D
)
a
t
(
a
,
 
S
)
 
 
 
 
 
 
 
 
1
A
c
t
i
o
n
 
L
e
v
e
l
 
 
 
 
 
 
 
0
A
c
t
i
o
n
 
L
e
v
e
l
 
 
 
 
 
 
 
 
1
F
a
c
t
 
 
L
e
v
e
l
 
 
 
 
 
 
 
 
 
2
A
c
t
i
o
n
 
L
e
v
e
l
 
 
 
 
 
 
 
2
F
a
c
t
 
L
e
v
e
l
F
a
c
t
 
L
e
v
e
l
n
o
f
u
e
l
(
R
)
n
o
o
p
u
n
l
o
a
d
(
b
,
R
,
S
)
u
n
l
o
a
d
(
a
,
R
,
S
)
l
o
a
d
(
a
,
R
,
S
)
l
o
a
d
(
b
,
R
,
S
)
n
o
f
u
e
l
(
R
)
m
o
v
e
(
R
,
S
,
D
)
a
t
(
a
,
S
)
 
 
 
 
 
 
0
a
t
(
b
,
D
)
a
t
(
a
,
D
)
I
n
i
z
i
a
l
i
:
F
a
t
t
iFigura 1.3: Esempio graco di un planning graph nel dominio Rocketworld. In grassettosono indicati i fatti veri e le azioni utilizzate nei vari istanti temporali.
Capitolo 1 - Introduzione 9proposte in questa tesi. I gra di pianicazione sono stati introdotti da Blum e Furst[11] ed utilizzati in molti recenti lavori sulla pianicazione [5, 30, 34, 38, 52, 57, 66, 88].Questa tecnica rappresenta uno dei piú entusiasmanti sviluppi della pianicazionedomain independent in Intelligenza Articiale, inoltre: utilizza un algoritmo, Graphplan [11], che é semplice e veloce - in molti casidiversi ordini di grandezza piú veloce dei sistemi precedenti come SNLP [71],Prodigy [73] e UCPOP [79]; permette di eettuare una particolare codica di problemi di pianicazione nel-l'ambito di un recente approccio basato su SAT, anch'esso di notevole successo[60, 61, 57].A dierenza dei metodi standard di pianicazione, che partono subito con una fasedi ricerca, Graphplan inizia costruendo il planning graph del problema da risolvere.Un planning graph é una particolare struttura dati che rappresenta il problema dipianicazione in modo da rendere espliciti molti vincoli associati al problema stesso,al ne di ridurre il costo della successiva fase di ricerca. Un planning graph hauna dimensione polinomiale e può essere costruito in tempo polinomiale rispetto alladescrizione del problema ed al numero di passi temporali (istanti) necessari per unasoluzione.La Planning Graph Analysis si applica a domini di pianicazione di tipo STRIPS[28] dove il tempo viene rappresentato in modo discreto. Ogni azione é associataad un istante temporale o time step; si parla in tal caso di Istanza di Azione.Un'azione svolta all'istante temporale t aggiunge (rende veri) alla descrizione dellostato del mondo tutti i fatti che sono tra i suoi eetti positivi e cancella (rende falsi)tutti fatti che sono tra i suoi eetti negativi. Le azioni di tipo no-op (o frame-action) sono speciali azioni che hanno un'unica precondizione che é uguale all'unicoeetto. Queste azioni vengono utilizzate in un planning graph per rappresentarela possibilità che un certo fatto vero ad un istante temporale persista nell'istantesuccessivo. Per esempio, nel dominio Rocketworld [98] (vedi gura 1.3) il pianogenerato da Graphplan è il seguente: al time-step 0, carica appropriatamente tutti gli oggetti nei rocket al time-step 1 muove irocket al time-step 2 scarica gli oggetti dai rocket. :::La semantica di un piano di questo tipo è che tutte le azioni in un dato time-steppossono essere svolte in qualsiasi ordine desiderato. Si verica inoltre che tutte le
10 1.2 - Pianicazione Mediante Analisi di Gra di Pianicazioneazioni dell'istante temporale i sono ordinate da un vincolo di precedenza () rispettoalle azioni dell'istante temporale successivo.Una caratteristica importante di questo algoritmo è la garanzia di trovare il pianopiú breve rispetto al numero di time-step coinvolti. Per esempio, nel dominio Roc-ketworld, in gura 1.4 viene individuato un percorso ottimale per i razzi al ne dimassimizzare l'esecuzione parallela delle azioni e ridurre il numero di istanti tempora-li necessari per l'esecuzione del piano. Un'altra caratteristica rilevante dell'algoritmoè quella di non essere particolarmente sensibile all'ordine con cui sono specicati gliobiettivi del problema di pianicazione, contrariamente ad approcci piú tradizionali(quali ad esempio UCPOP [79]).1.2.1 Piani Validi e Planning GraphUn piano valido per un problema di pianicazione consiste in un insieme di istanzedi azioni, ci saranno azioni al tempo 0, azioni al tempo 1 e così via. Nello stes-so time-step possono essere eseguite piú azioni, a patto che non interferiscano traloro. Intuitivamente, diciamo che due azioni interferiscono se una rende falsa unaprecondizione o un eetto positivo di un'altra (questa nozione verrà denita piú pre-cisamente in seguito). In un piano valido le azioni assegnate ad uno stesso time-steppossono essere eseguite in qualsiasi ordine, ottenendo esattamente lo stesso stato delmondo. Un piano valido può eseguire un'azione all'istante temporale t se il pianorende vere tutte le sue precondizioni al tempo t. Dato che le azioni no-op propaganoi fatti veri in avanti nel tempo, diciamo che un fatto é supportato al tempo t  1soltanto se questo è un eetto positivo di qualche azione svolta al tempo t1. Inne,un piano valido deve rendere supportati tutti i goal al livello nale.Planning GraphUn planning graph è un grafo diretto aciclico a livelli con due tipi di nodi e tre tipidi archi. I livelli si alternano tra livelli dei fatti che contengono i nodi-fatto (ognunoassociato ad uno specico fatto) e livelli delle azioni che contengono i nodi-azione(ognuno assegnato ad una specica azione). Di seguito indicheremo con [p] il nodofatto associato al fatto p, ed analogamente con [a] il nodo azione dell'azione a. Ilprimo livello del planning graph consiste in un livello dei fatti e contiene un nodoper ogni fatto presente nelle condizioni iniziali. I livelli in un planning graph sono:- fatti veri al tempo 0,- possibili azioni al tempo 0,- fatti che possono essere veri al tempo 1,- possibili azioni al tempo 1,
Capitolo 1 - Introduzione 11Problema: Rocket_aOggetti del dominio:place: london paris jfk bos;rocket: r1 r2;cargo: mxf avrim alex jason pencil paper april michelle betty lisa;Stato iniziale:at(r1,jfk) at(r2,bos) has-fuel(r1) has-fuel(r2) at(mxf,paris)at(avrim,paris) at(alex,paris) at(jason,jfk) at(pencil,london)at(paper,london) at(michelle,london) at(april,london)at(betty,london) at(lisa,london)Goal: at(mxf,bos) at(avrim,jfk) at(pencil,bos) at(alex,jfk)at(april,bos) at(lisa,paris) at(michelle,jfk) at(jason,bos)at(paper,paris) at(betty,jfk)Soluzione:Passo 0: load(jason,r1,jfk) Passo 4: load(april,r1,paris)move(r2,bos,london) refuel(r1)Passo 1: refuel(r2) load(pencil,r1,paris)load(pencil,r2,london) move(r2,paris,jfk)move(r1,jfk,bos) load(mxf,r1,paris)load(april,r2,london) Passo 5: unload(avrim,r2,jfk)load(lisa,r2,london) unload(alex,r2,jfk)load(michelle,r2,london) move(r1,paris,bos)load(paper,r2,london) unload(michelle,r2,jfk)load(betty,r2,london) unload(betty,r2,jfk)Passo 2: unload(jason,r1,bos) Passo 6: unload(april,r1,bos)refuel(r1) unload(pencil,r1,bos)move(r2,london,paris) unload(pencil,r1,bos)Passo 3: load(avrim,r2,paris) unload(mxf,r1,bos)refuel(r2)unload(pencil,r2,paris)load(alex,r2,paris)move(r1,bos,paris)unload(april,r2,paris)unload(lisa,r2,paris)unload(paper,r2,paris)Figura 1.4: Formalizzazione del problema Rocket_a e soluzione generata da Graphplan.
12 1.2 - Pianicazione Mediante Analisi di Gra di Pianicazione
- fatti che possono essere veri al tempo 2 e così via.L'assunzione del mondo chiuso dice che ogni fatto non esplicitamente noto come veronello stato iniziale é presunto falso. Un modo per implementare questa assunzione inGraphplan sarebbe di chiudere esplicitamente il livello zero del planning graph - cioèdi aggiungere letterali negativi per tutti i possibili fatti non esplicitamente dichiaraticome veri. Poichè esiste un numero innito di possibili fatti, si deve restringere taleapproccio ai sottoinsiemi rilevanti - cioè quelli che sono menzionati nelle precondizionidi qualche azione o in un goal; gli altri letterali non possono inuenzare nessunasoluzione. Una tecnica migliore consiste nell'utilizzare l'assunzione del mondo chiusopigramente, poichè riduce la dimensione del planning graph e diminuisce i costidell'espansione del grafo; si crea il livello zero del planning graph considerando solole proposizioni note come vere nello stato iniziale. Espandendo il planning graph allivello azione i si procede nel modo seguente:si supponga che l'azione a richieda :P come precondizione; se :P é nel planninggraph al livello dei fatti i si procede come al solito, altrimenti, se :P manca a livelloi si deve cercare di vedere se la sua negazione (il fatto P ) sia presente a livello zero.Se P é assente a livello zero, si aggiunge :P a tale livello e si aggiungono azionidi mantenimento per portare :P al livello corrente. Con questo semplice approccionon é necessario apportare cambiamenti al processo di estrazione delle soluzioni cheverrà descritto successivamente [99].Gli archi in un planning graph rappresentano esplicitamente le relazioni tra le azionied i fatti. I nodi delle azioni nel livello i sono connessi con:1. archi di precondizione ai propri nodi precondizione nel livello dei fatti i,2. archi positivi ai loro nodi positivi nel livello dei fatti i+1,3. archi negativi ai loro nodi negativi nel livello dei fatti i+1.Le condizioni imposte ad un planning graph sono molto piú deboli di quelle impostead un piano valido. In particolare, il livello delle azioni i contiene tutte le azioni lecui precondizioni appartengono al livello dei fatti i. Un fatto appartiene al livellodei fatti i se è un eetto positivo di qualche azione al livello delle azioni i  1. Unesempio di planning graph è dato in gura 1.3. Dato un problema di pianicazione, se esiste un piano soluzione per  che coinvolge t time-step, allora questo é unsottografo del planning graph con t livelli costruito per  [11].1.2.2 Relazioni di Mutua Esclusione tra i Nodi del Planning GraphLe relazioni binarie di mutua esclusione tra nodi dello stesso livello sono informazionicruciali per l'ecienza di Graphplan. Due azioni in un dato livello sono mutuamenteesclusive se nessun piano valido può eseguirle entrambe al corrispondente istante
Capitolo 1 - Introduzione 13
temporale. Analogamente, due fatti ad un dato livello sono mutuamente esclusivi senessun piano valido può renderli veri entrambi nello stesso istante temporale (cioènon esiste alcun stato del mondo raggiungibile a partire da quello iniziale in cui i duefatti sono entrambi veri). L'identicazione delle relazioni di mutua esclusione puòessere di enorme aiuto per ridurre il carico computazionale richiesto dalla successivafase di ricerca di un piano valido (un sottografo del planning graph).Graphplan individua e memorizza le relazioni di mutua esclusione attraverso poche esemplici regole che tuttavia non garantiscono di individuare tutti i possibili conittitra azioni. Precisamente, vi sono tre casi in cui due nodi azione [a]e[b], ad un datolivello del grafo, sono mutuamente esclusivi (vedi gura 1.5): eetti inconsistenti: si hanno quando una delle azioni rende falso un eettopositivo dell'altra; interferenza: si ha quando una delle azioni rende falsa una precondizionedell'altra; esigenze contrastanti: si hanno quando una precondizione dell'azione a ed unaprecondizione dell'azione b sono mutuamente esclusive nel corrispondente livellodei fatti.Due nodi-fatto [p] e [q] sono mutuamente esclusivi se tutti i modi per rendere veroil fatto p sono esclusivi con tutti i modi di rendere vero il fatto q (diciamo che ilsupporto é inconsistente).Per esempio, nel dominio Rocketworld (vedi gura 1.3) i nodi azione [move(R,S,D)]e [load(a,R,S)] al tempo 1 sono esclusivi perché il primo rende falso il fattoat(R,S)che è una precondizione del secondo (interferenza). I nodi-fatto [at(R,S)]e[at(R,D)] sono esclusivi al tempo 1 perché tutti i modi per generare il primo (cen'è uno solo: no-op) sono esclusivi con tutti i modi per generare il secondo (ce n'èuno solo: move); i nodi azione [load(a,R,S)] e [unload(a,R,S)] sono esclusi-vi perché hanno esigenze contrastanti: i fatti at(a,S) e in(a,R); i nodi azione[load(a,R,S)] e [noop_at(a,S)] sono mutuamente esclusivi poichè il primo hacome eetto negativo un eetto positivo dell'altro (eetti inconsistenti).Due nodi fatto possono essere mutuamente esclusivi in ogni livello di un planninggraph, oppure possono essere esclusivi nei primi livelli e poi non esserlo piú neilivelli successivi. Per esempio poichè nella gura 1.3 l'oggetto a e il rocket Rsono nella città S all'istante iniziale, [in(a,R)] e [in(R,D)] sono mutuamenteesclusivi nell'istante temporale 1 ma non lo sono piú nell'istante 2, poichè le azioniche possono renderli veri sono mutuamente esclusive nell'istante temporale 0 ma nonnell'istante temporale 1.Si noti che le nozioni di esigenze contrastanti tra nodi azione edimutua esclusionetra nodi fatto non sono soltanto proprietà logiche degli operatori. Piuttosto, esse
14 1.2 - Pianicazione Mediante Analisi di Gra di Pianicazione
Supporto inconsistente Effetti inconsistenti
Interferenza Esigenze contrastanti
m.e
m
.
e
m
.
e
n
u
o
v
a
 
m
.
e
.
n
u
o
v
a
 
m
.
e
.
n
u
o
v
a
 
m
.
e
.
n
u
o
v
a
 
m
.
e
.
Figura 1.5: Rappresentazione graca delle relazioni di mutua esclusione [99]. I cerchi deno-tano i nodi proposizione, i quadrati rappresentano i nodi azione, le linee curvele relazioni di mutua esclusione e le linee curve tratteggiate rappresentano lenuove relazioni di mutua esclusione individuate.