Routing adattativo dinamico: un approccio basato su agenti e stigmergia

I problemi di instradamento (o routing) di veicoli sono da sempre oggetto di ricerche. Una cospicua percentuale degli investimenti di un impresa finisce nel reparto di logistica e un altrettanta cospicua percentuale del prezzo dei prodotti che tale azienda vende è dovuta ai costi di trasporto.
Il routing però non è soltanto un problema interessante dal punto di vista imprenditoriale. La capacità di scegliere un percorso all'interno di un ambiente modellabile come un grafo è un operazione che interessa ogni attività umana ogni giorno. Pensiamo ad esempio a taxi,
autobus, corrieri, postini, ma anche situazioni che non coinvolgono direttamente la rete stradale: la costruzione di un percorso turistico in un museo o l'instradamento di pacchetti attraverso la rete Internet.
Data la fondamentale importanza di questa classe di problemi, discipline scientifiche come la Ricerca Operativa hanno studiato e messo a punto potenti algoritmi per l'instradamento e un framework concettuale su cui applicarli: la teoria dei grafi.
Gli algoritmi di Ricerca Operativa, e più in generale l'approccio che essa segue per risolvere i problemi di routing, non sono l'unico e il solo strumento disponibile per la costruzione di soluzioni.
Recentemente due paradigmi si sono fatti largo tra la comunità scientifica: il paradigma ad agenti e la metafora stigmergica. Il primo, nasce nell'ambito della computer science come evoluzione del paradigma ad oggetti, estendendo le forti limitazioni concettuali di questa ultima. Il paradigma ad agenti utilizza principalmente delle astrazioni, chiamate per l'appunto agenti, che ben si adattano ad essere applicate in un vasto ed eterogeneo numero di domini scientifici (scienze sociali, economia, . . . ). La caratteristica fondamentale di un agente è l'autonomia; un agente ha infatti il pieno controllo del suo flusso di esecuzione, diversamente dagli oggetti che possono solo invocare metodi (questa proprietà di ricorda facilmente con l'espressione "Agents can say No!"). In prima battuta, si può pensare ad un agente come ad un entità task-oriented cioè un entità che autonomamente e attivamente persegue il raggiungimento di un obiettivo.
Il secondo paradigma deriva direttamente dallo studio del comportamento degli insetti. La stigmergia è infatti il meccanismo che le grandi comunità di insetti sociali usano per coordinarsi e raggiungere obbiettivi inarrivabili senza la cooperazione di ogni singolo individuo della collettività. Benché questo sistema promuovi la cooperazione, non significa che i singoli componenti del sistema siano consapevoli di tale risultato. Ogni singola individualità di per sé non è affatto intelligente e non ha assolutamente i mezzi per poter mettere in pratica complessi algoritmi di problem solving o istituire e orchestrare un sistema basato su intricate topologie organizzazionali. La stigmergia ha incuriosito enormemente diversi ricercatori, primi tra tutti alcuni studiosi di Ricerca Operativa fra i quali spiccano nomi italiani, proprio per queste caratteristiche: la possibilità di ottenere un comportamento (definito emergente) dell'intero sistema volto al raggiungimento di un obiettivo tramite semplici interazioni attuate dagli (inconsapevoli) componenti di tale sistema.
L'obiettivo di questa tesi è quindi unire insieme i due paradigmi, o meglio, cercare di esprimere la stigmergia tramite astrazioni e un formalismo tipici del paradigma Agent-Oriented per costruire infine un sistema software che realizzi il routing di agenti attraverso un grafo.
Come scopo addizionale, questa tesi si propone anche di esporre un framework che possa essere utile in futuro per la sintetizzazione di sistemi software basati sull'approccio ad agenti e stigmergia per la risoluzione di problemi su grafi.