S. Rizzi. Agenti autonomi: problematiche di pianificazione, esplorazione e clustering. PhD Thesis, february 1996.

Introduzione

I risultati ottenuti nello sviluppo di sistemi artificiali in grado di esibire comportamenti giudicati intelligenti da un osservatore umano, sono tuttora di gran lunga inferiori alle originarie aspettative dell'Intelligenza Artificiale (IA). Tuttavia, essi hanno contribuito a far luce sull'importanza che rivestono strumenti di ragionamento logico-deduttivo e appropriati formalismi di rappresentazione della conoscenza nella risoluzione di problemi.

Uno dei settori in cui le tecniche di IA possono fornire un importante contributo e' senz'altro quello degli Agenti Autonomi (AA) che, in modo informale, possono essere definiti come robot flessibili comprendenti attuatori, sensori, strumenti di calcolo e attrezzature ausiliarie, in grado di eseguire una varieta' di compiti utili all'uomo in condizioni non prevedibili a priori. Gli AA sono concepiti per operare in ambienti a elevato rischio quali impianti chimici e nucleari, o inadatti all'uomo quali profondita' marine, stazioni spaziali, zone desertiche; in generale, essi permettono di svolgere compiti faticosi e ripetitivi in condizioni non stazionarie. I piu' significativi progetti di ricerca in questo campo hanno condotto alla realizzazione della serie di robot mobili HERMIES, dei MOBOTS del MIT e del sistema di navigazione Dolphin alla Carnegie Mellon University.

Lo sviluppo di un AA richiede necessariamente, oltre a una adeguata tecnologia robotica, di mutuare conoscenze da diverse aree dell'IA, quali l'apprendimento automatico, la rappresentazione della conoscenza, il ragionamento in condizioni di incertezza, il planning. In particolare, la continua interazione con un ambiente esterno enfatizza problematiche spesso assenti nelle applicazioni confinate in laboratorio. Tra queste, il mantenimento della corrispondenza tra la rappresentazione interna degli oggetti e le entita' del mondo reale (symbol grounding), la stretta connessione tra attuatori e sensori, necessaria per acquisire selettivamente informazione dall'ambiente, e i vincoli temporali imposti dalle contingenze esterne.

Organizzazione del lavoro

Una piena autonomia puo' essere raggiunta solo grazie alla capacita' di muoversi liberamente. Tra i diversi tipi di movimenti che un agente puo' effettuare (ad esempio ruotare su se stesso per inquadrare una certa porzione di ambiente con una telecamera, oppure azionare un braccio meccanico per afferrare un oggetto), e' di particolare interesse ai fini di questa dissertazione lo spostamento tra luoghi distinti all'interno dell'ambiente, che chiamiamo navigazione; la navigazione e' fisicamente possibile per un agente grazie ad appropriati attuatori, quali ruote o cingoli.

Un AA, chiamato a svolgere compiti che richiedono navigazione, deve essere capace di un comportamento reattivo che gli permetta ad esempio di evitare gli ostacoli imprevisti e gli altri agenti eventualmente presenti nell'ambiente; d'altro canto, esso deve essere in grado di pianificare a grandi linee i percorsi da compiere per raggiungere mete specifiche. Sia il comportamento reattivo sia la pianificazione di alto livello sono basati su una descrizione dell'ambiente; essi hanno pero' esigenze profondamente diverse. Il comportamento reattivo necessita di stabilire una ben radicata corrispondenza tra le entita' del mondo reale e la loro rappresentazione interna, e richiede quindi informazioni sensoriali locali. D'altronde, un eccessivo livello di dettaglio nella descrizione puo' risultare dannoso per la pianificazione di percorsi, che puo' essere portata a termine in modo piu' efficace sulla base di una rappresentazione simbolica dell'ambiente.

Nel capitolo 2 viene descritta un'architettura multi-strato per la rappresentazione di ambienti orientata alla navigazione; ciascuno strato si occupa di gestire il movimento dell'agente secondo una specifica astrazione, e rappresenta di conseguenza l'ambiente al livello di dettaglio e tramite il formalismo piu' consoni. Le relazioni intercorrenti tra i diversi strati dell'architettura sono riconducibili alle tre primitive di astrazione: classificazione, generalizzazione, aggregazione. Particolare rilevanza riveste la primitiva di aggregazione, la cui applicazione porta a partizionare l'ambiente in un insieme di regioni (cluster) connesse tra loro attraverso dei "passaggi". Il partizionamento puo' essere utilizzato per decomporre i compiti di navigazione in due livelli: a livello intra-cluster ogni regione e' vista come un "mondo a parte", e la dettagliata conoscenza disponibile e' idonea per lo svolgimento di compiti di navigazione a breve raggio; a livello inter-cluster, invece, la conoscenza delle caratteristiche globali di ogni regione e dei passaggi che collegano le diverse regioni permette di condurre a termine efficacemente i compiti a lungo raggio.

Nel capitolo 3 verranno illustrate le problematiche connesse alla formulazione e alla risoluzione di problemi di pianificazione di percorsi sull'architettura multi-strato proposta. In particolare verra' descritto un algoritmo, basato su tecniche di decomposizione divide-et-impera, che calcola un cammino ottimale per la visita di un insieme di risorse nel rispetto di vincoli temporali e di precedenza.

Il problema dell'esplorazione e' di interesse focale per agenti chiamati a portare a termine compiti di navigazione all'interno di ambienti la cui descrizione dettagliata non sia nota a priori. In questi casi l'agente deve infatti apprendere le informazioni che gli sono necessarie "sul campo", muovendosi nell'ambiente e interpretando i dati sensoriali acquisiti. Il capitolo 4 affronta questa problematica, definendo il concetto di profilo di esplorazione e proponendo un semplice algoritmo di esplorazione che consente di acquisire in modo efficiente e mirato la conoscenza sull'ambiente a uno specifico livello di astrazione.

L'identificazione di cluster in ambienti strutturati, per i quali siano note a priori le tipologie degli oggetti che si possono incontrare, si puo' basare su una meta-conoscenza di aggregazione che consenta di individuare regioni significative. Ad esempio, in un ambiente casalingo, i cluster possono corrispondere alle diverse stanze; il passaggio da una stanza all'altra coincide con l'attraversamento di una soglia, e puo' quindi essere riconosciuto. Nel caso di ambienti non strutturati, sui quali non si hanno informazioni a priori di nessun tipo, i cluster devono essere individuati sulla base di altri criteri. Nel capitolo 5 viene inquadrato il problema del clustering by discovery, ovvero della formazione di cluster durante l'esplorazione di un ambiente non noto. Vengono poi presentati tre diversi approcci al problema, di cui uno basato su tecniche genetiche.

Le problematiche fino a qui introdotte sono affrontate e risolte con riferimento a un singolo agente. Nell'ambito specifico delle metodologie di risoluzione di problemi di pianificazione ed esplorazione, e' invece di estremo interesse valutare l'impatto dell'utilizzo contemporaneo di piu' agenti; l'approccio multi-agente consente infatti, tramite il raggiungimento di un elevato grado di coordinazione, di portare a termine compiti di entrambi i tipi in tempi significativamente piu' ridotti. Il capitolo 6 e' dedicato alla descrizione di strategie per l'esplorazione multi-agente di ambienti sconosciuti, e mostra in particolare come un soddisfacente grado di cooperazione possa essere raggiunto attraverso la formazione dinamica di squadre di agenti. Il problema della pianificazione multi-agente e' invece discusso in termini generali nel capitolo 7 dove, accanto alle conclusioni del lavoro, vengono delineate le linee future di ricerca.