Bio-inspired Design Patterns in MAS
Indice
- Self-Organization nei Sistemi Multi-Agente
- Modello Bio-Inspired
- Modello Computazionale
- Design Pattern per la modellazione di fenomeni naturali
- Patterns Basici
- Patterns Composti
- Ciclo di vita dell'Infrastructural Agent
- Struttura dei Messaggi
- Progettazione platform-dependent
- Conclusioni
- Riferimenti
Self-Organization nei Sistemi Multi-Agente
Analizzando lo stato dell’arte delle insfrastrutture software odierne e rivolgendosi con un pizzico di lungimiranza a quelle che probabilmente si andranno ad affermare nelle prossime generazioni software, è immediato osservare che la complessità in esse sta inesorabilmente aumentando, raggiungendo livelli troppo alti per le astrazioni tradizionalmente utilizzate nell’ingegneria dei sistemi software e più in generale nelle scienze informatiche. Tale scenario è caratterizzato da sistemi computazionali che possono essere considerati in molti casi ubiqui, costantemente attivi e con un livello di connettività che permette di garantire pervasività nelle interconnessioni; ciò si verifica in special modo per i sistemi su larga scala, a causa dell’emergenza di nuove tecnologie, le quali mettono a disposizione un numero sempre maggiore di dispositivi orientati alla comunicazione mobile.E’ risaputo che l’avanzamento tecnologico renda teoricamente possibile il raggiungimento di obiettivi sempre più Importanti, ma ciò introduce un innegabile livello di difficoltà, a causa dell’aumento dei requisiti imposti, come la scalabilità (in relazione al numero di utenti coinvolti, alla dislocazione geografica e del numero di risorse coinvolte), la reattività (particolarmente importante per sistemi real-time), oppure la failure tolerance.Inoltre, seguendo il trend attuale, si può supporre con buona probabilità che tutti i sistemi informatici classificati come “della generazione successiva”, denominati Complessi, saranno caratterizzati da:- natura intrinsecamente dinamica, dove gli aspetti computazioni sono strettamente legati all’ambiente esterno che li circonda, non permettendo più di considerarli separatamente;
- vincoli legati alle risorse utilizzate, con l’obiettivo di ridurre i consumi e dimensioni delle parti fisiche;
- architetture eterogenee;
- assenza o impossibilità di un’infrastruttura e controllo centralizzati, attribuendo un peso crescente ai concetti di controllo e interazioni locali fra component.
- Decentralizzazione (intesa come l’assenza di un’entità centrale che coordina e la riorganizzazione delle rimanenti parti)
- Località (le vari entità individuali mantengono informazioni relativamente ai propri “vicini” definiti in modo relativistico come “locali”)
Modello Bio-Inspired
Se i Sistemi Auto-Organizzanti risultano essere facilmente modellabili attraverso i cosiddetti Sistemi Multi-Agente (MAS), appare spontaneo chiedersi quindi come progettare i vari agenti (e le interazioni fra essi) al fine di garantire l’auto-organizzazione del sistema. Una risposta a tale quesito può essere ricercata facendo riferimento ad un modello ispirato alle scienze naturali e, in particolare, alla biologia.In natura, è facile osservare come i vari organismi autonomi siano in grado di ottemperare alle proprie funzioni e, in questo modo, di collaborare al cosiddetto processo biologico. Oltre gli organismi, un ruolo fondamentale in natura è svolto dall’ambiente stesso, il quale costituisce lo spazio fisico in cui gli organismi risiedono e contestualmente fornisce risorse che possono essere utilizzate, consumate o modificate. Inoltre, nell’ambiente possono generarsi (in modo completamente autonomo o semi-controllato) eventi capaci di produrre cambiamenti sull’ambiente stesso ed osservabili dagli organismi, i quali in funzione degli eventi possono attuare cambiamenti o mutazioni al proprio comportamento. La figura che segue rappresenta in maniera formale i componenti chiave del modello biologico.Le risorse fornite dall’ambiente possono essere modificate sia dall’ambiente stesso sia dagli organismi. Questi ultimi infatti, utilizzano le risorse dell’ambiente attraverso un proprio processo interno che termina con la restituzione all’ambiente della risorsa modificata (in parte o completamente). Gli eventi, infine, oltre ad essere naturalmente osservabili dagli organismi e portati a modificare l’ambiente, possono anche subire alterazioni provenienti dall’ambiente stesso, il quale, generalmente attraverso altri eventi semispontanei, può indurre al cambiamento uno specifico evento.Strutturalmente, le caratteristiche di un organismo naturale sono evidenziabili in tre aspetti:- Autonomia, nell’agire e reagire;
- Proattività, nel attuare decisioni;
- Parziale conoscenza del mondo circostante.
- Forte dinamicità;
- Capacità di agire su organismi e risorse.
Modello Computazionale
I modelli computazionali stanno alla base della progettazione di un qualunque sistema artificiale. Essi mostrano quali sono le entità che entrano in gioco nel sistema e illustrano i comportamenti e le interazioni che tali entità mettono in atto. Dopo aver preso in considerazione il modello Bio-Inspired, dove si è visto che le entità che entrano in gioco sono gli organismi e il relativo ambiente dove tali organismi “vivono”, emerge la necessità di applicare tali conoscenze ai sistemi artificiale. Per tale ragione si è cercato di realizzare un modello chiaramente ispirato alla biologia ma orientato al mondo dei sistemi artificiali. Il paradigma dei Sistemi Multi-Agente (MASs) è generalmente riconosciuto come il miglior paradigma per la modellazione di sistemi naturali e per lo sviluppo di sistemi artificiali Self-Organizing.Il passaggio da un modello Bio-Inspired, sintetizzabile nei due livelli denominati Organisms ed Environment, a un modello computazionali per i sistemi artificiali, non può essere applicato direttamente.Le entità che interagiscono con l’ambiente, chiaramente, non sono più gli organismi naturali, ma entrano in gioco gli agenti software, entità autonome situate in un ambiente che possono precepire e influenzare. Allo stesso tempo, anche l’ambiente ha la capacità di poter influenzare gli agenti stessi.Se nel modello Bio-Inspired sono presenti gli organismi naturali che possiedono una propria collocazione intrinsica nell’ambiente con il quale interagiscono, nel modello computazionale non è così banale. Nell’ingegneria dei sistemi software, gli agenti necessitano di dispositivi che abbiano una propria capacità computazionale su cui risiedere. Tali dispositivi permettono agli agenti e all’ambiente di interagire fra di loro.Come conseguenza delle affermazioni fatte in precedenza, nel modello computazionale è stato introdotto un nuovo strato, detto Infrastructure Layer, livello indispensabile per gli agenti che vogliono interagire con l’ambiente (cioè rilevano l’ambiente attraverso i sensori o lo influenzano atttraverso gli attuatori) e comunicare con altri agenti presenti nel sistema. Oltre che per gli agenti, l’Infrastructure Layer è indispensabile per poter attuare tutti quei comportamenti dell’ambiente che vanno ad influenzare gli stessi agenti.Le entità che entrano in gioco nel modello computazionale sono:- Agenti (Agents), entità software autonome pro-active;
- Infrastruttura (Infrastructure), composta da un insieme di Host e Infrastructural Agents;
- Ambiente (Environment), spazio nella realtà in cui si manifestano gli eventi di interesse e dove si trovano tutte le infrastrutture prese in considerazione.
- Agents liberi di muoversi sugli Hosts (in questo caso denominati più propriamente Mobile Agents);
- Agents strettamente accoppiati agli Hosts (mobilità limitata).
Analisi dell'Architettura dell'Host
Nel modello computazionale considerato si viene a delineare un’entità chiamata host, parte del livello infrastrutturale, la quale rappresenta genericamente un esecutore automatico, con capacità computazionali, situato fisicamente all’interno dell’ambiente. Il modello di seguito proposto rappresenta la struttura del singolo host, per mettere in luce la relativa composizione interna, le risorse che mette a disposizione (quindi le possibili funzioni svolte) e quali relazioni intercorrono fra quest’ultimo e gli agenti che popolano il sistema. Le principali caratteristiche di un host sono riportate di seguito.- spazio di memorizzazione dedicato con dimensione variabile a seconda delle caratteristiche tecniche hardware;
- interfacce di comunicazione con le risorse dell’ambiente esterno (sensori, attuatori).
Analisi dell'Architettura del Sistema
Si propone di seguito un ulteriore modello dei componenti presenti nel sistema multi-agente, già descritto in precedenza, con l’obbiettivo di specificare le principali relazioni che intercorrono fra le tre parti fondamentali del sistema individuate, ovvero:- agenti software
- infrastruttura
- ambiente reale
- Real Environment
- come più volte menzionato rappresenta l’ambiente reale che circonda il sistema nel quale quest’ultimo è immerso;
- consente di dare forma alle risorse considerate e poter esprimere i concetti di località, distanza;
- la delimitazione fisica dell’ambiente dipende dallo specifico contesto di applicazione, cercando sempre di ottenere il giusto compromesso fra un buon grado di corrispondenza con la realtà e la semplificazione operata, necessaria nella fase di modellazione, effettuando scelte sulla base degli specifici scenari che si prospettano;
- Infrastructure
- anche in questo caso la propria delimitazione non può essere fissata a priori, data la medesima natura dell’ambiente;
- si è voluto mettere in luce tale riquadro per la singolare caratteristica di non essere compreso integralmente nell’ambiente, infatti i vari IA non risultano in alcun modo mappabili direttamente in entità fisiche presenti nell’ambiente; tale parte software, inclusa nel middleware del MAS con funzionalità e caratteristiche “built-in”, è il risultato di un processo adattativo incrementale volto alla completa modellazione in special modo di quelle capacità che sono insite nell’ambiente in natura;
- i sensori ed attuatori, considerando la loro parte prettamente hardware, sono situati nel modello al di fuori dello spazio logico dell’infrastruttura; essi rappresentano gli unici accessi effettivi all’ambiente esterno, mentre le loro interfacce di accesso (il controllo associato ad essi) costituiscono una parte di rilievo per il livello infrastrutturale;
- ogni host è dislocato nello spazio fisico, ma anche all’interno dell’infrastruttura, costituendo una specifica topologia dinamica, dato che è possibile introdurre cambiamenti a seconda di quale host sia inserito o non sia più considerato dal sistema; si ipotizza inoltre che sia possibile una qualche forma di comunicazione (tipicamente basata su protocolli di rete) fra uno o più host, resa possibile grazie ad un medium di comunicazione, che agisce in modo trasperente rispetto al sistema stesso considerato e pressoché ubiquio (si suppone sia la stessa rete Internet che supporti tale requisito);
- Infrastructural Agents & Software Agents
- introducendo una separazione netta di questi due riquadri rispetto alle altre entità che entrano in gioco, emergono le rispettive posizioni (software/infrastractural), entrambi rappresentanti di entità autonome che “guidano” il sistema, ma che sono da quest’ultimo anche supportate.
Design Pattern per la modellazione di fenomeni naturali
In natura, molti sono i fenomeni che svolgono un importante ruolo per la comunicazione tra gli organismi e non solo. Definendo un modello computazionale che trae ispirazione dal modello biologico, è evidente come sia necessario modellare unitamente ai concetti base, come ad esempio organismi o ambiente, anche tutti quei meccanismi o fenomeni che genericamente permettono la gestione e la trasmissione di tutte le informazioni.In termini tecnici, modellare meccanismi significa necessariamente definire design patterns che possano poi essere implementati sull’una o sull’altra tecnologia.Analizzando il modello biologico, i meccanismi che possono essere isolati sono essenzialmente suddivisibili in due livelli di astrazione: il livello base e il livello composto.A livello base sono evidenziabili i meccanismi di Diffusione, Evaporazione e Aggregazione delle informazioni. Componendo tra loro i meccanismi di base, si ottengono i meccanismi di livello composto che ne rappresentano un evoluzione. In particolare, a tale livello si evidenziano i cosiddetti meccanismi di Feromoni Digitali, Gradiente e Gossip. La figura che segue illustra le relazioni che coesistono tra i vari meccanismi. Per completezza, va aggiunto che è possibile isolare anche altri meccanismi ad un livello ancora più alto di quello dei composti che tuttavia non è oggetto del presente lavoro di progetto.Patterns Basici
Spreading Pattern
La diffusione (spreading) delle informazioni costituisce un fenomeno che in natura è guidato dall’ambiente. In un sistema computazionale multi-agente orientato all’auto-organizzazione, è necessario modellare tale fenomeno per permettere ai vari agenti di inviare progressivamente informazioni al fine di incrementare la conoscenza globale del sistema.Poichè nel modello computazionale descritto ogni agente è in grado di sostenere unicamente interazioni locali, il problema che si pone nella modellazione del pattern per lo spreading è dato dalla necessità di colmare la mancanza di conoscenza globale del sistema da parte di ogni agente. Un tale ostacolo, tuttavia, può essere superato definendo il concetto di agente vicino (neighbour agent). Ad ogni agente, infatti, deve essere possibile associare una lista di agenti vicini con i quali l’agente può comunicare direttamente e ai quali può inviare informazioni.Formalmente, il processo di spreading può essere descritto in termini matematici dalla seguente regola di transizione.SPREADING: {{{<}}} L,C {{{>}}} → {{{<}}} L<sub>1</sub>,C<sub>1</sub> {{{>}}}, ..., {{{<}}} L<sub>n</sub>,C<sub>n</sub> {{{>}}}
where {L<sub>1</sub>, ..., L<sub>n</sub>} = ν(L) and {C<sub>1</sub>, ..., C<sub>n</sub>} = σ(C,L)
where {L<sub>1</sub>, ..., L<sub>n</sub>} = ν(L) and {C<sub>1</sub>, ..., C<sub>n</sub>} = σ(C,L)
Aggregation Pattern
Il continuo diffondersi di informazioni nel sistema porta inevitabilmente ad un suo sovraccarico. Spesso, tuttavia, molte informazioni possono essere unite tra loro in quanto rappresentano un unico contesto informativo. Per ridurre il carico del sistema e, in secondo luogo, per riorganizzare le informazioni, ispirandosi sempre al contesto naturale, viene introdotto il pattern Aggregation. Formalmente, il meccanismo di aggregazione è descritto dalla seguente regola di transizione. AGGREGATION: {{{<}}} L,C<sub>1</sub> {{{>}}}, ..., {{{<}}} L,C<sub>n</sub> {{{>}}} → {{{<}}} L,C'<sub>1</sub> {{{>}}}, ..., {{{<}}} L,C'<sub>m</sub> {{{>}}} \
where {C'<sub>1</sub>,...,C'<sub>m</sub>} = ƒ({C<sub>1</sub>,...,C<sub>n</sub>}) and (m « n)
where {C'<sub>1</sub>,...,C'<sub>m</sub>} = ƒ({C<sub>1</sub>,...,C<sub>n</sub>}) and (m « n)
- Filtri, che selezionano un sottoinsieme specifico di informazioni;
- Trasformatori, che modificano specifiche informazioni;
- Miscelatori, che uniformano uno specifico gruppo di informazioni restituendo un’unica informazione compatta;
- Aggregatori, che applicano specifiche funzioni (matematiche e statistiche) ad un insieme di informazioni.
Evaporation Pattern
Nel modello biologico si evince chiaramente che molte informazioni, col trascorrere del tempo, diventano obsolete e quindi non più utili ai fini del sistema. Per questo motivo, l’ambiente e gli organismi attuano fenomeni specifici affinchè sia possibile eliminare tali informazioni. Per tradurre questo fenomeno nel modello computazionale è necessario introdurre il pattern evaporation, formalmente definito dalla seguente regola di transizione.EVAPORATION: {{{<}}} L,C {{{>}}} → {{{<}}} L,C' {{{>}}} \
where C' = ε(C,E<sub>ƒ</sub>)
where C' = ε(C,E<sub>ƒ</sub>)
Rel<sub>c'</sub> = Rel<sub>c</sub>*E<sub>ƒ</sub> \
where E<sub>ƒ</sub> ∈ {{{[0, ..., 1]}}}
where E<sub>ƒ</sub> ∈ {{{[0, ..., 1]}}}
Patterns Composti
Gradient Pattern
Il gradiente costituisce un pattern composto, il quale utilizza necessariamente i meccanismi elementari di diffusione ed aggregazione, descritti precedentemente, per poter propagare ed eventualmente manipolare informazioni caratterizzate da una maggior ricchezza nei contenuti; in particolare introduce i concetti di distanza e direzione, entrambi utili per incrementare la consapevolezza delle entità autonome coinvolte riguardo alla posizione assunta dalla sorgente di invio dell’informazione, nei casi in cui essa si trovi al di fuori del raggio di comunicazione.In ambienti caratterizzati da un alto grado di dinamicità dovuto a rempentini o frequenti modifiche a livello di topologia del sistema, tale pattern introdotto è in grado di mettere a disposizione un ulteriore meccanismo (evaporazione) per rendere possibile, con un determinato grado di libertà, l’adattamento ai cambienti topologici verificatisi nell’infrastruttura di rete che rende possibile il transito delle informazioni. In particolare, l’informazione diffusa, così strutturata, può essere soggetta ad evaporazione, riducendo la sua rilevanza nel tempo, e quindi rappresentativa del periodo temporale di attività dell’host da cui si è diffusa. Questa’ultima variazione possibile attribuisce al pattern il nominativo di Active Gradient.Il pattern Gradients è descritto dalle seguenti regole di transizione.GRADIENT(spreading): {{{<}}} L, {{{[}}} D,DIR,C {{{]}}} {{{>}}} → {{{<}}} L<sub>1</sub>, {{{[}}} D<sub>1</sub>±ΔD,DIR',C<sub>1</sub> {{{]}}} {{{>}}}, ..., {{{<}}} L<sub>n</sub>, {{{[}}} D<sub>n</sub>±ΔD,DIR',C<sub>n</sub> {{{]}}} {{{>}}} \
where {L<sub>1</sub>, ..., L<sub>n</sub>} = ν(L) and {C<sub>1</sub>, ..., C<sub>n</sub>} = σ( C,L )
where {L<sub>1</sub>, ..., L<sub>n</sub>} = ν(L) and {C<sub>1</sub>, ..., C<sub>n</sub>} = σ( C,L )
GRADIENT(ContentAggregation): {{{<}}} L, {{{[}}} D,DIR,C<sub>1</sub> {{{]}}} {{{>}}}, ..., {{{<}}} L, {{{[}}} D,DIR,C<sub>n</sub> {{{]}}} {{{>}}} → {{{<}}} L, {{{[}}} D,DIR,C'<sub>1</sub> {{{]}}} {{{>}}}, ..., {{{<}}} L, {{{[}}} D,DIR,C'<sub>m</sub> {{{]}}} {{{>}}} \
where {C'<sub>1</sub>, ..., C'<sub>m</sub>} = ƒ( {C<sub>1</sub>, ..., C<sub>n</sub>} ) and (m « n)
where {C'<sub>1</sub>, ..., C'<sub>m</sub>} = ƒ( {C<sub>1</sub>, ..., C<sub>n</sub>} ) and (m « n)
GRADIENT(DistanceAggragation): {{{<}}} L, {{{[}}}D<sub>1</sub>,DIR,C {{{]}}} {{{>}}}, ..., {{{<}}} L, {{{[}}} D<sub>n</sub>,DIR,C {{{]}}} {{{>}}} → {{{<}}} L, {{{[}}} D',DIR,C {{{]}}} {{{>}}} \
where D' = min/max( {D<sub>1</sub>, ..., D<sub>n</sub>} )
where D' = min/max( {D<sub>1</sub>, ..., D<sub>n</sub>} )
GRADIENT(DirectionAggregation): {{{<}}} L, {{{[}}} D,DIR<sub>1</sub>,C{{{]}}} {{{>}}}, ..., {{{<}}} L, {{{[}}} D,DIR<sub>n</sub>,C{{{]}}} {{{>}}} → {{{<}}} L, {{{[}}} D,DIR',C{{{]}}} {{{>}}} \
where DIR' =(DIR<sub>1</sub> × DIR<sub>2</sub> × ... DIR<sub>n</sub>)
where DIR' =(DIR<sub>1</sub> × DIR<sub>2</sub> × ... DIR<sub>n</sub>)
GRADIENT(evaporation): {{{<}}} L,C {{{>}}} → {{{<}}} L,C' {{{>}}} \
where C' = ε(C,E<sub>ƒ</sub>)
where C' = ε(C,E<sub>ƒ</sub>)
Digital Pheromones Pattern
Tale pattern è stato introdotto come soluzione a problematiche di coordinazione relative a comunicazioni che avvengono in modo indiretto, molto comuni in sistemi auto-organizzanti; traendo ispirazione dall’ambiente naturale, il feromone digitale costituisce una impronta, marca digitale, depositata dal Sw Agents nell’ambiente (l’host sul quale risiede), per fungere da segnale, evento utilizzabile per riuscire a strutturare un metodo di comunicazione prettamente indiretto con gli altri organismi (entità autonome) del sistema. Dato che è introdotto nell’ambiente e potenzialmente può pervenire ad ogni entità del sistema, è importante che il contenuto informativo sia corredato da informazioni che ne specifichino la distanza dalla sorgente che l’ha generata, la direzione di propagazione e, non meno importante, un riferimento temporale indicante la freschezza dell’informazione, in modo tale da emulare il caratteristico livello di concentrazione dei feromoni in natura. Mediante questa prima descrizione, si può ora definire il Digital Pheromone pattern come un pattern composto che utilizza i pattern Gradient ed Evaporation; conseguentemente i feromoni non sono altro che gradienti diffusi in modo esaustivo all’interno del sistema, con un determinato intervallo di attività, necessario per incrementare l’attualizzazione delle informazioni e, quindi, adeguarsi ai rapidi cambiamenti che si osservano in ambienti fortemente dinamici. Dal punto di vista strutturale, il meccanismo dei feromoni digitali è essenzialmente costituito dagli stessi elementi che compongono l’Active Gradient pattern, come si è potuto notare dai requisiti necessari elencati per i feromoni; ciò che differenzia questi due pattern compositi è da ricercare nella semantica attribuita alla definizione di comunicazione indiretta, infatti mediante il meccanismo dei feromoni digitali è responsabilità unica degli Agenti Software rendere accessibili le informazioni sotto-forma di traccia, sparse indefinitamente nella porzione di ambiente con il quale riescono ad interagire/inferire, mentre i meccanismi di diffusione, evaporazione e soprattutto di aggregazione risultano completamente trasparenti agli occhi delle prime entità autonome citate, perché, in questo caso, tali azioni sono attribuite al comportamento, che in natura è proprio dell’ambiente stesso, degli IA.Gossip Pattern
Il pattern denominato Gossip trae ispirazione dall’omonimo comportamento tipicamente umano di diffondere informazioni basandosi esclusivamente sulla conoscenza, limitata e parziale, di altri individui, dando vita al fenomeno conosciuto a livello internazionale come rumor.A differenza dei primi due pattern compositi, quest’ultimo si discosta dall’ambiente prettamente naturale; esso rappresenta nel modo migliore il concetto di condivisione di informazioni comuni, incrementalmente “assimilate” con lo scopo di aumentare la conoscenza individuale e rappresentarne pienamente la rapidità di diffusione.Considerando il livello del modello computazionale, il Gossip pattern è costituito dalla composizione dei pattern basici Aggregation e Spreading, utilizzati in un meccanismo concettualmente differente in relazione ai patterns Gradient e Digital Phermones, perché in esso si diffondono le medesime informazioni ricevute se non ne è presente alcuna di originale, individuabile solamente a livello locale; negli altri casi è necessario effettuare sulla totalità delle informazioni contenute nello spazio di memorizzazione locale un’operazione di aggregazione, con lo scopo di introdurre un nuovo contenuto informativo, caratteristica essenziale per poter terminare il processo mediante diffusione. \ Tale comportamento consente di incrementare rapidamente la conoscenza locale che ogni agente ha del sistema, eseguendo un’operazione di diffusione solamente se vi sono aggiornamenti considerevoli per il livello di conoscenza raggiunto.Il pattern Gossip è descritto dalle seguenti regole di transizione.GOSSIP(Aggregation): {{{<}}} L,C<sub>1</sub> {{{>}}}, ..., {{{<}}} L,C<sub>m</sub> {{{>}}}, {{{<}}} L, {{{[}}} Rcd,C<sub>m+1</sub> {{{]}}} {{{>}}}, ..., {{{<}}} L, {{{[}}} Rcd,C<sub>n</sub> {{{]}}} {{{>}}} → {{{<}}} L,C'<sub>1</sub> {{{>}}}, ..., {{{<}}} L,C'<sub>k</sub> {{{>}}} \
where {C'<sub>1</sub>, ..., C'<sub>k</sub>} = α( {C<sub>1</sub>, ..., C<sub>n</sub>} ) and (k « n)
where {C'<sub>1</sub>, ..., C'<sub>k</sub>} = α( {C<sub>1</sub>, ..., C<sub>n</sub>} ) and (k « n)
GOSSIP(BridgeSpreading): {{{<}}} L,C' {{{>}}} → {{{<}}} L<sub>1</sub>, {{{[}}} Rcd,C' {{{]}}} {{{>}}}, ..., {{{<}}} L<sub>n</sub>, {{{[}}} Rcd,C' {{{]}}} {{{>}}}
GOSSIP(IncSpreading): {{{<}}} L,C'' {{{>}}} → {{{<}}} L<sub>1</sub>, {{{[}}} Rcd,C'' {{{]}}} {{{>}}}, ..., {{{<}}} L<sub>n</sub>,{{{[}}} Rcd,C'' {{{]}}} {{{>}}}
where {L<sub>1</sub>, ..., L<sub>n</sub>} = ν(L) and C' = ( C ∨ {{{[}}} Rcd,C {{{]}}} ) and C'' = α( {C<sub>1</sub>, ..., {{{[}}} Rcd,C<sub>n</sub> {{{]}}}} )
GOSSIP(IncSpreading): {{{<}}} L,C'' {{{>}}} → {{{<}}} L<sub>1</sub>, {{{[}}} Rcd,C'' {{{]}}} {{{>}}}, ..., {{{<}}} L<sub>n</sub>,{{{[}}} Rcd,C'' {{{]}}} {{{>}}}
where {L<sub>1</sub>, ..., L<sub>n</sub>} = ν(L) and C' = ( C ∨ {{{[}}} Rcd,C {{{]}}} ) and C'' = α( {C<sub>1</sub>, ..., {{{[}}} Rcd,C<sub>n</sub> {{{]}}}} )
- aggregazione necessariamente eseguita in presenza di un numero di gossip maggiore di uno ed portata a termine dal Sw Agent (quando presente), per garantire l’invio delle sole informazioni aggiornate;
- gestione del gossip da parte del IA, se non è presente alcun Sw Agent nell’host considerato, agendo da “ponte” all’interno del processo di diffusione;
- aggiunta dell’attributo Rcd all’atto dell’invio del gossip nel sistema.
Ciclo di vita dell'Infrastructural Agent
Per come è stato descritto il modello computazionale, un ruolo centrale e di primaria importanza è certamente svolto dai vari Infrastructural Agent presenti ed associati ai diversi host del sistema. Simulando il comportamento dell’ambiente reale, infatti, sono loro a svolgere la maggior parte delle attività associate alla gestione/diffusione delle informazioni all’interno del sistema. Per questo motivo, risulta necessario analizzare dettagliatamente come, una volta inizializzato, ogni Infrastructural Agent operi in autonomia.Viceversa, non è interessante analizzare il comportamento di ogni agente software del sistema, essenzialmente per due motivi. Primo, ogni agente ha un proprio scopo computazionale che potrebbe anche essere unico all’interno del sistema; secondo, gli agenti software hanno in comune tra loro solamente il fatto di risiedere sul sistema e di comunicare con un host che non necessariamente risulta essere lo stesso durante l’intero tempo di vita dell’agente (mobilità degli agenti software). Perciò, le specifiche relative ad ogni agente software sono proprie dell’agente stesso e devono unicamente rispettare l’interfaccia di comunicazione prescelta affinché sia possibile per loro interagire col sistema. La figura che segue, illustra il cosiddetto Lifecycle per ogni Infrastructural Agent ed, essenzialmente, si compone di due macro fasi: la prima in cui l’infrastructural Agent viene inizializzato (contestualmente all’aggiunta di un nuovo host nel sistema) e la seconda, subordinata alla prima, in cui l’Infrastructural Agent risulta in uno stato proattivo e può quindi operare.Fase di Inizializzazione
In questa fase, l’IA viene inizializzato con tutte le informazioni a lui necessarie per poter operare. Quando un nuovo host interviene nel sistema, infatti, il proprio IA ha come unica esigenza quella di riempire la cosiddetta lista dei vicini, ovvero esso ha la necessità di sapere chi sono gli host a lui vicini. Per ottenere tale lista, l’IA interessato crea un opportuno messaggio ad hoc (Initialization Message) che invia in broadcast sul sistema e quindi si pone in attesa di risposte specifiche. Tale attesa è subordinata in termini di tempo alla capacità di reazione degli IA relativi agli host vicini, ma in ogni caso non può essere infinita. Una possibile politica di gestione dell’attesa potrebbe essere basata sul concetto di timeout. In particolare, l’IA resta in attesa di risposte per un tempo prefissato, dopo il quale assume di non avere vicini all’interno del sistema in quel momento e inizializza, pertanto, la propria lista di vicini con una lista vuota, procedendo quindi con la fase successiva. Viceversa, se entro il timeout riceve almeno una risposta, aggiunge il mittente di ogni risposta alla propria lista di vicini e, scaduto il timeout, procede comunque alla fase successiva.Fase Proattiva
Dopo essere stato inizializzato, ogni Infrastructural Agent si pone in una situazione di idle in cui rimane in attesa di ricevere messaggi. A fronte della ricezione di un messaggio, l’IA reagisce attivamente a seconda della tipologia del messaggio ricevuto e, in particolare, discrimina se il messaggio è un messaggio di inizializzazione oppure no. Infatti, se il messaggio ricevuto è di inizializzazione (ovvero inviato da un’altro IA che si trova nella fase precedente) l’IA che lo riceve deve gestirlo, costruendo l’opportuna risposta da inviare e modificando la propria lista di vicini, includendo cioè l’host di quest’ultimo IA.Al di la di questo, il comportamento più interessante lo si osserva quando l’IA, nella situazione di idle, riceve un messaggio che non sia di inizializzazione. In questo caso infatti si tratta di un "vero" messaggio del sistema che l’IA deve gestire per simulare quel comportamento che nel sistema biologico è svolto dall’ambiente.A fronte di tale ricezione, l’Infrastructural Agent reagisce avviando due flussi d’esecuzione concorrenti (sulla quale natura non si fanno ipotesi aggiuntive, per non diminuire il grado di generalità delle ipotesi), ognuno dei quali deputato ad un diverso compito: uno per la gestione del meccanismo di aggregazione e l’altro per la diffusione del messaggio ricevuto.Relativamente al primo flusso, il messaggio ricevuto viene analizzato per tentare di applicare il meccanismo di aggregazione al fine di creare un nuovo messaggio composto da quello appena ricevuto e da altri eventuali precedentemente ricevuti, presenti nello spazio locale dell’host in questione. Qualora il meccanismo di aggregazione sia attuabile, in funzione delle politiche predefinite, viene creato un nuovo messaggio che viene quindi inviato dall’IA a se stesso al fine di innescare il meccanismo di diffusione anche per questo nuovo messaggio frutto dell’aggregazione. Il secondo flusso è invece più articolato. Dal messaggio viene innanzi tutto estratto il coefficiente di evaporazione relativo, che, qualora risulti pari a zero, ovvero identifichi la situazione in cui si impone l’evaporazione dell’informazione, porta all’attivazione del meccanismo di evaporazione opportunamente gestito secondo quanto specificato nei paragrafi precedenti.Qualora tale coefficiente abbia un valore diverso da zero, si procede alla vera fase di diffusione del messaggio che inizia con la creazione della lista di destinatari per il messaggio, ottenuta da quella dei vicini dell’host relativo all’IA corrente; procedendo in questo senso si esclude sicuramente il mittente del messaggio da diffondere (che evidentemente è uno dei vicini) ed eventualmente altri vicini in relazione ad eventuali specifiche politiche di ottimizzazione. Quindi, viene valutato il tipo di messaggi, ovvero quale meccanismo di diffusione deve essere applicato (Spreading, Gradient, Digital Pherormone, Gossip) e in relazione a ciò viene avviato il processo di gestione del meccanismo scelto. In conclusione, gestito il messaggio, l’Infrastructural Agent torna nella fase di idle nella quale resta in attesa per nuovi messaggi da processare.Struttura dei Messaggi
Dopo aver descritto dettagliatamente il funzionamento del generico Infrastructural Agent del sistema e aver evidenziato come il relativo lifecycle sia in gran parte subordinato ai messaggi scambiati all’interno del sistema, sarà ora discussa la struttura che tali messaggi devono avere per garantire il trasporto dell’informazione e dei parametri per la gestione dei meccanismi di diffusione. Il modello che segue rappresenta una possibile struttura per i messaggi.Ogni messaggio è composto da sei elementi:- tipo, che rappresenta il meccanismo di diffusione mediante il quale il messaggio viene trasmesso sul sistema.
- corpo, che rappresenta il contenuto informativo del messaggio.
- coefficiente di evaporazione, che permette di attuare politiche di evaporazione secondo il meccanismo relativo.
- distanza, per identificare la distanza dall’host dal quale è partito inizialmente il messaggio.
- direzione, per identificare la direzione del gradiente.
- flag di avvenuta ricezione, per indicare che il contenuto del relativo gossip è frutto di una precedente ricezione.
Progettazione platform-dependent
Definiti i modelli necessari per descrivere compiutamente i pattern previsti negli obiettivi di progetto all’interno di un’ipotetica infrastruttura platform-independent, ci si appresta ad iniziare la fase di progettazione, basata sulle tecnologie scelte per portare a termine anche l’ultima fase di progetto, analisi e sperimentazione.L’intento finale si può riassumere nella realizzazione di una serie di librerie rappresentanti i pattern analizzati precedentemente, utilizzabili all’interno di un’opportuna infrastruttura ad-hoc, frutto di un’azione di mapping o correlazione più o meno accentuata fra le entità concettuali introdotte e le caratterisitiche/funzionalità principali delle due tecnologie Java utilizzate :- Jade - piattaforma software con l’obiettivo di fornire le necessarie funzionalità basiche per semplificare la realizzazione di applicazioni in campo distribuito, sfruttando ed utilizzando l’astrazione basata su Agenti;
- Tucson - modello per la coordinazione dei sistemi distribuiti basati sul meta-modello MAS, nato dall’esigenza di introdurre strumenti per la coordinazione in ambienti caratterizzati da una moltitudine di agenti;
- proattività e autonomia attribute agli agenti, unico tipo di entità utilizzabile all’interno di tale architettura;
- completa natura distribuita del sistema;
- semplicità nella gestione del ciclo di vita del singolo agente;
- supporto alla mobilità di tali entità;
- modellazione dello spazio di interazione degli agenti in modalità congruenti con gli obiettivi prefissati.
- presenza di un media di coordinazione come concetto che si sviluppa in una dimensione trasverale rispetto all’ambiente dove “vivono” le entità, definite in tale modello come i coordinabili;
- fusione dei modelli identificati come “information-driven” ed action-driven, in modo tale da rendere possibile l’osservabilità degli eventi, ma anche la possibilità di reagire ad essi;
- generalità del modello stesso, sempre più utilizzato in sistemi caratterizzati da un elevato livello di “apertura”;
- intrinseca distribuibilità dei sistemi basati su scambio di informazioni, costruiti partendo da esso;
- modellazione delle entità coordinabili, immerse nel sistema descritto, come agenti definiti mobili.
Livello Infrastrutturale Bio-Inspired (System View)
Il modello proposto di seguito fornisce un quadro complessivo circa la composizione dell’infrastruttura ibrida venutasi necesariamente a creare dopo la scelta effettuata sulle tecnologie da impiegare.La presenza di due differenti livelli concettuali, (“Base Infrastracture” e “Bio-Inspired Infrastracture”) è resa necessaria per identificare la struttura dei servizi fondamentali utilizzati (in questo caso presenti come commistione di elementi appartenenti agli ambienti Jade e Tucson, tema riconsiderato meglio nei paragrafi successivi) e, allo stesso tempo, per evidenziare l’introduzione di un ulteriore livello infrastrutturale mediano, appositamente ideato per realizzare, come già accennato nell’introduzione alle tecnologie, l’opera di mapping fra i concetti di entità che entrano in gioco nella tipologia di sistemi presi in esame, e quello di Agente autonomo, proattivo, relativo ad una specifica tecnologia, tipicamente "general-purpose", come risulta essere vero per Jade.Si può notare come l’integrazione delle due tecnologie considerate sia stata introdotta in entrambi i livelli infrastrutturali, subordinando gli elementi e servizi offerti dalla piattaforma Tucson ai componenti Jade-based, mostrando in che modo il modello di coordinazione basato sulla diffusione di Centri di Tuple sia introdotto come servizio, mentre è responsabilità dell’originaria piattaforma Jade gestire il cilco di vita ed ambiente di esecuzione di ogni agente.Per completare la descrizione del modello infrastrutturale che rappresenta il sistema in esame, è necessario specificare ulteriormente alcuni aspetti, di seguito elencati.- L’intero ambiente software, inteso qui come lo spazio virtuale in cui la totalità degli agenti risiede, è realizzato su un’unica Piattaforma Jade; tale scelta progettuale non vincola, in ipotetici sviluppi futuri, di estendere l’infrastruttura al fine di realizzare un’interazione inter-piattafroma, anche se solo mediante l’utilizzo di opportuni plug-in ed accorgimenti circa il concetto di “space-awarness”.
- Ogni Container Jade rappresenta concettualmente una porzione dello spazio fisico di interesse, riuscendo in questo modo a mappare l’esigenza di riproporre la presenza di un “ambiente” circostante, mediante tale astrazione; come si può notare dal modello sovrastante, ad ogni container è associato un Nodo Tucson, utilizzato per mantenere dati in forma locale rispetto all’attuale container (per esempio informazioni riguardanti la relazione di vicinanza con altri “spazi” virtuali); data la natura ad Agenti della piattaforma Jade ed i vincoli strutturali invariati, ogni container è in grado di permettere l’individuazione e il successivo aggancio di una pluralità di Agenti Jade.
- L’entità che è stata definita in precedenza come Host non è introdotta in tale modello dei componenti, perché, avendola definita come priva di della caratteristica autonomia e proattivà, proprie degli Agenti Bio-Inspired, si è ritenuto progettualmente non corretto introdurla all’interno dell’ambiente di visibilità di Jade, ovvero rapprasentando l’host come Agente. Ad ogni modo, si considera un host, ai fini della modellazione strutturale della nuova infrastruttura Bio-Inspired, l’insieme costituito dall’Infrastructural Agent ed il relativo Nodo Tucson.
- Si è scelto di associare il Nodo Tucson all’Infrastractural Agent, in modo tale da rappresentare compiutamente il concetto astratto di host (in particolare il nodo ha un ciclo di vita corrispondente a quello dell’IA); sempre tale agente, in virtù delle funzionalità inizialmente definite, è in grado di accedere al centro di tuple che rappresenta lo spazio locale (nel modello, “LTC”), ma anche agli altri eventuali centri di tuple secondari (nel modello “OTC”), utilizzati per mantenere traccia di eventuali dati locali relativi a configurazioni specifiche dell’host, oppure per realizzare una politica di gestione degli accessi.
- Ogni Software Agent può essere associato ad un unico host per volta, vincolo modellato tramite un apposito protocollo di connessione/disconnessione, trattato nel paragrafo successivo; si ricorda solamente che tali agenti sono in grado di percepire ed interagire solamente con il Nodo Tucson dell’host sul quale vivono; inoltre lo scope di attività è ridotto all’attuale spazio di memorizzazione locale (LTC).
- Il problema relativo alla rappresentazione del concetto di "vicinanza" trova soluzione in questa fase progettuale, perché in precedenza identificato come problematica secondaria, fortemente dipendente dalla tecnologia utilizzata. Sempre mediante l'ausilio della piattaforma Jade, si considerano vicini tutti gli host (di cui si ha solamente una rappresentazione logica), presenti ed attivi all'interno del medesimo Container Jade; la relazione di vicinanza si riflette, inoltre, anche a livello di questi ultimi, mantenendo le informazioni necessarie all'interno di appositi Centri di Tuple Tucson, definite staticamente all'attivazione della piattaforma, per esempio sfruttando specifici algoritmi di ordinamento.
Livello Infrastrutturale Bio-Inspired (Entity View)
Il seguente modello strutturale mostra come le entità analizzate in precedenza vengano mappate sulla base delle scelte tecnologie effettuate.Congruentemente con quanto stabilito in precedenza, le principali tipologie di entità a cui si fa riferimento sono:- InfrastracturalAgent
- SoftwareAgent
Progettazione e sviluppo dei Bio-Inspired Patterns
Descritta l’infrastruttura considerando le tecnologie prescelte, si pone ora il problema di stabilire come iniettare le funzionalità dei pattern bio-inspired nei vari agenti del sistema. In particolare, è necessario definire come realizzare il comportamento di ciascun infrastructural agent che, come è noto, possiede il compito di maggiore rilevanza. Il lifecycle di un infrastructural agent è stato descritto in termini generali come una macchina a stati e in Jade un tale comportamento è modellabile, ed associabile agli agenti, attraverso il concetto di Behaviour.In Jade un behaviour rappresenta un task che un agente può eseguire e che deve essere aggiuto all’agente specifico secondo specifiche politiche. Ogni behaviour è eseguito da un agente secondo uno scheduler cooperativo, non pre-emptive, che impone di fatto l’impossibilità di eseguire più behaviour contemporaneamente. Una volta avviato un behaviour, un agente può eseguirne un altro solo dopo che quello attivo abbia segnalato la sua completa terminazione.In definitiva, perciò, nel caso specifico dell’infrastructural agent, che prevede un comportamento ciclico che si interrompe unicamente in corrispondenza alla dismissione dell’agente, solo un behaviour può essere associato ed eseguito.Tuttavia, affinché sia possibile attuare una corretta separazione dei contenuti, la tecnologia Jade consente di associare uno o più sotto behaviuors ad un behaviour principale, quando quest’ultimo sia definito, tra le varie possibilità, come una macchina a stati.La figura che segue, riassume relativamente all’infrastructural agent la mappatura del suo behaviour sulla tecnologia ad agenti Jade e dei relativi sotto behaviours.In particolare, il macro comportamento è definito mediante un jade FSMBehaviour in cui gli stati figli corrispondono agli specifici behaviour relativi ai diversi pattern, associati al behaviour principale, definiti mediante l’uso della classe OneShotBehaviour che identifica un comportamento che dopo aver svolto il proprio compito termina rilasciando il controllo, o nello specifico caso in cui vengono utilizzati (ovvero come figli di un behaviour FSM) scatenando una transizione verso un altro stato.Volutamente, si è deciso di tralasciare eventuali altri behaviour “di servizio” in cui inserire altre sotto aprti del lifecycle dell’infrastructural agent; in quanto, tali parti possono essere anche specificate nella definizione iniziale dell’IABehaviour.Relativamente alle specifiche progettuali/implementative dei pattern bio-inspired si è scelto di non realizzare specifici modelli in quanto le uniche operazioni da compiere, identificate ed ampiamente discusse nelle sezioni di analisi, dovranno unicamente essere tradotte in codice operativo da inserire nella ridefinizione dei metodi (onStart(), action() e onEnd()) dei relativi behaviour.Conclusioni
Dopo aver analizzato dettagliatamente la realtà di riferimento relativa ai modelli ispirati alla biologia e agli specifici pattern, la progettazione effettuata risulta completa e dettagliata tale da rendere la successiva fase implementativa non necessaria al fine di aggiungere un ulteriore livello di dettaglio. In definitiva perciò, il progetto risulta concluso in tutte le sue parti ed introduce inoltre un valore aggiunto rispetto all'attuale stato dell'arte nell'ambito della ricerca sui modelli software ispirati alla biologia.Riferimenti
- Description and composition of bio-inspired design patterns: a complete overview (articolo in rivista, 2013) — Jose Luis Fernandez-Marquez, Giovanna Di Marzo Serugendo, Sara Montagna, Mirko Viroli, Josep Lluis Arcos
- Giovanna Di Marzo, Marie-Pierre Gleizes, Anthony Karageorgos. Self-Organisation and Emergence in MAS: An Overview. Informatica, An International Journal of Computing and Informatics, Vol. 30, No. 1, Publication date: June 2006
- Mariachiara Puviani, Giovanna Di Marzo Serugendo, Regina Frei, Giacomo Cabri. A method fragments approach to methodologies for engineering self-organising systems. ACM Transactions on Embedded Computing Systems, Vol. 9, No. 4, Article 39, Publication date: March 2010
- Mano Jean-Pierre, Bourjot Christine, Lopardo Gabriel, Glize Pierre. Bio-inspired Mechanisms for Artificial Self-organised Systems. Informatica, An International Journal of Computing and Informatics, Vol. 30, No. 1, Publication date: May 2005
- Falko Dresslera, Ozgur B. Akan. A survey on bio-inspired networking. Computer Networks, Vol. 54, Issue 6, Pubblication Date: April 2010
- Design Patterns for Self-Organizing Multiagent Systems (articolo in atti, 2007) — Luca Gardelli, Mirko Viroli, Andrea Omicini
- Description and Composition of Bio-Inspired Design Patterns: the Gradient Case (articolo in atti, 2011) — Jose Luis Fernandez-Marquez, Josep Lluis Arcos, Giovanna Di Marzo Serugendo, Mirko Viroli, Sara Montagna
- Description and Composition of Bio-Inspired Design Patterns: the Gossip Case (articolo in atti, 2011) — Jose Luis Fernandez-Marquez, Josep Lluis Arcos, Giovanna Di Marzo Serugendo, Matteo Casadei
- Digital Pheromone Mechanisms for Coordination of Unmanned Vehicles (articolo in atti, 2002) — H. van Dyke Parunak, Sven Brueckner, John Sauter
- TuCSoN Home Page
- JADE Home Page