Nella prima fase del lavoro ` e stato sviluppato un simulatore che, per la sua modularit` a, permette la facile verifica di leggi di controllo decentralizzate.

Sommario

L’argomento affrontato da questa tesi ` e la coordinazione di pi` u velivoli ap- plicando leggi di controllo decentralizzate.

Alcune delle tecniche pi` u consolidate sono state esaminate e classificate in diverse categorie.

Nella prima fase del lavoro ` e stato sviluppato un simulatore che, per la sua modularit` a, permette la facile verifica di leggi di controllo decentralizzate.

Uno degli approcci che utilizza statistiche di formazione e algoritmi di con- sensus per la stima di variabili globali ` e stato analizzato a fondo, ampliato nella parte che concerne la determinazione del rettangolo di contenimento e la stima di variabili globali con andamento lineare ed arricchito di termini di collision avoidance.

Infine, con la presente tesi, ` e stato proposto un nuovo meccanismo di coordi- nazione che permette la distribuzione decentralizzata degli agenti all’interno di un’area circolare di dato centro e raggio. Al nuovo controllo ho dato il nome di virtual edges poich` e ` e realizzato associando forze virtuali agli archi di una rete, anch’essa virtuale, che racchiude alcune propriet` a geometriche della distribuzione spaziale degli agenti.

Abstract

The topic of this thesis is the motion coordination of multi agent systems using decentralized control laws.

Some of the most well-established techniques had been considered and clas- sified within different classes.

In the first stage of my work I developed a modular software simulator that helps in verifying decentralized control laws.

One of the abstraction based approaches has been studied in depth. The formations are described by a set of summary statistics and consensus algo- rithms are used as decentralized estimators of global variables. I extended this technique fixing the spanning rectangle, deriving a consensus algorithm with zero steady state error for ramp inputs and adding terms for obstacle avoidance.

Finally in this thesis I propose a new coordination control that allow the

enclosure of the agents in a desired circular area using decentralized con-

trol laws. The new control has been named virtual edges for the virtual

forces applied by the edges of a virtual net that resemble some geometric

characteristics of the spatial distribution of the agents.

Indice

Introduzione 1

1 Classificazione dei Sistemi Multiagente 5

1.1 Cooperazione . . . . 5

1.2 Conoscenza . . . . 7

1.3 Coordinazione . . . . 8

1.3.1 Leader-Follower . . . . 9

1.3.2 Artificial Potential Functions . . . . 10

1.3.3 Virtual Structures . . . . 10

1.3.4 Behavior Based . . . . 11

1.3.5 Consensus Based . . . . 12

1.3.6 Abstraction Based . . . . 13

1.3.7 NSB Approach . . . . 13

1.4 Organizzazione . . . . 14

1.5 Comunicazione . . . . 14

1.6 Architettura . . . . 15

1.7 Grandezza del Team . . . . 15

1.8 Composizione del Team . . . . 16

2 Stima e Controllo Decentralizzato 17 2.1 Statistiche di Formazione . . . . 19

2.1.1 Spanning Rectangle . . . . 24

2.2 Consensus Estimator . . . . 25

2.2.1 Grafi di connessione . . . . 25

2.2.2 Static Consensus . . . . 26

2.2.3 Dynamic Consensus . . . . 27

2.3 Controllo . . . . 33

2.3.1 High-Pass Algorithm . . . . 35

3 Obstacle Avoidance 41 3.1 Obstacle avoidance con forze giroscopiche . . . . 43

2

3

4 Virtual Edges 50

4.0.1 Rete di Comunicazione . . . . 50

4.0.2 Forza Repulsiva degli Edges . . . . 54

4.0.3 Formazione . . . . 56

5 Sviluppo software di un simulatore Multiagente 60 5.1 Struttura del Simulatore . . . . 60

5.1.1 Layer I . . . . 62

5.1.2 Layer II . . . . 64

A Uso del Simulatore 73 A.1 Codice, Variabili Globali ed Esempi . . . . 73

A.1.1 Layer I . . . . 73

A.1.2 Layer II . . . . 75

A.1.3 Impostazione delle condizioni iniziali . . . . 77

Introduzione

Il crescente interesse per i problemi di coordinazione multiagente nasce dalla necessit` a di utilizzare tanti semplici velivoli autonomi di limitate capac- it` a anzich` e una grossa e potente macchina. La presenza di tanti agenti rende il sistema pi` u robusto e tollerante ai guasti e rende possibile la copertura di aree estese.

Si pensi ad esempio ad operazioni di ricerca di dispersi in zone disastrate, al monitoraggio di incendi, operazioni di sorveglianza, ricerca e smaltimento di sostante tossiche nell’ambiente, mappatura del territorio, oceanografia, ecc.

In ambito industriale potremo utilizzare squadre di robots cooperanti: ad un grande impianto fisso sostituiamo tanti robot pi` u semplici che coordinano il loro lavoro e/o i loro spostamenti.

Nello sviluppare le leggi di controllo ` e per` o necessario considerare le limi- tazioni hardware dovute al basso payload disponibile. Ci riferiamo in par- ticolare alle limitate capacit` a di calcolo, di sensing e di comunicazione. Le informazioni disponibili ad ogni singolo agente sono locali e non complete, mentre il compito richiesto deve soddisfare requisiti che sono globali e dipen- dono dallo stato di tutti gli agenti. Il comportamento collettivo deve emergere dalla cooperazione di tutti gli agenti.

Gli esempi che troviamo in natura di questo tipo di sistemi costituiscono un’ottima fonte di ispirazione; studi del settore dimostrano che molte specie di uccelli e pesci riescono a formare compatte e coerenti flotte senza la pre- senza di un organo di decisione centrale. Molto spesso la formazione rag- giunta migliora le performance dell’intero gruppo. Studi aerodinamici hanno dimostrato che la formazione a ’V’, utilizzata ad esempio durante i voli mi- gratori delle cicogne, aumenta il tempo di volo per le correnti di ’downwash’

create all’interno del gruppo. Pesci che si muovono in maniera coordinata sono capaci di avvistare tempestivamente un predatore, di confonderlo aven- do le sembianze di un unico e grande pesce e, al limite, di effettuare manovre evasive per minimizzare la probabilit` a di cattura dei membri. Il problema della coordinazione ` e solamente uno dei temi di ricerca della robotica coop- erativa ma ` e anche uno dei requisiti fondamentali per lo svolgimento della

1

2

maggior parte dei task.

In un contesto pi` u generale il comportamento cooperativo di alcune specie di insetti, tra cui formiche e api, da luogo a quello che ` e stato chiamato com- portamento emergente. Nessuno schema di divisione dei compiti ` e previsto per lo svolgimento del task: i membri si auto-organizzano facendo emergere da semplici regole locali comportamenti complessi.

La biologa Deborah M. Gordon afferma ”Le formiche non sono intelligenti, le colonie di formiche si”. Molti dei problemi risolti dal gruppo sono spes- so impossibili per una singola formica: trovare il tragitto pi` u breve verso la migliore fonte di cibo, assegnare diversi compiti alle operaie, difendere il territorio dagli intrusi. Le api sono in grado di prendere decisioni collettive, in modo decentralizzato, con meccanismi simili al voto; la decisione presa ` e molto spesso quella ottima per la soluzione del problema.

L’intelligenza collettiva, o Swarm Intelligence, ` e stata applicata per risol- vere problemi di ottimizzazione. Alcune societ` a telefoniche francesi e inglesi utilizzano agenti software che depositano ferormoni virtuali nelle stazioni di passaggio, simili a quelli utilizzati dalle formiche per lasciare ad altre formiche informazioni sulle piste migliori da seguire, rendendo pi` u veloci le comuni- cazioni sulle loro reti.

Il lavoro di tesi si ` e incentrato sul problema della formazione utilizzando controlli decentralizzati e si ` e svolto in tre diverse fasi: ricerca bibliografi- ca sulle tecniche pi` u comunemente utilizzate e contestuale sviluppo di un software di simulazione multiagente, scelta e ampliamento di un particolare approccio, proposta di un nuovo meccanismo di coordinazione.

Durante la fase di ricerca bibliografica si ` e cercato di classificare i meccanismi di coordinazione sulla base dell’approccio utilizzato e del tipo di formazione raggiungibile.

Per la scelta e l’ampliamento di un particolare approccio si ` e optato per una tecnica appartenente alla categoria degli approcci basati sull’astrazione della forma geometrica (Abstraction Based Approach): con poche variabili cerchi- amo di descrivere la formazione composta da tanti agenti. Queste variabili sono costruite in modo da poter essere stimate da algoritmi di consensus.

Un algoritmo di consensus consente di far convergere le variabili interne su cui lo eseguiamo ad un unico valore, che tipicamente ` e la media dei valori di ingresso di tutti gli agenti, scambiando informazioni con i soli vicini. Se ad esempio consideriamo come ingresso la posizione assoluta di ogni robot possiamo stiamare la posizione del baricentro, che ` e calcolato come media di tutte le posizioni.

Le modifiche apportate sono state l’utilizzo di un nuovo algoritmo di con-

sensus e l’aggiunta di termini di obstacle avoidance. Si sono inoltre ricavate

3

le espressioni necessarie alla determinazione del rettangolo di contenimento della formazione.

L’approccio da me proposto non pu` o essere classificato in nessuna particolare categoria in quanto utilizza elementi che sono peculiari ad almeno tre delle classi individuate. La rete di comunicazione non ` e definita solamente dal mas- simo raggio di comunicazione disponibile, ma ` e creata dinamicamente sulla base della distribuzione spaziale relativa tra gli agenti. La rete cos`ı costruita ha l’aspetto di una triangolazione di Delaunay sui punti individuati dalle posizioni degli agenti. L’algoritmo di creazione della rete ` e decentralizzato:

a partire da un unico edge gli agenti creano una rete connessa utilizzando un algoritmo iterativo che richiede la conoscenza della posizione dei vicini e della topologia locale della rete.

In particolare ogni agente deve poter stabilire, senza la completa conoscenza topologica della rete, quali tra i vicini sono tra loro collegati e quali si trovano all’interno del raggio di comunicazione l’uno dell’altro: a tale proposito per ogni agente sono previsti due segnali analogici con cui ` e codificata la topolo- gia locale, uno per la rete fisica (determinata dal raggio di comunicazione) e uno per la rete virtuale (costruita dinamicamente). Ad ogni agente ` e associ- ata una frequenza; i segnali trasmessi dovranno contenere la sua frequenza, le frequenze dei vicini ed eventualmente la frequanza dei vicini di secondo livello.

Il secondo passo consiste nell’associare forze virtuali di repulsione agli edge creati che rispettano alcune condizioni locali; in particolare richiediamo che gli estremi dell’edge siano vicini di primo grado del nodo su cui vogliamo calcolare la forza virtuale esercitata. Conoscendo la sola posizione dei vici- ni ` e possibile determinare direzione e verso della forza virtuale. Un simile approccio fa si che, una volta creata la rete, il movimento di alcuni agenti (interni) sia vincolato dalla posizione degli agenti esterni (i quali hanno al- meno una direzione di moto non vincolata).

Per ogni agente ` e previsto un termine di controllo proporzionale sulla po- sizione del baricentro della formazione che utilizza algoritmi di consensus per ottenere il segnale di feedback.

Restringiamo il problema della formazione ad un’area di contenimento cir- colare, di dato centro e raggio. Ogni agente ` e in grado di determinare, dalle connessioni presenti e dalla posizione dei vicini, se ` e un nodo interno o es- terno. I robot esterni sono responsabili di portarsi sul perimetro della cir- conferenza desiderata con l’utilizzo di forze di espansione virtuali dirette dal baricentro della formazione all’agente. Per uniformare la densit` a della dis- tribuzione facciamo agire sugli agenti pi` u interni forze virtuali dirette verso il baricentro dei vicini di primo grado.

Al controllo proposto sono stati aggiunti termini di obstacle avoidance. La

4

validit` a dell’approccio ` e dimostrata in simulazione.

L’argormento oggetto di tesi non ` e stato trattato in nessun corso previsto

dal mio piano di studi. Durante lo svolgimento della tesi ho avuto la oppor-

tunit` a di partecipare al corso breve tenuto dalla Professoressa Naomi Ehrich

Leonard, Princeton University, presso il Dipartimento di Sistemi Elettrici e

Automazione, Universit` a di Pisa (18-20 Aprile 2007) e al corso per dottoran-

di dal titolo ’Networked Embedded Control: Controllo e Stima Coordinata

Multiagente’, tenutosi a Bertinoro (FC), 12-14 Luglio 2007.

Capitolo 1

Classificazione dei Sistemi Multiagente

Sulla base del criterio di classificazione originarimente proposto da Dudek, [6], possiamo analizzare le caratteristiche di un sistema multiagente secondo due dimensioni (fig. 1.1): una dimensione di coordinazione e una dimensione di sistema; la prima rigurda il tipo di coordinazione emergente mentre la seconda riguarda le caratteristiche del sistema che influenzano lo sviluppo del team (come la comunicazione, la composizione del team, l’architettura e il numero di agenti).

Figura 1.1: Dimensioni di Classificazione

Le caratteristiche che influenzano la dimensione di coordinazione possono essere ulteriormente suddivise secondo la struttura gerarchica di figura 1.2.

Di seguito saranno analizzati e descritti i vari livelli della classificazione utilizzata.

1.1 Cooperazione

Il termine comportamento collettivo ` e riferito ad un sistema composto da almeno due agenti. Il comportamento cooperativo ` e una sottoclasse del

5

1.1#1 6

Figura 1.2: Dudek Taxonomy

comportamento collettivo ed ` e caratterizzato dalla cooperazione tra agenti.

In letteratura troviamo diverse definizioni di cooperazione, tra cui:

• utilizzo di comportamenti cooperativi diretti al raggiungimento di un obiettivo o di un interesse collettivo;

• forma di interazione generalmente basata sulla comunicazione;

• unirsi per fare qualcosa che crei risultati progressivi, tra i quali il miglioramento delle performance o il risparmio di energia.

In base a queste definizioni un sistema multirobot pu` o essere studiato e classificato secondo tre aspetti:

• task: lo studio della suddivisione e allocazione dei compiti o di altri aspetti legati all’intelligenza artificiale distribuita (DAI), come l’ap- prendimento e la razionalit` a;

• meccanismo di cooperazione: studio dei requisiti di informazione e risorse nonch` e di corretteza e robustezza del sistema;

• system performance: studio di possibili misure quantitative di collabo-

razione, come ad esempio il miglioramento del tempo di esecuzione di

un task.

1.2#1 7

Un comportamento cooperativo pu` o essere quindi definito come segue:

Cooperazione: Dato uno specifico task, un sistema mul- tirobot mostra un comportamento cooperativo se, grazie ad un meccanismo di cooperazione sottostante, si verifica un aumento dell’utilit` a totale del sistema.

1.2 Conoscenza

Questo livello concerne il grado di conoscenza di ogni agente riguardo agli altri membri: gli Aware Robots hanno una qualche conoscenza dell’attivit` a degli altri membri mentre gli Unaware Robots, in genere molto pi` u semplici, agiscono senza nessuna conoscenza dello stato degli altri membri del sistema.

La conoscenza dell’attivit` a degli altri non implica necessariamente la comu- nicazione, infatti pu` o essere dedotta da modelli rappresentativi, noti ad ogni agente, che permettono di inferire lo stato e/o le intenzioni degli altri osser- vando le caratteristiche dell’ambiente circostante.

La conoscenza delle intenzioni, azioni, capacit` a e dello stato degli altri com- ponenti pu` o favorire la cooperazione e diminuire la necessit` a di comuni- cazione. Questo aspetto dei sistemi multirobot ` e stato studiato nel cam- po del trasporto cooperativo di oggetti per la realizzazione della cosiddetta

’cooperazione senza comunicazione’; attraverso l’utilizzo degli oggetti come

mezzo di comunicazione i robot sono in grado di modellarsi a vicenda e di

coordinarsi per svolgere il trasporto. La modellazione del moto degli altri

agenti ` e spesso necessaria per il coordinamento motorio.

1.3#1 8

1.3 Coordinazione

Il terzo livello riguarda il meccanismo utilizzato per la coordinazione; la coordinazione ` e una forma di cooperazione in cui le azioni svolte da ogni agente tengono conto delle azioni svolte dagli altri membri in modo tale che il lavoro complessivo sia una coerente operazione di alto livello.

Un protocollo di coordinazione ` e definito come un insieme di regole che i robots devono seguire durante l’interazione reciproca. Una coordinazione forte ` e basata su protocolli di coordinazione predefiniti viceversa, se ci` o non accade, abbiamo una coordinazione debole.

Dato che l’effettivo utilizzo di protocolli di coordinazione tra agenti fisici pu` o risultare difficile, gli approcci basati sulla coordinazione forte sono utilizzati soprattutto in task di formazione. Di seguito saranno presentati alcune delle tecniche utilizzate per la coordinazione di pi` u agenti.

Lo studio delle tecniche di coordinazione ha costituito gran parte del lavoro di tesi. Nonostante la teoria del controllo di sistemi multiagenti sia molto recente (anni ’80) e attualmente non completa, tante sono le ricerche sulla coordinazione e formazione di pi` u velivoli e tanti sono gli approcci utilizzati.

Senza la pretesa di essere esaustivi, in questo paragrafo si esaminano alcuni degli approcci generalmente utilizzati per coordinare sciami o gruppi di ve- livoli. E’ necessario precisare la differenza tra sciami (molti agenti) e gruppi (pochi agenti), in quanto la dimensione del gruppo condiziona fortemente le tecniche utilizzabili. In gruppi di pochi velivoli (al massimo 5) ` e possibile l’ottimizzazione di traiettorie mediante l’utilizzo di approcci centralizzati che, chiaramente, non possono essere applicati a sciami di velivoli per l’enorme costo computazionale che comporterebbe un tale controllo. Per gli sciami sono state proposte nuove tecniche che, seppure non ottime, possono essere utilizzate per formazioni di dimensione arbitraria. Esistono inoltre tecniche di livello intermedio che, pur non richiedendo un approccio centralizzato, si basano su modelli di formazione la cui dimensione e complessit` a dipende dal numero di agenti (un esempio tipico ` e quello dell’utilizzo di strutture virtu- ali che, specificado i vincoli sulla posizione relativa di agenti vicini, hanno un’inevitabile crescita sulla complessit` a di modellazione all’aumentare del numero di agenti).

Gli approcci pi` u comunemente utilizzati, che descriveremo brevemente nei seguenti paragrafi, sono stati suddivisi nelle seguenti categorie:

• Leader-Follower

• Artificial Potential Functions

1.3#1 9

• Virtual Structures

• Behavior Based

• Consensus Based

• Abstraction Based

• NSB Approach

1.3.1 Leader-Follower [16] [17] [18] [20]

Le tecniche di leader-follower suppongono la presenza di un leader fisico di cui ` e definita la traiettoria. Gli ingressi di controllo degli altri membri sono calcolati direttamente in funzione della distanza dal robot leader o, indiret- tamente, in funzione della distanza da altri agenti. Generalmente si basano su tecniche geometriche e si estendono facilmente a sistemi con vincoli sulla velocit` a. Lo svantaggio principale di questo tipo di sistemi ` e la scarsa ro- bustezza: senza il leader il sistema non ` e in grado di svolgere il task. Nella sua formulazione originaria questo tipo di approccio non prevedeva inoltre al- cun feedback dal gruppo verso il leader, causando problemi alla contollabilit` a e alla stabilit` a dell’intero sistema. L’analisi di stabilit` a delle configurazioni pu` o effettuarsi con le tecniche utilizzate per lo studio di sistemi interconnes- si.

Negli articoli [16] e [17] sono presentati due tipi di controllo per i veicoli followers. In particolare ad ogni veicolo sono assegnati uno o due veicoli leader; il compito del controllo ` e mantenere determinate variabili di stato al set-point impostato. Le variabili di stato dipendono dal controllo utilizzato e sono misure relative.

La formazione pu` o essere quindi specificata assegnando ad ogni robot i nec- essari leader e utilizzando un leader fisico per guidarla. E’ possibile passare da una formazione ad un’altra cambiando il tipo di controllo e i leaders degli agenti. Le formazioni che si ottengono possono in un certo senso assimilarsi a quelle delle strutture virtuali, ma la presenza di un leader fisico lo fa collo- care in questa categoria.

L’articolo [18] studia la stabilit` a della cinematica dell’errore di formazione rispetto all’ingresso del leader che non dipende dagli altri agenti ed ` e un comando in velocit` a. Nello stesso articolo sono studiati i possibili benefici derivanti da eventuali connessioni di feedforward: il leader pu` o cos`ı regolare il proprio moto in funzione dello stato di alcuni altri agenti. Problemi di

’string stability’ di sistemi interconnessi sono invece trattati in [20].

1.3#1 10

1.3.2 Artificial Potential Functions [21] [22] [23] [24]

[25] [26] [27] [28]

Funzioni di potenziale artificiale sono comunemente utilizzate per la nav- igazione di robot autonomi in ambienti sconosciuti. In generale una funzione potenziale ` e composta da un termine di tipo attrattivo verso un target e un termine di tipo repulsivo verso un ostacolo. Un opportuna combinazione (spesso lineare) di questi due termini permette la generazione di ingressi di controllo che guidano il robot verso il target evitando gli ostacoli.

E’ possibile coordinare gruppi di velivoli utilizzando funzioni potenziali con minimi nello stato desiderato; in questo particolare contesto chiamiamo stato desiderato l’insieme delle distanze relative tra velivoli vicini. Dal gradiente di queste funzioni possiamo ricavare il controllo da applicare per raggiungere una data configurazione (in genere delle dimensioni di una forza).

E’ possibile tenere conto delle limitate capacit` a di sensing imponendo costante la funzione potenziale (e quindi nullo il suo gradiente) oltre prefissate dis- tanze tra robot; se la distanza relativa tra due velivoli ` e maggiore del raggio di sensing il potenziale artificiale sar` a nullo.

La configurazione finale non ` e unica e non prevede alcun ordinamento dei velivoli, che possono invece essere scambiati l’uno con l’altro. Il controllo ` e distribuito, non sono previsti leader.

Queste leggi di controllo sono generalmente spazialmente distribuite (dipen- dono solo dalla posizione relativa tra robot vicini) e sono invarianti a traslazioni e rotazioni. Per svolgere alcuni task non spazialmente distribuiti possono essere utilizzati uno o pi` u leader virtuali che guidano la formazione in parti- colari posizioni e/o configurazioni.

Lo spostamento della formazione avviene in direzione del gradiente di fun- zioni note a priori o deducibili dalle caratteristiche dell’ambiente (tecniche di gradient climbing).

A differenza di altri approcci l’utilizzo di funzioni potenziali pu` o prevedere lo studio di stabilit` a con funzioni di Lyapunov derivanti direttamente dalle funzioni potenziale.

1.3.3 Virtual Structures [13] [15] [19]

Per struttura virtuale di un insieme di punti nello spazio si intende l’in-

sieme di vincoli geometrici che devono essere imposti sulle distanze relative

tra agenti vicini per rendere la formazione rigida e unica. In questo contesto

la struttura geometrica locale dei vincoli deve essere nota ad ogni agente o

le traiettorie devono essere calcolate in modo centralizzato nel rispetto dei

vincoli. La pesantezza computazionale di questo secondo approccio rende il

1.3#1 11

metodo adatto solo per piccole formazioni.

Funzioni di potenziale artificiale possono essere utilizzate per ottenere con- figurazioni finali uniche e predicibili utilizzandole come Structural Potential Functions. In questo caso ` e necessario imporre una struttura specifica al grafo associato alla formazione dei veicoli e utilizzare funzioni potenziale per mantenere le desiderate distanze dai vicini [13].

La gestione del movimento della formazione avviene generalmente inserendo un leader virtuale e costruendo nuovi vincoli strutturali tra virtual leader e velivoli. Con il movimento del virtual leader si ` e cos`ı in grado di condizionare il movimento della formazione.

Negli articoli [14] e [15] i vincoli strutturali sono rispettati minimizzando una opportuna funzione costruita ad-hoc per la formazione desiderata. Utilizzan- do questo metodo ` e possibile ricavare la traiettoria di n virtual leader (uno per ogni agente) a partire dalla traiettoria del leader virtuale semplicemente minimizzando la funzione dei vincoli. Ogni agente ` e in grado di determinare la traiettoria del proprio virtual leader misurando la distanza tra i vicini su cui sono imposti vincoli strutturali e il virtual leader. In questo modo il problema del controllo di moto vincolato ` e stato risolto con il problema della stabilizzazione di un unico sistema che dipende sia dalla dinamica dei veicoli sia dalla struttura desiderata.

Formazioni rigide richiedono che siano rispettate contemporaneamente le equazioni cinematiche dei singoli agenti e i vincoli di distanza tra vicini: non tutte le formazioni possono essere realizzate. L’articolo [19] si focalizza il problema della realizzabilit` a delle formazioni: date le equazioni cinematiche di molti agenti e i vincoli di distanza tra veicoli, determinare quando esistono traiettorie che mantengono i vincoli.

Le formazioni rigide sono particolarmente indicate per task in cui pi` u agenti devono trasportare o spostare un unico oggetto in modo coordinato.

1.3.4 Behavior Based [29] [30] [32] [31] [34]

L’utilizzo di tecniche di Behavior Based Robotics permette l’implemen-

tazione di tecniche di coordinazione anche su robot di limitate capacit` a e

garantisce reazioni tempestive ai cambiamenti esterni. Il primo passo con-

siste nel suddividere il task in molti task pi` u semplici, al limite composti da

un unica azione. Dopodich` e sviluppiamo una logica per la commutazione

dei task basata sullo stato del velivolo e sulle caratteristiche dell’ambiente

esterno (in cui ` e compreso lo stato di eventuali agenti vicini). A titolo di

esempio l’articolo [29] utilizza il seguente insieme di azioni per svolgere un

task di formazione:

1.3#1 12

. move to goal

. avoid static obstacles . avoid robots

. maintain formation

La Swarm Intelligence si occupa di individuare le singole azioni ottimizzando la logica e i parametri che ne regolano l’esecuzione, [34] [31] [33]. L’obiettivo

`

e creare comportamenti complessi, spesso impossibili per un singolo agente, dalla coordinazione di semplici azioni. Queste tecniche funzionano bene so- lamente con un grande numero di agenti (in genere almeno 100); le scelte progettuali porranno un tradeoff tra semplicit` a di realizzazione del singolo e numero di unit` a necessarie.

Generalmente non ci sono tecniche formali e precise che garantiscono la con- vergenza di questi metodi ma ` e possibile studiarne l’evoluzione attraverso simulazioni e modelli probabilistici. Esistono due principali metodi di analisi:

il modello microscopico e il modello macroscopico. Il modello microscopico ` e basato sulle iterazioni tra agenti e tra agenti e l’ambiente: risolvendo o simu- lando un sistema composto da tanti agenti permette l’analisi e la verifica del sistema. Il modello macroscopico non considera le iterazioni e le traiettorie di ogni singolo agente, ma le modella tramite eventi socastici con probabilit` a determinata da considerazioni geometriche. Simulando in parallelo eventi stocastici per ogni singolo agente ` e possibile studiare il comportamento col- lettivo dello sciame.

1.3.5 Consensus Based [35] [37] [38] [39] [36] [40]

I problemi di coordinazione multiagente che utilizzano le tecniche del con- sensus sono il rendezvous e il flocking.

Un problema di rendezvous richiede agli agenti di convergere in un unico punto ed eventualmente al solito istante di tempo.

Nello stato di flocking gli agenti assumono la stessa velocit` a, in modulo e di- rezione. E’ preferibile inserire dei termini di attrazione/repulsione tra agenti per garantire la coesione del gruppo ed evitare collisioni.

Utilizzando algoritmi di consensus decentralizzati ` e infatti possibile far con- vergere ad uno stesso valore, e sotto opportune ipotesi di connesione del grafo di comunicazione, le variabili controllate di tutti gli agenti (punto di rendezvous o vettore velocit` a).

L’analisi di stabilit` a di queste tecniche si basa sulle propriet` a della matrice

1.3#1 13

Laplaciana costruita in funzione connessioni tra gli agenti.

Come sar` a dettagliatamente descritto nei seguenti paragrafi l’algoritmo di consensus pu` o essere applicato per stimare variabili globali altrimenti inac- cessibili ad un singolo agente (in particolare la posizione del baricentro ed eventuali momenti di ordine superiore), [9].

1.3.6 Abstraction Based [9] [11]

Una delle tecniche basate sull’astrazione della formazione sar` a ampia- mente trattata nei seguenti capitoli. L’obiettivo di queste tecniche ` e quello di individuare un insieme di variabili con cui descrivere la formazione. Il numero di abstract variables non deve dipendere dal numero di agenti e diminuisce all’aumentare del grado di astrazione richiesto. L’approccio in [9] utilizza i momenti d’inerzia del primo e secondo ordine come abstract variables per le formazioni.

In genere con le abstract variable si descrive una famiglia di formazioni: il numero di variabili necessarie per individuare un unica formazione sarebbe troppo elevato e renderebbe il metodo poco conveniente o addirittura inuti- lizzabile.

1.3.7 NSB Approach [42]

Gli approcci basati su questatecnica si rifanno alla teoria dei manipola-

tori ridondandi in cui i gradi di libert` a del robot sono maggiori rispetto a

quelli necessari per lo svolgimento del task (come il posizionamento dell’end-

effector). E’ possibile gerarchizzare i sub-task proiettando nel nullo del task

a priorit` a maggiore l’ingresso fornito dal task a priorit` a minore. In problemi

di formazione ` e possibile definire un task di obstacle-avoidance di pi` u alto

livello, uno di formation-keeping, uno di tracking e cos via in dipendenza

degli obiettivi. Tecniche di quest tipo mirano per` o al controllo del Platoon

e non del singolo robot, nel senso che sono spesso necessarie informazioni

globali sullo stato del sistema.

1.4#1 14

1.4 Organizzazione

Il quarto ed ultimo livello della piramide concerne il modo in cui il pro- cesso decisionale ` e realizzato.

Nella progettazione di un sistema multirobot la scelta dell’organizzazione ` e fondamentale. Possiamo avere strutture centralizzate caratterizzate da un singolo agente (o sistema di gestione esterno) adibito al controllo dell’intero gruppo e strutture decentralizzate che non prevedono la presenza di un unico agente di controllo. La forma di organizzazione decentralizzata pu` o essere realizzata sia mediante una struttura gerarchica (debolmente centralizzata), in cui sono presenti pi` u agenti con compiti di controllo, o completamente distribuita, in cui tutti gli agenti sono uguali rispetto al controllo.

Il comportamento di un sistema distribuito ` e spesso descritto usando termini come ’emergence’ o ’self-organization’.

L’utilizzo di controlli centralizzati permette l’ottimizzazione delle leggi di controllo, la pianificazione sicura delle traiettorie e lo svolgimento efficiente del task; ci sono comunque degli svantaggi insiti nell’adozione di architetture centralizzate, tra cui la complessit` a computazionale (in genere crescente al crescere del numero dei robots), la difficolt` a di implementazione, la mancanza di flessibilit` a e la scarsa robustezza che mostrano. Controlli completamente centralizzati implicano inoltre la perfetta conoscenza dell’ambiente di lavoro.

I controlli decentralizzati offrono robustezza rispetto ai guasti, scalabilit` a del sistema, affidabilit` a e il vantaggio del parallelismo. I sistemi distribuiti si ispirano spesso ai sistemi biologici e fisici che, mediante l’utilizzo di semplici regole, riescono a mostrare comportamenti complessi che vanno al di l` a della somma delle capacit` a dei singoli agenti. Non sempre per` o i sistemi distribuiti sono da preferirsi ai sistemi centralizzati, ad esempio nel caso in cui si ab- biano pochi agenti atti a svolgere un compito semplice. In genere vengono sviluppati sistemi ’ibridi’: un sistema centralizzato spesso non lo ` e mai com- pletamente e un sistema distribuito in genere prevede un pianificatore di alto livello.

1.5 Comunicazione

La rete di comunicazione di un sistema multiagente pu` o essere descritta dai seguenti parametri:

- Raggio di comunicazione: il raggio di comunicazione individua la

distanza massima consentita a cui due agenti sono in grado di comu-

nicare; questo parametro ` e dettato dalle limitazioni dell’hardware di

comunicazione e dipende dal mezzo di propagazione;

1.6#1 15

- Banda di comunicazione: la banda determina la quantit` a di infor- mazioni che possono essere scambiate su uno stesso canale; una ban- da limitata pu` o ridurre l’efficienza della cooperazione e rendere alcuni algoritmi non implementabili;

- Topologia di comunicazione: la topologia determina lo schema di scambio di messaggi tra agenti; in particolare possiamo individuare una modalit` a broadcast, in cui tutti possono comunicare con tutti, una modalit` a address based, in cui i messaggi devono avere un preciso destinatario, e una modalit` a graph based in cui le connessioni presenti sono definite da un grafo di comunicazione.

Questi parametri sono riferiti ad un meccanismo di comunicazione diretto, in cui assumiamo che ogni agente disponga di un dispositivo hardware dedicato;

un meccanismo di comunicazione viene invece definito indiretto quando lo scambio di messaggi avviene modificando lo spazio di lavoro. Questo ultimo meccanismo ` e definito anche stigmergy, termine coniato dal biologo P. Grass` e che significa incentivare il lavoro dall’effetto del lavoro gi` a svolto. In questo contesto il termine ` e utilizzato per indicare le comunicazioni che avvengono attraverso la modifica dell’ambiente.

1.6 Architettura

L’architettura di un sistema multirobot dipende dalla risposta del team alla dinamica dell’ambiente in cui opera. Possiamo individuare due tipi di architettura: una deliberativa e una reattiva.

In un architettura deliberativa il sistema reagisce ai cambiamenti dell’am- biente esterno utilizzando una strategia di riorganizzazione del lavoro dei membri del gruppo cos`ı da utilizzare tutte le risorse disponibili per raggiun- gere l’obiettivo globale.

In un architettura reattiva ogni componente segue un approccio individuale alla riorganizzazione del proprio lavoro cos`ı da raggiungere l’obiettivo che gli era stato assegnato.

1.7 Grandezza del Team

La grandezza del team ` e un fattore determinante nella progettazione di

sistemi cooperanti. Molte delle tecniche utilizzate per coordinare gruppi

di pochi agenti potrebbero non essere implementabili in sciami di grandi

dimensioni cos`ı come tecniche che presuppongono un numero elevato di agenti

1.8#1 16

potrebbero non convergere al goal desiderato. Quest’ultima considerazione ` e riferita ai sistemi autorganizzanti che presuppongono l’uso di meccanismi di autocatalisi che, per poter funzionare, richiedono la presenza di molti agenti.

1.8 Composizione del Team

Si definisce omogeneo un sistema in cui i robots hanno le stesse capacit` a;

al contrario si definisce eterogeneo un sistema in cui l’hardware e/o il con- trollo possono essere diversi da agente a agente. A livello di robot possiamo definire il parametro di task coverage come capacit` a di svolgere un dato task.

Questo parametro ` e un indice della necessit` a di cooperazione: quando il task

coverage ` e alto la richiesta di cooperazione ` e bassa perch` e ogni agente ` e in

grado di svolgerlo autonomamente. I membri di un team omogeneo hanno

generalmente un alto valore di task coverage che decresce mano a mano che

l’eterogeneit` a del sistema aumenta; il limite si raggiunge quando solo un com-

ponente ` e in grado di svolgere un determinato task. In genere l’eterogeneit` a

del sistema implica una maggiore complessit` a nell’allocazione dei task e nel-

la modellazione individuale degli altri membri del gruppo. L’allocazione dei

task tra i membri ` e necessaria anche in un sistema omogeneo e pu` o emergere

dinamicamente a run-time.

Capitolo 2

Stima e Controllo Decentralizzato

L’approccio utilizzato per controllare la formazione di grandi sciami di velivoli si basa sulla ricerca di una sufficiente astrazione della forma e della posizione dello sciame, una stima distribuita di variabili globali e un controllo di tipo gradientale.

Pi` u precisamente sfruttiamo le propriet` a di convergenza degli algoritmi di consensus per stimare quantit` a globali, altrimenti inaccessibili ai singoli ve- livoli, che descrivono la formazione. A tal fine ogni agente esegue l’algoritmo di consensus utilizzando dati relativi al proprio stato e allo stato dei soli vicini; l’algoritmo utilizzato in questo contesto converge alla media dei valori di input di ogni agente. I valori di input utilizzati da ogni velivolo sono la propria posizione e sue funzioni polinomiali. La media di questi valori, rag- giunta con il consensus, rappresenta quantit` a globali che sono un astrazione geometrica di forma e posizione dello sciame. Ad esempio la posizione del- lo sciame ` e individuata nella posizione del baricentro, calcolato come media delle posizioni dei singoli; inserendo come input il quadrato della velocit` a otteniamo quantit` a da cui possiamo risalire all’estensione della formazione rispetto al baricentro.

Il controllore di formazione di ogni velivolo pu` o utilizzare queste stime in retroazione per stabilizzare i velivoli su formazioni che soddisfino le statis- tiche desiderate. Le statistiche desiderate possono quindi essere ottimizzate in funzione del task assegnato e dell’ambiente in cui si opera. Nei paragrafi seguenti si introducono le statistiche di formazione utilizzate e si dimostra la convergenza degli algoritmi di consensus.

Trattandosi di sistemi non lineari non vale il principio di separazione; ` e quin- di necessario dimostrare la convergenza del sistema retroazionato controllo e stimatore. Una trattazione formale della tecnica utilizzata sar` a data nel

17

18

paragrafo 2.3.

Alcuni degli argomenti dei seguenti paragrafi sono stati tratti dagli articoli

[9] e [11] per le statistiche di formazione e il controllo, e [10] per gli algoritmi

di consensus.

2.1#1 19

2.1 Statistiche di Formazione

La formazione geometrica, costituita da un insieme di punti, ` e determi- nata dalla posizione assoluta di tutti gli agenti. Con un controllo centraliz- zato sarebbe possibile ottenere una qualsiasi formazione assegnando ad ogni agente una posizione nello spazio. Questo tipo di approccio richiederebbe la programmazione di ogni velivolo in modo diverso e un carico computazionale non scalabile con il numero di agenti.

L’utilizzo di funzioni potenziale di attrazione/repulsione tra robot permette la determinazione della dimensione massima dello sciame in dipendenza del numero di agenti. Un simile approccio ne garantisce la coesione ma non ne permette il completo controllo della forma. L’utilizzo di strutture virtuali permette il controllo della formazione ma la geometria deve essere specifica- ta con tecniche che non sono in genere scalabili con il numero di robot.

Considerando sciami di grandi dimensioni specificare l’esatta posizione di og- ni agente non ` e in genere necessario ed ` e possibile descrivere la formazione con un insieme di statistiche di formazione che formano una base per lo spazio di tutte le formazioni. Ad ogni distribuzione spaziale degli agenti ` e sempre possibile associare un numero di statistiche sufficienti a distinguer- la da ogni altra formazione. Utilizzando un numero limitato di statistiche specifichiamo una famiglia di formazioni con caratteristiche rispondenti ai requisiti delle statistiche scelte.

Le statistiche di ordine pi` u basso catturano le propriet` a essenziali della for- mazione fornendone un utile astrazione.

I momenti d’inerzia della formazione sono un esempio di statistiche di for- mazione con cui ` e possibile astrarre la geometria dello sciame; in particolare i momenti d’inerzia del primo e secondo ordine sono i momenti di ordine pi` u basso sufficienti a descriverne posizione, orientazione e forma.

Indichiamo lo spazio delle configurazioni Q di uno sciame di robot con Q = G ×S, dove S `e lo shape space della formazione e G `e il Lie Group SE(m) che rappresenta lo spazio delle posizioni e orientazioni di una data forma dello sciame nel piano (m = 2) o nello spazio (m = 3).

Le variabili q ∈ Q che specificano la configurazione possono essere quin- di suddivise come q = (g, s), dove g sono group variables e s sono shape variables che rappresentano una descrizione intrinseca del gruppo. Pi` u pre- cisamente data g ∈ SE(m), le variabili di forma s rappresentano posizione e orientazione di ogni robot relativa al riferimento g, e pu` o essere espressa come (s ₁ , s ₂ , ..., s _n ) per n robots.

Si assume inoltre che i robot siano intercambiabili e anonimi, esiste quindi una

simmetria di permutazione del gruppo; ogni permutazione degli elementi in

s rappresenta una stessa forma. Rappresentiamo inoltre i robots come punti

2.1#1 20

(cio` e molto piccoli rispetto all’estensione della formazione), quindi s _i ∈ < ^m . I momenti d’inerzia della formazione sono in genere calcolati considerando la massa di ogni agente; in questo contesto siamo interessati alle caratteristiche geometriche della formazione e assumiamo quindi tutti i robot di massa uni- taria. Indicando con p _i = [p _ix p _iy p _iz ] ^T la posizione del robot i nel piano, i momenti d’inerzia sono:

M _abc = 1 n

n

X

i=1

p ^a _ix p ^b _iy p ^c _iz (2.1) con a, b, c ≥ 0. L’ordine del momento ` e dato da a + b + c; il numero dei momenti di un dato ordine dipende quindi da m e non da n.

La gestione della formazione mediante statistiche prevede l’utilizzo di mo- menti di basso ordine che specificano una famiglia di formazioni: se sono specificati l vincoli di momento su n robot in uno spazio m-dimensionale, lo spazio delle formazioni che soddisfano i vincoli ` e di dimensioni (mn − l).

Dato che i momenti d’inerzia del primo e del secondo ordine sono sufficienti per specificare posizione, orientazione e forma dello sciame consideriamo le caratteristiche geometriche che possono essere specificate con queste statis- tiche.

Gli m momenti del primo ordine specificano il centro di massa della for- mazione. Dagli ^m(m+1) ₂ momenti del secondo ordine possiamo derivare ^m(m−1) ₂ variabili che descrivono l’orientazione degli assi principali d’inerzia dello sci- ame (ortogonali tra loro) e m abstract variables che specificano l’elongazione lungo gli assi principali.

Idealmente sarebbe auspicabile poter definire un ellissoide di contenimento di dimensioni indipendenti dal numero di robot e con semiassi di lunghezza pro- porzionale all’elongazione individuata dalle abstract variables, come mostra la figura 2.1.

Con i momenti d’inerzia del primo e del secondo ordine non ` e per` o pos- sibile ottenere una simile astrazione; possiamo comunque fornire delle inter- pretazioni geometriche che definiscono l’area di contenimento dei robot sulla base delle statistiche definite.

Per un arbitraria configurazione q ∈ Q, le group variables della configurazione sono definite come g = (R, µ) ∈ G = SE(3). Dove

µ = 1 n

n

X

i=1

q _i ∈ < ² (2.2)

rappresenta il centro di massa della formazione, ovvero la parte traslazionale

della trasformazione necessaria per passare dalle coordinate del sistema di

2.1#1 21

Figura 2.1: Configurazione dello sciame prima e dopo l’applicazione di un gradino sulla posizione del centro di massa

riferimento base alle coordinate del sistema di riferimento g. In questo riferimento le coordinate dei robot divengono

r _i = [x _ri , y _ri ] ^T = R ^T (q _i − µ), i = 1, ....n (2.3) L’equazione utilizzata per definire la parte rotazionale R ∈ SO(2) ` e la seguente

n

X

i=1

x _ri y _ri = 0 (2.4)

che parametrizzata con θ ∈ (−π/2, π/2) fornisce l’unica soluzione θ = 1

2 atan2(

n

X

i=1

(q _i − µ) ^T E ₁ (q _i − µ),

n

X

i=1

(q _i − µ) ^T E ₂ (q _i − µ)) (2.5) con

E 1 =  0 1 1 0



, E 2 =  1 0 0 −1



(2.6) la matrice R ∈ SO(2) pu` o scriversi come

R =  cos θ − sin θ sin θ cos θ



, RR ^T = R ^T R = I (2.7)

Definiamo delle nuove abstract variables espresse nel riferimento g, invarianti

2.1#1 22

quindi a traslazione e rotazione del centro di massa, come segue:

a ₁ = _n ¹ P n i=1 x ² _ri a 2 = _n ¹ P n

i=1 y _ri ²

(2.8)

E’ stato necessario definire queste nuove variabili per effettuare delle con- siderazioni geometriche riguardo all’area occupata dai robot. Per motivi che saranno chiariti con la descrizione dello stimatore decentralizzato non ` e possi- bile utilzzare come riferimento di controllo direttamente le abstract variables relative.

Considerando una pianificazione delle statistiche desiderate in variabili rel- ative (a ₁ , a ₂ ), di cui se ne conosce l’interpretazione geometrica, ` e neces- sario ricavare le espressioni dei momenti d’inerzia del secondo ordine che le realizzano. A tal fine imponiamo il sistema di equazioni nelle incognite (M _x

, M _y

, M _xy ) e con parametri (µ, θ, a ₁ , a ₂ ).

x _ri = cos θ(q _ix − µ _x ) + sin θ(q _iy − µ _y )

y _ri = − sin θ(q _ix − µ _x ) + cos θ(q _iy − µ _y ) (2.9)

1 n

P n

i=1 x ² _ri = a 1 1

n

P n

i=1 y _ri ² = a ₂

1 n

P n

i=1 x _ri y _ri = 0

(2.10)

M _x

= _n ¹ P n i=1 q ² _ix M _y

= _n ¹ P n

i=1 q ² _iy M _xy = ¹ _n P n

i=1 q _ix q _iy

(2.11)

sostituendo la nella e utilizzando la otteniamo il seguente sistema:

a ₁ = M _x

cos ² θ − µ ² _x cos ² θ+

M _y

sin ² θ − µ ² _y sin ² θ+

2 cos θ sin θM _xy − 2 cos θ sin θµ _x µ _y (2.12)

2.1#1 23

a ₂ = M _x

sin ² θ − µ ² _x sin ² θ+

M _y

cos ² θ − µ ² _y cos ² θ−

2 cos θ sin θM _xy + 2 cos θ sin θµ _x µ _y (2.13)

0 = −M _x

sin θ cos θ + µ ² _x sin θ cos θ+

M _y

sin θ cos θ − µ ² _y sin θ cos θ+

cos ² θM _xy − cos ² θµ _x µ _y − sin ² θM _xy + sin ² θµ _x µ _y (2.14) risolvendo il sistema otteniamo

M _x

= ¹ ₂ (2µ ² _x + a ₁ + a ₂ + (a ₁ − a ₂ ) cos 2θ) M _y

= ¹ ₂ (2µ ² _y + a 1 + a 2 − (a 1 − a 2 ) cos 2θ)

M _xy = (µ _x µ _y + (a ₁ − a ₂ ) sin θ cos θ)

(2.15)

Se sono noti i momenti d’inerzia ` e possibile ricavare le abstract variables relative come segue

θ = ¹ ₂ arctan 2(2n(M _xy − µ _x µ _y ), n(M _x

− µ ² _x − M _y

+ µ ² _y )) a 1 = (M _x

− µ ² _x ) cos ² θ + (M _y

− µ ² _y ) sin ² θ + (−µ x µ y + M xy ) sin ² θ a ₂ = (M _y

− µ ² _y ) cos ² θ + (M _x

− µ ² _x ) sin ² θ + (−µ _x µ _y − M _xy ) sin ² θ

(2.16)

l’espressione per θ ` e stata ricavata espandendo la sommatoria dell’equazione 2.5 e sostituendo l’espressione dei momenti.

Definiamo

Σ = _n ¹ P n

i=1 (q i − µ)(q i − µ) ^T Γ = −nT ΣT

T =  0 −1

1 0



(2.17)

dato che T ^T = T ⁻¹ = −T , le matrici Γ e nΣ hanno gli stessi autovalori.

2.1#1 24

2.1.1 Spanning Rectangle

Le variabili µ e Γ possono essere viste come il centroide e il tensore d’in- erzia del sistema di particelle q _i nel riferimento base W. Indichiamo con {M} il riferimento virtuale g = (R, µ) in {W}. Le variabili r _i sono i punti q _i espressi nel riferimento {M}. La rotazione (R) definisce quindi l’orientazione del sistema di riferimento {M} rispetto a {W} in modo tale che il tensore d’inerzia delle particelle r _i in {M} sia diagonale. Gli autovalori di tale ten- sore sono na ₁ e na ₂ e rappresentano misure della distribuzione spaziale dei robot lungo gli assi del sistema di riferimento virtuale M.

Le abstract variables definiscono un limite alla regione occupata dai robots.

Dall’equazione 2.8 segue immediatamente

|x ri | ≤ √ na 1

|y _ri | ≤ √ na ₂

(2.18)

Un insieme di n robots descritto dalla variabile astratta A = (g, a) = (R, µ, a 1 , a 2 )

`

e contenuto in un rettangolo centrato in µ e ruotato di R ∈ SO(2) nel riferi- mento base {W}. I lati del rettangolo sono dati da 2 √

na ₁ e 2 √ na ₂ .

Da notare che i lati del rettangolo e la rotazione da applicare sono espressi in funzione di abstract variables che non corrispondono ai momenti d’inerzia definiti. Le statistiche (a 1 , a 2 ) sono calcolate nel sistema di riferimento rela- tivo ed ` e quindi necessario utilizzare le equazioni 2.15 per ricavare i momenti del secondo ordine corispondenti.

La dipendenza della lunghezza dei lati del rettangolo dal numero di agen- ti non permette di separare completamente il processo di pianificazione della formazione dalla sua composizione.

Il processo di pianificazione definisce infatti la formazione fornendo le carat- teristiche geometriche necessarie allo svolgimento del task e quindi posizione, orientazione e dimensioni del rettangolo (µ, θ, l 1 , l 2 ). Da questi dati possiamo ricavare le statistiche di formazione in termini di (µ, M _x2 , M _y2 , M _xy ).

Se vogliamo far variare nel tempo il numero di agenti ` e necessario ricavare

nuovamente le espressioni dei momenti: se il numero di agenti aumenta (n) e

le statistiche vengono mantenute costanti (a ₁ , a ₂ ) il pi` u grande rettangolo di

contenimento aumenta e quindi le specifiche richieste potrebbero non essere

mantenute. Conoscendo il numero massimo di agenti possiamo ricavare il

pi` u grande rettangolo ma questo risulterebbe eccessivamente conservativo.

2.2#1 25

2.2 Consensus Estimator

Problemi di consensus sono stati originariamente affrontati dalla comu- nit` a informatica nel campo della teoria degli automi e del calcolo distribuito.

In generale in un problema di consensus si richiede che pi` u agenti spazial- mente distribuiti raggiungano uno stesso valore di uscita senza il ricorso ad un coordinatore centrale e senza l’utilizzo di comunicazioni globali. In base al valore di consenso raggiunto possiamo classificare come linear consensus quegli algoritmi decentralizzati che hanno come valore di uscita una combi- nazione lineare dei valori di ingresso di ogni agente. Una classe particolare di questo tipo di algoritmi sono gli avarage consensus in cui il valore di uscita ` e la media aritmetica dei valori di ingresso degli agenti. Se non diversamente specificato nel seguito faremo riferimerimento a questo tipo di algoritmi.

La maggior parte dei problemi di consensus studiati in letteratura sono prob- lemi di static consensus per cui il valore di consenso finale ` e la media dei valori degli stati iniziali di ogni agente; per questo tipo di problemi non ` e neces- sario prevedere una variabile di input ma basta inizializzare la variabile di stato su cui eseguiamo il consensus con i corretti valori iniziali. I problemi di dynamic consensus prevedono invece il tracking della media di valori che cambiano nel tempo; ` e necessario inserire variabili di input che influenzino in modo opportuno la convergenza dell’algoritmo. Nel seguito introduciamo la notazione utilizzata e presentiamo gli algoritmi di consensus proposti in [10].

2.2.1 Grafi di connessione

Una rete di agenti pu` o essere rappresentata in forma compatta con l’utiliz- zo di grafi. Con la costruzione di opportune matrici ` e possibile rappresentare le informazioni che un agente ha sullo stato degli altri; tali informazioni pos- sono pervenire sia tramite un canale di comunicazione fisico sia da sensori a bordo del velivolo. Un grafo G = (V, E ) ` e individuato da un insieme di n nodi V= (v 1 , v 2 , ..., v n ) e da un insieme di archi E ⊆ V × V. Un grafo si dice non-diretto se (i, j) ∈ E ⇔ (j, i) ∈ E ; diretto nel caso in cui la connessione tra due nodi sia unidirezionale, cio` e pu` o accadere che (i, j) ∈ E e (j, i) / ∈ E.

Un grafo si dice connesso se per ogni nodo i esiste un percorso che lo con- nette ad ogni altro nodo j. Le connessioni tra i nodi di un grafo possono essere rappresentate in forma compatta utilizzando la matrice di adiacenza, A ∈ < ^n×n definita come:

a _ij =  0 (i, j) / ∈ E

1 (i, j) ∈ E (2.19)

2.2#1 26

L’insieme dei vicini di un nodo i ` e indicato con N _i = {j : (i, j) ∈ E } = {j : a _ij = 1}.

La matrice di connessione rappresenta il numero di archi uscenti da un nodo,

`

e una matrice diagonale di dimensione n × n i cui elementi sono definiti come:

d _ii = X

j

a _ij (2.20)

La matrice Laplaciana ` e definita come la differenza tra la matrice di adiacenza e la matrice di connessione:

L = D − A (2.21)

Un grafo non-diretto e connesso ha una matrice Laplaciana simmetrica, semi- definita positiva, il cui spazio nullo corrisponde al consenso; per costruzione si ha infatti

L · 1 = 0 (2.22)

dove con 1 si ` e indicato il vettore colonna con tutti gli elementi pari a 1.

Questa variabile rappresenta la condizione di consenso, infatti x = α1 indica che tutte le variabili locali su cui eseguiamo il consenso, x _i , sono uguali tra loro.

2.2.2 Static Consensus

L’algoritmo di consensus statico classico ` e costituito da una variabile di stato inizializzata con i valori locali di ogni singolo agente e fatta evolvere utilizzando le informazioni disponibili ad ogni nodo. Pi` u precisamente ogni nodo trasmette ai propri vicini la sua variabile di stato ed esegue il seguente algoritmo:

˙x _i = X

j∈N

(x _j − x _i ) (2.23)

raggruppando in forma matriciale

˙x = −Lx (2.24)

Questa dinamica ` e completamente distribuita, l’informazione necessaria per l’aggiornamento della variabile di stato ` e ricavata utilizzando solamente le informazioni provenienti dai vicini (l’insieme N i ).

La matrice Laplaciana di un grafo non-diretto ` e simmetrica e semi-definita positiva: la dinamica ` e quindi stabile e deve convergere ad un valore di regime.

Sotto le stesse ipotesi vale P

j L _ij = 0; per ogni vettore x con identiche

componenti, x _i = x _j per ogni i e j, si ha Lx = 0. Ogni consenso ` e quindi una

2.2#1 27

condizione di equilibrio. E’ possibile dimostrare che per un grafo connesso tutti gli equilibri corrispondono a consensus.

Infine P

j L ij = 0 implica la seguente propriet` a di conservazione:

d dt

X

i

x _i

!

= 1 ^T ˙x = −1 ^T Lx = 0 (2.25) L’algoritmo proposto porta quindi ogni condizione iniziale ad un consenso, e conserva la somma degli stati iniziali. Questo implica che tutte le componenti del vettore x devono convergere al valore:

1

n 1 ^T x(0) = 1 n

X

i

x _i (0) (2.26)

che rappresenta la media dei valori iniziali delle variabili x _i .

2.2.3 Dynamic Consensus

Consideriamo adesso il caso in cui il consensus debba essere effettuato su variabili che cambiano nel tempo. Associamo ad ogni agente un segnale z _i (t), definiamo il vettore di tali segnali z = [z ₁ , z ₂ , ..., z _n ] e cerchiamo un algoritmo distribuito che permetta ad ogni agente di seguire la media dei termini z _i :

¯

z (t) = 1 n

X

i

z _i (t) (2.27)

Oltre al segnale d’ingresso z _i ogni agente mantiene una variabile locale x _i , che ` e una stima tempo variante del valore della media ¯ z i (t).

L’algoritmo di static consensus pu` o essere scritto come:

 ˙x = −Lx

x(0) = z ₀ (2.28)

Per ricavare una rappresentazione nel dominio della frequenza di questo algo- ritmo consideriamo il vettore delle condizioni iniziali come un ingresso. Dato che stiamo considerando un prolema di consenso statico ` e naturale consider- are come ingresso un gradino, cio` e Z (s) = ^z _s

. La trasformata di Laplace di x ` e:

X (s) = (sI + L) ⁻¹ z ₀ = s (sI + L) ⁻¹ z ₀

s = s (sI + L) ⁻¹ Z(s) (2.29) Questa equazione ` e stata ricavata assumendo uno specifico ingresso Z(s).

Tuttavia la funzione di trasferimento che suggerisce

H _xz = s(sI + L) ⁻¹ (2.30)

2.2#1 28

rappresenta un meccanismo naturale per un consensus dinamico. Consideri- amo il sistema LTI (Linear Time Invariant) associato, con ingresso z(t):

 ˙x = −Lx + ˙z

x(0) = z(0) (2.31)

La modifica apportata non comporta l’utilizzo di variabili globali, l’algoritmo proposto ` e ancora completamente distribuito.

La propriet` a di conservazione valida per l’algoritmo di consensus statico im- plica che per la dinamica dell’equazione 2.31 vale la seguente propriet` a di conservazione:

d dt

X

i

x i

!

= d dt

X

i

z i

!

(2.32) La somma istantanea delle variabili di stima x _i ` e pari alla somma istantanea delle variabili di ingresso z <sub>i</sub> ; questo ` e quello che ci dobbiamo attendere per avere un inseguimento della media delle variabili di ingresso. Formalizziamo con le seguenti proposizioni.

Proposition 1 Si consideri il sistema LTI descritto dalla seguente funzione di trasferimento MIMO

H _xz = s(sI + L) ⁻¹ (2.33)

dove L ` e la matrice Laplaciana di un grafo non-diretto e connesso.

Supponiamo che il segnale Z(s) abbia tutti i poli nella met` a sinistra del piano complesso, e abbia al massimo un polo in zero. Allora per ogni i si ha:

lim _t→∞ x _i (t) − 1 n

X

j

z _j (t)

!

= 0 (2.34)

Ogni agente raggiunge asintoticamente il consenso dinamico con errore a regime nullo.

Proof. Consideriamo il segnale di errore e(t) e la sua trasformata di Laplace E(s) = X(s) − 1

n 11 ^T Z(s) (2.35)

Questo ` e il vettore delle differenze tra le variabili di stima x i e la media istantanea dei termini z _i (t). Ricordando la funzione di trasferimento H _xz possiamo ricavare la seguente funzione di trasferimento da Z(s) a E(s):

H ez = s(sI + L) ⁻¹ − 1

n 11 ^T (2.36)

2.2#1 29

La Laplaciana di un grafo non-diretto ` e una matrice simmetrica e ammette quindi decomposizione spettrale

L = X

i

λ _i P _i (2.37)

dove i termini λ i sono gli autovalori di L e i termini P i sono le matrici di proiezione sugli autospazi mutuamente ortogonali di L.

Se il grafo G ` e connesso valgono le seguenti:

(1) λ ₁ = 0 (2) P ₁ = _n ¹ 11 ^T (3) λ _i > 0 ∀i > 1.

Riscrivendo l’equazione 2.36 utilizzando la decomposizione spettrale, le pro- priet` a appena enunciate e la propriet` a di traslazione dello spettro di una matrice sommata ad un termine del tipo sI si ha:

H _ez = 1

n 11 ^T + X

i>1

s s + λ _i P _i

!

− 1

n 11 ^T = X

i>1

s

s + λ _i P _i (2.38) Questa funzione di trasferimento ha un unico zero nell’origine e tutti i termini della sommatoria sono stabili. Per un arbitrario input Z(s), con al massimo un polo nell’origine, il teorema del valore finale implica e(t) → 0 per t → ∞.

Corollary 2 Supponiamo che C(s) sia una funzione di trasferimento stabile con inversa stabile, e k zeri nell’origine. Sia Z(s) un segnale con poli nella met` a sinistra del piano complesso e al massimo k poli in s = 0. Allora la dinamica di consenso data dalla funzione di trasferimento

H _xz = C(s) (C(s)I + L) ⁻¹ (2.39) segue la media di consenso sull’ingresso Z(s) con errore a regime nullo.

La Proposizione 1 garantisce il consenso su ogni segnale che ha un valore di regime (al massimo un polo in s = 0). Il Corollario 2 ` e una generalizzazione che, grazie all’aggiunta di un opportuno filtro C(s), garantisce il consenso dinamico su segnali pi` u generali che hanno un limite di crescita polinomiale.

Per esempio, veicoli equipaggiati con accelerometri possono raggiungere il

consenso dinamico sulla loro posizione (la cui media rappresenta il baricen-

tro) con errore a regime nullo per ingressi a rampa. Il paragrafo seguente

introduce un algoritmo con queste propriet` a.

2.2#1 30

Type II Consensus

L’algoritmo di consensus che verr` a presentato ` e stato chiamato di Tipo II in analogia con la nomenclatura utilizzata per i sistemi lineari. Un sistema lineare di Tipo II ha una funzione di trasferimento in ciclo aperto con due poli nell’origine ed il sistema in ciclo chiuso ha errore nullo ad un ingresso a rampa. L’algoritmo di consensus in esame presenta, analogalmente ad un sistema lineare di Tipo II, un ’errore di stima’ nullo per ingressi a rampa:

pi` u precisamente se la media dei valori di ingresso varia come una rampa l’algoritmo proposto ` e in grado di seguirla con errore a regime nullo.

L’algoritmo ` e stato ricavato imponendo una funzione di trasferimento per il termine C(s) dell’equazione 2.39 del tipo:

C(s) = s ²

(s + α) ² (2.40)

La funzione di trasferimento H _xz risulta quindi

H xz = s ² (s + α) ²

 s ²

(s + α) ² I + L

 −1

(2.41) da cui

 s ²

(s + α) ² I + L



X(s) = s ²

(s + α) ² Z(s) (2.42) Possiamo ricavare una rappresentazione diretta nello spazio degli stati im- ponendo condizioni iniziali nulle, x(0) = 0; con semplici passaggi algebrici ricaviamo:

s ² I + (s + α) ² L
X(s) = s ² Z(s) (2.43) risolvendo in s si ha

s ² (I + L)X(s) + 2α s LX(s) + α ² LX(s) = s ² Z(s) (2.44) Analizziamo adesso la forma della matrice (I + L); consideriamo i pesi della rete tutti uguali tra loro e pari ad 1: l’elemento (i, j) della matrice L sar` a uguale ad 1 se i nodi i e j possono comunicare, zero altrimenti. L’elemento (i, i) della matrice Laplaciana sar` a dato dal grado di connessione del nodo (cio` e dal numero di archi uscenti, indicato con |N _i |). La matrice identica aggiunge un termine unitario agli elementi diagonali della matrice.

Per poter ricavare un algoritmo decentralizzato ` e necessario esprimere per

componenti l’uguaglianza 2.44. A tale proposito utilizzeremo le consider-

2.2#1 31

azioni appena fatte sulla matrice (I + L).

s ² X _i + s ² X

j∈N

(X _i (s) − X _j (s)) + 2α s X

j∈N

(X _i (s) − X _j (s)) + α ² X

j∈N

(X _i (s) − X _j (s)) = s ² Z _i (s) (2.45)

Considerando l’operatore s come derivatore possiamo riformulare l’uguaglian- za 2.45 come di seguito

¨

x _i + X

j∈N

(¨ x _i − ¨ x _j ) + 2α X

j∈N

( ˙x _i − ˙x _j ) + α ² X

j∈N

(x _i − x _j ) = ¨ z _i (2.46)

L’algoritmo che ne ricaviamo ` e quindi il seguente (1 + |N i |)¨ x i = X

j∈N

¨

x j + 2α X

j∈N

( ˙x j − ˙x i ) + α ² X

j∈N

(x j − x i ) + ¨ z i (2.47)

Come ` e evidente l’algoritmo ` e completamente decentralizzato in quanto ogni agente utilizza le informazioni provenienti dai soli vicini (le sommatorie sono effettuate su N _i ) e variabili di ingresso a lui locali (z _i e sue derivate).

Le simulazioni di seguito si riferiscono ad una rete di comunicazione fissa con matrice Laplaciana ’quasi circolare’. Questo significa che ogni agente ` e connesso a soli due agenti, ed il primo e l’ultimo non sono connessi tra loro;

pi` u precisamente assegnamo ad ogni agente un’etichetta identificata da un numero da 1 ÷ n, l’agente i sar` a connesso agli agenti i − 1 ed i + 1 se i 6= 1 e i 6= n (questi ultimi saranno collegati rispettivamente agli agenti 2 e n − 1).

La topologia della rete collegata in questo modo e composta da 15 agenti ` e mostrata in figura 2.2.

Le due figure 2.3 e 2.4 mostrano il massimo e minimo errore di stima della posizione del baricentro ottenuto utilizzando gli algoritmi di consensus in 2.31 (linea ratteggiata) e in 2.47 (linea continua). La legge di controllo usata sar` a presentata nel prossimo paragrafo.

Le statistiche desiderate sono calcolate imponendo una rampa sul baricentro;

i momenti del secondo ordine sono calcolati fissando il valore di a ₁ e a ₂ e

utilizzando le equazioni in 2.15.

2.2#1 32

Figura 2.2: Topologia della rete utilizzata per la simulazione

Figura 2.3: Errore di stima del baricentro, µ _x

Figura 2.4: Errore di stima del baricentro, µ _y