1.3 Squadre e gerarchie di robot . . . . 12

1 Introduzione 9

1.1 I sistemi multirobot . . . . 10

1.2 L’ importanza della comunicazione . . . . 11

1.3 Squadre e gerarchie di robot . . . . 12

1.4 Movimenti coordinati . . . . 13

2 Descrizione, collocazione e contributo del lavoro di tesi 17 2.1 Focalizzazione della ricerca su sistemi embedded connessi in rete 18 2.2 Obiettivi stabiliti dal progetto RUNES . . . . 19

2.3 Contributo del lavoro di tesi alla ricerca . . . . 19

2.4 Caratteristiche principali di algoritmi distribuiti e decentralizzati 21 2.5 Descrizione della piattaforma Hardware-Software progettata . 24 3 Implementazione della rete Wireless 30 3.1 Motivazioni della scelta del protocollo 811.15.4 promosso dall’alleanza Zigbee . . . . 31

3.2 I sensori TMote Sky . . . . 38

3.3 Requisiti Hardware e Software . . . . 40

3.4 Scelta del Sistema Operativo . . . . 42

2

dati . . . . 55 4.3 Il protocollo di gestione del campo dati . . . . 55

5 Gestione locale dei dati 59

5.1 Progetto locale della struttura dati orientata al controllo multi- agente . . . . 60 5.2 Implementazione di librerie matematiche per i sensori TMoteSky 63 5.3 Interfacciamento verso il microcontrollore dell’agente . . . . . 67

6 Gestione dei dati lato Server 71

6.1 Gestione della visione e calibrazione delle telecamere . . . . . 72 6.2 Progetto di un’architettura computazionale parallela multi-

thread . . . . 82 6.3 Integrazione dati e implementazione di liberie ad alto livello

per l’interfacciamento con la rete wireless . . . . 85 7 Test della piattaforma harware-software progettata e conclu-

sioni 89

7.1 Test della pattaforma progettata tramite l’algoritmo Genera- lized RoundAbout Policy . . . . 90 7.2 Risultati ottenuti . . . . 92

3

7.3 Discussione di vantaggi e svantaggi di potenziali implementazioni 93 7.4 Sviluppi futuri . . . . 95

Bibliografia 97

2.4 Blocco di interfacciamento tra la rete wireless e l’elettronica pre-

sente su ogni agente . . . . 27

2.5 Possibili sensori . . . . 28

2.6 Schema del Progetto : vi ` e presente un server PC connesso ad una telecamera. Le informazioni rilevate sono inviate attraverso la rete wireless ad ogni singolo agente. I controllore multiluivello imple- mentato embedded le utilizzer` a per calcolare le corrette manovre da compiere. . . . . 29

3.1 Tabella di confronto fra protocolli wireless . . . . 32

3.2 Ptotocollo 802.15.4 e Alleanza ZigBee . . . . 33

3.3 Possibili livelli fisici dello standard 811.15.4 . . . . 34

3.4 DSSS nel protocollo 811.15.4 . . . . 36

3.5 Protocollo CSMA/CA . . . . 37

3.6 Wireless Sensor TMote Sky . . . . 39

3.7 Diagramma a blocchi di una TMote Sky . . . . 41

3.8 Rappresentazione grafica di un componente TinyOs . . . . 44

3.9 Rappresentazione grafica di un componente nelle applicazioni nesC 47 4.1 Descrizione di un pacchetto dati generato da un singolo agente . . 52

4.2 Descrizione di un Raw Data contenente un pacchetto dati generato da un agente . . . . 53

4.3 Descrizione di una trasmissione completa di una informazione fra due agenti . . . . 54

4.4 Descrizione dei livelli della rete implementata . . . . 56

4.5 Descrizione del vettore di stato di ogni agente . . . . 57

4.6 Modalit` a di composizione del payload . . . . 57

5.1 Descrizione della struttura locale di ogni nodo . . . . 61

5.2 Polinomi di MacLaurin approssimanti il seno . . . . 66

5.3 Plonomi di MacLaurin approssimanti la cosinusoide . . . . 67

5.4 Funzionalit` a dei 10Pin di espansione dei sensori TMoteSky . . . . 68

5.5 Funzionalit` a degli ulteriori 6Pin di espansione dei sensori TMoteSky 68 5.6 Rete logica di interfacciamento TMote-Microcontroller . . . . 69

6.1 Immagine del modello WebCam utilizzato nella tesi . . . . 73

6.2 Corrispondenza fra punti scena e punti immagine . . . . 73

6.3 Modello geometrico interno della telecamera . . . . 74

6.4 Modello semplificato unidimensionale della telecamera . . . . 75

6.5 Rappresentazione scenario . . . . 80

6.6 Parametri Intrinseci della telecamera . . . . 81

6.7 Rappresentazione scenario . . . . 81

6.8 Parametri Estrinseci della telecamera . . . . 82

6.9 Architettura Client-Server . . . . 84

6.10 Gestione dei campi visivi . . . . 87

...a chi mi ha permesso di dare sempre il massimo

...a chi mi ha fatto innamorare e vedere i colori dell’amore ...a chi mi ha protetto guardandomi dall’alto

...a chi ha reso possibile uno dei giorni pi` u belli della mia vita

...a chi ha permesso ad un sogno di avverarsi

resto il termine ROBOT significa proprio lavoro forzato. Se per` o ci spostia-

mo nei laboratori di ricerca il panorama ` e ben diverso: teste meccaniche che

sorridono, umanoidi che giocano come bambini o che imparano a riconoscere

i propri istruttori. Dunque l’obiettivo non ` e pi` u solo quello di creare schiavi

meccanici, dato che i robot antropomorfi e zoomorfi potranno forse un giorno

essere ottimi compagni artificiali capaci di muoversi, esprimersi e apprendere

come le creature viventi del nostro pianeta.

1.1 I sistemi multirobot

Gruppi di robot programmati per operare insieme si chiamano siste-

mi multirobot. A seconda delle prestazioni loro richieste, possono collaborare

oppure agire in competizione. Lo sviluppo tecnologico generale avvenuto ne-

gli ultimi anni ha permesso di abbattere costi e migliorare le prestazioni dei

dispositivi. Tale sviluppo ha investito anche la robotica, permettendo cos`ı

gi` a in fase di sperimentazione, l’uso di un maggior numero di robot rispetto

a quello consentito negli anni precedenti. Un sistema multirobot affronta un

compito con un approccio che possiamo definire distribuito nello spazio: i

robot componenti il sistema svolgono ciascuno un’attivit` a specifica che pu` o

essere uguale o diversa da quella degli altri, in punti diversi dello spazio. Al

contrario un singolo robot pu` o affrontare vari compiti distribuiti nel tempo,

svolgendo cio` e una sequenza di operazioni, spesso nello stesso punto dello

spazio. Uno obiettivo appropriato per un sistema multirobot ` e di fatto quel-

lo che prevede un problema generale, suddivisibile in problemi pi` u semplici,

ciascuno dei quali assegnabile ad un singolo robot del sistema. Spesso il

lavoro di robot in parallelo consente di svolgere compiti anche complessi in

minor tempo. Gruppi di robot sono suddivisibili in omogenei se sono tutti

dello stesso tipo e svolgono tutti quanti compiti singolarmente uguali, mentre

vengono detti eterogenei se sono composti da tipologie diverse (manipolato-

ri,veicoli) con compiti spesso diversi fra loro. Un’altra suddivisione pu` o essere

fatta in base all’organizzazione e alle relazioni che intercorrono fra i robot di

un sistema multiagente. Esistono infatti sistemi gerarchici, in cui un singolo

robot comanda e coordina le azioni degli altri che compongono il gruppo e si-

stemi non gerarchici in cui ogni robot ha la medesima importanza degli altri.

un secondo robot che il primo ha eseguito il suo sottocompito. In alternativa, i robot possono scambiarsi messaggi tramite una rete di comunicazione che

` e solitamente via radio o, in ogni caso, di tipo wireless, senza scomodi fili

che ne intralcino il movimento. Dato che la comunicazione ` e uno scambio di

conoscenza, in questo caso tale scambio dipende dal compito che i robot sono

chiamati ad affrontare: si va dalle semplici segnalazioni (ho finito di eseguire

il mio sottocompito) fino a contenuti intenzionali complessi (ho deciso di in-

traprendere questa azione per raggiungere il tal specifico obiettivo). Inoltre

la comunicazione fra robot serve anche per organizzare il sistema stesso (ad

esempio per eleggere un robot coordinatore), per la distribuzione dei compiti

e persino per sincronizzare le operazioni coordinate. Esistono diversi tipi di

approccio a sistemi multirobot. Per esempio viene detto approccio evoluti-

vo, anche definito dal basso, quello caratterizzato dalla realizzazione di robot

dotati di capacit` a elementari e di meccanismi di apprendimento dall’esperien-

ze, che vengono combinate e modificate, fino ad formare un comportamento

globale complesso e significativo. Nell’approccio opposto, cio` e cognitivo o

dall’alto ` e il progettista che sviluppa, realizza e implementa la maggior par-

te delle capacit` a complesse dei robot tramite la programmazione. Entrambi

gli approcci per` o si occupano sia delle abilit` a per operare nell’ambiente sia

di quelle cooperative e ciascuno dei due comporta i suoi vantaggi e svan-

taggi. L’approccio cognitivo non richiede tempi di apprendimento lunghi, a

differenza di quello evolutivo, in quanto quest’ultimo permette un migliore adattamento ai cambiamenti dell’ambiente in cui operano i robot. Un vasto ramo della ricerca ` e aperto in questa direzione.

1.3 Squadre e gerarchie di robot

Se l’interazione reciproca tra pi` u robot permette loro di affrontare compiti molto complessi, le tecniche e i protocolli per realizzarla possono es- sere di svariati tipi. Una di queste modalit` a prevede che pi` u veicoli autonomi siano progettati per un lavoro di squadra, organizzato secondo una gerar- chia. Un tale sistema rappresenta una sorta di sintesi dei vantaggi offerti dalle ricerche sulla modularit` a, sulla cooperazione e sulla versatilit` a: van- taggi che vengono ulteriormente amplificati dalla distribuzione dei ruoli su livelli distinti, fra diversi tipi di robot. Gerarchie di robot possono ad esempio essere generate a priori sulla base dell’importanza dei compiti svolti all’in- terno del sistema, oppure pi` u semplicente in base alla dimensioni o al costo di un agente. Lo studio e l’implementazione di sistemi multirobot portano diversi vantaggi in fase di sviluppo. Innanzitutto i robot, anche di tipolo- gie diverse, possono essere progettati indipendentemente consentendo cos`ı di ripartire i compiti di progettisti e programmatori. Inoltre la ripartizione di un sistema in livelli semplici e specializzati ` e pi` u economica della costruzio- ne di un singolo robot complesso. L’ulteriore vantaggio indiscutibile di una architettura multirobot ` e la sua robustezza. Essa pu` o cio` e gestire eventuali malfunzionamenti con flessibilit` a: se un robot della squadra si danneggia, essa pu` o provvedere a ovviare alla perdita e portare avanti il compito globale anche in fase operativa. Un ruolo fondamentale in architetture di questo tipo

` e svolto dalla comunicazione, spesso facilitata da una struttura piramidale,

perderebbe anche il controllo di tutti i robot sottoposti.

1.4 Movimenti coordinati

Nelle applicazioni che prevedono la partecipazione di pi` u robot ` e fondamentale che i comportamenti individuali siano a tal punto coordinati da consentire al sistema un comportamento globale e unitario. Questo vale sia nel caso in cui i singoli robot di un gruppo si occupino di un particola- re aspetto di un compito pi` u generale, sia che ciascuno di essi si comporti esattamente come gli altri, con cui per` o deve interagire. I numerosi approcci possibili per l’organizzazione di un sistema multirobot possono essere pensati come vie di mezzo tra due soluzioni estreme. Infatti, la coordinazione dell’at- tivit` a di ciascun robot pu` o essere basata sia sullo scambio di informazioni, sia su informazioni disponibili a livello individuale, indipendenti dagli altri robot. Fondendo queste due soluzioni estreme, le azioni svolte in modo indi- pendente dai singoli agenti formano la coordinazione dell’attivit` a collettiva.

Un tipico compito di gruppo, che richiede movimenti locali coordinati, ` e per

esempio la navigazione in formazione. Navigare in formazione significa che

un gruppo di robot si muove in un ambiente mantenendo una determinata

configurazione geometrica. Per esempio si pu` o chiedere che la formazione

stabilita inizialmente sia mantenuta anche quando i robot aggirano un osta- colo o deve essere per esempio ripristinata nel caso un membro ne fuoriesca, oppure uno vi si aggiunga in un secondo tempo.

Figura 1.1: Veicoli incolonnati

L’utilit` a di navigare in formazione per una squadra di robot mobili pu` o

essere paragonata ai vantaggi apportati dagli animali dagli spostamenti in

gruppo, per esempio in volo: a fronte di una minore esposizione ai predatori

si ottiene infatti una maggiore capacit` a di individuare pericoli e le fonti di

nutrimento. In effetti un interessante filone di ricerca riguarda proprio la

navigazione in formazione dei robot volanti. Le stesse considerazioni sono

comunque valide nel dominio dei robot mobili in generale, ad esempio in am-

bito militare e non solo. Per i robot infatti, navigare in formazione spesso

rappresenta una capacit` a elementare su cui si basano funzionalit` a collettive

pi` u complesse, quali la misurazione di grandezze ambientali, l’esplorazione

del territorio e la ricerca di obiettivi specifici. Per ridurre la complessit` a dei

ma multirobot. Nel metodo per esempio di riferimento al vicino ogni robot decide la propria posizione sulla base di quella dei vicini. In altre parole, le informazioni necessarie a un robot per posizionarsi in modo corretto sono quelle relative all’orientamento e alla posizone dei vicini. Tali informazioni in genere sono rese disponibili da sensori locali del robot oppure comunicate dal vicino stesso. Ogni metodo ovviamente comporta vantaggi e svantaggi che lo rendono piu o meno adatto a certi tipi di scenari. Il metodo di rife- rimento al vicino di fatto minimizza le informazioni necessarie al robot, in quanto il meccanismo di scambio ` e limitato alle informazioni relative ai vi- cini di riferimento. In questo modo il sistema ` e molto pi` u robusto in quanto non si affida a un sistema di comunicazione globale che in caso di malfun- zionamento potrebbe compromettere l’efficienza dell’intero sistema. Inoltre risulta molto pi` u scalabile perch` e ` e semplice aggiungere nuovi robot al siste- ma. Allo stesso tempo per` o c’` e il rischio che se anche un solo agente perde il contatto con i vicini, l’intero sistema non si comporti nel modo desiderato.

In un metodo centralizzato viceversa, si grantisce una buona efficienza sulla base di informazioni scambiate con l’intero sistema multirobot, ma allo stesso tempo perde di robustezza, poich` e necessit` a di una comunicazione globale e centrale.

Un altro tipico obiettivo per veicoli che condividono uno stesso spazio di la-

voro ` e la risoluzione di conflitti. Un interessante filone della ricerca si sta

concentrando in questi anni sullo studio di metodi per un coordinamento si-

curo dei movimenti, in modo da evitare collisioni. Tali strategie di controllo

potrebbero essere orientate alla pianificazione di movimenti per aerei, oppure

al coordinamento di veicoli autonomi adibiti al trasporto di materiali o per-

sone. Anche per questa classe di strategie di controllo, approcci centralizzati

comportano notevoli differenze rispetto a soluzioni decentralizzate.

In questo capitolo saranno descritte le problematiche che vanno affrontate

durante la progettazione di un sistema di controllo multiagente, con partico-

lare attenzione alla struttura informativa che vi ` e alla base. Saranno oltres`ı,

descritti i problemi sui quali si sta focalizzando la ricerca europea, e il con-

tributo fornito da questo lavoro di tesi. In ultimo luogo verr` a descritta la

piattaforma hardware-software progettata.

2.1 Focalizzazione della ricerca su sistemi em- bedded connessi in rete

Il lavoro che sar` a illustrato in questo documento si colloca all’inter-

no di un progetto europeo: il progetto RUNES: Reconfigurable Ubliquitous

Networked Embedded Systems. Tale progetto ha l’obiettivo di favorire la ri-

cerca e lo sviluppo di sistemi embedded connessi attraverso una rete, che

operano e si adattano all’ambiente circostante. La complessit` a e la realizza-

zione di tali sistemi impone la ricerca, lo studio e la valutazione di tecnologie

sempre pi` u all’avanguardia e innovative che consentano di semplificare il pi` u

possibile i problemi pratici d’implementazione. Il largo utilizzo di sistemi

wireless richiede oramai uno studio dettagliato delle tecnologie disponibili e

delle loro potenzialit` a. E’ sempre pi` u richiesta inoltre una standardizzazione

di tali metodologie di contollo per sistemi embedded collegati tramite reti

wireless, in modo da poter avere livelli di astrazione sempre maggiori, cos`ı

da facilitare sempre di pi` u il compito di sviluppatori e progettisti. Questo

comporterebbe un drastico taglio dei costi di produzione per lo sviluppo di

nuove applicazioni, oltre che a minori tempi di commercializzazione di un

prodotto. Il progetto RUNES rappresenta uno degli sforzi della ricerca in

questa direzione.

sforzo date le difficili specifiche che si propongono. In particolare, il progetto RUNES a livello europeo si pone i seguenti obiettivi:

1. Valutazione delle tecnologie radio e wireless esistenti.

2. Ricerca nell’area di sistemi embedded collegati attraverso reti wireless.

3. Sviluppo di reti con nodi singolarmente intelligenti.

4. Sviluppo di reti autorganizzanti e adattive.

5. Sviluppo di nuove metodologie di controllo avanzato.

6. Sviluppo di strumenti utili alla creazione di sistemi networked.

7. Creazione di applicazioni per la validazione di progetti.

Oltre all’Universit` a di Pisa, come si pu` o notare in Figura 2.1 fanno parte di tale progetto ulteriori 21 partners provenienti da 8 nazioni diverse.

2.3 Contributo del lavoro di tesi alla ricerca

Il progetto studiato e implementato in questa tesi si propone di sviluppare

una piattaforma hardware e software, in grado di poter simulare e testare al-

goritmi di controllo decentralizzato progettati per sistemi multiagente. Tale

Figura 2.1: Mappa dei partecipanti al progetto RUNES

progetto comporta una valutazione oggettiva a priori delle tecnologie dispo-

nibili, fornendo una soluzione ingegneristica, la quale abbia come specifiche

primarie le caratteristiche di riconfiguarabilit` a, scalabilit` a e risparmio ener-

getico della soluzione adottata. Come si evince dalle specifiche, tale lavoro

trova giusta collocazione all’interno del progetto RUNES, cercando di fornire

un pesante contributo in termini di ricerca e soluzioni proposte nell’area di

interesse considerata. In particolare la tesi prevede lo sviluppo di una re-

te wireless, posta alla base di nodi dotati di una propria intelligenza. Tale

progetto ` e implementato in modo tale da risultare facilmente riconficurabile

e molto versatile verso le metodologie di controllo avanzato, ponendosi co-

me un utile strumento per la validazione di progetti di controllo distribuiti

e decentralizzati. Offre quindi un significativo contributo agli obiettivi del

progetto Runes 1,2,3,6,7 descritti nel paragrafo precedente.

deve essere capace autonomamente di osservare l’ambiente a lui circostante, di ricavarsi le informazioni occorrenti, e di attuare il controllo. Non esiste quindi una decisione approvata da tutti globalmente, ma ogni agente agi- sce in base alle informazioni locali ricavate autonomamente, confidando che anche gli altri si comportino allo stesso modo, nel caso questo non ` e vero, si parla di controllo non collaborativo. I sistemi decentralizzati si distinguo- no dai sistemi distribuiti in quanto quest’ultimi possono contare su alcune facilitazioni derivanti da una unit` a centralizzata. In particolare un sistema decentralizzato ` e caratterizzato dalle seguenti caratteristiche principali:

• non esiste un leader : nessun agente dovrebbe essere fondamentale per portare al termine il compito assegnato alla rete.

• la comunicazione fra i nodi dovrebbe essere ristretta il pi` u possibile a una node-to-node communication.

• la topologia della rete non `e conosciuta a priori e oltretutto non `e fissata nel tempo. Ogni nodo dovrebbe essere sicuro delle informazioni riguardanti solo i suoi vicini.

Oltre alle limitazioni alle quali ` e soggetto un sistema decentralizzato offre anche molti vantaggi quali:

• scalabilit` a del sistema in quanto esistono limitazioni dovute alla capa-

cit` a di calcolo di un nodo centralizzato, o limitazioni dovute alla banda delle comunicazioni;

• robustezza, infatti il sistema `e robusto e tollerante ai guasti perch´e sup- porta cambiamenti dinamici nella topologia della rete come l’aggiunta o la perdita di nodi;

• possono essere usate tecniche di programmazione modulare.

Elencate queste caratteristiche principali, per il corretto funzionamento ` e

fondamentale trovare un compromesso fra le specifiche richieste dal control-

lo e le comunicazioni richieste fra gli agenti. In particolare, trattandosi di

comunicazioni wireless, ` e importante tenere di considerazione fenomeni co-

me perdita di pacchetti, effetti di quantizzazione delle informazioni, e ritardi

spesso variabili. Le strategie di controllo tradizionali si basano su assunzio-

ni ideali riguardo l’ammontare, il tipo e l’accuratezza delle informazioni che

possono circolare all’interno di un controllore. L’implementazione reale forni-

sce dei limiti che possono rendere false alcune assunzioni considerate vere in

partenza. Le prestazioni del sistema a ciclo chiuso, possono essere seriamente

degradate e talvolta pu` o esserci anche perdita di stabilit` a. Questi problemi

si manifestano in particolar modo in sistemi decentralizzati dove le capacit` a

di calcolo a bordo di ogni agente e le risorse di comunicazione comuni sono

molto limitate. Le metodologie di controllo per l’evoluzione di sistemi em-

bedded posti in rete sono diverse e spesso prevedono reti che possono essere

costituite da sensori o attuatori in continuo scambo di informazioni. L’aspet-

to principale che differenzia una comune applicazione di sistemi embedded

in rete, da una applicazione di controllo attraverso una rete wireless, sta nel

fatto che possono esserci dei veri e propri vincoli Real-Time. Ad esempio nel

caso di una applicazione che prevede il collezionamento di dati e lo studio di

con molta attenzione, in quanto in un sistema decentralizzato, devono essere presi in considerazione ritardi di comunicazione spesso non noti a priori, a causa di una topologia della rete variabile nel tempo. Note queste proble- matiche, i controlli da applicare a sistemi interconnessi tramite reti wireless possono essere sviluppati in diversi modi. Un anello di controllo prevede sen- sori, controllori, ed attuatori che sono implementati come nodi separati della rete. Spesso anche ogni singolo controllore ` e composto da elementi in cascata che possono a loro volta essere implementati su altri nodi connessi alla rete.

Utilizzando per esempio schemi in cui i sensori e gli attuatori vengono ri-

spettivamente ascoltati e comandati dal controllore via wireless, potrebbero

essere introdotti dei ritardi nell’anello di controllo dovuti alla comunicazione

attraverso la rete. Infatti, i valori dei sensori e i segnali di controllo vengono

trasmessi attraverso una rete dalla topologia variabile, la quale comporta dei

ritardi che in qualche modo devono essere attentamente considerati durante

il controllo dell’impianto. Esiste quindi la necessit` a di studiare una teoria

per sistemi interconnessi attraverso una rete, che prenda in considerazione

ritardi, limitazioni sulla frequenza di trasmissioni dati, perdita di pacchetti

ecc. Un altro esempio potrebbe essere quello di avere un algoritmo ad alto

livello che fornisce dei riferimenti a sistemi embedded. Lo scopo principale

di una tale implementazione ` e che l’impianto pu` o essere controllato local-

mente da uno o pi` u controllori, e si fa in modo che gli anelli di controllo

base non siano interconnessi da una rete wireless. Solamente i moduli ad alto livello sono connessi tramite rete wireless. Utilizzando uno schema di questo tipo, esistono limitazioni e vincoli Real-Time molto meno restrittivi, rispetto all’implementazione considerata nel primo esempio, e l’ammontare dell’informazione circolante ` e spesso di minore quantit` a.

In questa tesi, oltre agli obiettivi focalizzati nei paragrafi precedenti, ` e sta- to posto come scopo fondamentale il raggiungimento di un controllo di tipo decentralizzato. Per questo motivo i livelli del controllore sono stati imple- mentati embedded mentre il server di visione su PC e la rete wireless hanno il compito di fornire i dati provenienti dalla telecamera ai controllori in cascata implementati su ogni singolo agente.

2.5 Descrizione della piattaforma Hardware- Software progettata

La piattaforma Hardware-Software progettata ` e costituita da una strategia di controllo di alto livello che in base all’evoluzione dell’intero sistema mul- tiagente, genera dei comandi che ogni robot dovr` a seguire, cos`ı da mantenere un comportamento coordinato di gruppo. Strategie di controllo come sche- matizzato in Figura 2.2 possono avere vari obiettivi, come la risoluzione di conflitti, il movimento in formazione ecc. In particolare in questa tesi ` e stata scelta la strategia di controllo Generalized Roundabout Policy[5] come test della piattaforma progettata. Questa tipologia di contollo ` e orientata alla risoluzione di conflitti fra agenti che condividono un medesimo spazio di la- voro tramite lo scambio di informazioni relative unicamente alle rispettive posizioni.

Il sistema (come schematizzato in Figura 2.3) prevede una rete wireless, che

Figura 2.2: Esempi di algoritmi decentralizzati ad alto livello

consenta lo scambio di informazioni fra gli agenti. Oltre alle caratteristiche e alle problematiche riassunte nei paragrafi precedenti, occorre stabilire dei protocolli di trasmissione sicuri che consentano un veloce ed efficace scambio di informazione.

Il progetto di tale sistema di controllo richiede lo studio e la progettazione di un circuito come in Figura 2.4 che consenta di stabilire una comunicazione fra le informazioni ricevute da ogni nodo e l’agente che deve interpretarle, il quale sulla base di esse, deve prendere delle decisioni ed attuare il controllo in maniera corretta.

Per ogni agente ` e previsto un controllore dinamico ad alta frequenza che consenta di interpretare, seguire e generare controlli in funzione delle in- formazioni ricevute attraverso la rete wireless. E’ necessaria inoltre una sensoristica (alcuni sinsori possibili sono visibili in Figura 2.5 )che fornisca periodicamente le informazioni sullo stato attuale del sistema.

L’intero schema di controllo progettato ` e schematizzato in Figura 2.6. Co- me si pu` o notare la piattaforma Hadware-Software progettata ` e composta essenzialmente da due sottoinsiemi fondamentali:

1. un primo insieme che prevede la progettazione di una architettura di

Figura 2.3: Schema di una possibile rete wireless

rete con protocolli molto flessibili, atti a provvedere e scambiare tutte le informazioni occorrenti ai singoli agenti.

2. il secondo insieme prevede la progettazione di un veicolo capace di interpretare le informazioni ottenute, cos`ı da generare controlli che gli consentano di mantenere un giusto comportamento coordinato.

Il progetto documentato in questa tesi ` e focalizzato sull’ insieme numero

1. E’ stato utilizzato quindi un approccio a scatola nera, in quanto in questa

tesi ogni agente sar` a considerato solamente come un nodo della rete wireless,

al quale fornire periodicamente le giuste informazioni necessarie al calcolo del

controllo implementato embedded e largamente documentato nella tesi svol-

ta da L.Decaria. Si discuter` a quindi delle problematiche della gestione della

grande mole di informazione che richiede un controllo decentalizzato, ponen-

Figura 2.4: Blocco di interfacciamento tra la rete wireless e l’elettronica presente su ogni agente

do particolare attenzione alla versatilit` a, alla scalabilit` a e alla portabilit` a del

progetto che sono obiettivi peculiari della ricerca in questo campo.

Figura 2.5: Possibili sensori

Figura 2.6: Schema del Progetto : vi ` e presente un server PC connesso ad una

telecamera. Le informazioni rilevate sono inviate attraverso la rete wireless ad ogni

singolo agente. I controllore multiluivello implementato embedded le utilizzer` a per

calcolare le corrette manovre da compiere.

Implementazione della rete Wireless

Per l’applicazione descritta nel secondo capitolo ` e necessario lo stu-

dio e l’implementazione della rete wireless. In commercio esistono numerosi

dispositivi che forniscono tecnologie per la comunicazione senza fili. Occorre

quindi una trattazione e una discussione su quale protocollo di trasmissione

risulti pi` u idoneo a soddisfare le specifiche poste nel capitolo secondo.

basso costo e consente di ottenere un’alta densit` a di nodi per rete.

Il protocollo 811.15.4 ` e pensato per reti a bassa velocit` a con scambio di infor- mazione costituite da dispositivi alimentati tramite batterie che non possono esssere sostituite frequentemente, come nelle reti di sensori. Queste caratteri- stiche lo rendono idoneo per applicazioni distribuite di misura e di controllo.

Nonostante l’esistenza di numerosi protocolli wireless, il protocollo 811.15.4

` e quello che pi` u si adatta all’applicazione progettata. Infatti come si nota in Figura 3.1 tecnologie largamente diffuse come Bluetooth non sono state studiate per applicazioni di controllo decentralizzato dove l’energia e le risor- se sono limitatissime. Nonostante i dispositivi hardware che supportano la tecnologia 811.15.4 su cui si basa l’alleanza ZigBee siano molto simili ai di- spositivi che supportano il Bluetooth, la potenza richiesta nelle trasmissioni

` e molto diversa proprio a causa del diverso protocollo di trasmissione adotta- to. Si consideri che un dispositivo che fa uso della tecnologia Zigbee, in sleep mode assorbe solamente circa 1µA di corrente, a differenza dei dispositivi Bluetooth, che assorbono circa 15mA. Le velocit` a di trasmissione raggiun- te sono entrambe molto elevate e sono rispettivamente 250Kbps e 723kbps.

Guardando la tabella di confronto ` e facile notare che la tecnologia 811.15.4

ha una velocit` a molto inferiore rispetto alle altre tecnologie, ma tuttavia pi` u

che sufficiente per gli scopi di questa tesi.

Figura 3.1: Tabella di confronto fra protocolli wireless

La tecnologia Zigbee rappresenta l’alleanza industriale che mira a promuo- vere lo sviluppo e la diffusione dello standard 811.15.4 il quale definisce le direttive a livello fisico e il controllo degli accessi al canale. Dalla Figura 3.2 si vede come lo scopo dello standard 802.15.4 ` e quello di definire le caratteri- stiche dei wireless sensor. Come tutti i membri della famiglia IEEE 802, esso si preoccupa di definire solamente i primi due livelli del modello ISO/OSI, vale a dire il livello fisico e il livello MAC. L’interoperabilit` a tra i costruttori potr` a essere garantita nel momento in cui si affermer` a il protocollo definito dall’alleanza Zigbee, cio` e un’associazione internazionale di societ` a che lavo- rano insieme per abilitare e promuovere la tecnologia wireless Zigbee come open standard.

Dalla Figura 3.3 si nota che questo standard prevede tre bande di frequenza

per la comunicazione, ognuna delle quali fornisce un diverso numero di canali

e una differente velocit` a di trasmissione per i dati.

Figura 3.2: Ptotocollo 802.15.4 e Alleanza ZigBee

Offre infatti pi` u livelli fisici di trasmissione e possono essere raggiunte velocit` a di invio dati di:

• 250 kbps @ 2,4GHz con modulazione O-QPSK

• 40 kbps @ 915MHz con modulazione BPSK

• 20 kbps @ 868MHz con modulazione BPSK

L’utilizzo scelto in questo lavoro di tesi ` e quello principale previsto per questo tipo di protocollo, ovvero a 2.4GHz, dove a livello fisico sono allocati 16 canali in frequenza.

Il protocollo 802.15.4 adotta un sistema di modulazione del tipo Direct Se-

quence Spread Spectrum (DSSS), tecnologia di trasmissione a frequenza diret-

ta a banda larga, cio` e ogni bit viene trasmesso come una sequenza ridondante

di bit detta chip. Il segnale risultante viene quindi propagato su una banda

maggiore di quella necessaria ma con livelli di potenza molto bassi. Si chiami

C la capacit` a del canale espressa in bit per secondo, essa ` e la massima velo-

cit` a di trasmissione per una teorica BER:Bit Error Rate, e rappresenta quindi

Figura 3.3: Possibili livelli fisici dello standard 811.15.4

la performance del canale desiderata. Detta B l’ampiezza di banda richiesta espressa in Hz, essa rappresenta il prezzo da pagare per la trasmissione in quanto la frequenza ` e una risorsa limitata, e indicando con S/N rapporto segnale-rumore la giustificazione teorica di quanto detto risiede nel fatto che per il teorema di Shannon vale la seguente relazione:

C = B ∗ Log

(1 + S/N ) (3.1)

Il rumore pu` o essere provocato da ostacoli, campi magnetici, e onde estra-

nee alla trasmissione che interferiscono. Osservando l’equazione 3.1 ` e facile

notare che si pu` o mantenere una data prestazione C del canale o addirittura

incrementarla aggiungendo banda al segnale, anche quando la potenza del

Ln(1 + x) = x − x

/2 + x

/3 − x

/4... (3.3)

si ottiene:

C/B = 1.443 ∗ (S/N − (S/N )

/2 + (S/N )

/3). (3.4)

In genere nelle applicazioni dove viene usato il DSSS il rapporto S/N ` e basso. Considerando quindi S/N<<1, l’espressione di Shannon diventa sem- plicemente

C/B = 1.433 ∗ S/N. (3.5)

Quindi per poter trasmettere informazione libera da errore per un dato rapporto segnale-rumore nel canale, ` e necessario incrementare la banda di trasmissione.

Il protocollo MAC che controlla l’accesso al mezzo, ovvero quando ` e possi-

bile trasmettere o ricevere viene gestito a livello del Link Layer. Il proto-

collo utilizzato nelle WLAN prende il nome di CSMA/CA ed ` e derivato dal

Figura 3.4: DSSS nel protocollo 811.15.4

CSMA/CD il quale ` e alla base delle reti Ethernet. La sostanziale differen-

za fra i protocolli CSMA/CA e CSMA/CD risiede nel fatto che in una rete

Ethernet ` e possibile effettuare la Collision Detection(CD) poich` e una stazio-

ne ha la possibilit` a di ascoltare mentre trasmette e quindi di rendersi conto

se due stazioni stanno trasmettendo nello stesso momento. Questa soluzione

non ` e possibile nelle reti Wireless dove un’antenna pu` o solo trasmettere o ri-

cevere in un dato momento ed oltretutto la transazione fra le due fasi richiede

tempo. Pertanto il protocollo di accesso al canale delle Wlan introduce la

Collision Avoidance che purtroppo riduce la velocit` a e l’efficienza dello scam-

bio di informazioni. Come descritto in Figura 3.5 l’idea dei protocolli CSMA

(Carrier Sense Multiple Access) ` e che prima di trasmettere occorre ascoltare

la portante per controllare se qualcuno sta trasmettendo. Se nessuno sta tra-

smettendo, ` e possibile inviare il pacchetto, altrimenti ` e necessario attendere

il termine della trasmissione dell’altro. A questo punto una stazione attende

un numero random di Slot. Uno Slot ` e un intervallo di tempo, stabilito a

priori di una lunghezza tale da consentire il passaggio della fase di ascolto

aggiunti cos`ı altri meccanismi atti a gestire pi` u efficacemente le trasmissioni.

Figura 3.5: Protocollo CSMA/CA

In primo luogo vi sono il Positive Acknowledgement ed il MAC Level Retran-

smission. Appena una stazione ha finito di ricevere un pacchetto, invia un

Ack per confermare la ricezione prima che inizi per tutte le stazioni l’attesa

con un numero random di Slot. Se la stazione che ha inviato il pacchetto

non riceve l’ Ack, significa che c’` e stata un’interferenza ed il pacchetto ` e ri-

inviato immediatamente. In questo modo il protocollo minimizza i ritardi e

garantisce l’arrivo in sequenza dei pacchetti.

3.2 I sensori TMote Sky

La rete progettata nell’applicazione ha una topologia variabile ed ` e

composta da agenti mobili, ognuno dei quali identifica un nodo e pu` o ospi-

tare piccoli sensori wireless che consentono lo scambio di informazioni utili

con l’esterno. Le reti di sensori vengono sviluppate, come in questo caso,

per applicazioni data centric ovvero l’importanza risiede principalmente nei

dati rilevati o contenuti dai nodi, piuttosto che nella computazione eseguita

embedded. La gestione di una rete per un controllo multiagente non ` e im-

mediata, in quanto i nodi hanno risorse energetiche molto limitate e qualit` a

dei canali di comunicazione bassa. Inoltre, l’energia disponibile ` e utilizzata

non solo per lo scambio dati, ma anche per il calcolo embedded del controllo

cinematico e dinamico oltre che per l’attuazione dei motori. La tecnologia

converge quindi verso nodi di elaborazione estremamente miniaturizzati, che

integrino la totalit` a delle funzionalit` a on-chip. Questo porta a dover consi-

derare capacit` a di elaborazione e memorie di dimensioni molto ridotte. A

causa di questi motivi le reti di sensori pongono problematiche nuove per

quanto riguarda la progettazione del software. Questo avviene sia a livello di

software di sistema, sia per quanto riguarda la progettazione dell’intero siste-

ma distribuito. Per l’implementazione di una piattaforma hardware-software

per la simulazione di algoritmi di controllo multiagente, con le caratteristiche

descritte nel capitolo secondo, sono stati scelti degli smart sensors, ovvero

di sensori wireless di nome Mote. In particolare si ` e fatto uso dei sensori

TMote Sky, la cui immagine ` e riportata in Figura ??, sviluppati dalla Mo-

teIv Corporation, societ` a consolidata nello sviluppo di piattaforme wireless e

appartenente alla societ` a Texas Instruments[16].

Figura 3.6: Wireless Sensor TMote Sky

I TMote Sky[16] sono sensori di piccola dimensione e presentano caratteri- stiche utilissime all’implementazione di un controllo come in Figura 2.6 in quanto mettono a disposizione:

• dimensioni di HxWxP =1.26*2.56*0.24 in.

• velocit` a di trasmissione dati di 250 kbps @ 2,4GHz sfruttando il pro- tocollo IEEE 802.15.4 e sftuttando un Transceiver Wireless.

• un facile scambio di informazioni con altri dispositivi che supportano gli stessi standard.

• un microprocessore della Texas Instruments con velocit` a di clock di 8

Mhz con una memoria RAM di 10k e una memoria Flash di 40K.

• un’antenna integrata sulla scheda, con un raggio di azione di 50m in ambienti chiusi e di 125m in ambienti all’aperto.

• l’utilizzo dello standard IEEE 802.15.4 per ottenere un bassissimo consumo di corrente.

• un rapido risveglio dallo stato di basso consumo Sleep(< 6µs)

• una facile programmabilit` a attraverso una comune porta USB del PC.

• un supporto per i pi` u diffusi Sistemi Operativi sviluppati per la tecno- logia Mote.

Oltre alle caratteristiche tecniche utili al progetto, tali dispositivi consento- no di abbattere allo stesso tempo molti costi in quanto gli schematici e tutto l’occorrente per la loro costruzione fisica sono di dominio pubblico e facil- mente reperibili sulla rete. Possono quindi essere realizzati autonomamente in laboratorio.

3.3 Requisiti Hardware e Software

Come detto nei paragrafi precedenti i sensori devono essere piccoli,

leggeri e caratterizzati da consumi estremamente bassi. I primi due requi-

siti sono necessari per permettere di adattare l’applicazione ad una grande

variet` a di ambienti. Il terzo requisito ` e fondamentale in applicazioni come

questa in cui l’energia ` e limitata localmente. In particolare, ogni agente di

questo progetto ` e alimentato da una batteria che offre in uscita 7.2 V e pu` o

arrivare ad erogare una corrente massima di 2100 mA. Un risparmio ener-

getico significa dotare di maggiore autonomia l’intero sistema. Inoltre nello

Figura 3.7: Diagramma a blocchi di una TMote Sky

sviluppo di un contollo multiagente, dove i costi di costruzione di ogni vei- colo mobile risultano gi` a onerosi, ` e di fondamentale importanza la scelta di moduli wireless dai costi molto ridotti.

In una strategia di controllo distribuito o decentralizzato molte delle opera-

zioni sono di carattere concorrente. Possono verificarsi ad esempio situazioni

in cui il processore ` e impegnato nel trasferimento dei dati e in maniera concor-

rente deve eseguire delle operazioni locali. Questo requisito ` e implementato

dal sistema operativo residente sul sensore TMote dal momento che non ` e

fattibile sviluppare architetture parallele con dimensioni ed hardware cos`ı li-

mitato.

Il software progettato per una rete wireless atta a fornire informazioni neces- sarie per il controllo di un sistema multirobot ` e sottoposto a problematiche aggiuntive rispetto al software atto alla gestione delle comuni reti. Esso in- fatti deve poter funzionare con ridotte risorse di elaborazione. Per dotare di versatilit` a, modularit` a, e riconfigurabilit` a la piattaforma hardware-software progettata verso algoritmi di controllo ad altro livello decentralizzati o distri- buiti ` e auspicabile progettare programmi con linguaggio pi` u astratto possi- bile, che consentano al progettista di non dover reimplementare componenti riutilizzabili. Il software deve inoltre essere in grado di astrarre la comples- sit` a e la topologia della rete in modo da renderla facilmente scalabile verso diversi tipi di algoritmi di controllo. Per ovviare a quanto detto, occorre la scelta accurata di un sistema operativo che consenta di far fronte alle proble- matiche da affrontare in maniera pi` u conveniente possibile per lo scopo della tesi.

3.4 Scelta del Sistema Operativo

Non tutti i sistemi operativi presenti sul mercato risultano idonei

alla gestione dei dati per una applicazione di controllo multiagente. Un

sistema operativo general pourpose ad esempio sarebbe troppo dispendioso

in termini energetici. Per l’implementazione di una piattaforma hardware-

software atta a simulare algoritmi di controllo distribuiti o decentralizzati

occorre la scelta di un sistema operativo con delle caratteristiche e delle

specifiche ben precise. Occorre infatti che abbia ridotte dimensioni, basso

consumo durante l’elaborazione dei dati e consumo quasi nullo durante lo

stato di idle. Deve poter gestire la concorrenza ed implementare protocolli

di rete e di trasmissione delle informazioni ad alto livello poco dispendiosi in

2. sistemi operativi che includono strati software tipici dei sistemi general pourpose ma in versione ridotta (ad esempio BerthaOs e Mantis).

I sistemi di primo tipo consentono di fatto una sola applicazione in ese- cuzione su un singolo sensore TMote Sky. Se tuttavia a prima vista questo appare come una grande limitazione, una simile implementazione consente di avere bassissimi consumi (non esistendo context switch) ed applicativi locali molto piccoli in quanto debbono essere inserite nel codice solo le funzionalit` a richieste.

Nei sistemi operativi di secondo tipo nonostante sia fornita un’alta versatilit` a ed essendo possibile eseguire pi` u applicazioni in contemporanea, ` e difficilis- simo tenere i consumi e le risorse energetiche sotto controllo.

Per lo svolgimento di questo lavoro di tesi ` e stato scelto il sistema operati- vo TinyOs che appartiene al primo filone dei sistemi esistenti, e consente la versatilit` a necessaria alla gestione delle informazioni per un controllo multia- gente, unita a tutti i vantaggi descritti in precedenza.

TinyOs ` e implementato in linguaggio nesC e offre un modello di programma-

zione basato su eventi. Ogni applicazione ` e composta da diversi componenti

la cui elaborazione viene avviata solamente al verificarsi di un determinato

evento. Questo approccio si contrappone al tradizionale paradigma basato su

stack e switching del contesto di esecuzione. In questo modo quando il sen-

sore TMote Sky ` e in stato di idle non esegue alcuna operazione consumando minime quantit` a di energia, per questo motivo quindi TinyOs pur permet- tendo la concorrenza evita l’attivit` a di context switching tipica dell’approccio tradizionale. L’unico componente sempre presente in ogni applicazione ` e lo scheduler il quale ha il compito di mandare in esecuzione i vari task dei di- versi componenti seguendo una politica di tipo FIFO, run to competition. In altre parole un task non pu` o interrompere un altro task.

Figura 3.8: Rappresentazione grafica di un componente TinyOs

TinyOs ` e dotato di event handlers e command handlers. I componenti co-

municano tra di loro invocando comandi gestiti dai command handlers e

sollevando eventi gestiti dai event handlers. Entrambi vengono eseguiti a

• hardware abstractions: mappano le funzionalit` a fornite via software sulle funzionalit` a fornite da hardware creando un’astrazione dello stesso utilizzabile dai moduli superiori.

• syntetic hardware: simulano il comportamento di un harware pi` u com- plicato di quello realmente presente sul sensore.

• high level software component : si occupano di eseguire algoritmi che prescindono dal particolare hardware.

3.5 Vantaggi e svantaggi della realizzazione di software per la rete di sensori mediante NesC

Una rete progettata per la gestione delle informazioni in un sistema di controllo multiagente prevede lo sviluppo di software di sistema. Gli ap- plicativi per i sensori TMote Sky sono stati sviluppati in linguaggio NesC.

Tale linguaggio ` e caratterizzato dall’essere basato sul C. Il principale van-

taggio di tale uso, oltre all’elevate prestazioni, consiste nella familiarit` a dei

programmatori con i linguaggi C oriented rendendo cos`ı particolarmente fa-

cile la portabilit` a di progetti e applicazioni su altre piattaforme hardware od

altri sistemi operativi. Tuttavia il linguaggio C non si adatta a molti requi-

siti che occorrono ad una rete wireless dedicata al controllo di un sistema multiagente. Ad esempio non ` e previsto un approccio ad eventi. I paradig- mi di programmazione software con metodologie standard rivolte a sistemi operativi general pourpose devono essere profondamente cambiati. In una applicazione di controllo infatti non ` e consigliabile effettuare polling su un buffer di ricezione per ottenere messaggi in arrivo dagli agenti vicini. Questo approccio comporterebbe spreco di risorse energetiche e soprattutto spreco di capacit` a di calcolo e tempo per la computazione del controllo.

NesC ` e una variante del linguaggio C sviluppato per la programmazione dei sensori Mote. Per certi versi questo linguaggio ` e un’estensione del C (offre un’implementazione ad eventi) mentre per altri ne risulta come una limita- zione, restringendo le operazioni sui puntatori. In accordo con la politica di gestione delle risorse del sensore Mote(sleep-awake), le applicazioni scritte in NesC sono event driven: i componenti sono mandati in esecuzione solo quan- do si verifica un evento che li riguarda. Essendo anche TinyOs programmato in NesC, ogni volta che un’applicazione viene compilata, anche i componenti del sistema operativo vengono compilati insieme ad essa ed il risultato costi- tuisce l’intero software del sensore. Questo approccio consente un notevole risparmio di energia e memoria a scapito della versatilit` a. Infatti dopo la compilazione e il trasferimento del software all’interno del sesnore TMote Sky non ` e pi` u possibile installare ulteriori applicazioni, effettuare linking di- namico a librerie esterne, o riconfigurare dinamicamente il codice inserito.

Dal punto di vista dell’affidabilit` a, la presenza di una singola applicazione

alla volta e l’assenza di link dinamico permette di eseguire molti controlli

statici sulla bont` a del codice che altrimenti non sarebbero possibili. Inoltre,

funzionalit` a proprie del C, come allocazione dinamica e puntatori a funzione,

che spesso sono fonte di problemi relativi alla robustezza del codice, vengono

Figura 3.9: Rappresentazione grafica di un componente nelle applicazioni nesC

Ogni interfaccia ` e bi-direzionale e modella un servizio offerto/fornito dal componente. Le interfacce sono a loro volta costituite da un’insieme di co- mandi ed eventi. Per ogni interfaccia fornita da un componente quest’ultimo implementa i comandi, mentre l’utilizzatore implementa il codice relativo agli eventi. Per ogni interfaccia utilizzata da un componente quest’ultimo imple- menta gli eventi ed invoca i comandi.

La scomposizione di una applicazione in eventi ` e molto vantaggiosa in quan-

to permette di creare un livello di astrazione hardware del sensore TMote

Sky. Attraverso parole chiave proprie del linguaggio ` e possibile anche solle-

vare eventi relativi alle interfacce e regolarne la gestione. Ogni applicazione ` e

composta da due moduli separati. Uno modulo viene detto di configurazione

e definisce di quali componenti viene fatto uso e di come sono connesse le

interfacce fra di essi. Il secondo modulo viene detto di implementazione e vi

viene definito il codice per la gestione dei dati e le azioni da intraprendere

al verificarsi degli eventi sulle interfacce. La concorrenza fra i task viene

gestita dallo scheduler di TinyOs. Gli eventi e gli handlers associati hanno

una priorit` a pi` u alta, quindi ogni task che viene gestito con una politica FI-

FO ` e interrompibile da un interrupt proveniente da un evento che solleva un

handler associato.

In questo capitolo verr` a descritta la gestione delle informazioni cir-

colanti all’interno della rete wireless presente a monte degli agenti. Verrano

descritte le tecniche di scambio dati fra nodi della rete, e i protocolli utilizzati

allo scopo di evitare perdita delle informazioni o ambiguit` a di interpretazio-

ne. Sar` a descritta infine la perdita di risoluzione dovuta alla quantizzazione

numerica con l’utilizzo di tali protocolli.

4.1 Progetto del protocollo ad alto livello per lo scambio dei dati fra agenti

In una rete wireless, ` e fondamenale poter inviare e ricevere infor- mazioni in modo univoco, in modo che quando un agente genera e invia un messaggio, questo venga ricevuto solo da chi pu` o riceverlo. Solamente in que- sto modo si pu` o garantire il giusto fluire delle informazioni sulla rete evitando problemi di interpretazione e congruenza dei dati che potrebbero seriamente compromenttere la stabilit` a del controllo.

Per questa tesi ` e stata utilizzata la tecnologia Active Message messa a di- sposizione da TinyOs. Questa tecnologia consente di inviare messaggi a tutti o a un singolo nodo. I protocolli di routing sono implementati ad un livello superiore, quindi presenta solo un meccanismo di indirizzamento verso nodi vicini. Active Messages ` e una modalit` a di scambio dati molto leggera, in quanto ogni pacchetto ` e un’entit` a indipendente contenente l’identificatore di un handler da richiamare sulla macchina di destinazione e i dati del pacchet- to. Questo sistema permette di evitare il complesso utilizzo di buffer delle implementazioni del protocollo TCP/IP. Il principale svantaggio di questo approccio ` e che tutti i nodi comunicanti devono avere lo stesso software o quantomeno implementare un componente che definisca lo stesso handler.

Ad ogni nodo ` e assegnato un indirizzo locale, ed un identificativo di gruppo.

I gruppi possono essere 255, e solamente nodi apparteneti ai medesimi grup- pi possono scambiare informazioni attraverso la rete utilizzando un handler dedicato.

In rispetto di quanto detto, come si nota dalla Figura 4.1 ogni pacchetto

spedito da un agente ` e composto da tre porzioni fondamentali: Intestazione,

Data e Check.

informazione fra due nodi. Il campo local address ` e composto dall’indirizzo del nodo destinatario della rete, a cui ` e stato inviato il messaggio. Il campo handler ` e composto da un parametro che richiama una particolare routine di ricezione che necessariamente deve avere implementata all’interno del nodo che riceve il pacchetto, permettendogli cos`ı di interpretare correttamente il campo dati pervenuto. Infine, l’intestazione comprende un ulteriore campo, che prende il nome di group id, il quale specifica il gruppo a cui apparntiene tale agente. Ogni messaggio, anche se inviato in broadcast sar` a ricevuto so- lamente dagli agenti appartenenti al medesimo gruppo.

La seconda porzione del pacchetto ` e composta solamente dalle informazioni che un agente desidera inviare in rete. La grandezza del payload non pu` o superare la lunghezza di 28 byte.

Infine, si nota una parte che prende il nome di check dedicata al control-

lo di correttezza dei dati trasmessi. Attraverso i dati contenuti nel campo

CRC infatti, l’agente che riceve il pacchetto pu` o controllare che durante la

trasmissione wireless non si siano verificati errori, e che le informazioni ri-

cevute siano quindi corrette. In questo caso, se richiesto dal trasmettitore,

a livello link layer (come descritto nel capitolo precedente), il ricevente po-

trebbe inviare un ack per segnalare la corretta ricezione, o in caso contrario

prendere provvedimenti, come scartare il pacchetto, o addirittura richiedere

un’ulteriore trasmissione.

Figura 4.1: Descrizione di un pacchetto dati generato da un singolo agente Ad un livello di astrazione inferiore, prima di essere inviato sulla rete, ogni pacchetto ` e ulteriormente inglobato in una struttura che prende il nome di Raw Data Packet. Come si nota dalla Figura 4.2 ogni Raw Data Packet

` e a sua volta composto da tre porzioni: Intestazione, DataMessage, Segnala- zione di fine trasmissione.

La porzione riguardante l’intestazione del Raw Data Packet ` e composta da un byte protetto che prende il nome di Sync Byte, adibito ad una segnalazione preventiva di inizio trasmissione ed ha la funzione di sincronizzare dei nodi che abbiano intenzione di dialogare tra di loro. Dell’intestazione fa parte anche il campo Type. Tale valore specifica se il trasmettitore chiede un ack dal nodo che ha ricevuto il pacchetto come conferma di una giusta trasmis- sione. La seconda porzione del Raw data Packet ` e composta da un intero messaggio generato dall’agente gi` a descritto ampiamente. Infine, ` e presente un’ultima porzione composta ancora da un Sync Byte attraverso il quale il nodo trasmettitore segnala il termine della trasmissione al ricevitore.

Ovviamente, la presenza di byte uguali al byte protetto all’interno dei

campi dati del Data Message possono comportare anomalie di sincronizza-

zione. Onde evitare problemi di questo tipo, ogni agente durante la compo-

sizione di un messaggio, controlla se vi sono byte uguali a quelli adibiti alla

sincronizzazione. Nel caso essi siano presenti, l’agente si serve di un Esca-

Figura 4.2: Descrizione di un Raw Data contenente un pacchetto dati generato da un agente

pe Byte, anch’esso protetto. Tale uso consiste nel sostituire il byte protetto

con un Escape Byte seguito da un byte che rappresenta un’operazione di or

esclusivo fra il Sync Byte e il valore 0x20. Tale soluzione viene descritta in

maggior dettaglio in Figura4.3.

Figura 4.3: Descrizione di una trasmissione completa di una informazione fra

due agenti

natari.

Come si nota dalla Figura 4.4, nel momento in cui un nodo invia un mes- saggio, avviene un primo filtaggio relativo al gruppo a cui appartiene l’a- gente destinatario. Un secondo filtraggio avviene tramite l’indirizzo locale (non esclusivo) assegnato ad ogni agente. All’interno di ogni gruppo possono esserci pi` u agenti che condividono il medesimo indirizzo, e questa soluzio- ne permette di poter implementare ulteriori sottogruppi all’interno di ogni gruppo principale. Giunto a questo punto, ogni messaggio ` e sottoposto ad un ulteriore filtraggio messo in atto dal comando handler che consente di iden- tificare una particolare ed esclusiva routine di ricezione. Una volta avviata essa mette a disposizione le giuste funzioni di interpretazione dei dati. Per questo motivo solamente gli agenti che implementano le funzioni appropria- te possono interpretare correttamente i dati giunti attraverso la rete. Tali handlers sono stati implementati in NesC e i loro scopi principali saranno descritti in seguito.

4.3 Il protocollo di gestione del campo dati

Fino a questo momento sono state discusse le modalit` a con cui due agenti si

scambiano una generica informazione contenuta all’interno di un DataMes-

sage.

Figura 4.4: Descrizione dei livelli della rete implementata

Occorre ora stabilire un protocollo globale con cui ogni veicolo compone i da- ti da inviare in rete, ovvero la modalit` a di compilazione del campo payload.

Ogni agente ` e stato costruito come un uniciclo, e i vantaggi di una simile soluzione sono ampiamente descritti nella tesi di L. Decaria [2]. Come noto in letteratura, un veicolo di tipo uniciclo ` e caratterizzato da un vettore di stato [x, y, ϑ] ma come si nota in Figura 4.5 la piattaforma hardware-software progettata ha lo scopo di gestire un ambiente costituito da pi` u veicoli, quin- di per apportare una maggiore versatilit` a e riconfigurabilit` a ` e stata inserita un’ulteriore variabile che prende il nome di Id (Identificatore), il cui utilizzo comporta dei vantaggi che saranno discussi in seguito.

Ogni vettore di stato ` e impacchettato nel campo payload in quattro porzioni diverse, ad ognuna delle quali sono stati attribuiti due byte, eccetto che per la porzione dedicata alla variabile id a cui ` e stato assegnato un solo byte.

Come si nota in Figura 4.6 questo protocollo consente di inviare lo stato di

Figura 4.5: Descrizione del vettore di stato di ogni agente un agente in 7 byte.

Figura 4.6: Modalit` a di composizione del payload

Con una soluzione di questo tipo, gli identificatori, che sono esclusivi di ogni

veicolo, possono essere al massimo 2

= 255 mentre le grandezze relative alle

variabili di stato che riguardano la posizione sono considerate come millime-

tri, cosicch` e l’ambiente massimo disponibile dove ` e possibile far svolgere dei

compiti agli agenti ` e di 2

= 65536 mm ovvero 65, 536 metri. La variabile di

stato angolare ` e rappresentata in gradi, e qualsiasi valore maggiore dell’ango-

lo giro viene modulato su 360

. Tramite questo tipo di quantizzazione nelle

informazioni riguardanti la posizione degli agenti ` e presente una perdita di

risoluzione dell’ordine di 10

m. Per quanto riguarda le variabili angolari ` e

presente una perdita di risoluzione dell’ordine di 10

gradi.

ne versatile e facilmete adattabile per applicazioni di controllo distribuito o

decentralizzato.

5.1 Progetto locale della struttura dati orien- tata al controllo multi-agente

La struttura locale residente in ogni nodo della rete ` e stata progettata in modo da offrire le pi` u comuni funzionalit` a necessarie alla gestione di un controllo multiagente. Essa ` e composta essenzialmente di tre livelli detti rispettivamente: componenti, interfacce, e comandi-eventi. I componenti messi a disposizione da TinyOs sono numerosissimi, e date le limitazioni poste dall’ hardware dei sensori TMoteSky, in fase di progetto occorre una scelta accurata ed orientata verso applicazioni di controllo.

Il componente principale ` e il Main che mette a disposizione un’ interfaccia StdControl, che ha la funzione di collegarsi con lo schedulatore di TinyOs.

La funzionalit` a del Main non ` e documentata in quanto rimane la medesima per qualsiasi tipo di applicazione, quindi per una sua esauriente trattazione si rimanda alla guida presente sul sito[4].

I componenti scelti in fase di progettazione per offrire una massima versatilit` a verso algoritmi di controllo multirobot possono essere osservati in Figura 5.1, e le rispettive funzionalit` a sono elencate di seguito.

GenericComm - Questo componente ` e stato inserito perch` e si occupa

della gestione di scambio dati via radio, gestendo ad alto livello il protocollo

802.15.4 descritto al Capitolo 3. Esso fornisce delle interfacce che prendono

il nome rispettivamente di SendMesg e ReceiveMsg. La caratteristica princi-

pale di queste interfacce consiste nel fatto di essere parametrizzate, ovvero,

sono associate ad un rispettivo ed esclusivo handler. In questa tesi ad ogni

nodo sono stati assegnate 7 interfacce per ognuno dei due tipi, in modo da

poter creare un numero sufficientemente alto per la tipologia delle informa-

zioni scambiabili fra agenti durante il tempo di operabilit` a.

Figura 5.1: Descrizione della struttura locale di ogni nodo

L’intefaccia ReceiveMsg a sua volta mette a disposizione un evento attraverso il quale segnala la ricezione di un messaggio da un altro nodo, mentre l’in- tefaccia SendMsg mette a disposizione un comando per inviare un pacchetto di dati, associato ad un evento per segnalare l’avvenuta spedizione.

LedsC - Questo componente ` e stato inserito per la gestione dei leds. Ha la sola funzione di segnalare lo stato in cui si trova il nodo in quel momento.

Tale componente mette a disposizione un’interfaccia Leds, che a sua volta

mette a disposizione dei comandi con cui si pu` o gestire lo stato dei led. Tale

componente, seppur non utile alla strategia di controllo ` e stato inserito per segnalare tramite spie luminose lo stato in cui si trova l’agente durante lo svolgimento delle manovre.

HPLUartC - Questo componente ` e stato inserito per la gestione del protocollo RS232. E’ strettamente necessario perch` e spesso in un’applica- zione di controllo i dati collezionati dal sensore wireless devono essere messi a disposizione di un microcontrollore che implementa l’intelligenza di ogni agente. Il protocollo RS232 ` e largamente diffuso e il suo inserimento com- porta un alto livello di compatibilit` a con quasi la totalita dei microcontrollori commerciali. L’interfaccia messa a disposizione ` e l’HLPUart che a sua volta provvede dei comandi ed eventi per la gestione di singoli byte scambiati at- traverso il protocollo seriale.

HPLUsart0M - Questo compomente ` e di fondamentale importanza per un’applicazione di controllo in cui il sensore TMoteSky ha necessit` a di dialogare con una periferica hardware esterna. Infatti mette a disposizione un’interfaccia di nome HplUsart che fornisce i metodi per abilitare l’ascolto di informazioni provenienti dal canale radio oppure tramite i canali del cir- cuito di espansione descritto nel datasheet [3].

TimerC - Tale componente ` e stato inserito perch` e in una applicazione

di controllo che punta alla massima decentralizzazione, ` e di fondamentale

importanza che le operazioni degli agenti siano sincronizzate. Inoltre, come

descritto dal protocollo CSMA/CA anche lo scambio di informazioni tra no-

di non pu` o avvenire simultaneamente in quanto il canale attraverso il quale

dialogano ` e esclusivo, rendendo cos`ı di fondamentale importanza un tempo

zione i metodi per settare il verso dei canali (I/O) e per gestire i livelli logici in uscita.

BusArbitrationC - Questo compomente fornisce un’interfaccia di nome BusArbitration che attraverso dei comandi ed eventi consente la gestione del bus dati all’interno del sensore. Infatti i TMote Sky consentono una gestione mutuamente esclusiva del circuito di espansione e del canale radio. Tale caratteristica rende necessario l’utilizzo di un modulo software che consenta di assegnare il bus dati correttamente in base alle operazioni necessarie ad un dato momento.

5.2 Implementazione di librerie matematiche per i sensori TMoteSky

In applicazioni di controllo multiagente spesso i dati scambiati con gli al-

tri nodi possono richiedere funzioni matematiche non disponibili nel sistema

operativo TinyOs per i sensori TMote. Il motivo di tale mancanza deriva

dal fatto che questi dispositivi non sono orientati ad operare in sistemi di-

namici, ma piuttosto sono nativi per applicazioni di collezionamento dati

come monitoraggio di ambienti. Una tale orientazione emerge osservando le

caratteristiche principali descritte nel datasheet, quali una grande memoria

per il collezionamento di dati ed una capacit` a di calcolo molto esigua. In sistemi di controllo decentralizzati gli interi algoritmi computazionali sono implementati embedded, dove spesso le risorse sono limitatissime, e occor- re quindi riuscire a sfuttare tutta la capacit` a di calcolo disponibile su ogni agente. Le operazioni pi` u frequenti da effettuare durante la preparazione dei dati da scambiare in rete sono di tipo matematico, e non sarebbe pertan- to pensabile di non dotare la piattaforma hardware-sotware progettata della possibilit` a di effettuare tali operazioni a monte di un generico microcontrol- lore interamente dedicato alla gestione dei movimenti dell’agente. Sono state implememntate quindi delle librerie interamente implementate in linguaggio NesC che forniscono le possibilit` a appena descritte.

Per le funzioni trigonometriche elementari,

y = sin(x) (5.1)

y = cos(x) (5.2)

ma basilari in una applicazione orientata ad implementare un controllo de- centralizzato ` e stata utilizzata un’approssimazione tramite il polinomio di MacLaurin, cio` e il polinomio di Taylor che approssima la funzione nell’intor- no di x = 0. In altre parole il polinomio di MacLaurin p(x) di grado n che meglio approssima la funzione f (x) ` e quello cha ha lo stesso valore di f (0) e di tutte le derivate fino all’ennesima sempre per x = 0.

Per quanto detto deve quindi risultare:

P (0) = f (0); P

(0) = f

(0); P

(0) = f

(0)...P

(0) = f

(0) (5.3)