Con questo elaborato ci proponiamo di illustrare l'algoritmo
di pianificazione GPG-LS basato sulla rappresentazione del Planning-Graph.
Per una migliore comprensione del lavoro svolto facciamo questa breve introduzione
nella quale illustreremo i concetti fondamentali che stanno alla base di
quanto fatto.
Il Planning_Graph
Per illustrare correttamente un problema di pianificazione è
necessario avere come INPUT:
-
una descrizione degli stati iniziali I
-
una descrizione delle azioni che possono essere eseguite nel nostro piano
dette Operatori O
-
una descrizione dei GOAL G che il nostro problema si prefigge di
raggiungere
-
un linguaggio di pianificazione L per descrivere gli stati iniziali
I,
gli operatori O e i goal G
L'OUTPUT del problema è un insieme di azioni che, eseguite
secondo certi vincoli di ordinamento, trasformano i fatti iniziali I
in goal G.
Il linguaggio di pianificazione adottato è il linguaggio STRIPS
in cui ogni operatore è caratterizzato da:
-
Nome dell'operatore: E' una lista di simboli dove il primo simbolo
indica il nome dell'operatore e i successivi sono variabili e costanti
che riguardano le precondizioni e gli effetti dell'operatore stesso
-
Precondizioni: sono l'insieme dei fatti che devono essere veri affinché
l'operatore possa essere usato.
-
Effetti: sono l'insieme dei fatti che descrivono come cambia il
mondo quando l'operatore è applicato. Si dividono in due categorie:
-
Additivi: fatti che vengono resi veri dall'operatore
-
Cancellanti: fatti che vengono resi falsi dall'operatore
Il Planning-Graph è un grafo aciclico e partizionato
(organizzato in vari livelli) ed è una rappresentazione compatta
dello spazio di ricerca.
I nodi del Planning-Graph sono di due tipi:
-
nodo fatto: associato a una proposizione
-
nodo azione: associato a un'azione
Un'azione è un operatore a cui sono state istanziate le variabili;
essa è applicabile se ognuna delle sue precondizioni è vera.
Questi nodi sono connessi mediante archi che vanno da nodi di tipo fatto
a nodi di tipo azione, se i fatti sono precondizioni delle azioni stesse,
e da nodi azione a nodi fatto, se i primi sono effetti dei secondi. Ogni
azione e fatto sono associati a un loro livello.
Il Planning-Graph è suddiviso in livelli. I livelli corrispondono
a istanti temporali e ogni livello è composto a sua volta da un
sotto-livello dei fatti e un sotto-livello delle azioni. Ad esempio il
livello zero sarà costituito dai fatti dell'istante iniziale e dalle
azioni eseguibili. Al livello uno ci saranno i fatti che possono essere
resi veri dalle azioni del livello precedente e a sua volta delle altre
azioni e così via fino ad arrivare al livello GOAL.
Se a uno stesso livello una coppia di fatti o azioni non possono essere
resi veri si ha una relazione di mutua esclusione.
In particolare due nodi azione sono mutuamente esclusivi se siamo in
uno dei seguenti casi:
-
Interferenza: quando una delle due azioni rende falsa una precondizione
dell'altra
-
Effetti inconsistenti: quando una delle azioni rende falso un effetto
positivo dell'altra
-
Esigenze contrastanti: quando una precondizione della prima è
mutuamente esclusiva con una precondizione della seconda
Mentre due fatti sono mutuamente esclusivi in caso di:
-
Supporto inconsistente: tutti i modi per rendere vero il primo fatto
sono mutuamente esclusivi con tutti i modi per rendere vero il secondo.
La generazione di un piano è costituita da due fasi separate:
-
costruzione del Planning-Graph
Per la costruzione di un Planning-Graph si parte dal livello zero
e si procede incrementalmente nel seguente modo:
- aggiungere le azioni applicabili e i rispettivi effetti nel livello
successivo
- inserire le relazioni di mutua esclusione
Si procede finché tutti i nodi goal non sono supportati e non
sono mutuamente esclusivi oppure il grafo è stabilizzato (cioè
fino a quando due livelli adiacenti contengono le stesse informazioni;
in tal caso anche tutti i livelli successivi saranno uguali e non avrebbe
senso continuare l'espansione).
-
ricerca di un sottografo soluzione (vedi cap. 1.2 per informazioni sulla
ricerca da noi esaminata)
Una soluzione di un problema di pianificazione è un piano che garantisce
il raggiungimento dei goal G partendo dallo stato iniziale
I.
Quindi alla fine avremo un insieme ordinato di azioni che definiscono un
piano completo e consistente.
In particolare un piano sarà completo quando le precondizioni
di ogni azione sono supportate mentre consistente quando non esiste
alcuna contraddizione nell'ordinamento dei vincoli o nei legami delle variabili.
Nei problemi di pianificazione gli elementi dello spazio di ricerca
sono dei sottografi del Planning-Graph mentre gli operatori che permettono
di passare da uno stato all'altro sono particolari operazioni di inserimento
e rimozione di azioni dal piano parziale corrente valutate mediante una
funzione costo. Quindi uno stato Goal è un sottografo rappresentante
un piano completo e consistente.
L'insieme delle azioni che possono essere aggiunte o rimosse è
determinato dalle inconsistenze presenti nel sottografo cioè dalle
relazioni di mutua esclusione e dai fatti non supportati. In particolare
definiamo:
Action Subgraph A è un sottografo del
Planning-Graph tale che se un nodo azione appartiene ad A allora:
- tutti i nodi e gli archi precondizione dell'azione appartengono ad A
- tutti i nodi effetti additivi e gli archi additivi dell'azione sono in
A
Solution Subgraph S è un Action subgraph tale
che:
- tutti i nodi goal sono supportati
- ogni nodo precondizione di ogni nodo azione è supportato
- non esistono relazioni di mutua esclusione tra coppie di nodi azione
Gli algoritmi di ricerca locale non esaminano lo spazio di ricerca
esaustivamente, ma solo delle zone dove si ritiene più probabile
trovare la soluzione. In particolare essi tendono a spostare il proprio
stato verso la regione di ammissibilità. Essi sono caratterizzati
da:
-
Spazio di ricerca: E' lo spazio all'interno del quale gli algoritmi
di ricerca operano. Non deve essere troppo grande, ma nel contempo deve
contenere tutte le soluzioni
-
Relazione di vicinato: Deve permettere di connettere elementi dello
spazio di ricerca.
-
Funzione costo: Viene applicata agli elementi del vicinato per determinare
quale sarà il prossimo ad essere esaminato
-
Determinazione dello stato iniziale
Tornando al Planning-Graph la ricerca locale è basata su due fasi:
-
INIZIALIZZAZIONE: Nel livello iniziale dell'action-subgraph vengono
inserite tutte le azioni del piano e le no-op non mutuamente esclusive
con esse le cui precondizioni sono supportate. A questo punto si itera
il procedimento per gli istanti di tempo successivi. Il piano in questione
sarà caratterizzato da un certo numero di istanti temporali e quindi
il rispettivo Planning-Graph avrà un corrispondente numero di livelli.
Se al livello finale una coppia di nodi goal risultano mutuamente esclusivi
il Planning-Graph sarà espanso ulteriormente finché tutti
i goal saranno non mutuamente esclusivi tra loro.
-
FASE DI RICERCA: Una volta completata l'inizializzazione la fase
di ricerca sceglierà casualmente un'inconsistenza dell'action-subgraph
corrente. Se l'inconsistenza scelta è un fatto possiamo per rimuoverla
o aggiungere un nodo azione che la supporti oppure cancellare un'azione
connessa a tale nodo da un effetto cancellante. Se l'inconsistenza scelta
è un'azione in mutua esclusione con un'altra possiamo rimuovere
una delle azioni. Notiamo che quando aggiungiamo o rimuoviamo un
nodo azione dal Planning-Graph si aggiungono o rimuovono anche gli archi
che collegano tale nodo con le corrispondenti precondizioni ed effetti
nel Planning-Graph. L'aggiunta di un nodo azione potrebbe comunque provocare
l'introduzione di altri inconsistenze. Per questo la scelte delle azioni
da introdurre deve essere oculata cioè deve essere guidata da una
funzione obiettivo.
L'organizzazione del programma
GPG (Greedy Planning Graph) è un algoritmo per
l'adattamento e la generazione di piani che utilizza ricerca locale e sistematica
(IPP).
La parte di GPG che si occupa dell'adattamento di piani mediante ricerca
locale è contenuta principalmente in WALKGRAPH.C, mentre
le strutture dati sulla quale essa si basa sono nella corrispondente libreria
WALKGRAPH.H.
Per una migliore comprensione delle modifiche fatte illustriamo brevemente
lo scopo delle principali funzioni usate nella ricerca locale (molte di
esse sono appunto state modificate da noi):
-
WALK_IPP: E' la funzione principale che si occupa di gestire le
varie modifiche fatte al piano. Essa inizializza il planning-graph (INITIALIZE)
e usa altre funzioni (tra le quali CHOOSE_ACT_FA) per la modifica
del piano; se dopo un certo numero di FLIPS (cioè di modifiche)
non si è ancora giunti alla soluzione provvede a riiniziare da capo
(RESTART) cioè rifare una nuova inizializzazione del piano e ritentare
altre modifiche. Se dopo un certo numero di RESTART non si è ancora
giunti alla soluzione allora la funzione dichiara fallimento.
-
CHOOSE_ACT_FA: E' la funzione è richiamata da WALK_IPP
e si occupa semplicemente di scegliere casualmente un fatto o un'azione
tra quelli falsi. A questo punto comunica la sua scelta a FIX
-
FIX: E' una delle funzioni più importanti in quanto essa
si occupa di:
-
Esaminare il fatto o l'azione: Se si tratta di un fatto verifica
che sia realmente falso e che sia precondizione di qualcosa (se non è
precondizione di niente non ci interesserà renderlo vero); se si
tratta invece di un'azione esamina che tutte le sue precondizioni siano
soddisfatte e non sia mutuamente esclusiva con altre azioni. Se il fatto
o l'azione non si rivelano falsi li rimuove dalle liste che tengono conto
rispettivamente dei fatti e delle azioni false ed esce.
-
Definizione del vicinato: Mediante la funzione CHOOSE_ACTIONS
definisce
l'insieme di azioni che possono rimuovere l'inconsistenza. Se non ci sono
azioni in grado di farlo ritorna errore.
-
Pesa il vicinato: Chiamando la funzione FIND_MIN individua
l'elemento migliore del vicinato.
-
Scelta del vicino: Se tutto il vicinato ci fa peggiorare con una
certa probabilità p scegliamo casualmente un elemento del
vicinato mentre con probabilità 1-p scegliamo il migliore
(se ci sono più vicini migliori scegliamo casualmente uno di essi).
Se esiste qualche elemento del vicinato che ci fa migliorare con probabilità
p'
sceglieremo casualmente uno di questi elementi mentre con probabilità
1-p'
scegliamo il migliore (se ci sono più vicini migliori scegliamo
casualmente uno di essi).
-
FIND_MIN: Trova l'azione tra i vicini con più basso costo
inserendo i vicini in un'apposita lista. Per individuare il costo di un'azione
usa un'altra importante funzione chiamata ACTION_COST. Oltre a ciò
deve individuare altri parametri utili a FIX come ad esempio il costo minore,
il numero di azioni con costo minore di zero (cioè che migliorano
la situazione) e, se ci sono più azioni ottime, il loro numero.
-
ACTION_COST: Questa funzione ha il compito di definire il costo
per l'inserimento o la rimozione di un'azione.
-
INSERT_REMOVE_ACTION: E' l'azione che si occupa effettivamente di
inserire o rimuovere l'azione. Nel caso l'azione non sia già presente
nel piano dovremo inserirla altrimenti eliminarla. Essa deve occuparsi
di aggiornare i fatti precondizione della nostra azione, i parametri che
tengono conto delle relazioni di mutua esclusione e i fatti effetti dell'azione.
-
INITIALIZE: Inizializza il grafo inserendo varie azioni secondo
alcune diverse modalità da specificare su riga di comando:
-
Inizializzazione di tipo 0: Si parte dal livello GOAL-1 e si va
via via verso i livelli inferiori inserendo casualmente delle azioni che
hanno come effetti additivi le precondizioni non soddisfatte del livello
superiore
-
Inizializzazione di tipo 1: Si parte dal livello GOAL-1 e si va
via via verso i livelli inferiori inserendo le migliori azioni che risolvono
una delle inconsistenze frutto di precondizioni non soddisfatte del livello
superiore
-
Inizializzazione di tipo 2: Si parte dal livello GOAL-1 e si va
via via verso i livelli inferiori inserendo la prima azione che si trova
in grado di risolvere le inconsistenze causate da precondizioni non soddisfatte
del livello superiore
-
Inizializzazione di tipo 3: E' un inizializzazione RANDOM cioè
dove si introducono a caso alcune azioni (si avvale della funzione iniz_random)
-
VERIFY_PLAN: E' una funzione che viene richiamata quando si ha apparentemente
trovato una soluzione per verificare la sua correttezza. Per fare ciò
memorizza le azioni (comprese le noop) presenti nella soluzione, cancella
tutto il piano e lo ricostruisce inserendo le azioni una per volta. Se
si manifesta una inconsistenza comunica che la soluzione trovata non è
corretta altrimenti valida il piano.
In particolare il nostro lavoro ha portato all'analisi e sperimentazione
di modifiche all'algoritmo GPG-LS scritte in linguaggio C e descritte approfonditamente
nella
Relazione,
Le modifiche apportate
Sono state implementate quattro innovazioni:
|
