Il labirinto dell’inganno

Fabio Limardo

abstract

Il labirinto dell’inganno è un semplice gioco in cui due squadre avversarie si confrontano per cercare l’uscita di un labirinto. Le squadre sono formate da agenti software di due diverse tipologie, con obiettitivi distinti ma con la necessità di cooperare per raggiungere l'obiettivo comune di trovare l'uscita da labirinto.

Introduzione
Vision
Goals
Requisiti
Analisi dei requisiti
Glossario dei Termini
Modello del Dominio
Analisi del Problema e significatività per il corso di Sistemi Autonomi
Progetto
Policy e gestione del concetto di Trustability
Implementazione
- Problemi Implementativi

Introduzione

In questo progetto vogliamo esplorare i metodi e le tecnologie per la definizione di un Multi-Agent System (M.A.S.), descrivendone dunque comportamenti, singoli e dell’intero sistema, interazione e coordinazione tra i componenti. L’esempio delle due squadre che competono tra di loro per raggiungere un’obiettivo, la collaborazione interna tra i membri della squadra e l’interazione con l’ambiente mettono in luce gli aspetti evidenziati.

Vision

Si vuole andare a mostrare come un sistema di agenti autonomi possano auto-organizzarsi per raggiungere un obiettivo e compiere scelte oculate in base alle informazioni ricevute dagli altri membri e estrapolate dall'ambiente, andando a sottolineare come l'intelligenza derivante dall'interazione sia effettivamente una componente ortogonale alla classica espressività computazionale definita da una Turing Machine.

Goals

Realizzare un prototipo del gioco per mettere in opera la Vision, modellando i membri della squadra come agenti, definire artefatti con cui questi possano interagire e descrivere un’ambiente in cui questo sistema possa evolvere.

Requisiti

I requisiti vengono dati dalla struttura e dalle regole del gioco. Gli elementi del gioco sono:

Un labirinto, dove gli agenti dovranno trovare la strada per l’uscita.
Gli artefatti, sono aiuti che possono indicare se la strada che stiamo percorrendo sia corretta.
Le due squadre, formate da due tipologie di agente:
- - Il "Velocista", con l'obiettivo di trovare l'uscita dal labirinto;
  - Il "Detective, con l'obiettivo di analizzare gli artefatti, ricavandone informazioni utili e andandoli a modificare se necessario.

Gli agenti di tipo Velocista delle due squadre cercano l’uscita dal labirinto e comunicano agli agenti Detective il ritrovamento degli artefatti in modo che possano essere analizzati ed eventualmente usati e/o modificati. Ogni artefatto può essere modicato in modo tale da cercare di fornire un'indicazione corretta per il Velocista della medesima squadra del Detective che va a modificarlo oppure cercare di fornire indicazioni sbagliate per la squadra avversaria. Bisogna dunque andare a definire un concetto di trustability per gli artefatti. Vince la squadra che per prima trova l'uscita.

Analisi dei requisiti

Il labirinto sarà formato da un'insieme di corridoi, è l'ambiente nel quale gli agenti andranno a operare e in cui gli artefatti andranno situati, un insieme di risorse e vincoli che l'agente può sfruttare e per i quali è condizionato.Gli artefatti saranno dei contenitori di conoscenza che permetteranno agli agenti di interagire con l'ambiente in modo più consapevole, questo significa che devono essere in grado di mostrare all'esterno la conoscenza che incorporano e gli agenti, ma non sono contenitori statici : deve essere possibile modificarli per cambiarne le caratteristiche.L'agente Velocista deve essere un'entità autonoma, proattiva perchè guidata dall'obiettivo di dover trovare l'uscita del labirinto e reattiva rispetto all'ambiente e agli artefatti e in grado di comunicare con gli agenti Detective. \ L'agente Detective deve essere un'entità automa anch'esso, proattiva perchè guidata dallo scopo di trovare gli artefatti e analizzarli, reattiva rispetto agli ambienti e in grado ci comunicare i risultati dell'analisi ai Velocisti \

Glossario dei Termini

Termine	Descrizione
Labirinto	Ambiente in cui si svolge il gioco
Squadra Rossa/blu	Le due squadre che si fronteggiano
Velocista	Membro della squadro atto a trovare l'uscita
Detective	Membro della squadra atto a decriptare gli artefatti
Artefatto	Oggetto che può indicare una strada corretta o meno
Trustability	Proprietà che determina l'affidabilità dell'informazione dell'artefatto
Correctness	Indica se la strada porta verso l'uscita o meno

Modello del Dominio

Definiamo un modello per le entità coinvolte nel sistema partendo da quanto emerso in Analisi dei Requisiti.Labirinto

public interface ILabirintoModel {

public abstract int[] getPosition();

public abstract void setArtefattoDaAnalizzare(IArtefatto a);

public abstract IArtefatto getArtefattoDaAnalizzare();

public abstract ICella[][] getTable();

public abstract ICella getCella(int x, int y);

public abstract IArtefatto[] getArtefattiArray();

}

A questo livello possiamo già mostrare il labirinto come ambiente di gioco.

Le ' X ' rappresentano i muri, i ' blank ' i possibili corridoi e gli ' * ' la strada corretta. Artefatto

public interface IArtefatto {

public abstract void setStradaCorretta(boolean sc);

public abstract boolean isStradaCorretta();

public abstract String getName();

public abstract int[] getPos();

public abstract String getCambio();

public abstract float getTrustability();

public abstract void setTrustability(float trustability);

}

\ Agente

public interface IAgentAction {

public abstract boolean trovaEntrata();

public abstract boolean selezionaDirezione();

public abstract boolean controllo(String dir);

public abstract boolean cercaArtefatto();

public abstract boolean apriArtefatto();

public abstract boolean analizzaArtefatto(String name);

public abstract boolean cambiaArtefatto(String name, String correctness, String trustability);

public abstract int[] getPosition();

Analisi del Problema e significatività per il corso di Sistemi Autonomi

In fase di analisi dei requisiti si sono evidenziati alcuni aspetti peculiari che gli agenti del sistema devono possedere, come autonomia, proattività, attività e interazione con l'ambiente e con gli altri agenti.Aspetti che è possibile ritrovare in quello che viene definito Agent Oriented Programming, ovvero un nuovo paradigma di programmazione che ha alla base il concetto di Agente Software, inteso come un'entità autonoma dal punto di vista computazionale (inteso come computazione possibile secondo l'espressività permessa dalla Turing Machine) , ovvero un entità che incapsula il proprio flusso di controllo e comunica con le altre entità del sistema attraverso lo scambio di messaggi.Inoltre gli agenti (con agente d'ora in poi intenderemo agente software):

sono proattivi: hanno un goal, ovvero hanno un obiettivo da raggiungere, in questo caso l'uscita dal labirinto o la ricerca degli artefatti;
sono reattivi all'ambiente che li circonda, quindi bisognerà far si che l'agente abbia la caratteristica di essere situatedness, quindi immerso nell'ambiente con la capacità di percepire i cambiamenti e adeguare il proprio comportamento per raggiungere il proprio goal, quindi andare ad analizzare le possibili strade per uscire dal labirinto;
sono sociali, non solo possono comunicare tra loro, ma possono anche condividere obiettivi, anche se Velocista e Detective hanno obiettivi distinti, collaborano e si coordinano per raggiungere l'obiettivo collettivo di primeggiare sulla squadra avversaria.

I nostri agenti per adattarsi alle al contesto ambientale e sociale in cui si trovano e per effettuare scelte oculate devono essere intelligenti, dove per intelligenza si va a intendere in generale la capacità di imparare a fare un miglior uso della propria autonomia.Vogliamo dunque che il nostro agente sia in grado di effettuare scelte intelligenti in base ai propri Mental States, basati sia sulla rappresentazione della conoscenza del loro mondo (Epistemic States), sia sull'insieme degli obiettivi dell'agente (Motivational States).Queste caratteristiche possono essere ritrovate nell'architettura BDI (Belief,Desire Intentions), dove:

Belief sono l'insieme delle credenze che possiede l'agente circa ciò che lo circonda.
Desire sono i desideri (goals) cui l'agente vuole conseguire.
Intentions sono un sottoinsieme dei goals per i quali è stato messo in atto un piano d'opera per raggiungerli.

Gli artefatti possono essere visti come strumenti che mediano le azioni con l'ambiente, contenendo informazioni che possono indicare influenzare il processo di reasoning dell'agente.Non hanno dei goal da raggiungere, ma devono essere poter letti e manipolati dall'agente che può affidargli una destination : l'agente infatti potrebbe decidere di modificare l'informazione contenuta nell'artefatto con il duplice scopo di aiutare i membri della sua squadra oppure disorientare gli avversari. Gli artefatti dunque sono degli oggetti passivi con delle interfacce per accedervi: possono essere costruiti come classi oggetti dell'OOP.Un'altra questione che si evince dall'analisi dei requisiti è la necessità di introdurre un concetto di trustability tale che ogni artefatto possa essere identificato come affidabile o meno circa l'informazione che incapsula e permette un uso consapevole dei\

Progetto

Per affrontare il progetto, data l'analisi del problema, si è deciso di utilizzare Jason, un interprete basato su Java per una versione estesa di Agent Speak, quest'ultimo è un linguaggio astratto usato per descrivere e programmare agenti BDI. Jason ci permette di descrivere Belief, Goals e Plans attraverso regole Prolog-Like, è possibile definire dei piani per i quali vengono utilizzate delle funzioni Java che possono essere richiamate direttamente dall'interprete Jason. Molto utile è anche il meccanismo che mette a disposizione per l'aggiornamento della Beliefs tramite la cattura dei cambiamenti attraverso l'aggiornamento dei Percepts ambientali. \

Struttura

Proseguendo quindi l'analisi di progetto facendoci guidare dall'architettura BDI, definiamo la struttura dell'agente come l'insieme delle credenze, degli obiettivi e dei piani per mettere in opera tali obiettivi.

Belief

Nella Beliefs Base ci saranno tutte le credenze che che l'agente avrà sullo stato in cui si trova l'ambiente e gli artefatti.I tipi di beliefs si distingueranno in base a che l'agente sia di tipo Velocista o Detective, anche se alcune informazioni circa l'ambiente interessano entrambi.Ci sono i beliefs legati al movimento

startTrovato //L'agente cerca la l'ingresso nel labirinto
direzione(D) // L'agente sceglie la direzione che vorrebbe percorrere
direzioneNonPercorribile // La scelta della direzione a portato alla scoperta che per qualche ragione non è possibile proseguire
direzionePercorribile //E' stata scelta direzione per la quale è possibile andare avanti
posizione(X,Y) //Indica la posizione in cui l'agente si trova sulla griglia
fineGioco //l'uscita è stata trovata, il gioco termina

\ Beliefs legati agli artefatti per il Velocista

artefattoTrovato // Indica che un artefatto è stato trovato nella posizione corrente.
artefatto(N,C) // Indica che l'agente legge il nome (N) e la correcteness (C) che indica se la strada suggerita
               // dall'artefatto sia verso l'uscita o meno.                               .
artefattoRegistrato(N,C,T,V,K) // Indica che l'artefatto è già stato analizzato dal Detective e quindi abbiamo molte
                              // più informazioni su di lui molte più informazioni su di lui il significato dei parametri
                              // lo vedremo meglio più avanti.

\Beliefs legati agli artefatti per il Detective

artefattoTrovato // Indica che un artefatto è stato trovato nella posizione corrente.
artefattoScoperto(N,C,T,V,K)// Indica che l'agente analizza un artefatto e ne legge il nome (N) e altri parametri
// che vedremo in dettaglio nelle sezioni successive.
artefattoRegistrato(N,C,T,V,K) // L'artefatto è già stato analizzato dal Detective e lo aggiorniamo nel caso
// un Velocista dovesse incontrarlo.

Comportamento

Il comportamento di un agente è definito dai piani che esso applica per raggiungere il suo scopo.Andiamo a vedere anche qui il comportamento in base al tipo di agente.Velocista - Movimento : il velocista ha come obiettivo principe di trovare l'uscita dal labirinto, per iniziare cerca l'entrata.

!getStartPosition
: not startTrovato
<- trovaEntrata ; .print("startTrovato");
!trovaUscita.

\Inizia ora la ricerca dell'uscita, selezionaDirezione è un azione esterna che permette di scegliere una direzione in cui muoversi in modo casuale, a meno di non avere informazioni aggiuntive tipo la strada indicata da un artefatto. Verificata la fattibilità della mossa è possibile proseguire.

+!trovaUscita
: startTrovato
<- selezionaDirezione.

\Il prossimo passo è dipendente dal fatto se selezionaDirezione è andata a buon fine oppure no: nel primo caso si cercherà se esiste un artefatto nella posizione appena raggiunta, nel secondo si andrà a scegliere una nuova direzione.

+!nextStep
: direzioneNonPercorribile
<- .print("Non è possibile proseguire per la direzione desiderata"); selezionaDirezione.

+!nextStep
: direzionePercorribile
<- .print("Avanziamo");
!checkForArtefacts.

\Velocista - Artefatti : il Velocista deve cercare gli artefatti e nel caso li trovi li può leggere per capire come e se utilizzarli in base alla Beliefs Base

+!checkForArtefacts
: true
<- cercaArtefatto;
!leggiArtefatto.
+!leggiArtefatto
: artefattoTrovato
<- apriArtefatto.

\Detective - Movimento: non riporto i piani per il movimento riferiti al Detective in quanto in logica molto simili a quelli già visti per il Velocista, l'unica cosa che cambia di significativo è che stavolta l'obiettivo principe del Detective non è quello di uscire dal labirinto ma di analizzare Artefatti. andiamo a vedere dunque i piani che gli permettono raggiungere il suo goal Detective - Artefatti : quando un nuovo artefatto viene trovato, si va a vedere se non è stato ancora registrato lo stesso artefatto (lo si riconosce da N che indica i nome), altrimenti continua la tua ricerca.

+artefattoScoperto(N,C,T,V,K)
: artefattoScoperto(N,C,T,V,K) & not artefattoRegistrato(N,_,_,_,&#95 & K=1
<- -+artefattoRegistrato(N,C,T,V,K);
.send(velocistaRosso,tell,artefattoRegistrato(N,C,T,V,1));
selezionaDirezione.
+artefattoScoperto(N,C,T,V,K)
: artefattoRegistrato(N,_,_,_,&#95
<- selezionaDirezione.

\Quando un Velocista incontra un artefatto, il suo utilizzo viene registrato dal Detective, ipotizzando che una volta che dopo un certo numero di volte che l'artefatto venga utilizzato dalla propria squadra o non serva più e possiamo cambiarlo per disorientare la squadra avversaria oppure è stato usato da una squadra avversaria prima di noi e ne vogliamo cambiare l'interpretazione.

+artefatto(N)
: artefattoRegistrato(N,C,T,V,K) & V == 3
<- cambiaArtefatto(N,C,T);
analizzaArtefatto.

+artefatto(N)
: artefattoRegistrato(N,C,T,V,K) & V < 3
<- R = V+1; -+artefattoRegistrato(N,C,T,R,K);
.send(velocistaRosso,untell,artefattoRegistrato(N,C,T,R,K)).

\ Schema comportamentale di un Velocista

\Schema comportamentale di un Detective

Interazione

Di seguito una versione schematizzata dell'interazione tra i componenti.Il Sequence Diagram di UML a mio parere mal si adatta a un contesto in cui avviene scambio di messaggi tra entità autonome, basandosi sul concetto di invocazione di metodo e ritorno, noi invece vogliamo mostrare il concetto di come l'arrivo di un messaggio possa scatenare una serie di eventi gestiti dall'agente destinatario in base al proprio Mental State .Userò dunque una versione modificata del Sequence Diagram in cui andremo a inserire elementi tipici dello schema comportamentale, l'unica interazione schematizzata in modo classico sarà l'accesso dal parte Detective all'artefatto per modificarne le caratteristiche, con questo si vuole evidenziare la natura passiva dell'artefatto. \Vediamo dunque un primo schema di interazione circa il ritrovamento di un Artefatto da parte del Detective

Il seguente invece mostra lo schema di interazione quando un Velocista trova un Artefatto

Policy e gestione del concetto di Trustability

Come accennato in precedenza un artefatto è modificabile dai Detective di entrambe le squadre perciò bisogna instaurare una logica per poter instaurare un concetto di affidabilità circa l'informazione incapsulata nell'Artefatto. L'idea di base è quella di assegnare un valore a un parametro che può assumere valori compresi tra 0 e 1.

Lo 0 rappresenta il massimo dell'affidabilità per la squadra Blu
L'1 rappresenta il massimo dell'affidabilità per la squadra Rossa
Quando viene creato l'artefatto ha un'affidabilità di 0.5 ed è ritenuto affidabile da entrambe le squadre

Ogni volta che il Detective procede alla modifica di un Artefatto ne aggiorna anche la Trustability seguendo il seguente schema

Implementazione

L'implementazione di una versione prototipale del progetto è stata eseguita utilizzando l'IDE Eclipse Luna utilizzando la JDK 1.8 e Jason 1.4.1

Problemi Implementativi

Durante la realizzazione del prototipo siamo inciampati in un bug noto di Jason (come confermato dagli stessi sviluppatori), purtroppo sembra che il programma non termini sempre l'esecuzione come ci aspetteremmo, in altri si blocca l'esecuzione di alcuni agenti e come caso limite che va in crash l'intero MAS.Anche dopo aver scoperto di essere di fronte a un bug noto abbiamo comunque continuato a cercare una soluzione per aggirare il problema andando ad analizzare i log del debug di Jason in cui purtroppo però non abbiamo rilevato nulla di anomalo, di fatto dal log pare che l'esecuzione continui in modo corretto.In ogni caso abbiamo di seguito un screenshot di come appare il programma nel caso in cui vince la squadra rossa

Il codice del prototipo è disponibile su GitHub a questo indirizzo