MAS for SOS: models and technologies

Indice

1 - Introduzione

E’ indubbio come le infrastrutture e i servizi informatici siano di vitale importanza in ogni aspetto del mondo moderno. Possiamo assistere ad una loro continua e costante crescita, che porta alla sempre più chiara inadeguatezza delle soluzioni tradizionali per la loro gestione. L’attenzione viene sempre più posta verso sistemi software robusti, affidabili, scalabili ed in grado di adattarsi ai cambiamenti dell’ambiente, con un minimo intervento esterno. Al momento la maggioranza dei sistemi è affidata ad un controllo centralizzato, che però tende a divenire sempre meno gestibile con l’aumento della complessità. La soluzione è quella di spingersi verso software capace di cambiare in base all’ambiente e di adattarsi ai fallimenti, senza controllo centralizzato. Devono essere quindi in grado di auto-organizzarsi. L’ Auto-Organizzazione è sempre più considerata come metodo per la risoluzione di complicati problemi di ingegneria, e la sua applicazione in differenti aree informatiche è sempre più frequente e soggetto di ricerca.

Torna all'Indice

2 - Agenti e Sistemi Multi Agente

Il seguente capitolo ha lo scopo di introdurre e approfondire i concetti principali per comprendere il dominio dei sistemi multi agente (Multi-Agent System o MAS). Per prima cosa verrà affrontato e descritto il concetto di Agente in particolare capiremo che cos’è un agente, quali sono le sue proprietà e verranno descritte le differenze e analogie tra Oggetti e Agenti. Dopo questa breve ma necessaria introduzione agli Agenti, inizieremo a parlare dei MAS, ovvero dei Sistemi Multi-Agente. Anche in questo caso capiremo che cos’è un MAS e quali sono le sue proprietà. Infine verrà introdotto il concetto di Ambiente e ci soffermeremo soprattutto sulla stretta relazione che intercorre tra Ambiente e MAS, spiegando il perché questo tipo di interazione ha un ruolo chiave nel ciclo di vita di questi sistemi.

Torna all'Indice

2.1 - Agenti

Prima di iniziare a parlare dei MAS, è opportuno partire da una descrizione delle entità che compongono questi tipi di sistemi, ovvero gli agenti. Questa sezione ha quindi il compito di introdurre il concetto di Agente. Verranno descritte le principali proprietà di un agente, mettendo in luce soprattutto le proprietà più interessanti che un agente necessita per appartenere a un MAS. Poi verranno descritti i vari tipi di architetture che caratterizzano un agente e infine per comprendere al meglio il concetto di agente verrà descritta la relazione tra agente e oggetto.

Torna all'Indice

2.1.1 - Definizione di un Agente

Un agente è un’entità fisica o virtuale (Software) che ha le seguenti caratteristiche:

  • Autonoma.
  • Situato in un ambiente e in grado di agire in esso o su esso.
  • Possiede una rappresentazione parziale del suo ambiente.
  • In grado di comunicare con altri agenti.
  • Possiede un obiettivo individuale e una funzione di soddisfazione.
  • Possiede delle risorse.
  • In grado di percepire il suo ambiente.
  • Possiede delle abilità e offre dei servizi.
Il comportamento di un Agente deve dipendere fortemente dalle sue percezioni, dalla sua conoscenza, dalle sue abilità, dalle sue intenzioni, dalle varie interazioni… Un agente ha il seguente ciclo di vita:
  • Percezione: l’agente percepisce nuove informazioni provenienti dal suo ambiente.
  • Decisione: l’agente sceglie le azioni che sono da fare.
  • Azione: l’agente agisce, esegue le azioni che ha scelto della fase precedente.
Alcuni esempi di Agente possono essere i seguenti: l’assistenza clienti in un sistema di recupero delle informazioni, un esperto in un sistema di diagnosi, un giocatore in una squadra di calcio, una formica in un formicaio.

example.jpg

Torna all'Indice

2.1.2 - Proprietà di un Agente

  • Agent Autonomy: L’autonomia è la proprietà più importante per un agente. L’autonomia può beneficiare l’esistenza dell’agente con la proprietà di vitalità, ovvero quando un agente è in grado di mantenere alcuni dei suoi parametri in un determinato intervallo. Ad esempio un robot può mantenere la sua energia ad un determinato livello, al fine di continuare a vivere. L’autonomia può essere intesa anche come autonomia di vita: un agente è in grado di vivere in modo indipendente dall’esistenza degli altri agenti. Per esempio se consideriamo un insieme di robot identici che devono ordinare delle scatole in una stanza, se un robot ad un certo punto non riesce più a svolgere il proprio servizio, un altro robot può continuare svolgendo anche i suoi task. Per un agente artificiale, l’autonomia è intesa come autonomia del controllo delle decisioni. Un agente deve essere in grado di decidere quale sarà o quale non sarà la sua prossima azione. L’agente deve essere in grado di prendere decisioni in base alle sue percezioni, alla sua conoscenza e ai suoi desideri. Un agente, per essere qualificato come autonomo, deve essere in grado di percepire e agire. Il livello di autonomia di un agente dipende naturalmente dal contesto. La cosa più importante da sottolineare è che se un’entità è senza autonomia, non può essere considerata un agente.
  • Reactive Agent: Un agente reattivo è un agente in grado di reagire ai cambiamenti all’interno dell’ambiente circostante e mantenere un’interazione con esso. In generale un agente agisce per raggiungere i suoi obiettivi avendo quindi un comportamento che dipende direttamente dall’ambiente. La formica è un tipico esempio di agente reattivo. Il suo comportamento è dettato da un insieme di regole condizione-azione secondo il quale quando le condizioni di una regola vengono soddisfatte dalla percezione dell’ambiente e/o dal proprio stato interno l’azione viene eseguita. Una formica raccoglierà del cibo se percepisce del cibo vicino a se stesso nel proprio ambiente.
  • Proactive Agent: Un agente proattivo è in grado di generare e raggiungere i propri obiettivi. Non è solo guidato dagli eventi, ma è anche guidato dai suoi obiettivi. Per esempio consideriamo un agente di tipo E-commerce che può decidere di abbandonare un suo obiettivo “compra l’oggetto X”, perché il prezzo è troppo alto ed optare quindi sull’acquisto di un altro oggetto.
  • Social Agent: Un agente si dice sociale se è a conoscenza di altri agenti ed è in grado di interagire. Questa è una proprietà necessaria per un agente che fa parte di un MAS.
  • Communicating Agent: Un agente si dice comunicante se è in grado di interagire con gli altri agenti tramite l’invio e la ricezione di messaggi.
  • Situated Agent: Un agente situato è un agente che comunica con gli altri agenti tramite l’ambiente e interagisce con l’ambiente modificandolo.
  • Adaptive Agent: è un agente che può mutare i suoi comportamenti durante la sua vita. Per fare ciò necessita di una determinata memoria per apprendere e quindi memorizzare i suoi futuri comportamenti. L’apprendimento può essere fatto con metodi classici come: bucket-brigate (catena umana), algoritmi genetici… In generale nel MAS la fase di apprendimento in un agente tiene conto degli altri agenti.
  • Mobile Agent: Gli agenti che vengono progettati possono possedere alcune di queste proprietà, quindi risultano modulari. La modularità permette di progettare una vasta gamma di agenti diversi tra loro.
Torna all'Indice

2.1.3 - Architettura di un Agente

Gli agenti appartengono a tre moduli principali:

  • Percezione: Il modulo di percezione ha il compito di prendere in considerazione gli eventi provenienti dall’ambiente degli agenti, che dipendono dal modo in cui l’agente interagisce con il suo ambiente. Ad esempio per gli agenti comunicanti può essere una boxmail per ricevere messaggi da altri agenti, mentre per gli agenti situati possono essere dati provenienti da sensori di rilevamento.
  • Decisione: Questo modulo è composto da strumenti di supporto alla conoscenza e alle decisioni utili per attivare gli agenti ad eseguire i loro compiti o a raggiungere i loro obiettivi.
  • Azione: Il modulo di azione gestisce tutte le attività da completare in base ai risultati del processo di ragionamento. L’insieme di tutte queste azioni ci permettono di osservare dall’esterno il comportamento dell’agente.
L’architettura di un agente si differenzia in tre classi principali:
  • Architettura Reattiva
  • Architettura Cognitiva
  • Architettura Ibrida
Torna all'Indice

2.1.4 - Relazione tra Agenti e Oggetti

Gli oggetti sono delle entità programmate che hanno delle ovvie similarità con gli agenti, ma hanno anche grandi differenze. Come gli oggetti anche gli agenti hanno uno stato interno e comportamenti modulari. Per gli oggetti abbiamo i metodi, mentre per gli agenti abbiamo le competenze o le abilità. Entrambi agiscono per modificare il proprio stato e comunicano tra loro tramite lo scambio di messaggi. Una delle più importanti differenze risiede nell’autonomia del controllo. Nel caso degli agenti chi riceve una richiesta tramite un messaggio può decidere di eseguire o no la richiesta. Quindi chi riceve ha il potere di decidere. Mentre nel caso degli oggetti è chi invia il messaggio che prende la decisione, perché l’oggetto che riceve una chiamata a un metodo, deve eseguire. L’ambiente per un agente è un concetto importante, mentre per un oggetto è poco importante. Nella programmazione ad oggetti non ci sono linee guida per implementare le proprietà di reattività, probabilità e sociabilità in modo dinamico. Le metodologie object-oriented sono insufficienti per la progettazione di agenti, ecco perché sono nate nuovi modelli, metodologie e strumenti adatti per la progettazione di agenti. Le relazioni “is-a” o “is-part-of” che ritroviamo nel modello a oggetti sono insufficienti per modellare l’organizzazione di un sistema complesso. Gli agenti hanno una significativa parte sociale, che influenza i suoi comportamenti. Le interazioni tra gli agenti sono ricche e complesse da implementare. Mentre la comunicazione tra oggetti consiste solo in chiamate a metodi e la loro interazione è definita in modo rigido. Il concetto di agente è attualmente più di una tecnologia efficiente, rappresenta un nuovo concetto di progettazione del software, dove l'agente è un software autonomo che persegue un obiettivo, che si trova all'interno di un ambiente e interagisce con altri agenti con le lingue di protocollo. Spesso, un agente viene considerato come oggetto "intelligente", o come un livello di astrazione sopra oggetti e componenti. Gli agenti e gli oggetti sono paradigmi essenziali per aiutare i progettisti di sistemi software. Perché il concetto di agente è a un livello di astrazione superiore dell'oggetto, facilita la specifica e la progettazione di applicazioni complesse. La programmazione di tali sistemi in genere è realizzato utilizzando linguaggi a oggetto, ma alcuni linguaggi di programmazione ad agente sono in fase di sperimentazione.

Torna all'Indice

2.2 - Sistemi Multi Agente

2.2.1 - La Storia dei MAS

I MAS sono i maggiori esponenti tra i sistemi artificiali che si basano sulla complessità e la distribuzione. Il paradigma MAS appare per la prima volta verso il 1980, dove le sue prime specifiche riguardavano il comportamento collettivo. I MAS vengono distinti in tre generazioni diverse;

  • Prima Generazione (1970-1980): La prima generazione si concentra sul problem solving distribuito. In questi sistemi la conoscenza e l’elaborazione sono distribuiti, ma il controllo è centralizzato, inoltre sono sistemi ad hoc con nessun potenziale di riusabilità.
  • Seconda Generazione (1980-1990): La seconda generazione si basa su sistemi con controllo decentralizzato e sistemi generici per aumentare la riusabilità.
  • Terza Generazione (1990-2000): La terza generazione si basava sulle interazioni tra Agenti
  • Attuale Generazione (2000-…): La generazione attuale centra il suo interesse sull’ambiente, l’apertura e le dinamiche di questi sistemi, e le tecniche MAS iniziano a diventare la strada per la progettazione di SOS (Self-Organising System).
Torna all'Indice

2.2.2 - Definizione di MAS

Un sistema multi agente (MAS) può essere definito come un insieme di agenti che interagiscono tra loro all’interno di un ambiente comune per risolvere dei compiti comuni. Ogni agente cerca di raggiungere i propri obiettivi che a volte possono essere in conflitto con gli obiettivi di un altro agente. I sistemi multi agente possono essere distinti in tre classi principali:

  • MAS in interazione con gli utenti: In generale questo tipo di sistema è costituito da un agente assistente che a sua volta rappresenta un’utente del sistema. Le difficoltà alla base di questa tipologia di sistema sono nell’avere un giusto modello di utente e nel facilitare le interazioni tra sistema e utente.
  • Simulazione con MAS: Questa tipologia di MAS effettua delle simulazioni su modelli di fenomeni naturali con lo scopo di predirli e capirli. Le entità coinvolte nella simulazione vengono rappresentate da agenti, in particolare le entità che interagiscono con altre entità o interagiscono con l’ambiente. Il lavoro che deve svolgere il sistema non è definito in modo specifico, quindi è il sistema che si modella e si comporta come se fosse un sistema reale. Il lavoro più complicato per chi modella questo tipo di MAS è quello di settare in modo opportuno i vari parametri degli agenti, in modo da ottenere un comportamento globale desiderato.
  • Risoluzione di problemi collettivi: Un agente in questa tipologia di sistema ha il compito di risolvere un lavoro globale condiviso da tutta la comunità. Quindi l’obiettivo è quello di far cooperare tutti gli agenti per arrivare a una soluzione globale del problema. Per fare questo ogni agente è dotato di abilità e risorse parziali, inoltre ha una conoscenza e una rappresentazione dell’ambiente limitate.
Torna all'Indice

2.2.3 - Proprietà dei MAS

  • Autonomo: Un sistema è autonomo quando non è controllato da entità esterne. Questa proprietà è soddisfatta se il sistema è composto da agenti autonomi.
  • Distribuito, Decentralizzato: Le informazioni e la conoscenza è distribuita a tutti gli agenti del sistema. La conoscenza può essere di due tipi: una conoscenza relativa alle abilità, necessaria per le applicazioni e una conoscenza relativa alla rappresentazione del mondo circostante.
  • Asincrono, Parallelo: In un sistema MAS l’esecuzione degli agenti avviene in modo asincrono e parallelo.
  • Aperto/Chiuso: Un sistema MAS si dice aperto quando gli agenti al suo interno possono essere rimossi in runtime e i nuovi agenti possono essere progettati da progettisti differenti.
  • Eterogeneo/Omogeneo: Questa proprietà può dipendere da diversi fattori, ma quello che ci interessa di più è a livello dell’architettura. Quindi un sistema si dice omogeneo se tutti gli agenti al suo interno hanno la stessa architettura. Altrimenti si dice eterogeneo. In un sistema eterogeneo gli agenti hanno architetture differenti, quindi una delle imprese più importanti diventa l’interoperabilità tra gli agenti.
Torna all'Indice

2.2.4 - Problematiche dei MAS

Si possono rilevare cinque principali problematiche nei confronti della creazione di sistemi multi agente.

  • Azioni simultanee: come può un insieme di agenti agire simultaneamente in un ambiente frammentato, e come interagisce tale ambiente in risposta agli agenti? Le questioni qui sottintese sono, tra le altre, quella della rappresentazione dell'ambiente per mezzo degli agenti, della collaborazione tra gli agenti, e della pianificazione dell'attività di una molteplicità d'agenti.
  • Relazione con il mondo esterno: è da considerare la problematica dell'agente e della sua relazione col mondo esterno, la quale è rappresentata dal modello cognitivo di cui dispone l'agente. Ogni singolo individuo in una società costituita da molteplici agenti deve essere in grado di mettere in opera le azioni più rispondenti ai suoi obiettivi. Tale attitudine alla decisione è legata ad uno stato mentale che riflette le percezioni, le rappresentazioni, le convinzioni ed un certo numero di parametri "psichici" (desideri, tendenze...) dell'agente. La problematica in questione copre anche la nozione dei vincoli dell'agente nei confronti di un agente terzo.
  • Interazioni: I sistemi ad agenti multipli necessitano altresì dello studio della natura delle interazioni, come fonte di opportunità, da una parte, e di vincoli dall'altra. La problematica dell'interazione si interessa alle modalità di interazione (quale linguaggio? quale supporto?), all'analisi ed alla concezione delle forme d'interazione tra agenti. Le nozioni di collaborazione e di cooperazione (considerata come collaborazione + coordinamento delle azioni + risoluzione dei conflitti) sono in questo campo questioni fondamentali. Se si applicano le mere conoscenze dei sistemi a singolo agente a quelli multi agente si avranno degli agenti egoisti (self-interested) che non coopereranno in alcun modo, dunque l'obiettivo del sistema sarà raggiunto in minima parte.
  • Adattamento: Di seguito può richiamarsi la problematica dell'adattamento, in termini di adattamento individuale o apprendimento da una parte, e adattamento collettivo o evoluzione dall'altra parte.
  • Implementazione: Infine, rimane da discutere la questione della realizzazione effettiva e dell'implementazione dei sistemi multi agente, tramite la strutturazione dei linguaggi di programmazione in più tipologie, che vanno da un linguaggio di tipo L5, o linguaggio di formalizzazione e specifica, ad un linguaggio di tipo L1, che è quello dell'implementazione effettiva. Tra le due classi, si trovano i linguaggi per la comunicazione tra agenti, la descrizione delle leggi dell'ambiente e la rappresentazione delle conoscenze.
Torna all'Indice

2.3 - Ambiente

2.3.1 - Interazione tra Ambiente e Sistema

È difficile dare una definizione precisa sulla relazione che intercorre tra ambiente e MAS. La seguente proposta cerca di dare una definizione generale. Partiamo considerando un sistema S e un ambiente ES situati all’interno di un dominio W (dominio definito come il mondo in cui siamo situati). Definiamo quindi W = S U ES. Il nostro sistema S è immerso dentro l’ambiente ES con cui interagisce e da cui non può essere dissociato. L’ambiente ES è uno spazio comune per tutti gli agenti che compongono S. Il sistema e l’ambiente sono fortemente legati tra loro e hanno un’influenza sui loro rispettivi comportamenti, possiamo quindi parlare di attività di un sistema o di un ambiente. Più precisamente il sistema percepisce e agisce all’interno dell’ambiente, e di conseguenza i suoi comportamenti modificano lo stato dell’ambiente che reagisce applicando una determinata pressione sul sistema. Questa pressione viene percepita dal sistema che agisce di conseguenza con altre azioni sull’ambiente. Quindi ci troviamo davanti ad una interazione basata su azione-reazione che evolve col tempo. Infatti l’ambiente in cui il sistema è immerso, applica vincoli in cui il sistema deve adattarsi. Questa interazione porta ad influenze reciproche che rafforzano il rapporto tra sistema e ambiente. Torna all'Indice

2.3.2 - Tipologie di ambiente

  • Physical Environment: Per definizione l’ambiente fisico fornisce principi e processi per governare e sostenere una popolazione di entità. L’ambiente fisico consiste di risorse materiali (oggetti passivi o attivi come feromone, cibo, ostacoli) che rientrano tra gli oggetti che un agente può percepire. Grazie all’ambiente fisico, gli agenti possono interagire tra loro in modo indiretto. Ovvero possono interagire tra loro modificando l’ambiente, come fanno per esempio le formiche che rilasciano nell’ambiente del feromone per scambiarsi informazioni. L’ambiente fisico ha un’importanza diversa a seconda del dominio applicativo. Per gli agenti software l’ambiente fisico può essere trascurato, perché si suppone che un messaggio raggiunga il destinatario, ma per gli agenti situati è essenziale.
  • Social Environment: Per definizione l’ambiente sociale è di per se un ambiente di comunicazione dove gli agenti possono interagire in modo coordinato. L’ambiente sociale è composto dalla conoscenza degli agenti. In un MAS, gli agenti costituiscono il sistema ed evolvono simultaneamente insieme all’ambiente. Le relazioni che ci sono tra i vari agenti possono essere forti o deboli a seconda delle abilità e delle conoscenze che un agente deve apprendere da altri agenti per completare i suoi obiettivi, perché come abbiamo già detto la conoscenza è distribuita tra tutti gli agenti del sistema. Per interagire in modo efficiente ogni agente necessita di avere una rappresentazione della conoscenza degli altri agenti.
  • Communicating Environment: Per definizione l’ambiente di comunicazione fornisce principi, processi e strutture utili per definire una infrastruttura che consenta agli agenti di trasmettere informazioni.
Torna all'Indice

2.3.3 - Proprietà dell’ambiente

  • Raggiungibile o Non-Raggiungibile: Un ambiente si dice raggiungibile da un agente se i sui sensori sono in grado di rilevare tutti gli aspetti rilevanti per la scelta delle proprie azioni. Per esempio negli scacchi l’ambiente di una pedina è raggiungibile perché quando gioca può osservare tutta la scacchiera. Mentre nel calcio un giocatore ha una percezione limitata del suo ambiente.
  • Deterministico o Non-Deterministico: L’ambiente è deterministico se il suo stato futuro può essere determinato dal suo stato attuale e dalle azioni scelte dagli agenti. Negli scacchi l’ambiente di una pedina è deterministico perché quando una pedina gioca, è l’unica, e può quindi prevedere lo stato futuro del gioco. Nel calcio l’ambiente di un giocatore è non-deterministico.
  • Statico o Dinamico: L’ambiente è dinamico per un agente se può cambiare il suo stato mentre un agente sta deliberando. Per esempio nel gioco degli scacchi l’ambiente di una pedina è statico, perché quando una pedina delibera, nessun altro può giocare. Mentre nel calcio l’ambiente di un giocatore è dinamico, perché mentre un giocatore delibera, gli altri giocatori possono agire.
  • Discreto o Continuo: L’ambiente è discreto se ci sono un numero limitato di percezioni e azioni chiaramente definite. Per esempio nel gioco degli scacchi l’ambiente di una pedina è discreto, perché ci sono un numero limitato di percezioni e azioni. Mentre il mondo reale è un esempio di ambiente continuo.
Torna all'Indice

3 - Sistemi Auto-Organizzanti

Dopo avere analizzato i concetti fondamentali, passiamo alla trattazione dei temi fondamentali. Verrà introdotto il concetto di Auto-Organizzazione, i requisiti da soddisfare nell’approcciarsi ad essa e come procedere per la misurazione e la valutazione. Punto fondamentale poi sarà l’unione tra questo concetto e i sistemi multi agente. Torna all'Indice

3.1 - Definizione di SOS

Organizzazione sta per le relazioni tra le parti in termini di struttura ed interazione, mentre Auto indica che la forza guidante deve essere interna, specificamente distribuita tra i componenti. Self-Organisation : Meccanismo o processo che rende un sistema in esecuzione in grado di cambiare la propria organizzazione senza comandi esterni. L’auto-organizzazione è un processo nel quale gli schemi al livello globale di un sistema emergono esclusivamente dalle numerose interazioni tra i componenti di basso livello del sistema. Queste interazioni sono guidate da regole messe in pratica solamente utilizzando informazioni locali, senza far riferimento allo schema globale. L’organizzazione interna, per esempio nell’adattarsi ai cambiamenti negli obiettivi e nell’ambiente, può quindi cambiare senza comandi esterni.

Torna all'Indice

3.2 - Fenomeni Emergenti

Si è parlato di “emergere” degli schemi globali. Con emergence ci si riferisce proprio a quel fenomeno che vede comparire strutture, schemi, e proprietà durante il processo di auto-organizzazione nei sistemi complessi. I fenomeni emergenti occorrono nel macro-livello, in contrasto con i componenti del micro-livello, da cui derivano. I fenomeni emergenti presentano diverse caratteristiche. Per prima cosa non sono predicibili a partire dai componenti di basso livello, emergono ad alto livello e sorgono con il tempo, non sono dati a priori. Questi fenomeni possono quindi emergere nei sistemi che:

  • Presentano interazioni non lineari e sono tipicamente rappresentati come feedback-loops
  • Presentano auto-organizzazione
  • Vanno oltre all’equilibrio: Non si ha interesse in uno stato finale, ma nelle dinamiche del sistema
Per l’auto-organizzazione sono quindi necessarie:
  • Autonomia ed incapsulamento del comportamento
  • Azioni locali e percezioni
  • Ambiente distribuito, supportante le interazioni
  • Supporto per organizzazione e concetti di cooperazione
Si può facilmente riconoscere come il paradigma ad agenti offra delle astrazioni adeguate per soddisfare ogni requisito. Gli agenti infatti garantiscono l’autonomia e l’incapsulamento. I situated agents, agenti incorporati nell’ambiente, per le azioni locali e le percezioni. MAS si occupano brillantemente della distribuzione dei componenti e del supporto dell’ambiente ed infine anche del supporto dell’organizzazione e della cooperazione.

I MAS sono quindi divenuti un riferimento per modellare ed ingegnerizzare l’auto-organizzazione.

Torna all'Indice

3.3 - Misure per l'Auto-Organizzazione

La questione della misurazione e valutazione dei meccanismi di auto-organizzazione ha finora ricevuto scarsa attenzione, nonostante che una corretta valutazione è fondamentale sia per il confronto tra meccanismi sia per gli approcci tradizionali. Il primo passo per derivare dei criteri quantitativi per valutare l'efficacia di auto-organizzazione è quello di controllare che queste misure riguardino:

  • una struttura organizzativa osservata;
  • un processo che produce e mantiene tale struttura;
  • una determinata funzione o un obiettivo globale che il sistema si propone di soddisfare mediante l'utilizzo di “auto-organizzazione”.
Inoltre, un sistema di auto-organizzazione è materia di studio sia se può essere analizzato da prospettive locali che globali, sia se l'auto-organizzazione si estende su più livelli gerarchici annidati. In entrambi i casi, le misurazioni relative alla struttura del sistema, del processo o della funzione, possono essere prese ad ogni livello. La misurazione delle strutture è basata sulla valutazione della struttura del sistema dopo che è stato stabilizzato a seguito di una serie di modifiche di auto-organizzazione. Le misure incentrate sul processo di autorganizzazione sono legate alla dinamica dei sistemi e alla sua evoluzione nel tempo e si focalizzano sul modo in cui il sistema di auto-organizzazione è in grado di raggiungere il suo scopo. Pertanto, in questo caso le misure riguardano le caratteristiche del problema del sistema da risolvere e sono simili a quelle utilizzate per la valutazione delle prestazioni nei sistemi classici.

Esempi di misure tipiche di auto-organizzazione sono:

  • capacità di raggiungere un'organizzazione in grado di soddisfare l'obiettivo del sistema nel suo complesso una volta che il sistema viene avviato (successo / fallimento / tempo richiesto, convergenza);
  • capacità di raggiungere una riorganizzazione dopo un evento perturbante (successo / fallimento / tempo necessario);
  • grado di controllo decentrato (centrale / totalmente decentrata / ibrido);
  • la capacità di resistere a perturbazioni: la stabilità / adattabilità
Torna all'Indice

4 - Sistemi Multi Agente e Auto-Organizzazione

Il dinamismo e l’apertura dei sistemi ad agenti, e la sempre maggiore distribuzione, complessità e cambiamenti dinamici nelle richieste, rendono i SOS un’accoppiata quasi perfetta per i MAS. I MAS sono inoltre tra i più rappresentativi nel lavorare con complessità e distribuzione, tra i sistemi artificiali spingendo la ricerca verso i “Self-Organizing MAS” e l’unione tra pattern “nature-inspired” e astrazioni orientate agli agenti. Questa unione permette la progettazione di sistemi più complessi.

L’obiettivo dei ricercatori nei self-organizing MAS è quindi quello di integrare l’auto-organizzazione all’interno dei sistemi multi agente. La complessità consiste nel trovare dei meccanismi efficaci, che riescano a guidare il comportamento degli agenti al micro-livello, quindi rendendoli in grado di auto-organizzarsi e di ottenere al macro-livello il comportamento che ci si aspetta. Bisogna quindi trovare quelle regole che permettano di ottenere il comportamento collettivo richiesto, quindi che permettano l’emergence del comportamento globale.

Quando si parla di comportamento emergente, si ha un’antinomia, poiché da una parte accade e non può essere sotto controllo, dall’altra invece si vogliono soddisfare determinati requisiti. Vogliamo quindi controllare il comportamento emergente dei sistemi. E’ necessario quindi capire profondamente la relazione tra micro e macro livelli e costruire un sistema capace di auto-organizzarsi ed auto-adattarsi alle dinamiche ambientali.

Nello sviluppare sistemi artificiali auto-organizzanti che mostrino proprietà di emergence, ci imbattiamo in due problematiche principali:

  • Data la non linearità del comportamento degli agenti e nelle dinamiche ambientali, come possiamo fare per definire il comportamento globale a partire dal comportamento dei componenti di basso livello?
  • In secondo luogo, l’auto-organizzazione permette la progettazione di MAS sottospecificati, dato che il sistema può auto adattarsi a nuovi vincoli posti successivamente. La progettazione ne risulta semplificata e i costi di sviluppo diminuiscono, ma d’altra parte la validazione di questi risultati ne risulta invece appesantita. Come possiamo valutare la validità e la qualità di un sistema come lo abbiamo descritto?
Per quanto riguarda la prima problematica possiamo dire che la forward engineering non è praticabile. Quindi ci basiamo sull’esistenza di un sistema naturale che ci dia una soluzione utilizzabile. I processi di “ispirazione” dai modelli naturali non possono essere considerati un approccio scientifico. Sono necessari approcci più formali.

Un design-pattern offre una soluzione riutilizzabile per un problema ricorrente. Nel caso in esame, sono un approccio attuabile per codificare con successo le soluzioni dateci dal sistema naturale ai problemi di computer science.

Per quanto riguarda invece la seconda problematica, per risolverla ci avvaliamo di processi iterativi di ingegnerizzazione. Attualmente, la strada più affidabile consiste nel migliorare iterativamente il sistema tramite strumenti matematici (analisi statistica, ottimizzazione dei parametri comportamentali) o tramite programmazione adattativa semi-autonoma.

Torna all'Indice

5 - Modelli e Tecnologie

Agli inizi gli studi e le ricerche dei sistemi MAS e degli agenti si focalizzavano sul comprendere le questioni sociali (social issue), le varie implicazioni in termini di linguaggi, l’infrastruttura software, i rapporti con i metodi object-oriented e le tecnologie. Le ricerche si concentravano su tre principali aspetti:

  • Comprendere il pieno potenziale del paradigma agente
  • Sviluppare le prime tecnologie basate su agenti
  • Agenti correlati con i paradigmi tradizionali e tecnologie.
Nel corso di questo capitolo sono elencati ed approfonditi i vari modelli di ispirazione dei sistemi multi agente arricchiti da esempi concreti realmente testati. Oltre ai modelli saranno presentate anche le tecnologie necessarie a realizzarli.

Torna all'Indice

5.1 - Modelli di ispirazione

I MAS adottano modelli ispirati all’ambiente naturale e ai suoi complessi sistemi. Questi sistemi mostrano delle features come la distribuzione, tolleranza ai guasti, robustezza, adattività ed apertura. Quello che vogliamo è capire questi sistemi per poi riportarli nei sistemi computazionali. La maggior complessità dei sistemi computazionali complessi deriva dall’interazione. Molti sistemi naturali si basano su semplici ma potenti meccanismi di coordinazione, come l’auto-organizzazione, per cui ha senso usarli come fonte d’ispirazione per sistemi MAS complessi.

I MAS si ispirano a tre principali gruppi:

  • Sistemi naturali
    • Fisici
    • Biologici
    • Sociali
  • Sistemi aziendali ed economici
  • Sistemi artificiali
Torna all'Indice

5.1.1 - Sistemi Naturali

L’auto-organizzazione e i fenomeni emergenti possono essere osservati in molti sistemi naturali ad esempio, gli insetti che vivono in colonie come le formiche, api, vespe e termiti, hanno dimostrato di integrare perfettamente le loro attività individuali. Nonostante ogni singolo insetto sembra operare individualmente e senza essere soggetto ad alcun controllo centrale. L’interazione tra i membri in tali colonie è portata indirettamente attraverso modifiche asincrone e successivamente viene percepito lo stato del loro ambiente. Altri esempi di sistemi di auto-organizzazione naturali comprendono gli stormi di uccelli e branchi di pesci. In questi casi, il comportamento collettivo di auto-organizzazione si ottiene dalla percezione sincrona dell'ambiente e seguendo semplici regole. Ad esempio, cercare di rimanere in prossimità evitando collisioni con i membri del gruppo simili e allo stesso tempo tentando di mantenere una distanza dalle entità dissimili, in questo modo gli uccelli o pesci possono ridurre in modo significativo la probabilità di essere attaccati da un predatore. Tali sistemi presentano diversi ed interessanti complessi comportamenti, ed hanno emergenti proprietà derivanti da interazioni locali tra comportamenti elementari esercitati individualmente. Il comportamento collettivo che ne emerge è il risultato del processo di “auto-organizzazione” in cui i membri sono impegnati con le loro ripetute azioni e le interazioni con l'ambiente che è in continuo cambiamento. Un tipico esempio di auto-organizzazione emergente nei sistemi naturali riguarda le colonie di formiche alla ricerca di cibo che vanno in giro ad esplorare il loro ambiente di ricerca. Quando riescono nel loro compito, tornano al nido dopo aver piazzato nell’ambiente sostanze chimiche che vengono successivamente utilizzati da altre formiche come indicatori di vicinanza alla fonte di cibo. Una volta scoperta la fonte di cibo, viene creato un percorso costituito da sostanze chimiche tra la fonte di cibo e il nido. Questo in realtà è il percorso più breve possibile tenendo conto dei vincoli ambientali, ed è ottenuto come risultato dell'attività collettiva delle formiche.

Ovviamente questo percorso può essere identificato solo da osservatori esterni, per esempio le singole formiche non possono vedere il percorso nella sua interezza. Il campo di ricerca che indaga sui modelli e le tecniche computazionali ispirati dalla natura è chiamato Natural Computing, e cerca di capire i sistemi di ricerca in natura in termini di elaborazione delle informazioni. Si tratta di un campo altamente interdisciplinare che collega le scienze naturali con la scienza informatica, sia a livello di tecnologia informatica che a livello di ricerca fondamentale. Il Natura Computing copre molti settori, tra cui la pura ricerca teorica, gli algoritmi e le applicazioni software, così come la biologia, la chimica e la fisica sperimentale e la ricerca di laboratorio. I sistemi naturali possono essere classificati come sistemi fisici, sistemi biologici e sistemi sociali. Sistemi fisici

Sistemi Fisici

Le teorie di “auto-organizzazione” sono state originariamente sviluppate nell'ambito della Fisica e della Chimica per descrivere la nascita di modelli macroscopici e le interazioni definite a livello microscopico. Una caratteristica comune dei sistemi Fisici di auto-organizzazione è l'esistenza di una certa soglia critica, che quando raggiunta provoca un cambiamento immediato dello stato del sistema. Tale soglia critica può essere una combinazione di valori di alcune variabili di sistema, ad esempio temperatura, pressione e velocità. L'effetto di “auto-organizzazione” è osservato globalmente quando il sistema transita da uno stato disordinato caotico ad uno stabile. Ad esempio in un sistema termodinamico come in uno costituito da una quantità di gas, le proprietà di temperatura di sistema e pressione sono emergenti in quanto non sono determinati da una particolare particella di gas. Invece sono definiti dalle posizioni e dalla velocità di tutte le particelle nel sistema. Analogamente, le reazioni chimiche creano nuove molecole che hanno proprietà che nessuno degli atomi visti prima della reazione possiede. Inoltre, la magnetizzazione di una moltitudine di rotazioni nei materiali magnetici è un chiaro caso di auto-organizzazione perché, sotto una certa temperatura, le rotazioni magnetiche si ordinano spontaneamente tutte nella stessa direzione creando così un forte campo magnetico.

Sistemi Biologici

L'auto-organizzazione è un fenomeno comune nei sottosistemi degli organismi viventi. A conseguenza di ciò un importante campo della ricerca biologica si occupa di determinare le immutazioni nell'evoluzione degli organismi viventi, ed in particolare la comparsa spontanea di ordine nei sistemi viventi complessi a causa dell’auto-organizzazione. Nell'ottica della ricerca biologica, il significato comune di “auto-organizzazione” è definito dalla comparsa globale di un particolare comportamento o caratteristica che non può essere ridotto alle proprietà dei componenti dei sistema individuali come le molecole, gli agenti e le cellule. Un esempio è “l'auto-organizzazione” del citoscheletro, volto ad analizzare processi collettivi di reazione e la diffusione dei filamenti citoscheletri. Il citoscheletro è la base dell'architettura interna del citoplasma delle cellule eucariotiche. Le cellule eucariotiche sono cellule appartenenti ad organismi di livello superiore che contengono un vero nucleo delimitato da una membrana nucleare. Tali cellule si trovano nelle piante e negli animali, e sono generalmente localizzate in organi, come il fegato, o in sottosistemi, come il sistema nervoso che, mediante processi metabolici nonostante l'aumento della complessità del sistema, fornisce un livello superiore di funzionalità. Quello che ne risulta sono funzionalità completamente nuove, e trascendono ogni individuali funzionalità offerte dalle rispettive cellule. Per esempio i sottosistemi del corpo umano gestiscono trasparentemente le funzioni vitali: come la pressione sanguigna, la digestione, o la creazione di anticorpi. Le cellule eucariotiche sono le unità fondamentali e di funzionamento della vita e si evolvono progressivamente secondo le modifiche esterne al loro ambiente. L'evoluzione è ottenuta mediante l'utilizzo di metabolici processi interni, come la mutazione o selezione naturale, e fornisce la base per l'evoluzione negli organismi viventi e nelle specie naturali. Ulteriori modelli di sistemi biologici di “auto-organizzazione” comprendono il sistema immunitario dei mammiferi, la rigenerazione delle cellule e il comportamento del cervello umano. Un esempio di quest'ultimo è la coscienza dell'uomo definita da Searle come una proprietà del cervello al più alto livello. Biologicamente, il cervello è un sistema complesso composto da un insieme di neuroni che interagiscono tra di loro. Anche se la coscienza è il risultato di una serie di operazioni dei neuroni fatto a un livello più basso, non è attualmente possibile capire o spiegare la coscienza umana osservando i neuroni del cervello e le loro interazioni.

Sistemi sociali

Nelle società dei sistemi naturali, le entità comunemente mostrano comportamenti sociali che portano alla auto-organizzazione, auto-adattamento e auto-mantenimento della organizzazione della società, che si osservano spesso in alcuni comportamenti della società globale. I comportamenti individuali sociali vanno da quelli osservati nelle entità biologiche, per esempio i batteri, le cellule e gli insetti, come ragni, a quelli osservati negli animali più grandi e gli esseri umani. Una caratteristica importante dei comportamenti della società è la loro formazione ottenuta da risultati sviluppati da interazioni relativamente semplici, in una rete di individui. Questi comportamenti risultanti sono guidati da processi dinamici, che sono disciplinati da semplici e generiche leggi. Ad esempio, un importante ragione che storicamente ha innescato comportamenti collettivi nelle società naturali, è quello della sopravvivenza delle specie . Questo obiettivo non è esplicitamente espresso a livello individuale, ma si riflette nel comportamento collettivo dei membri della società attraverso il compimento di funzioni sociali e dinamiche di gruppo, consentendo il mantenimento dell'organizzazione del sistema. Per esempio, gli insetti si organizzano attività come la ricerca di cibo o la costruzione del nido. La comunicazione tra gli insetti è realizzata attraverso un meccanismo di comunicazione indiretto, stigmergia, che viene realizzato attraverso l'ambiente della società. La stigmergia è un metodo di comunicazione utilizzato nei sistemi decentralizzati col quale gli individui del sistema comunicano fra loro modificando l'ambiente circostante. Gli insetti, come le formiche, termiti o api, implementano la stigmergia marcando il loro ambiente utilizzando una sostanza chimica volatile, chiamato feromone. Successivamente organizzano i loro movimenti in base alla posizione dei feromoni nell’ambiente, per esempio le formiche usano questa tecnica per segnalare un percorso alimentare. Le Informazioni ottenute attraverso i feromoni costituiscono una comunicazione indiretta: attraverso l’ambiente, infatti gli insetti hanno generalmente un comportamento semplice, e nessuno di loro da solo può fornire la completa soluzione del problema(una formica non è a conoscenza della fonte di cibo) . Tuttavia, le interazioni tra comportamenti individuali danno luogo ad un comportamento collettivo di società organizzata, per esempio le formiche sono in grado di esplorare il loro ambiente, trovare il cibo ed infine informare il resto della colonia. A differenza degli altri organismi viventi, gli esseri umani comunemente si organizzano in società avanzate in modo da poter servire a molti scopi. Ad esempio, possono utilizzare la comunicazione diretta, impegnarsi in negoziazioni, costruire economie e organizzare i mercati azionari. Il comportamento sociale degli esseri umani è tipicamente “self-organising” e ciò porta alla nascita di nuovi comportamenti complessi. In molti casi il comportamento umano si basa su una piccola gamma di informazioni locali e la comunicazione è effettuata su interazioni dirette o indirette locali, che portano alla nascita di complessi comportamenti sociali. Un esempio rappresentativo di un fenomeno emergente nelle società umane è quello delle credenze comuni, ad esempio l'etica del lavoro, sviluppato e promosso attraverso comunicazioni locali come il pettegolezzo.

Torna all'Indice

5.1.2 - Sistemi aziendali ed economici

In questo ambiente l'auto-organizzazione è disciplinata da leggi di business e di mercato. Nei sistemi commerciali ed economici, i comportamenti individuali sono volti al compimento di obiettivi (“goal-oriented”) e il loro obiettivo primario è quello di aumentare il loro profitto. In questo caso, la dinamica del sistema viene gestita dall'attività, sviluppata per affrontare vincoli commerciali ed economici al fine di raggiungere un equilibrio globale attraverso cui il sistema può sopravvivere. In tale contesto, sono stati sviluppati diversi modelli che regolano le operazioni di business, come il management, il marketing e modelli economici, che si basano su auto-organizzazione. Ad esempio, uno di questi modelli, preso dal marketing, è la variabile di uno-a–uno del modello di Pricing che si riferisce a fornire un'offerta personalizzata per ogni cliente utilizzando le tecnologie di Internet. Il modello prevede l'auto-organizzazione delle politiche di marketing, cambiando gli obiettivi dei clienti, i prezzi proposti sulla base di un mercato dinamico, le caratteristiche dei clienti e gli obiettivi di business. Un esempio di società che utilizza questo tipo di marketing è la FedEx. La società consente ai clienti di accedere ai sistemi informatici, tramite il sito Web, per monitorare lo stato del loro pacchi. Per i clienti aziendali, FedEx fornisce strumenti software che permettono di organizzare automaticamente la spedizione e monitorare i pacchi usando il proprio computer. Ogni cliente è sottoposto a prezzi diversi a seconda di una varietà di parametri. Molti siti web, come e-Bay, applicano prezzi variabili per le loro offerte. Un altro esempio di un modello di business “auto-organizzante” nel settore del management afferma che un business è composto da reti di gruppi di lavoro che possono cambiare la loro struttura, i collegamenti e il comportamento in risposta alle esigenze di business. Lo scopo di tale modello è quello di bilanciare le decisioni di auto-organizzazione, che sono prese dai gestori e adattate dalle interazioni tra i dipendenti durante le operazioni di business. L’enfasi della teoria dell’attività è risolvere potenziali conflitti di interesse sia all’interno che all'esterno dell'attività cooperativa dell'azienda.

Torna all'Indice

5.1.3 - Sistemi artificiali

I sistemi artificiali auto-organizzati sono quelli costruiti fin dall'inizio con capacità di auto-organizzative. I meccanismi possono essere ispirati dai sistemi naturali esistenti oppure possono essere creati espressamente per questo scopo. Tra i sistemi artificiali auto-organizzati, osserviamo diverse tendenze che vanno dall'applicazione di modelli di auto-organizzazione ispirati alla natura, alla creazione di nuovi meccanismi e infrastrutture a supporto dell’auto-organizzazione dei sistemi artificiali. Gli sciami forniscono una grande fonte di ispirazione, soprattutto per la gestione dei sistemi di reti fisse e mobili, come il routing, il bilanciamento del carico, o la sicurezza. Inoltre, sono stati sviluppati modelli di auto-organizzazione mirati ad applicazioni particolari. Ad esempio, un sistema artificiale auto-organizzante costruito per il coordinamento e l'organizzazione di un gruppo di robot. In tale contesto, i robot trasportano gli oggetti tra due stanze collegate con due corridoi che non possono essere utilizzate da più di un robot alla volta. I robot sono dotati di percezione locale e possono applicare un atteggiamento di collaborazione nella scelta del corridoio da utilizzare. Il risultato è il miglioramento delle prestazioni del sistema ottenute dalla specializzazione corridoio, dove il movimento in ogni corridoio è fatto in una direzione specifica.

Torna all'Indice

5.2 - Tecnologie

La maggior parte dei sistemi naturali, quando osservati nella loro complessità, esibiscono propri meccanismi. In corrispondenza, molti approcci odierni al coordinamento dei MAS integrano differenti fonti di ispirazione:

  • TOTA: utilizza meccanismi stigmergici e field based (come Co-Fields, ispirati dal modo in cui le masse e le particelle si muovono ed auto-organizzano in base a campi gravitazionali ed elettromagnetici)
  • SAPERE: Modello di coordinamento che integra una metafora chimica per guidare l’evoluzione del coordinamento, astrazioni biochimiche per la topologia e la nozione di ecosistema per modellare la struttura del sistema e le dinamiche.
Abbiamo poi la diffusione di tecnologie tuple-based: Gli agenti si sincronizzano, cooperano e competono basandosi su tuple, disponibili negli spazi di tuple che operano come media di coordinamento, associativamente accedendo, consumando e producendo tuple. Possiamo considerare Linda come l’antenato di tutti i modelli di coordinamento tuple-based. Linda è però concepita come un modello di coordinamento per sistemi chiusi e paralleli, rendendolo inefficace per problemi odierni nei sistemi aperti e concorrenti. Quindi, partendo da Linda, sono stati creati un gran numero di nuovi modelli tuple-based. Abbiamo per esempio StoKlaim, che aggiunge un’estensione probabilistica e la possibilità di modellare fenomeni non deterministici, o anche SwarmLinda, che aggiunge la Swarm Intelligence, al fine di ottenere scalabilità, adattività e tolleranza ai guasti.

Torna all'Indice

6 - Conclusioni

In questa relazione abbiamo introdotto alcuni concetti principali per capire i Sistemi Multi Agenti, descrivendo in particolare qual è l’utilizzo attuale di questi sistemi e quali saranno i suoi sviluppi futuri, che come abbiamo definito sono orientati in modo molto chiaro verso sistemi auto organizzanti. Partendo dalla descrizione delle entità principali che costituiscono il sistema, ovvero gli Agenti, definendo le proprietà, l’architettura e le relazioni che intercorrono tra essi abbiamo descritto le proprietà e le architetture dei sistemi multi agente che dipendono fortemente dagli agenti che lo compongono. Abbiamo poi introdotto il concetto di Ambiente, altra entità che svolge un ruolo molto importante all’interno dei sistemi multi agente, perché permette diverse tipologie di interazione tra agenti e sistema. L’interazione è un concetto fondamentale per lo sviluppo futuro di sistemi auto organizzanti. Per fare questo salto di qualità ci avvaliamo di numerosi modelli sui quali basare le nostre ricerche ed ispirarci, abbiamo visto come un piccolo comportamento di un sistema può dar vita a complessi ed interessanti studi. Entrando nell’ottica dei sistemi multi agente ci si accorge facilmente come molte cose che ci circondano possano essere materia di studio, purtroppo però mancano delle tecnologie ad hoc per i nostri scopi.

Torna all'Indice

Bibliografia

Marie-Pierre Gleizes, Valérie Camps, Anthony Karageorgos, Giovanna Di Marzo Serugendo(2011) Agents and Multi-Agent Systems

Andrea Omicini and Stefano Mariani (2013) Agents & multiagent systems: En route towards complex intelligent systems

Andrea Omicini (2012) Nature-inspired Coordination for Complex Multi-Agent Systems

Giovanna Di Marzo Serugendo, Marie-Pierre Gleizes, Anthony Karageorgos (2011) Self-organising Software: From Natural to Artificial Adaptation

Giovanna Di Marzo Serugendo, Marie-Pierre Gleizes, Anthony Karageorgos (2005) Self-organization in multi-agent systems

Vittikh, V.A., Skobelev, P.O. Multi-agent systems for modelling of self-organization and cooperation processes

Federico Bergenti, Marie-Pierre Gleizes, Franco Zambonelli. Methodologies and Software Engineering for Agent Systems. The Agent-Oriented Software Engineering Handbook

Wikipedia.

Torna all'Indice