Coordination for SOS: models and architectures towards autonomous systems

Indice


1. Introduzione

2. Architetture
* 2.1 Stigmergia

    • 2.1.1 Feromoni Digitali
  • 2.2 Coordinazione Chimica
  • 2.3 Coordinazione Field-Based
3 Modelli
  • 3.1 Gamma
  • 3.2 Linda
  • 3.3 Stoklaim
    • 3.3.1 Introduzione: Klaim
    • 3.3.2 Stocastic Klaim: Stoklaim
  • 3.4 Swarmlinda
  • 3.5 Respect
    • 3.5.1 Tuple Spaces: I Limiti
    • 3.5.2 Verso I Tuple Centres
    • 3.5.3 I Tuple Centres
    • 3.5.4 Tuple Centres Temporizzati
4 Conclusione

5 Bibliorgrafia

1. Introduzione

In questo elaborato si vuole descrivere come la ricerca si sta evolvendo nel cercare la soluzione adatta nello sviluppo di un modello di coordinamento per SOS (Self Organized System), in altre parole tutti quei meccanismi o processi che rendono un sistema in esecuzione in grado di cambiare la propria organizzazione senza comandi esterni.

Per giungere a soluzioni implementative valide sarà osservato e descritto il comportamento di sistemi presenti in natura che caratterizzati da architetture di coordianmento ben definite, come ad esempio la stigmergia utilizzata da formiche e termiti per auto-organizzarsi, e la coordinazione basata su reazioni chimiche.

Saranno poi descritti i modelli computazionali che rappresentano la base della coordinazione tra SOS e le varie evoluzioni di essi che sono stati progettati ai fini di riprodurre il comportamento dei sistemi naturali e chimici sopra citati nel rispetto di alcune delle caratteristiche che li contraddistunguono.

Il raggiungimento di un traguardo importante come quello di poter rappresentare sistemi naturali e chimici attraverso modelli computazionali è un’evoluzione considerevole per la tecnologia poiché modelli di coordinazione per SOS completi, possono essere applicati a diverse implementazioni di MAS (Multi-Agents System) rendendo la computazione molto più efficace.

2. Architetture

Osservando gli avvenimenti naturali che accadono ogni giorno sul nostro pianeta si possono notare alcuni fenomeni che mettono in pratica veri a propri meccanismi di auto-organizzazione. Un esempio molto interessante è la stigmergia, utilizzata dalle formiche e dalle termiti per coordinarsi indirettamente, la quale si basa sul rilascio e l’intercettazione di feromoni nell’ambiente.

Un altro sistema molto interessante è quello basato sulle reazioni chimiche per cui la natura ha dettato delle regole che permettono la produzione di molecole a seguito di reazioni specifiche.

Queste architetture sono un punto di partenza per poter studiare e implementare modelli computazionali per l’auto-organizzazione.

2.1 Stigmergia

La stigmergia è un metodo di comunicazione utilizzato nei sistemi decentralizzati col quale gli individui del sistema comunicano fra loro modificando l'ambiente circostante. La stigmergia è stata osservata inizialmente in natura; per esempio, le formiche comunicano le une con le altre lasciando una traccia di feromoni quindi una colonia di formiche è un esempio di sistema stigmergico. Un altro esempio comune può essere definito dalla costruzione dei nidi delle termiti. Anche le termiti usano i feromoni per costruire strutture molto complesse seguendo un semplice insieme di regole decentralizzato. Ogni insetto scava una pallina di fango dal suo ambiente, la copre di feromoni e la lascia sul terreno. Le termiti sono attratte dai feromoni degli insetti dello stesso termitaio e quindi depositano le loro palline di fango vicino a quelle già depositate. Con il tempo questo comportamento porta a costruire pilastri, archi, gallerie e camere.

Il termine è stato introdotto dal biologo francese Pierre-Paul Grassé nel 1959 (6) riferendosi al comportamento delle termiti. Lo definì come: "Stimolazione degli operai mediante il risultato ottenuto."

2.1.1 I feromoni digitali

Il mondo reale prevede tre operazioni sui feromoni chimici che supportano le azioni degli insetti.

Si aggregano informazioni raccolte dai singoli operatori nel tempo raccogliendole insieme.

I feromoni evaporano con il passare del tempo. Questa pratica è un’alternativa innovativa al mantenimento tradizionale della memoria. Le modalità di memorizzazione tradizionali permettono di ricordare tutto quello che viene detto a meno che non ci sia un motivo per dimenticarlo, ed è necessario spendere grandi quantità di computazione in un problema NP-completo per individuare incongruenze che derivano da cambiamenti nell’ambiente. Le formiche iniziano immediatamente a dimenticare tutto quello che imparano, se non gli è costantemente ricordato. Così le informazioni non utili saranno cancellate automaticamente entro un tempo stabilito.

Loro rilasciano feromoni nei luoghi vicini per permettere ai loro simili che passano nelle vicinanze di accedervi.

Il campo che le formiche costruiscono con i feromoni nell'ambiente è, infatti, un campo potenziale che guida i loro movimenti. A differenza di molti potenziali campi utilizzati in applicazioni robotiche convenzionali, soddisfa le caratteristiche delle 4-D:

  • Diverso: le formiche possono rispondere a combinazioni di feromoni, modificando così la loro reazione a seguito di più input ricevuti nello stesso momento.
  • Distribuito: il campo potenziale è generato da depositi di feromoni che sono rilasciati in tutto l'ambiente. Questi depositi svolgono la loro funzione vicino a dove sono rilasciati, e sono utilizzati principalmente dalle formiche che sono vicino a loro.
  • Decentralizzato: sia il comportamento della formica che il mantenimento del feromone sul campo sono decentrati. Le formiche interagiscono solo con i feromoni nelle loro immediate vicinanze, depositando e leggendo l’intensità locale del campo del feromone. Poiché la diffusione decresce rapidamente con la distanza, i depositi sono effettuati solo nelle immediate vicinanze del campo.
  • Dinamico: sotto rinforzo continuo, l'intensità del campo del feromone si stabilizza rapidamente, con una funzione concava di tempo proporzionale a

dinamismoferomonidigitali.png

dove E appartiene a (0,1) è la velocità di evaporazione. Così le nuove informazioni sono rapidamente integrate nel campo, mentre le informazioni obsolete vengono dimenticate automaticamente, attraverso l'evaporazione dei feromoni.

Un'implementazione di feromoni digitali si compone di due elementi: l’ambiente (che mantiene il campo del feromone ed esegue azioni che rappresentano l’aggregazione, l’evaporazione , e la diffusione), e i walker (che depositano e reagiscono al campo mantenuto dall'ambiente). La nostra applicazione ha due specie corrispondenti di agenti. Un insieme di agenti place con le relazioni di adiacenza che costituiscono l’ambiente e ogni walker è rappresentato da un agente walker.

Ogni agente place mantiene una variabile scalare corrispondente a ogni tipo di feromone. Esso aumenta questa variabile quando riceve altri feromoni dello stesso tipo (sia mediante deposito di un walker o per propagazione da un luogo confinante), la variabile nel tempo si consuma e i feromoni dello stesso tipo si propagano negli angenti place confinanti basandosi sulla forza del feromone. Se l'intensità del feromone in una posizione scende sotto una certa soglia, il software non elabora più il feromone, e quest’ultimo scompare.

In linea di principio, non ci sono restrizioni sull’area occupata dagli agenti place. In problematiche fisiche di movimento, ogni agente place è responsabile di una zona precisa, e l’area degli agenti place rappresenta adiacenza tra queste zone. Ci sono diversi modi in cui gli agenti place possono essere assegnati allo spazio. Nel nostro caso abbiamo suddiviso lo spazio fisico in esagoni, ognuno dei quali rappresenta un agente place con sei di essi vicini.

Un agente walker visita un agente place in un dato momento. Esso può leggere l’intensità attuale dei feromoni presenti in quel posto in funzione del loro tipo, e deposita feromoni nell’ambiente. Si può anche determinare dall'agente place la forza relativa di un dato tipo in quel luogo e di quelli a lui vicini. Un walker si sposta da un luogo all'altro facendo girare una sorta di roulette i cui segmenti sono stabiliti secondo i valori dell’intensità degli agenti place vicini. (13)

Tali tecniche possono essere applicate nel gioco degli scacchi o per fare ottimizzazione combinatoria, sono stati anche applicati all’indistria manifatturiera e nel settore militare.

2.2 Coordinazione chimica

L’ispirazione della coordinazione chimica viene dall'idea che i fenomeni fisici complessi sono guidati da (relativamente) semplici reazioni chimiche capaci di coordinare i comportamenti di una grande quantità di agenti, nonché l'evoluzione del sistema globale.

Il modello che rappresenta la coordinazione chimica è formato da un’estensione della versione base di Linda (3.2) con l’utilizzo di diversi tuplespaces. Si può rappresentare il coordinamento basato su reazioni chimiche attribuendo, per ogni tupla, un valore intero definito "concentrazione", misurando il valore di pertinenza/attività della tupla nel tuplespace corrente: maggiore è tale concentrazione, più è probabile e frequente che la tupla sarà recuperata e selezionato dalle leggi di coordinamento per influenzare il comportamento del sistema. La concentrazione delle tuple è dinamica, come tipicamente lo è la pertinenza delle attività all’interno del sistema. In particolare, la concentrazione della tupla evolve "spontaneamente" similmente a quanto avviene nelle reazioni chimiche, cioè, una tupla con concentrazione N è gestita in pratica nello stesso modo di una sostanza chimica fatta di N molecole della stessa specie. Ciò si ottiene attraverso regole di coordinamento espresse sotto forma di reazioni chimiche, l'unica differenza rispetto alle reazioni chimiche standard è che vengono prodotti templates di tuple invece che molecole. (15)

2.3 Coordinazione Field-based

La coordinazione Field-based (basata sui campi) è un tipo di coordinazione indiretta ispirata alla fisica. Lo spazio in cui vivono gli “agenti” si sviluppa sulla base della forza dei campi, ad esempio, campi gravitazionali, campi elettromagnetici e chimici.

Gli agenti a loro volta possono contribuire a distribuire campi nello spazio. Gli agenti sono influenzati nelle loro attività dai campi percepiti localmente (tipo e forza). I campi vengono aggiornati automaticamente per riflettere le condizioni attuali.

Quando si parla di coordinazione Field-based, si fa riferimento al termine agente per riferirsi a qualsiasi tipo di entità autonoma situata in un ambiente, capace di percepirlo attraverso i campi e quindi capace di interagire con suoi simili.

L’ambiente (enivronment) nella coordinazione Field-based, è in genere quello spazio in cui gli agenti eseguono le loro azioni e dove i campi si propagano.

I campi (fields) all’interno di un ambiente sono "proprietà distribuite" di tale ambiente e descrivono dettagli di esso in modo distribuito.

3. I modelli

Utilizzando come punto di partenza le architetture sopracitate sono stati implementati modelli di computazione capaci di rappresentare alcune dinamiche dell’auto-organizzazione naturale.

I modelli di coordinazione base che rappresentano il punto di partenza per tutti gli approfondimenti sono Gamma e Linda, da qui sono state sviluppate diverse evoluzioni di essi tentando di implementare modelli capaci di gestire altri aspetti caratterizzanti del coordinamento in natura e in chimica.

3.1 Gamma

Il modello Gamma può essere descritto come un trasformatore multiset e la sua computazione può essere paragonata a una reazione chimica: un calcolo può essere visto come una successione di reazioni che consumano elementi del multiset e ne producono di nuovi, secondo particolari regole. Il calcolo termina quando non ci sono regole da poter applicare agli elementi presenti.

Quando la condizione vale per diversi sottoinsiemi disgiunti, le reazioni possono avvenire in qualsiasi ordine o simultaneamente, così i programmi Gamma spesso contengono una grande quantità di parallelismo implicito. Questo può essere visto come un vantaggio importante per quanto concerne l’implementazione perché rende Gamma un candidato interessante per l'esecuzione su processori paralleli.

La struttura base utilizzata è il multiset, il quale è come un set (lista) ma presenta i vantaggi di non avere nessuna struttura gerarchica e di permettere l’esistenza di diverse occorrenze dello stesso elemento. Il multiset può contenere elementi di diverso tipo tra cui numeri reali, interi, caratteri, tuple e multiset. La notazione { } è utilizzata per rappresentare i multisets.

Le operazioni principali utilizzate sui multiset sono:

  • Unione: il numero di occorrenze di un elemento in M1+M2 è la somma del numero di occorrenze in M1 e in M2;
  • Differenza: il numero di occorrenze di un elemento in M1-M2 è la differenza numero di occorrenze in M1 e in M2 (se questa differenza è maggiore o uguale a zero, altrimenti è zero);
  • Selezione nondeterministica: oneof(M) produce un elemento arbitrariamente selezionato di M.
Il modello possiede proprietà interessanti che possono essere riassunte come segue:
  • Si basa su un impianto di strutturazione dei dati di alto livello, il multiset, che non introduce inutili dipendenze “artificiali” tra i dati;
  • Si pone l'accento sul principio di località che è molto utile per quanto riguarda la costruzione di un programma e all'attuazione del parallelismo.
Queste proprietà sono state sfruttate nella progettazione di un programma dal quale deriva un metodo che può essere applicato per lo sviluppo di programmi Gamma totalmente corretti.

E’ facile notare che il modello di calcolo Gamma comporta un approccio molto insolito per la progettazione del programma. Un programma non è più visto come una sequenza d’istruzioni che modificano uno stato, ma piuttosto come un trasformatore multiset che opera su tutti i dati contemporaneamente.

E’ chiaro che questa codifica si discosta dalla tradizionale vista ricorsiva dei tipi di dati. Gamma pone l’accento su una vista topologica di tipi di dati: ad esempio, una sequenza è un multiset di valori, alcuni dei quali sono legati da relazioni con i successori, tuttavia, qualsiasi valore della sequenza può reagire indipendentemente dagli altri. Quest’approccio originale ci permette di esprimere la soluzione di molti problemi in modo elegante e diverso. (1)(2)

3.2 Linda

Linda è un modello di coordinazione e comunicazione fra diversi processi paralleli che operano su oggetti archiviati e recuperati da una memoria associativa condivisa e virtuale. (5)

Questo modello è implementato come un “lunguaggio di coordinazione” in cui diverse operazioni primitive che operano su sequenze ordinate di oggetti tipizzati, “tuple”, sono aggiunte al linguaggio sequenziale, come ad esempio il C, ed è presente una memoria logicamente globale e associativa, chiamata tuplespace, nella quale i processi archiviano e recuperano le tuple.

Il modello originale Linda richiede quattro operazioni che i singoli processi svolgono sulle tuple e sul tuplespace:

  • In: legge e rimuove (consuma) atomicamente una tupla dal tuplespace;
  • rd: legge un tuplespace in modo non ditruttivo;
  • out: produce una tupla scrivendola nel tuplespace;
  • eval: crea nuovi processi per valutare delle tuple, scrivendo il risultato nel tuplespace.
Rispetto ad altri modelli di elaborazione parallela, Linda è più ortogonale nel considerare un processo di coordinazione come un'attività separata dal calcolo, ed è più in generale in grado di assumere vari livelli di concorrenza mono-processore, multi-processore, multi-thread, o in rete, basandosi su un singolo modello. La sua ortogonalità permette ai processi di elaborazione in diversi linguaggi e piattaforme d’interoperare con le stesse primitive. La sua genericità consente a un sistema Linda multi-threaded di essere distribuito tra più computer senza modifiche.

Mentre i modelli di message-passing richiedono processi strettamente associati a una sequenza o protocollo d’invio di messaggi, i processi Linda sono disaccoppiati da altri processi, comunicando solo attraverso il tuplespace, un processo non deve necessariamente avere alcuna definizione di altri processi, tranne che per i tipi di tuple consumati o prodotti (per l’accoppiamento dei dati).

Alcuni ricercatori hanno proposto l’aggiunta di più primitive per supportare i diversi tipi di comunicazione e coordinazione tra sistemi informatici (aperti e distribuiti) e per risolvere particolari problemi derivanti da vari usi del modello. I ricercatori hanno sperimentato con vari strumenti d’implementazione la memoria condivisa virtuale per questo modello. Molti di questi ricercatori hanno proposto modifiche più grandi al modello originale Linda, sviluppando una famiglia di sistemi noti come sistemi di Linda-like e implementati come tecnologia ortogonale (a differenza della versione originale). Un esempio è il linguaggio Ease programmato da Steven Ericsson-Zenith.

3.3 StoKlaim

StoKlaim è un’estensione stocastica di Klaim, modello di coordinazione tra apparati mobili derivato da Linda.

3.3.1 Introduzione: Klaim

Klaim (Kernel Language for Agents Interaction and Mobility) è un linguaggio di programmazione lato kernel utilizzato per definire agenti in movimento e le loro strategie d’interazione. (3)

Le caratteristiche distintive di quest’approccio sono l'uso esplicito dei luoghi per accedere a dati o risorse computazionali e la presenza di un semplice sistema per controllare le regole di accesso.

La scelta delle primitive di Klaim è stata fortemente influenzata da algebre di processo e da Linda. Infatti, il nostro linguaggio può essere visto come un processo di calcoli asincroni di alto livello le cui azioni di base sono le primitive originali Linda arricchite con informazioni esplicite circa la posizione dei nodi in cui sono allocati i processi e le tuple.

Posizioni esplicite consentono al programmatore di distribuire e recuperare dati e processi da e verso i punti di una rete e organizzare il tuplespace in diversi spazi dislocati. Inoltre, i luoghi, considerati come tipi di dato del primo ordine, possono essere creati dinamicamente e comunicati attraverso la rete. Il risultato complessivo è un potente formalismo di programmazione che, ad esempio, può essere facilmente utilizzato per modellare l’incapsulamento. Infatti, un modulo incapsulato può essere implementato come un tuplespace appartenente a una posizione privata, e questo garantisce accesso controllato ai dati.

La separazione della distribuzione logica dei processi e delle loro mappature fisiche nella rete porta alla condivisione del controllo tra programmatori e un coordinatore di rete. L’attuale linguaggio di coordinamento è progettato per gestire tutte le questioni riguardanti la distribuzione fisica dei processi. I coordinatori hanno il completo controllo dei cambiamenti di configurazione della rete che possono essere causa di aggiunta o eliminazione di elementi software e luoghi, o trasmissione di programmi e di risorse.

La struttura attuale, in termini di processi e coordinatori, offre un mezzo di astrazione pulito per i linguaggi di programmazione globali, serve a studiare applicazioni di migrazione e a comprendere l’entità delle scelte di configurazione prima di procede con l'effettiva implementazione.

Per tener conto di problemi di sicurezza, estendiamo i processi e i coordinatori Klaim con un semplice sistema di classificazione che può essere utilizzato per applicare staticamente proprietà di sicurezza. Più precisamente, il sistema di classificazione consente di verificare se le operazioni di processi Klaim intendono agire sui luoghi di una rete rispettando le regole di accesso.

Klaim è costituito da un nucleo Linda con diversi tuplespaces e da una collezione di operatori utilizzati per i processi di costruzione, adottati dal CCS di Milner (8). La caratteristica che lo distingue è che le tuple e le operazioni su di esse si trovano in punto specifico di una rete.

3.3.2 Stocastic Klaim: StoKlaim

I problemi di prestazioni e affidabilità sono molto importanti per la computazione basata sulla rete, a causa dell’enorme dimensione dei sistemi - la rete in genere è costituita da migliaia o addirittura milioni di nodi - e la loro forte dipendenza riguardante la mobilità e all'interazione. Interruzioni spontanee di un elaboratore possono facilmente portare al fallimento dell’esecuzione remota o in movimento di un processo, mentre singhiozzi accidentali della rete possono causare la perdita di frammenti di codice o ritardi non prevedibili.

L'enorme quantità di dispositivi informatici coinvolti nella computazione globale produce un tasso d’insuccesso che non può essere ignorato. La presenza di tali fenomeni casuali implica che le definizioni di correttezza della computazione globale del software e delle loro garanzie di privacy non sono rigide come:

"O è sicuro o non lo è"

ma ha un carattere meno assoluto, ad esempio:

"Nel 99,7% dei casi, la privacy può essere garantita”.

La complessità intrinseca della totalità dei calcolatori, però, complica seriamente la valutazione di questi problemi. Metodi sistematici, tecniche e strumenti, tutti basati su solide basi matematiche ad esempio metodi formali, sono quindi necessari per stabilire i requisiti e le garanzie di prestazioni e affidabilità. L’introduzione di StoKlaim serve a estendere la programmazione e i formalismi affermati nell'informatica globale, Klaim, con la gestione dei ritardi casuali.

Le azioni in Klaim indicano esplicitamente il luogo in cui avranno effetto. Klaim supporta aspetti fondamentali per il computing a livello globale come la distribuzione dei processi, la valutazione a distanza, il codice on-demand, e la creazione del luogo.

In StoKlaim, si presume che le azioni abbiano una durata casuale governata da una distribuzione esponenziale negativa. Il modello operativo risultante è quindi una catena di Markov a tempo continuo (CTMC), uno dei modelli più popolari per la valutazione delle prestazioni e affidabilità dei sistemi di elaborazione delle informazioni. La nostra estensione è ispirata da estensioni Markoviane di algebre di processi tradizionali. Le durate esponenziali mantengono una semantica semplice ma sembrano avere un’espressività un po’ limitata; tuttavia, le combinazioni appropriate di distribuzioni esponenziali possono approssimare distribuzioni generali con arbitraria precisione. Di conseguenza, esse sono adeguate per molti fenomeni della vita reale (come i tassi di guasto e tempi di attesa) e, soprattutto, sono la più appropriata approssimazione stocastica nel caso in cui si conosca la durata media. L’approccio in questione può essere dimostrato modellando la diffusione di un virus attraverso una rete. (4)

3.4 SwarmLinda

Negli ultimi anni, sono stati studiati nel campo dell'informatica i nuovi modelli provenienti dalla biologia. L'interesse primario è di utilizzare questi modelli come tecniche per trovare soluzioni applicabili ai problemi NP-hard.

In questi modelli, attori (formiche, termiti, ecc.) sacrificano obiettivi individuali (se presenti) a beneficio della collettività. Essi agiscono molto decentralizzati. Il lavoro è svolto da decisioni puramente locali e con l’adozione di azioni che richiedono solo piccoli calcoli. Queste caratteristiche permettono a questi sistemi di essere molto scalabili. Questo sciame d’intelligenza (Swarm Intelligence) è un'interessante occasione per ripensare la scalabilità della struttura delle tuple.

L'uso di tali principi come alternativa ai regimi orientati ai dati potrebbe consistere semplicemente in un sistema in cui i modelli sono modellati come formiche che cercano cibo (tuple corrispondenti). Si può concepire il "mondo" dei server Linda come uno spazio bidimensionale in cui le formiche cercano il cibo, lasciando un sentiero che traccia gli eventi di successo.

Con un’ottimizzazione dei sentieri orientato in base al comportamento della formica, possono essere individuati percorsi di produttori/cosumatori di tuple e quindi utilizzati per ottimizzare le prestazioni del sistema: invece di interrogare insiemi di repliche, il "modello formica" porta direttamente al punto in cui ci si aspetta l’incontro con del cibo. Tecnicamente, queste relazioni tra i singoli messaggi si sostituiscono ai luoghi presenti tra il produttore e il consumatore.

Quanto sopra è solo un esempio. Un modello SwarmLinda più realistico dovrebbe prendere in considerazione alcuni principi che possono essere osservati nella maggior parte dei sistemi Swarm:

  • Semplicità: gli individui Swarm sono creature semplici che svolgono compiti semplici. Non fanno nessun ragionamento complesso e implementano un piccolo insieme di semplici regole. L'esecuzione di queste regole porta alla nascita di comportamenti complessi. Soggetti attivi in un sistema SwarmLinda devono anche obbedire al principio di semplicità ed essere "piccoli" in termini di utilizzo delle risorse.
  • Dinamismo: Gli sciami naturali si adattano dinamicamente ai cambiamenti degli ambienti. In sistemi distribuiti aperti, la configurazione di applicazioni e servizi in esecuzione cambia nel tempo. Se una tupla si trova in una determinata posizione, non significa necessariamente che esisteranno altre tuple simili nella stessa posizione in futuro.
  • Località: individui Swarm osservano la loro zona adiacente e prendono decisioni in base al loro punto di vista locale. La chiave verso la scalabilità in SwarmLinda consiste nella regola per cui i soggetti attivi devono eseguire solo ricerche locali e interrogare solo i diretti vicini.
Per comprendere appieno questi principi, bisogna capire come un sistema SwarmLinda dovrebbe essere organizzato. I sistemi Linda non considerano il concetto di formiche o di cibo. Un sistema SwarmLinda deve astrarre questi concetti all’interno del mondo Linda.

Possiamo definire uno SwarmLinda attraverso le seguenti astrazioni: gli individui sono soggetti attivi che sono in grado di osservare la loro zona, muoversi nell'ambiente, e cambiare lo stato dell'ambiente in cui si trovano. L'ambiente è il contesto che gli individui osservano e su cui lavorano. Lo stato è un aspetto dell'ambiente che può essere osservato e modificato dagli individui. (14)

3.5 ReSpecT

ReSpecT (Reaction Specification Tuples) è un linguaggio logico per il coordinamento dei sistemi software complessi. ReSpecT promuove un modello di coordinazione dotato di tuple centres programmabili, versatile nella coordinazione dei media. Il comportamento dei tuple centres di ReSpecT è programmato attraverso il linguaggio ReSpecT di primo ordine. (9)

3.5.1 Tuple spaces: i limiti

Il problema principale di modelli di coordinazione basati sui tuplespace è correlato al comportamento fisso del mezzo coordinazione. Dato un modello che adotta tuplespace come supporti di coordinamento, il comportamento del tuplespace, rappresentato dalle sue transizioni di stato in risposta ad eventi di comunicazione, viene impostato una volta per tutte dal modello, e non può essere adattato per l'applicazioni specifiche che lo richiesdono. Per esempio, nell versione originale di Linda si può solo leggere, scrivere o consumare una singola tupla alla volta, e accedere ad un tupla nel tuplespace attraverso un meccanismo di corrispondenza incorporato nel modello associativo. Questo comportamento potrebbe considerarsi sufficientemtne espressivo per far fronte a tutti i casi di coordinamento richiesti da un sistema multiagente, facendo si che tutto il carico di lavoro sia afidato al tuplespace stesso.

Tuttavia, può anche accadere che meccanismi basati su tuplespace standard non siano sufficienti a supportare direttamente le politiche richieste di coordinamento e, di conseguenza, non possono essere incorporati nel mezzo di coordinamento.

3.5.2 Verso i Tuple centres

I suddetti limiti potrebbero essere superati mantenendo la rappresentazione delle informazioni e la percezione separate nello spazio d’interazione dell'agente. Questo, infatti, consentirebbe ai protocolli d‘interazione dell'agente di essere organizzati in base alla percezione dello spazio di comunicazione che l’agente stesso desidera, indipendentemente dalla sua rappresentazione effettiva in termini di tuple. Inoltre, mettendo correttamente in relazione la rappresentazione delle informazioni e la percezione, gli agenti potrebbero essere trasportati dal valore di coordinamento, integrando ogni regola di coordinamento all’interno dei mezzi.

Questa è la motivazione che porta alla definizione del modello tuple centres (centri di tuple), il quale consiste in un un tuple space il cui comportamento in risposta ad eventi di comunicazione non è più fissato per sempre nel modello di coordinazione, ma può essere definito in base alle politiche di coordinamento necessarie. Dal momento che ha esattamente la stessa interfaccia, un tuple centre viene percepito da agenti come tuple space standard. Tuttavia, un tuple centre può comportarsi in un modo completamente diverso rispetto ad un tuple space, poiché il suo comportamento può essere specificato in modo da incapsulare le norme di coordinamento che regolano l'interazione dell’agente.

3.5.3 I Tuple centres

Un tuple centre è un tuple space migliorato con uno specifico comportamento, definendo il comportamento del tuple centre in risposta ad eventi di comunicazione. Un dettaglio del comportamento del tuple centre è espresso attraverso un linguaggio di specifica delle reazione, e associa ogni evento di comunicazione che si verifica nel tuple centre ad un (eventualmente vuoto) insieme di attività computazionali chiamate reazioni. Più precisamente, un linguaggio di specifica delle reazioni

  • consente le definizioni di calcoli all'interno di un tuple centre, chiamate reazioni
  • permette di associare reazioni (sia in entrata che in uscita) a eventi di comunicazione che si verificano in un tuple centre.
Ogni reazione può in linea di principio accedere e modificare l'attuale stato del tuple centre (analogamente all'aggiunta o la rimozione di tuple) e accedere a tutte le informazioni relative all' attivazione dell’evento di comunicazione (ad esempio l'agente in esecuzione, l'operazione richiesta, la tupla coinvolta, ecc), che è completamente visibile. Così, la semantica delle primitive di comunicazione tuple space normali non è più vincolata ad essere semplice come nel modello Linda (cioè, l'aggiunta, la lettura e la rimozione di tuple), ma può essere prodottoad un livello di complessità come richiesto dalle esigenze specifiche dell’applicazione.

Ogni evento di comunicazione può innescare una molteplicità di reazioni che vengono eseguite localmente al tuple centre. Quando si verifica un evento di comunicazione, un tuple centre prima si comporta allo stesso modo di un tuple space standard, poi esegue tutte le reazioni innescate prima di servire qualsiasi altro evento comunicazione attivato da un agente. Questo produce tuple centres con due caratteristiche principali:

  • poiché una specifica di comportamento vuota comporta reazioni non attivate indipendentempete dal evento di comunicazione, il comportamento di un default di un tuple centre è quello di un tuple space nel caso in cui non venga data alcuna specifica di comportamento;
  • dal punto di vista degli agenti, il risultato della chiamata di una primitiva di comunicazione è la somma degli effetti della stessa primitiva e di tutte le reazioni attivate su di essa, percepita complessivamente come un'unica transizione dello stato del tuple centre.
Quindi, le reazioni sono eseguite in modo tale che il comportamento visibile di un tuple centre in risposta a un evento di comunicazione è percepito dagli agenti come una transizione unica dello stato del tuple centre, come nel caso dei tuple space. Tuttavia, a differenza di un tuple space standard, le cui transizioni di stato sono limitate all’aggiunta, lettura o cancellazione di una singola tupla, la transizione dello stato di un tuple centre può essere complessa a seconda di quanto è necessario. Questo rende possibile distinguere il punto di vista dell'agente rispetto al tuple centre (percepito come uo tuple space standard) dallo stato attuale di un tuple centre, e di collegarli in modo tale da incorporare le regole di coordinamento governano il sistema multiagente.

Complessivamente, i tuple centres promuovono una forma di coordinazione ibrida, volta a preservare i vantaggi dei modelli di data-driven, pur affrontando i loro limiti in termini di capacità di controllo. Quindi, un tuple centres è fondamentalmente un mezzo di coordinazione data-driven, che viene percepito come tale dagli agenti. Tuttavia, un tuple centre offre anche alcune funzionalità tipiche di modelli di control-driven, come la completa visilbilità di eventi di comunicazione, così come la capacità di reagire selettivamente a eventi di comunicazione e implementare le regole di coordinamento manipolando lo spazio di interazione. (10)

3.5.4 Tuple Centres temporizzati

I tuple centres temporizzati estendono i tuple centres standard. In primo luogo, la definizione del tempo attuale per un tuple centre viene descritta come un tempo locale, relativo e discreto. Concettualmente, il tempo di un tuple centre è generato da un orologio interno tuple centre stesso: non può essere stabilita in linea di principio nessuna relazione tra il preciso istante di due differenti tuple centre. L'ora corrente di un tuple centre temporizzato è pari a zero quando esso è effettivamente creato dall'infrastruttura in fase di esecuzione. Il tempo assoluto è disponibile, se opportunamente calcolato aggiungendo l'ora(assoluta) di creazione del tuple centre all’ora corrente.

Rispetto al modello formale, il tempo di una transizione è introdotto nel ciclo di lavoro di un tuple centre base, in aggiunta alle transizioni esistenti di comprensione, comunicazione, e reazione. Il tempo di una transizione è destinato ad avere la priorità rispetto a tutte le altre transizioni, compresa la reazione. Concettualmente, la transizione di tempo che viene eseguita ad ogni battito del clock del tuple centre è considerata una reazione alla generazione di un evento di tempo per ogni battito.

Quindi, analogamente agli eventi di comunicazione, è possibile specificare reazioni innescate da eventi temporali (reazioni temporizzate). Le reazioni temporizzate seguono la stessa semantica di altre reazioni: una volta attivate, vengono inserite nel set di reazioni innescate e poi eseguite, atomicamente, in un ordine non deterministico. Poiché in un dato momento, può verificarsi un solo evento di tempo, ogni reazione temporizzata viene eseguita solo una volta.

Come risultato, un tuple centre temporizzato può essere programmato per reagire al trascorrere del tempo, in modo da applicare policy coordinamento basate sul tempo. (11)

4. Conclusioni

Si può dedurre da quanto documentato che i modelli di coordinamento di cui sopra non riescono a cogliere tutte le caratteristiche essenziali del coordinamento ispirato alla natura.

I modelli di coordinamento, per lo più, catturano solo alcune delle dinamiche complessive del sistema che li rende sostanzialmente sicuri. Per esempio, Gamma imita reazioni chimiche, ma non coglie aspetti essenziali nei processi chimici come i tassi di reazione e di concentrazione mentre tuplespace di tipo (bio)chimico sfruttano appieno la metafora chimica fornendo leggi chimiche dipendenti dal tempo e stocastiche. (15) (16)

Per questo diversi gruppi di ricerca tentano di estendere i modelli tuple-based esistenti per raggiungere la potenza espressiva necessaria per modellare e costruire MAS con una complessità paragonabile a sistemi naturali.

La maggior parte dei sistemi naturali, quando osservati in tutta la loro complessità, presenta diversi livelli ognuno con le proprie metafore ei meccanismi corrispondenti, molti nuovi approcci al coordinamento MAS complesso integrano diverse fonti d’ispirazione, come ad esempio TOTA che sfrutta sia i meccanismi di coordinamento filed-based che quelli di tipo stigmergico e il modello di coordinamento SAPERE utilizzato per gli ecosistemi di servizi pervasivi i quali integrano la metafora chimica per guidare l'evoluzione delle astrazioni di coordinamento, le astrazioni biochimiche per la topologia e la diffusione e la definizione di ecosistema, al fine di modellare la struttura e la dinamica complessiva del sistema. (7) (17) (18)

Più in generale, lo scopo della ricerca in quest’ambito è di permettere a MAS coordinati di catturare ed esprimere appieno le dinamiche dei sistemi naturali complessi. (12)

5. Bibliografia

1 Banâtre, J.-P., Fradet, P., and Le Métayer, D. (2001).
Gamma and the chemical reaction model: Fifteen years after.
In Calude, C. S., Pâun, G., Rozenberg, G., and Salomaa, A., editors, Multiset Processing. Mathematical, Computer Science, and Molecular Computing Points of View, volume 2235 of LNCS, pages 17–44. Springer.

2 Banâtre, J.-P. and Le Métayer, D. (1990).
The GAMMA model and its discipline of programming.
Science of Computer Programming, 15(1):55–77.

3 De Nicola, R., Ferrari, G., and Pugliese, R. (1998).
KLAIM: A kernel language for agent interaction and mobility.
IEEE Transaction on Software Engineering, 24(5):315–330.

4 De Nicola, R., Latella, D., Katoen, J.-P., and Massink, M. (2006).
StoKlaim: A stochastic extension of Klaim.
Technical Report 2006-TR-01, Istituto di Scienza e Tecnologie dell’Informazione “Alessandro Faedo” (ISTI).

5Gelernter, D. (1985).
Generative communication in Linda.
ACM Transactions on Programming Languages and Systems, 7(1):80–112.

6 Grassé, P.-P. (1959).
La reconstruction du nid et les coordinations interindividuelles chez Bellicositermes natalensis et Cubitermes sp. la théorie de la stigmergie: Essai d’interprétation du comportement des termites constructeurs.
Insectes Sociaux, 6(1):41–80.

7 Mamei, M. and Zambonelli, F. (2004).
Programming pervasive and mobile computing applications with the TOTA middleware.
In Pervasive Computing and Communications, pages 263–273. 2nd IEEE Annual Conference (PerCom 2004), Orlando, FL, USA, 14–17 March 2004. Proceedings.

8 R. Milner (1989).
Communication and Concurrency.
Prentice Hall International.

9 Omicini, A. and Denti, E. (2001).
From tuple spaces to tuple centres.
Science of Computer Programming, 41(3):277–294.

10 Omicini, A., Ricci, A., and Viroli, M. (2005).
Time-aware coordination in ReSpecT. In Jacquet, J.-M. and Picco, G. P., editors, Coordination Models and Languages, volume 3454 of LNCS, pages 268–282.
Springer-Verlag. 7th International Conference (COORDINATION 2005), Namur, Belgium, 20–23 April 2005. Proceedings.

11 Omicini, A., Ricci, A., and Viroli, M. (2007).
Timed environment for Web agents.
Web Intelligence and Agent Systems, 5(2):161–175.

12 Omicini, A. and Viroli, M. (2011).
Coordination models and languages: From parallel computing to self-organisation.
The Knowledge Engineering Review, 26(1):53–59. Special Issue 01 (25th Anniversary Issue).

13 Parunak, H. V. D., Brueckner, S., and Sauter, J. (2002).
Digital pheromone mechanisms for coordination of unmanned vehicles.
In Castelfranchi, C. and Johnson, W. L., editors, 1st International Joint Conference on Autonomous Agents and Multiagent systems, volume 1, pages 449–450, New York, NY, USA. ACM.

14 Tolksdorf, R. and Menezes, R. (2004).
Using Swarm Intelligence in Linda Systems. In Omicini, A., Petta, P., and Pitt, J., editors, Engineering Societies in the Agents World IV, volume 3071 of LNCS, pages 49–65. Springer.
4th International Workshops (ESAW 2003), London, UK, 29-31 October 2003. Revised Selected and Invited Papers.

15 Viroli, M., Casadei, M., Nardini, E., and Omicini, A. (2010).
Towards a chemical-inspired infrastructure for self-* pervasive applications. In Weyns, D., Malek, S., de Lemos, R., and Andersson, J., editors, Self-Organizing Architectures, volume 6090 of LNCS, chapter 8, pages 152–176. Springer.
1st International Workshop on Self-Organizing Architectures (SOAR 2009), Cambridge, UK, 14-17 September 2009, Revised Selected and Invited Papers.

16 Viroli, M., Casadei, M., and Omicini, A. (2009).
A framework for modelling and implementing self-organising coordination. In Shin, S. Y., Ossowski, S., Menezes, R., and Viroli, M., editors, 24th Annual ACM Symposium on Applied Computing (SAC 2009), volume III, pages 1353–1360, Honolulu, Hawai’i, USA. ACM.

17 Viroli, M., Pianini, D., Montagna, S., and Stevenson, G. (2012).
Pervasive ecosystems: a coordination model based on semantic chemistry. In Ossowski, S., Lecca, P., Hung, C.-C., and Hong, J., editors, 27th Annual ACM Symposium on Applied Computing (SAC 2012), Riva del Garda, TN, Italy. ACM.

18 Zambonelli, F., Castelli, G., Ferrari, L., Mamei, M., Rosi, A., Di Marzo, G., Risoldi, M., Tchao, A.-E., Dobson, S., Stevenson, G., Ye, Y., Nardini, E., Omicini, A., Montagna, S., Viroli, M., Ferscha, A., Maschek, S., and Wally, B. (2011).
Self-aware pervasive service ecosystems.
Procedia Computer Science, 7:197–199. Proceedings of the 2nd European Future Technologies Conference and Exhibition 2011 (FET 11).