Torna alla Home Page del corso
Torna alla pagina degli Elaborati
Successiva
|
|
|
|
|
|
|
|
|
|
INTRODUZIONE
Lo scopo di questo lavoro consiste nella definizione di un indice in grado di rappresentare efficacemente le differenze esistenti tra due piani. Il confronto potrebbe essere molto utile sia nella valutazione di due differenti pianificatori applicati al medesimo problema che nello studio dei piani proposti da un unico pianificatore al variare del problema sottopostogli.
Per chiarezza nell'esposizione saranno utilizzati termini differenti per distinguere le operazioni che compongono il piano. Il termine Azione indicherà d'ora in poi un'operazione in se' e non vincolata all'appartenenza ad un piano. I piani sono composti da Istanze di azioni, in quanto in essi ogni azione puo' apparire piu' volte. Mentre esiste sempre una sola Azione di un certo tipo, in un piano esistono numerose Istanze, alcune delle quali rappresentanti la stessa Azione eseguita piu' volte.
Figura 1: Esempio di piani, istanze ed azioni.
La Figura 1 illustra una situazione tipica. I due piani sono composti da Istanze (rappresentate in minuscolo: a1,b,c,a2, ...) che rappresentano Azioni prese da un opportuno insieme predefinito (rappresentate in maiuscolo: A e' l'azione cui appartengono le istanze ai). All'interno di un piano le istanze sono ordinate da relazioni d'ordine parziale che vincolano temporalmente i tempi di esecuzione delle stesse. Affermeremo che "a12 precede b11" (indicato per brevita' con a12 --> b11) se esiste nel piano 1 una relazione indicante che a12 debba essere eseguita prima di b11. Analogamente esiste la relazione inversa rappresentata da "b12 segue a11" (b12 <-- a11). Due istanze potrebbero non essere in relazione tra loro se l'ordine di esecuzione relativo e' indifferente per l'attuazione del piano; in questo caso la relazione sara' indicata con un tratto (a12 -- b11), indicante che le due istanze possono essere eseguite contemporaneamente oppure indifferentemente prima l'una e poi l'altra. Le relazioni godono della proprieta' di transitivita' per cui se aRb e bRc allora aRc (R indica sia --> che <--). In un piano tutte le coppie di istanze sono tra esse in relazione; tuttavia per chiarezza di rappresentazione le relazioni derivabili per transitivita' non saranno disegnate.
Un primo grossolano confronto puo' essere fatto osservando le Azioni utilizzate da ciascun piano, in quanto se completamente differenti e' probabile che essi si riferiscano a domini diversi.
Molto piu' interessante risulta il confronto delle relazioni, in quanto tramite esse e' possibile analizzare i differenti comportamenti dei pianificatori. Una misura in questo senso e' fornita dalla valutazione del numero di relazioni differenti tra le istanze di un piano e quelle corrispondenti di un altro di riferimento. Per eseguire questo confronto e' necessario associare univocamente tutte le istanze di un piano con quelle dell'altro; puo' quindi essere necessario rimuovere dai piani alcune istanze (quelle che compaiono in un solo piano o piu' numerose).
Tutto cio' che si puo' concludere ignorando le relazioni riguarda la presenza di Istanze aggiuntive in un piano rispetto all'altro e l'esistenza di Azioni diverse; pertanto gli indici calcolati riguardano:
La seguente figura illustra i conteggi ed i calcoli relativi ai piani precedentemente illustrati:
Figura 2: Determinazione degli indici sulle azioni.
Per facilitare la lettura dei risultati e' preferibile normalizzare gli indici calcolati affinche' il loro valore ricada nell'intervallo [0,1] indipendentemente dai piani utilizzati. In particolare, N1 ed N2 possono essere divisi per il numero totale di Azioni presenti complessivamente nei due piani, mentre N3 per il numero totale di Istanze. In questo modo (1-N3') puo' essere usato per esprimere in percentuale quanto i due piani siano simili (a meno delle relazioni); ottenendo per il caso riportato una valore pari al 55%.