Realizzazione di un algoritmo di pianificazione basato su euristiche che operano su modelli rilassati

xii
evidenziato miglioramenti in relazione sia al tempo richiesto per ottenere una 
soluzione sia alla capacità di risolvere i problemi all'aumentare della complessità 
degli stessi.  
La Parte I della tesi ha il compito di fornire al Lettore una panoramica dello stato 
dell’arte sugli argomenti prettamente inerenti questo lavoro. Nel Capitolo 1 si 
descrivono i Sistemi ad Agenti in generale  e i vari paradigmi connessi a questa 
branca dell’Intelligenza Artificiale.  Il Capitolo 2 tratta il comportamento proattivo di 
un Agente Intelligente, argomento intimamente connesso con il presente lavoro di 
tesi. Nel Capitolo 3 si descrive l’infrastruttura HW[] [ARMANO03A] al quale il 
pianificatore oggetto della tesi deve essere reso compatibile.  
La Parte II  è invece dedicata ai contenuti specifici e innovativi di questo lavoro. Nel 
Capitolo 4 si fornisce una panoramica sull’argomento della Pianificazione Euristica 
nello spazio degli stati, sull’importante formalismo STRIPS riguardante la specifica 
dei domini e dei problemi di pianificazione e sull’algoritmo A* con le sue peculiarità 
e la descrizione di una variante di esso. Nel Capitolo 5  si descrive formalmente la 
funzione euristica del pianificatore HSP [BONET-GEFFNER-01] e se ne fornisce una sua 
implementazione in pseudocodice.  Il Capitolo 6 è dedicato alla parte prettamente 
innovativa di questo lavoro e descrive la funzione euristica Look-Ahead e le 
considerazioni che hanno portato al suo studio.  Nel Capitolo 7 è presente una 
descrizione del sistema di pianificazione YAHP, implementato in questo lavoro di 
tesi. La descrizione degli esperimenti condotti sul nuova sistema e risultati di tali 
esperimenti sono riportati nel Capitolo 8. 
14
PARTE I - STATO DELL’ARTE 
15
1I SISTEMI AD AGENTI 
Per un crescente numero di applicazioni sono richiesti dei sistemi in grado di 
decidere autonomamente ciò di cui necessitano al fine di soddisfare gli obiettivi per i 
quali sono stati progettati. A questa particolare categoria appartengono gli Agenti. 
Gli Agenti che devono poter agire in modo robusto in ambienti complessi, 
imprevedibili ed in continua e rapida evoluzione, in cui vige un’elevata probabilità 
che le azioni possano fallire, sono definiti intelligenti e, talvolta, autonomi. 
L’interesse verso lo studio e la progettazione dei sistemi ad Agenti Intelligenti 
Autonomi ha subito una forte crescita verso la fine degli anni ’80. Da quel periodo i 
temi di discussione sono stati molteplici, tra cui la definizione stessa di agente e delle 
proprietà che caratterizzano i sistemi di cui fanno parte. 
Potrebbe infatti sorprendere il fatto che non esista tuttora una definizione 
universalmente accettata del termine agente e che anzi vi siano dibattiti e 
controversie sul tema. La motivazione principale è legata al fatto che le varie 
caratteristiche che un agente dovrebbe presentare assumono diversi livelli di 
importanza a seconda del contesto (dominio) in cui esso opera. Ciononostante, i 
ricercatori del campo hanno scelto di affidarsi ad una definizione informale di agente 
(comunque necessaria, onde evitare la perdita di significato del termine a causa del 
suo abuso), cercando di trovare un accordo sulle proprietà fondamentali che esso 
deve possedere, prima tra tutte la nozione di autonomia. 
1.1 Generalità 
Secondo la definizione di Wooldridge, un Agente è un sistema (hardware e/o 
software) capace di operare autonomamente in un ambiente in modo da soddisfare le 
proprie specifiche di progetto. 
È però importante chiarire il concetto di autonomia, implicitamente richiamato nella 
definizione precedente, con il quale si intende l’abilità di svolgere un compito senza 
ricorrere all’intervento del progettista o ad altri sistemi esterni, mantenendo 
contemporaneamente il controllo del proprio stato interno e del suo significato. 
16
Da questo punto di vista, anche sistemi relativamente semplici possono essere 
classificati come agenti autonomi. Ad esempio, un termostato possiede un sensore  
rilevatore di temperatura con il quale è in grado di interagire con l’ambiente esterno, 
segnalando se la temperatura di un ambiente è ottimale oppure no. Più in generale, 
un sistema di controllo automatico è in grado di garantire il comportamento 
desiderato anche in condizioni di variabilità ambientali. Nessuno però si 
permetterebbe di classificare i due sistemi come intelligenti! Pertanto le definizioni 
precedenti acquistano maggiore significato quando aumenta la complessità delle 
funzioni da svolgere. Ma non basta. Per poter parlare di agenti autonomi che siano 
anche intelligenti occorre aggiungere alle caratteristiche già descritte la nozione di 
flessibilità. 
Un Agente Intelligente deve operare in un determinato ambiente in modo flessibile 
per poter conseguire i propri obiettivi sia durante l’acquisizione di informazioni 
attraverso un sistema di percezione, sia durante l’esecuzione di azioni attraverso un 
sistema attuatore. La flessibilità di comportamento viene quindi mostrata sia nei 
confronti dell’ambiente esterno che degli obiettivi da conseguire. Ciò consente nel 
primo caso la variabilità del contesto applicativo e nel secondo la possibilità di 
cambiare gli obiettivi o di aggiungerne di nuovi; in altre parole, non occorre dire ad 
un Agente Intelligente che cosa fare o come farlo, ma cosa deve ottenere come 
risultato finale della propria attività. 
Il contesto applicativo può essere un ambiente fisico reale (come nel caso di agenti 
robot), una simulazione (come nel caso di un videogioco) o un ambiente puramente 
software (come il mondo di internet, in cui si parla di software agents). Le percezioni 
e le azioni varieranno da caso a caso; ad esempio per un agente software 
coincideranno con delle chiamate a funzioni o metodi. 
L’enfasi che è stata data all’integrazione con l’ambiente, dal quale vengono ricevute 
le percezioni e sul quale il sistema agisce modificandolo, ha dato luogo all’attributo 
“situato” (situated), divenuto specifico e comune nel linguaggio dell’intelligenza 
artificiale. In questo senso un Sistema Esperto non è un agente, perché è svincolato 
dall’ambiente e, sebbene possieda capacità di ragionamento autonomo, non agisce 
autonomamente, ma si comporta come una specie di consulente di un utente umano, 
da cui riceve delle domande e a cui si sostituisce nelle azioni. 
17
1.2 Caratteristiche e proprietà distintive 
La definizione esatta delle proprietà che caratterizzano un Agente Intelligente rimane 
una questione ancora irrisolta; tuttavia, sono state individuate alcune caratteristiche, 
pressoché universalmente accettate, che devono essere presenti nel corredo 
comportamentale di questi sistemi, ovvero: 

 Proattività: viene anche indicata come comportamento “goal-oriented”, con 
cui si intende la capacità di porre in atto un comportamento che conduca al 
raggiungimento dell’obiettivo dato. In altre parole gli Agenti Intelligenti 
prendono l’iniziativa per soddisfare i loro obiettivi. Fondamentale a questo 
scopo è la capacità di sintetizzare ed eseguire azioni o sequenze di azioni 
(denominate piani) in funzione dell’obiettivo (goal) e della situazione di 
partenza (stato iniziale). Ricade nel comportamento proattivo anche la 
capacità di modificare, quando possibile, i propri piani, adattandoli alle 
mutevoli condizioni di un ambiente dinamico. 

 Autonomia: il significato di questa proprietà si chiarisce non tanto fornendo 
un’interpretazione del concetto di autonomia quanto indicando in che cosa un 
Agente è autonomo, e quali sono i limiti della sua autonomia. A questo 
proposito sono presenti due interpretazioni, una debole ed una forte; la prima 
(che è la più comunemente usata in letteratura) si riferisce all’autonomia 
dell’Agente nella scelta ed esecuzione delle azioni per il raggiungimento di 
un obiettivo assegnato dall’esterno; la seconda (si veda [CASTELFRANCHI 94]) è 
di più radicale accezione e prevede che venga effettuata in modo autonomo 
anche la scelta degli obiettivi, prospettando in tal modo una sorta di vita 
propria del sistema. 

 Reattività: indica la capacità di percepire l’ambiente esterno, per individuare 
eventi di interesse, siano essi pericoli od opportunità favorevoli, e reagire in 
tempo ragionevole ai cambiamenti che si verificano mettendo in atto 
opportuni comportamenti. 

 Capacità sociale: indica la possibilità di interazione con altri Agenti. Infatti, 
le applicazioni della tecnologia ad Agenti non si limitano ad un'unica entità 
che agisce singolarmente, ma fanno riferimento al più ampio contesto dei 
18
Sistemi MultiAgente, in cui coesistono ed operano più entità autonome. Il 
livello di interazione differisce tra un sistema e l’altro; si va da una relativa 
autosufficienza a forme complesse di competizione e cooperazione in vista di 
obiettivi comuni o divergenti. Esistono sostanzialmente due approcci nella 
progettazione di sistemi ad agenti. Un primo approccio focalizza sulle 
caratteristiche del singolo agente (la microarchitettura), mentre il secondo si 
occupa di definire i protocolli di interazione (livello sociale o 
macroarchitettura) ed è tipico di settori come la DAI (Distributed Artificial 
Intelligence) che studia metodi di cooperative problem-solving. È comunque 
universalmente accettato che un Agente debba saper interagire con altri 
Agenti e un’immediata conseguenza di questo è la necessità di definire un 
opportuno linguaggio di comunicazione. 
Vale la pena di osservare che queste proprietà sono molto più esigenti di quanto 
possa sembrare a prima vista. Se consideriamo la proattività, e quindi il 
comportamento rivolto ad un obiettivo, non è difficile pensare ad un sistema in grado 
di esibirla, basti pensare ad una comune procedura in un linguaggio di 
programmazione. Va tutto bene nei modelli funzionali, cioè che dato un ingresso x, 
producono in uscita una qualche funzione f(x) dell’ingresso, di cui un esempio 
classico sono i compilatori. Questi modelli fanno però delle assunzioni molto 
restrittive, in particolare suppongono che l’ambiente esterno non cambi durante 
l’esecuzione della procedura. In caso contrario, il comportamento del sistema può 
essere indefinito e il sistema può bloccarsi (o, come si dice, entrare in crash). 
All’aumentare della complessità dell’ambiente, questo tipo di assunzioni non sono 
accettabili. Diversamente, un agente deve essere reattivo, quindi rispondere alle 
variazioni del suo ambiente che provocano cambiamenti nei suoi obiettivi o nelle 
assunzioni su cui si basano le procedure al momento dell’esecuzione. 
Come è stato accennato, non è difficile realizzare sistemi puramente proattivi e 
nemmeno sistemi puramente reattivi, ovvero che reagiscono continuamente al loro 
ambiente. Ciò che invece si rivela articolato è la costruzione di un sistema che 
bilancia efficacemente i due comportamenti. 
19
Inoltre, anche l’abilità sociale, altra componente dell’agire in modo autonomo e 
flessibile, presenta la sua complessità. Infatti, non si tratta semplicemente di uno 
scambio binario di informazioni, cosa che fanno quotidianamente milioni di 
computer nel mondo, ma di un insieme di attività più sofisticate di cooperazione, 
condivisione di obiettivi, comprensione e riadattamento di esperienze altrui, tutte tra 
loro interconnesse. 
In definitiva, gli Agenti Intelligenti sono entità dotate di un comportamento flessibile, 
in grado di adattarsi ai cambiamenti dell’ambiente in cui operano, che possono 
conseguire obiettivi complessi in modo autonomo e presentano una capacità sociale 
che può arrivare alla collaborazione di più agenti verso un obiettivo comune. 
1.3 Classificazione degli ambienti applicativi 
Il problema principale che deve risolvere un agente è quello di decidere quali azioni 
eseguire per soddisfare al meglio i propri obiettivi. La complessità del processo 
decisionale dipende fortemente dalle caratteristiche dell’ambiente di riferimento. 
È diventata consuetudine classificare la tipologia di un ambiente in base alle seguenti 
proprietà [RUSSELL-AND-NORVIG-95]: 

 Accessibile/non accessibile: un ambiente è accessibile per un Agente se 
questi può ottenere in ogni istante tutte le informazioni che sono necessarie al 
corretto svolgimento della sua attività. Si noti che l’attribuzione di questa 
caratteristica va fatta in relazione all’informazione di interesse per l’Agente. 
Purtroppo questa proprietà viene meno in ambienti anche solo moderatamente 
complessi. Tipicamente gli ambienti applicativi sono solo parzialmente 
accessibili. Cause frequenti di parziale accessibilità negli ambienti fisici sono 
la limitatezza del raggio di percezione dell’Agente rispetto all’estensione 
dell’ambiente, e la presenza di ostacoli fisici alla percezione (muri). La 
parziale accessibilità dell’ambiente viene indicata anche come conoscenza 
incompleta sullo stato. 

 Statico/dinamico: un ambiente è statico per un Agente se la sola causa delle 
sue variazioni è costituita dalle azioni che l’Agente vi compie. La staticità 
20
viene meno in un ambiente multi-agente (in cui più processi sono 
contemporaneamente attivi) o comunque in presenza di fattori di evoluzione 
esogeni all’Agente stesso. In generale quindi l’Agente non ha il controllo 
totale dell’environment, ma può solo influenzarne i cambiamenti. Il mondo 
fisico è un ambiente fortemente dinamico. 

 Azioni deterministiche/non deterministiche: l’ipotesi di azioni deterministiche 
implica che l’Agente conosca perfettamente l’esito delle proprie azioni 
sull’ambiente. Un’azione è non-deterministica se il suo modello non ne 
comprende alcuni effetti, o non specifica le condizioni sotto le quali tali 
effetti si verificano. Il carattere non-deterministico di un’azione può 
discendere dall’intrinseco modello probabilistico di essa (si pensi al lancio di 
una moneta) o dall’incompletezza del modello di essa contenuto nell’Agente. 
In realtà si può pensare di ricondurre queste due circostanze al secondo caso, 
se si pensa che il modello probabilistico di un’azione deriva dalla mancanza, 
o dall’eccessiva complessità di un modello del tipo causa-effetto. Il non-
determinismo delle azioni viene indicato anche come conoscenza incompleta 
sulle azioni. Il mondo fisico nel suo insieme può essere considerato come non 
deterministico. 

 Discreto/Continuo: un ambiente è discreto se esiste un numero finito e 
prefissato di azioni e percezioni. Un esempio classico è il gioco degli scacchi, 
mentre la guida di un taxi è un esempio di ambiente continuo. 

 Complessità: infine, è consuetudine classificare i domini applicativi in base al 
loro grado di complessità: esso si può misurare in base al carattere più o 
meno articolato delle azioni a disposizione, ed al numero complessivo di stati 
che l’ambiente può assumere.  
Un altro parametro comunemente introdotto è la proprietà di determinismo di un 
ambiente; in un certo senso essa può considerarsi come una proprietà derivata, dato 
che è possibile dedurla una volta assegnate le altre. 
Possiamo utilizzare la seguente definizione di ambiente deterministico: un ambiente 
è deterministico dal punto di vista di un Agente che vi opera, se questi può sempre 
prevederne autonomamente l’evoluzione ed i cambiamenti [RUSSELL AND NORVIG 95].  
21
In base a tale definizione, un ambiente può risultare non-deterministico agli occhi di 
un Agente perché non interamente accessibile (se non si conosce esattamente lo stato 
in cui ci si trova non se ne possono prevedere i cambiamenti), dinamico (il 
comportamento di altri agenti ed eventi esogeni rendono imprevedibile lo stato futuro 
dell’ambiente) o anche qualora l’Agente non abbia il controllo e la conoscenza 
completa delle proprie azioni. In realtà se un ambiente è sufficientemente complesso, 
il fatto che sia deterministico non è di grande aiuto: ai fini pratici esso appare di fatto 
non-deterministico [WOOLDRIDGE 99]. 
È importante rimarcare il fatto che le proprietà sopra descritte non intendono dare 
una classificazione dell’ambiente in termini assoluti, bensì dal punto di vista 
dell’Agente che vi opera. 
1.4 Architetture per Sistemi ad Agenti 
Una volta definite le principali caratteristiche comportamentali di un Agente, non è 
affatto immediato individuare un’architettura o delle tecnologie che presentino dei 
vantaggi in senso assoluto rispetto alle altre: ogni scelta è il risultato di un 
compromesso fra potere di modellazione ed efficienza di comportamento. 
Quel che appare chiaro è la necessità di dotare tali sistemi di un sottosistema di 
percezione, un attuatore, un meccanismo di selezione delle azioni e di reazione ad 
eventi esogeni. Tali caratteristiche possono essere realizzate tramite il ricorso a 
soluzioni di rappresentazione, architetturali e tecnologiche anche molto differenti, ed 
infatti molto differenti sono le soluzioni proposte nel corso degli anni dai ricercatori 
AI. È possibile individuare alcuni fondamentali tipi di approccio alla progettazione 
pratica di sistemi intelligenti: uno basato sulla logica (o deliberativo), uno basato su 
riflessi (o reattivo), le diverse soluzioni ibride fra i due, ed infine l’approccio BDI. 
1.4.1 Soluzioni basate sulla logica: architetture deliberative 
Si tratta dell’approccio più antico, tipico dell’Intelligenza Artificiale simbolica, e 
consiste nel considerare un Agente Intelligente come un particolare tipo di sistema 
basato sulla conoscenza. Esso prevede che l’Agente possieda una rappresentazione 
22
esplicita del mondo, espressa come un insieme di formule logiche, un sistema a 
frame o una rete semantica, e tramite una qualche forma di manipolazione simbolica 
possa: 

 aggiornare la propria conoscenza sul mondo in base alle percezioni ricevute 
(in questa fase può anche essere compresa la deduzione di proprietà del 
mondo non evidenti) 

 decidere autonomamente, in base alle informazioni disponibili, le azioni da 
eseguire per il raggiungimento del proprio obiettivo; 

 aggiornare la propria conoscenza in base alle azioni eseguite.
Il processo di manipolazione simbolica per eccellenza è l’inferenza, e fu quello 
adottato inizialmente [GREEN 69]; il suo utilizzo però si rivelò presto inadatto a causa 
della sua intrattabilità (l’inferenza in logica del prim’ordine è semi-decidibile; per le 
sue estensioni modali il problema è drammaticamente amplificato), che lo rende 
impraticabile in ambienti dinamici con un tempo fra una variazione e l’altra inferiore 
al tempo richiesto dal processo di inferenza. Il processo di inferenza puro venne 
prima sostituito dal Calcolo delle Situazioni, che però rivelò anch’esso delle gravi 
carenze (il famigerato problema del frame), e successivamente, all’inizio degli anni 
’70, dalla Pianificazione [FIKES-AND-NILSSON-71]. Lo svantaggio derivante 
dall’utilizzo di metodi dedicati come la pianificazione è la perdita del pieno potere 
espressivo della logica del prim’ordine; inoltre con essi è possibile realizzare solo il 
comportamento goal-driven. 
Ancora oggi il principale problema connesso alla realizzazione di una architettura 
deliberativa è la complessità computazionale; vi sono inoltre altri problemi ancora 
aperti, come la mappatura tra percezioni provenienti dai sensori e rappresentazione 
simbolica interna. 
1.4.2 Soluzioni basate sui riflessi: architetture reattive 
L’approccio reattivo nasce nella seconda metà degli anni ’80 come reazione ai 
problemi di intrattabilità ed efficienza  tipici delle architetture logiche. Viene