Swarm intelligence

La swarm intelligence, in italiano l'intelligenza di sciame, è un termine coniato per la prima volta nel 1988 da Gerardo Beni, Susan Hackwood e Jing Wang in seguito a un progetto ispirato ai sistemi robotici. Esso prende in considerazione lo studio dei sistemi auto-organizzanti, nei quali un'azione complessa deriva da un'intelligenza collettiva, come accade in natura nel caso di colonie di insetti o stormi di uccelli, oppure banchi di pesci, o mandrie di mammiferi.

colonia di formiche

«Chi è a governare? Chi è che dà ordini, che immagina cosa accadrà in futuro, elabora piani e mantiene l’equilibrio?»

(Maurice Maeterlinck)

Caratteristiche

Secondo la definizione di Beni e Watt la swarm intelligence può essere definita come: “Proprietà di un sistema in cui il comportamento collettivo di agenti (non sofisticati) che interagiscono localmente con l'ambiente produce l'emergere di schemi funzionali globali nel sistema”.

• ogni individuo del sistema dispone di “capacità limitate”;
• ogni individuo del sistema non conosce lo stato globale del sistema;
• assenza di un ente coordinatore (ad esempio in uno sciame di api, l'ape regina non coordina l'attività delle altre api).

Dalla biologia all'informatica

Robot insetto

Scelta del percorso più breve da parte delle formiche

Uno dei temi analizzati dai ricercatori si basa sull'analisi del comportamento in natura degli insetti rispetto alla collettività. In particolare, si prendono in esame sciami di api, oppure colonie di formiche. Stupisce come una tale organizzazione collettiva di alto livello scaturisca dalla somma delle più semplici azioni, come, ad esempio, quelle svolte da una colonia di formiche per difendere il territorio, costruire un nido perfettamente organizzato, ricercare fonti alimentari, il tutto senza avere un ente simbolico che li comandi. A differenza di organismi più complessi, come ad esempio i mammiferi, gli insetti hanno quantità molto limitata di intelligenza singola, che però, a livello di gruppo, presenta caratteristiche sorprendenti: è il caso della ricerca del cibo delle formiche. Ogni formica, mentre cammina, deposita sul terreno una sostanza chimica, il feromone. La scelta del percorso da seguire alla ricerca del cibo è guidata dall'intensità del feromone: più esso è intenso, più è probabile che venga scelta una determinata direzione; ma il feromone evapora nel tempo, quindi rimarranno "marcati" solo i percorsi usati più di frequente. In ambito informatico, la ricerca è interessata alla simulazione di un comportamento intelligente analogo a quello esibito da sciami di insetti. L'aspetto più interessante dei sistemi basati sulla swarm intelligence, rispetto ai sistemi tradizionali, è che l'insieme degli individui che lo compongono lavora senza un controllo centralizzato. Il comportamento collettivo osservabile è, quindi, il frutto delle semplici iterazioni che ha un singolo componente verso gli altri oppure verso l'ambiente.

I-Swarm

Microrobot

Il progetto I-Swarm (Intelligent Small World Autonomous Robots for Micromanipulation), di cui fanno parte 10 partner europei, rappresenta il primo tentativo di replicare un robot autonomo di dimensioni millimetriche con lo scopo di realizzare uno "sciame di microrobot". Tale sciame prende riferimento da ciò che viene in natura dando luogo a fenomeni di auto organizzazione. La swarm robotic (robotica di sciame) mira, infatti, alla programmazione di un grande gruppo di robot con il fine di organizzare comportamenti collettivi utili per lo scopo desiderato, evidenziando ciò che viene definita "intelligenza di sciame". La strategia adottata si basa sull'osservazione degli sciami in natura. I vantaggi principali sono i seguenti:

• auto-organizzazione;
• flessibilità;
• adattabilità (ambiente);
• robustezza del sistema.

Un microrobot prodotto durante un lavoro di tesi (Università Politecnica delle Marche)

In pratica prendono le migliori caratteristiche degli swarm. Grazie a recenti sviluppi della miniaturizzazione e della microtecnologia, è stato possibile riuscire a produrre ed assemblare "masse di micro robot". Questa è una caratteristica fondamentale in quanto i micro robot hanno bisogno di operare in gruppo, al fine dello svolgimento di un compito. In futuro, grazie a tale tecnologia, si potrà utilizzare la swarm robotic in vari ambiti, come ad esempio:

• monitoraggio ambientale (sia per quanto riguarda la sicurezza che per quanto riguarda l'esplorazione di luoghi inaccessibili all'uomo);
• esplorazione spaziale;
• assemblaggio di micro dispositivi;
• biomedicina.

Prototipi dell'I-Swarm

Attualmente nel progetto I-Swarm sono stati sviluppati alcuni prototipi di dimensioni 3 mm³ in fase di collaudo. Essi sono costituiti da alcuni moduli funzionali miniaturizzati e assemblati uno sopra l'altro collegati attraverso un circuito flessibile. Ricava un'energia attraverso la luce per mezzo di piccole celle solari miniaturizzate. Il movimento è affidato a delle microscopiche zampe composte da materiale piezo-elettrico che vengono azionate e comandate da un microprocessore integrato che ne determina anche la direzione di moto. Per comunicare, questi micro robot dispongono di un sistema di infrarossi che permette la trasmissione di informazioni sullo spostamento tra le singole entità dello sciame, è presente anche un'antenna che funge come sensore di contatto. Sebbene questi prototipi non sono ancora operativi, è importante sottolineare il fatto che sono molto importanti per quanto riguarda lo sviluppo di metodi di produzione d'assemblaggio di chip robot.

Stigmergia

"La stigmergia è una forma di comunicazione che avviene alterando lo stato dell'ambiente in un modo che influenzerà il comportamento degli altri individui per i quali l'ambiente stesso è uno stimolo." (J. Kennedy, R. C. Eberhart, "Swarm Intelligence", Morgan Kaufmann Publishers, 2001).

Il termine stigmergia fu introdotto dallo zoologo Pierre-Paul Grassè, al fine di spiegare il comportamento delle termiti durante la costruzione dei nidi; esso deriva dalle parole greche “stigma” ed “ergon”, cioè “segno” e “lavoro”, il che significa "lavoro guidato da stimoli". La stigmergia fornisce una visione ad alto livello in cui N agenti cooperano per raggiungere un qualche obiettivo, si ottiene quindi un meccanismo generale che relaziona il comportamento individuale con quello della colonia. La Stigmergia può essere attiva o passiva e in genere presenta le seguenti caratteristiche:

• Scalabilità;
• Tolleranza ai guasti;
• Adattabilità;
• Velocità;
• Modularità;
• Autonomia;
• Parallelismo.

La struttura fortemente parallela degli sciami, permette di sfruttare il numero degli individui, effettivamente disponibili ad ogni istante di tempo, capaci di percepire l'ambiente ed interagire con esso. La comunicazione mediata dall'ambiente è un esempio di stigmergia: dal momento che il peso della comunicazione non aumenta al variare delle dimensioni del gruppo, la stigmergia consente grande scalabilità, infatti la dimensione di uno sciame può variare senza che questo alteri significativamente la vita della colonia, per esempio nel caso di guasti o malfunzionamenti. In robotica, il coordinamento dei componenti stigmergici all'interno del sistema è gestito da un agente hardware intelligente (smart agent).

Stigmergia e tolleranza ai guasti

In ogni applicazione swarm, il “comportamento della colonia” dipende dalle interazioni fra i singoli individui che la compongono. Lo smart agent è in grado di percepire l'ambiente circostante e di prendere decisioni in merito al quantitativo di informazioni da trasferire. Esso è in grado di trasferire dati solo dalla propria memoria. Si ha una ‘'’stigmergia attiva'’', quando avviene un'esplicita movimentazione dei dati. Il carico di lavoro è distribuito in modo che il maggior numero possibile di enti disponibili possa essere coinvolto nel processo, di conseguenza si sfrutta al massimo la piattaforma computazionale ad ogni istante, riducendo i ritardi di elaborazione anche in presenza di elementi guasti. I comportamenti collettivi permettono di ottenere tolleranza ai guasti. Si utilizza l'algoritmo di cell exclusion. Sono stati sviluppati due meccanismi di cell exclusion. Uno di essi è il “bypass”: il componente guasto diventa “trasparente”, cosicché i dati provenienti dagli altri enti non possono essere caricati nella memoria del componente difettoso, rimanendo comunque disponibili per tutta la colonia. Il secondo meccanismo consiste nell'isolare completamente l'elemento guasto, bloccando le sue porte di I/O. In questo caso, il comportamento stigmergico è molto utile per sfruttare tutti i componenti sani del sistema, superando così le difficoltà legate al numero ridotto di componenti disponibili.

Algoritmi di Swarm

Le applicazioni di I-Swarm hanno dato vita a tre algoritmi fondamentali: ACO, PSO e FSO

ACO

Colonia di formiche

Lo studio sulla swarm intelligence ha portato alla formazione dell'algoritmo ACO (Ant Colony Optimization), introdotto per la prima volta nel 1992 da Marco Dorigo del Politecnico di Milano. Esso viene utilizzato per la risoluzione di problemi di complessa computazione. L'idea di base di questo algoritmo prende spunto dall'organizzazione di una colonia di formiche, si usa infatti un meccanismo di feedback positivo come una sorta di "feromone virtuale", per rafforzare quelle parti di soluzione che contribuiscono alla risoluzione del problema. Per evitare invece la convergenza verso opzioni non idonee, viene utilizzato un meccanismo di feedback negativo (ad esempio l'evaporizzazione del feromone virtuale) che introduce una componente temporale nell'algoritmo. Il punto di forza dell'ACO consiste quindi nella creazione di un “sistema intelligente distribuito”. Ciò significa che le scelte adottate non sono prese da un'unica entità che lavora al problema, bensì da una colonia, che agisce autonomamente e per mezzo dei feromoni riesce a condividere le soluzioni appena vengono trovate, adattandosi dinamicamente all'ambiente. Un esempio di applicazione in cui poter sfruttare questo algoritmo è il routing di telecomunicazioni, infatti tramite l'ACO si potrebbe ottimizzare la scelta del miglior percorso di trasmissione dati.

PSO

Stormo di uccelli migratori in formazione.

L'algoritmo PSO (Particle Swarm Optimization) è stato implementato nel 1995 dallo psicosociologo James Kennedy e dall'ingegnere Russell C. Eberhart. Esso prende come punti di riferimento il comportamento di stormi di uccelli e banchi di pesci. Prendiamo in considerazione la ricerca di cibo da parte di uno stormo di uccelli. Se un singolo individuo avvista del cibo, ha due alternative: una individuale che consiste nell'allontanarsi dal gruppo per avvicinarsi alla fonte di cibo e l'altra è quella di rimanere nello stormo. Se però accade che più di un uccello si accorge della fonte di cibo, è possibile che tutto lo stormo cambi direzione in quanto è avvenuta una "propagazione di informazione" nella collettività. Vi è quindi una sorta di compromesso tra individualismo e collettività che genera dei benefici, in quanto i singoli individui sono influenzati dalle azioni reciproche. In questo contesto ricopre un ruolo molto importante anche la "vicinanza", in quanto permette un flusso di informazione globale.

FSO

Tale algoritmo prende le origini da un lavoro di [1], nel quale viene proposto un comportamento sociale, che sembra essere alla base del volo degli uccelli. Tale regola semplicemente suggerisce il fatto che gli uccelli in volo mediano la propria velocità rispetto ad altri sette individui scelti a caso nello stormo.Flock of Starlings Optimization

Applicazioni dell'intelligenza di sciame

Esempio di applicazione spaziale

Esempio di applicazione robotica in fabbrica

Principali applicazioni di Swarm Intelligence:

Implementazioni ACO

• Problemi di combinatoria
• Robotica
• Telecomunicazioni

Implementazioni PSO e FSO

• Reti neurali artificiali
• Modelli di evoluzione grammaticale
• Distribuzione dell'energia elettrica

Altre applicazioni:

• Controllo di veicoli militari senza pilota
• Nanobot
• La programmazione di fabbrica;
• Controllo decentralizzato dei veicoli senza piloti;
• Implementazioni a scopo medico.

Vi è inoltre un'applicazione di intelligenza di sciame nella vita artificiale, studiata da Mark Millonas (1994), il quale segue cinque principi base articolati da quest'ultimo:

• Il principio di prossimità: la popolazione dovrebbe essere in grado di portare avanti semplici computazioni spaziali e temporali.
• Il principio di qualità: la popolazione dovrebbe essere in grado di rispondere a fattori di qualità nell'ambiente.
• Il principio della risposta differenziata: la popolazione non dovrebbe svolgere la sua attività attraverso canali eccessivamente stretti.
• Il principio di stabilità: la popolazione non dovrebbe cambiare il suo modo di comportarsi ogni volta che cambia l'ambiente.
• Il principio di adattabilità: la popolazione deve essere in grado di cambiare comportamento quando ne va del costo computazionale.

Bibliografia

• E. Bonabeau, M. Dorigo, G. Theraulaz. Swarm intelligence. From natural to artificial systems, Oxford University Press, 1999.
• S. Camazine, J.L. Deneubourg, N.R. Franks, J.Sneyd, G.Theraulaz, E.Bonabeau. Self-Organization in Biological Systems, Princeton University Press, 1999.
• M.Dorigo, T.Stützle. Ant Colony Optimization, The MITPress, 2004.
• Marco Dorigo and Guy Theraulaz Swarm Intelligence: From Natural to Artificial Systems by Eric Bonabeau, 1999 ISBN 0-19-513159-2
• Mitchel Resnick, Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds ISBN 0-262-18162-2
• James Kennedy and Russell C. Eberhart, Swarm Intelligence, ISBN 1-55860-595-9
• Andries Engelbrecht, Fundamentals of Computational Swarm Intelligence, Wiley & Sons. ISBN 0-470-09191-6
• Jean-Baptiste Waldner, Nanocomputers and Swarm Intelligence, ISTE, ISBN 978-1-84704-002-2, 2007.
• Miller, Peter, Swarm Theory, National Geographic Magazine, luglio 2007, National Geographic
• Michael G. Hinchey, Roy Sterritt, Chris Rouff, Swarms and Swarm Intelligence, articolo su IEEE Computer Society
• From Ants to People: an Instinct to Swarm, NY Times, 11-13-07
• Swarm Intelligence (Journal) Chief Editor: Marco Dorigo. Springer New York. ISSN 1935-3812 (Print) 1935-3820 (Online)
• Eva Horn, Lucas Marco Gisi (Ed.): Schwärme - Kollektive ohne Zentrum. Eine Wissensgeschichte zwischen Leben und Information, Bielefeld: transcript 2009. ISBN 978-3-8376-1133-5
• J. Kennedy, R. C. Eberhart, Swarm Intelligence, Morgan Kaufmann Publishers, 2001.