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

(1)

Sommario

L’argomento affrontato da questa tesi `e la coordinazione di pi`u velivoli applicando 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 consensus 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, è stato proposto un nuovo meccanismo di coordinazione 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è è realizzato associando forze virtuali agli archi di una rete, anch’essa virtuale, che racchiude alcune proprietà 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 control 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.

(2)

Introduzione

Il crescente interesse per i problemi di coordinazione multiagente nasce dalla necessità di utilizzare tanti semplici velivoli autonomi di limitate capacità anzichè una grossa e potente macchina. La presenza di numerosi agenti rende il sistema più 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 è però necessario considerare le limi- tazioni hardware dovute al basso payload disponibile. Ci riferiamo in particolare alle limitate capacità 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 dipendono 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 presenza di un organo di decisione centrale. Molto spesso la formazione raggiunta 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 avendo le sembianze di un unico e grande pesce e, al limite, di effettuare manovre evasive per minimizzare la probabilità di cattura dei membri. Il problema della coordinazione è solamente uno dei temi di ricerca della robotica coope- rativa ma è anche uno dei requisiti fondamentali per lo svolgimento della maggior parte dei task.

(3)

In un contesto più generale il comportamento cooperativo di alcune specie di insetti, tra cui formiche e api, da luogo a quello che è stato chiamato comportamento emergente. Nessuno schema di divisione dei compiti è 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 spesso 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, è stata applicata per risolvere problemi di ottimizzazione. Alcune società 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ù 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 bibliografica sulle tecniche pi`u comunemente utilizzate . sviluppo di un software di simulazione multiagente

. scelta e ampliamento di un particolare approccio

. proposta di un nuovo meccanismo di coordinazione, da me chiamato virtual edges

L’argormento oggetto di tesi non è stato trattato in nessun corso previsto dal mio piano di studi. Durante lo svolgimento della tesi ho avuto l’oppor- tunità di partecipare al corso breve tenuto dalla Professoressa Naomi Ehrich Leonard, Princeton University, presso il Dipartimento di Sistemi Elettrici e Automazione, Università 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.

(4)

1 Meccanismi di Coordinazione

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. Le tecniche di coordinazione multiagente pi`u consolidate sono state classificate nelle categorie descritte di seguito.

Leader-Follower Le tecniche di leader-follower suppongono la presenza di un leader fisico di cui è definita la traiettoria. Gli ingressi di controllo degli altri membri sono calcolati direttamente in funzione della distanza dal robot leader o, indirettamente, in funzione della distanza da altri agenti. Generalmente si basano su tecniche geometriche e si estendono facilmente a sistemi con vincoli sulla velocità. Lo svantaggio princi- pale di questo tipo di sistemi è la scarsa robustezza: senza il leader il sistema non è in grado di svolgere il task. Nella sua formulazione originaria questo tipo di approccio non prevedeva inoltre alcun feed- back dal gruppo verso il leader, causando problemi alla controllabilità e alla stabilità dell’intero sistema. L’analisi di stabilità delle configu- razioni può effettuarsi con le tecniche utilizzate per lo studio di sistemi interconnessi.

Artificial Potential Functions Le funzioni di potenziale artificiale sono funzioni che causano forze di attrazione o repulsione tra coppie di agenti, a seconda che la distanza relativa sia maggiore o minore del valore desiderato. Una volta disegnata la funzione potenziale desiderata ricaviamo la legge di controllo come somma dei gradienti delle funzioni potenziali tra l’agente e i suoi vicini. Queste leggi di controllo sono generalmente spazialmente distribuite (dipendono solo dalla posizione relativa tra robots vicini) e sono invarianti a traslazioni e ro- tazioni. L’utilizzo di funzioni potenziali pu`o prevedere lo studio di stabilit`a con funzioni di Lyapunov derivanti direttamente dalle funzioni di potenziale.

Virtual Structures Per struttura virtuale di un insieme di punti nello spazio si intende l’insieme di vincoli geometrici che devono essere im- posti 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

(5)

computazionale di questo secondo approccio rende il metodo adatto solo per piccole formazioni. 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. Le formazioni rigide sono particolarmente indicate per task in cui pi`u agenti devono trasportare o spostare un unico oggetto in modo coordinato.

Behavior Based L’utilizzo di tecniche di Behavior Based Robotics permette l’implementazione di meccanismi di coordinazione anche su robot di limitate capacità e garantisce reazioni tempestive ai cambiamenti esterni. Il primo passo consiste nel suddividere il task in molti tasks più semplici, al limite composti da un’unica azione. Dopodichè svilup- piamo una logica per la commutazione dei tasks basata sullo stato del velivolo e sulle caratteristiche dell’ambiente esterno (in cui è compreso lo stato di eventuali agenti vicini). La convergenza di questi metodi può essere studiata con modelli probabilistici.

Consensus Based I problemi di coordinazione multiagente che utilizzano le tecniche del consensus 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à, in modulo e direzione. E’ preferibile inserire dei termini di attrazione/repulsione tra agenti per garantire la coesione del gruppo ed evitare collisioni. L’analisi di stabilità di queste tecniche si basa sulle proprietà della matrice Laplaciana costruita in funzione connessioni tra gli agenti.

Abstraction Based 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. 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 inutilizzabile.

(6)

2.1 Statistiche di Formazione

Considerando sciami di grandi dimensioni specificare l’esatta posizione di ogni agente non è in genere necessario ed è 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 è 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. Le statistiche di ordine più basso rappresentano quindi un utile astrazione della formazione totale permettendo il controllo di grandi sciami. Di seguito sarà illustrata la soluzione proposta in [1].

I momenti d’inerzia della formazione sono un esempio di statistiche di formazione 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.

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â_ixp^b_iyp^c_iz (1) con a, b, c ≥ 0. L’ordine del momento è dato da a + b + c. Solamente i momenti del primo e secondo ordine saranno utilizzati per la specifa della formazione. L’analisi sarà effettuata considerando sciami in due dimensioni, m = 2.

I due momenti del primo ordine specificano il centro di massa della formazione, µ = [µ_x, µ_y]^T. Il momento incrociato M_xy determina l’orientazione degli assi principali d’inerzia mentre i due momenti M_x² e M_y² ne determi- nano l’elongazione.

Da considerazioni effettuate nel riferimento relativo alla formazione, centrato in µ e ruotato dell’angolo che rende nullo M_xy^rel, ho determinato il rettangolo di contenimento della formazione. La criticit`a di questa misura `e che si tratta di un approssimazione per eccesso e la lunghezza dei lati del rettangolo dipende da n. Le espressioni necessarie ad individuare il rettangolo di contenimento a partire dalla conoscenza dei momenti, e viceversa, sono state ricavate utilizzando alcune delle considerazioni in [3].

Le statistiche di formazione presentate possono essere stimate da ogni agente eseguendo gli algoritmi di consensus decentralizzati descritti di seguito.

(7)

2.2 Algoritmi di Consensus

Un algoritmo di consensus `e un algoritmo iterativo che, eseguito sulle variabili locali ad ogni agente, converge ad un unico valore. Ogni agente ha un insieme di variabili interne che sono aggiornate dall’algoritmo in funzione delle variabili ricevute dai vicini. Analizzando la rete di comunicazione e i pesi attribuiti alle connessioni `e possibile dimostrare che le variabili interne di ogni agente convergono ad un unico valore, che chiameremo valore di consenso.

Gli algoritmi di consensus possono dividersi in algoritmi di static consensus e dynamic consensus, come proposto in [2]. Gli algoritmi di static consensus non prevedono variabili di input e il consenso finale raggiunto `e la media dei valori iniziali delle variabili interne di tutti gli agenti. Un algoritmo di dynamic consensus permette di seguire la media di input, locali ad ogni agente, che hanno un limite di crescita polinomiale il cui grado dipende dall’algoritmo utilizzato.

L’algoritmo di consensus statico pu`o essere realizzato con il seguente algoritmo decentralizzato:

˙x_i = X

j∈Ni

(x_j− x_i) (2)

dove xi e xj sono le variabili degli agenti i e j su cui eseguiamo il consensus, mentre Ni `e l’insieme dei vicini del nodo i.

In forma matriciale si ha:

˙x = −Lx (3)

dove con L si è indicato la matrice Laplaciana del grafo. Gli elementi dia- gonali di L corrispondono alla somma degli archi uscenti dal corrispondente nodo (se il peso degli archi non è unitario avremo la somma dei pesi delle connessioni uscenti). L’elemento (i, j) sarà pari al peso cambiato di segno dell’arco (i, j), se l’arco non è presente consideriamo un peso nullo.

La matrice Laplaciana di grafi non diretti (in cui le connessioni sono bidi- rezionali e con stesso peso nelle due direzioni) è simmetrica e semi-definita positiva. Sotto le stesse condizioni la dinamica del sistema 3 è quindi sta- bile e converge ad un valore di regime. Se le componenti del vettore x = [x₁, x₂, ..., x_n]^T sono tutte uguali, x_i = x_j per tutte le coppie (i, j), si ha Lx = 0. Una qualsiasi condizione di consenso è un equilibrio del sistema 3.

Se il grafo è connesso si può anche dimostrare che ogni equilibrio corrisponde a consenso. Il valore di consenso raggiunto è la media dei valori iniziali delle variabili x_i, come chiarificato dalla seguente proprietà di conservazione:

d dt

X

i

x_i

!

= 1^T ˙x = −1^TLx = 0 → 1 n

X

i

x_i(t) = 1 n

X

i

x_i(0) (4)

(8)

L’algoritmo di consensus dinamico proposto in [2] `e descritto dalle seguenti equazioni e deriva da considerazioni effettuate sulla risposta in frequenza del sistema 3.

˙x = −Lx + ˙z

x(0) = z(0) (5)

con z = [z₁, z₂, ..., z_n]^T vettore degli ingressi. Tutte le variabili x_i convergono alla media dei valori z_i, con errore a regime nullo, se il segnale di ingresso `e un gradino.

Seguendo gli stessi passi ho ricavato un algoritmo di consensus che permette il tracking di segnali di ingresso a rampa. L’algoritmo `e stato chiamato di tipo due in analogia alla notazione utilizzata per i sistemi lineari.

(1 + |Ni|)¨x_i = X

j∈Ni

¨

x_j − 2αX

j∈Ni

( ˙x_i− ˙x_j) − α² X

j∈Ni

(x_i − x_j) + ¨z_i (6)

Da un punto di vista implementativo questo algoritmo necessita di una maggiore banda di comunicazione; ogni agente deve infatti trasmettere la varia- bile di consensus (x_i) e le sue derivate ( ˙x_i e ¨x_i). Equipaggiando i veicoli con accelerometri raggiungiamo il consenso dinamico sulle loro posizioni con errore a regime nullo per ingressi a rampa. La figura seguente mostra l’errore di stima della coordinata x del baricentro quando tutti gli agenti si muovono alla stessa velocit`a, mettendo a confronto gli algoritmi 5 e 6.

L’errore a regime dell’algoritmo 6 `e dovuto al tempo di campionamento della simulazione. La condizione di consenso non sar`a mai raggiunta dall’algoritmo 5.

(9)

3 Virtual Edges

Il problema che affrontiamo con la progettazione di un nuovo meccanismo di coordinazione è la disposizione decentralizzata degli agenti all’interno di un’area di contenimento circolare. E’ prevista una fase di inizializzazione in cui viene creata una rete di comunicazione ausiliaria, che chiameremo strutturale, la cui proiezione sul piano possiede alcune proprietà. Per proiezione della rete sul piano intendiamo un insieme di punti, individuati dalla posizione assoluta degli agenti, e un insieme di segmenti i cui estremi sono le coppie di nodi comunicanti. La rete di comunicazione sarà creata da algoritmi decentralizzati e sarà costituita da un insieme di triangoli di connessione non sovrapposti. Un triangolo di connessione è un insieme di tre nodi e degli edges che li collegano; due triangoli di connessione non sono sovrapposti se tutti i punti di intersezione dei segmenti che individuano gli edges sono nodi.

Il controllo di ogni agente `e calcolato associando agli edges della rete di comunicazione ausiliaria delle forze repulsive. Il campo di forza risultante fa si che il movimento degli agenti pi`u interni sia vincolato dalla posizione degli agenti esterni che, avendo almeno una direzione di moto non vincolata, saranno responsabili del controllo dell’estensione della formazione.

Il baricentro sar`a stimato con gli algoritmi di consensus presentati e control- lato con un controllo proporzionale da tutti gli agenti.

Nell’eseguire l’algoritmo di creazione della rete ogni nodo individua la presenza di eventuali edges di cui è un nodo estremo e ne determina i semipiani di separazione. Due semipiani sono di separazione per un edge se la retta che li divide passa per i suoi estremi. La sequenza logica eseguita da ogni agente è descritta dai seguenti passi in cui si è inserito l’apice * in riferimento al nuovo grafo di connessione strutturale creato.

1. Determinazione dell’insieme di nodi comuni ai due estremi Pij = {k ∈ E, j ∈ Ni t.c. k ∈Ni & k ∈Nj}

2. Se |N^∗ij| = 0 AND Pij 6= 0, con N^∗ij = {k ∈ E t.c. i, j ∈ N^∗k}, aggiungere al grafo G^∗ il nodo k ∈ Pij pi`u vicino al centro del segmento congiungente i due nodi estremi, exit;

3. Se |N^∗ij| = 1 AND Pij 6= 0, con N^∗ij = {k ∈E t.c. i, j ∈ N^∗k}, aggiungere al grafo G^∗ il nodo k ∈ Pij pi`u vicino al centro del segmento congiungente i due nodi estremi che si trovi nel semipiano opposto al semipiano di appartenenza del nodo in N^∗i, exit;

4. Se |Nij^∗| = 2 OR Pij = 0 exit

(10)

I nodi possono individuare le connessioni presenti utilizzando un ulteriore canale di comunicazione analogico. Associamo ad ogni nodo una frequenza;

ad ogni istante ogni nodo trasmetter`a un segnale cos`ı costruito:

s_i = S(Ni∪ i) = s(f_i) + X

j∈Ni

as(f_j) + b X

k /∈Ni,k∈S Nj,j∈Ni

s(f_k) (7) con b < a < 1 e s(f ) una funzione generatrice di segnali di frequenza f . Lo spettro in frequenza del segnale trasmesso da ogni nodo avrà dei picchi sulle frequenze che corrispondono ai vicini di primo e secondo grado. Analiz- zando l’ampiezza dei picchi è possibile stabilire quali nodi sono di primo livello e quali di secondo: l’ampiezza di questi ultimi sarà infatti minore (b < a) rispetto a quelli di primo grado. Dato che i grafi di comunicazione sono sostanzialmente due, uno distance dependent, G(E, V), che tiene conto del limitato raggio di comunicazione dell’hardware, e uno structure dependent, G^∗(E^∗,V^∗), creato dinamicamente durante l’inizializzazione, sarà necessario utilizzare due segnali analogici.

Analizzando in frequenza i due segnali ricevuti dai vicini, e conoscendo la loro posizione, possiamo ricavare tutte le informazioni necessarie per eseguire in modo decentralizzato l’algoritmo di costruzione della rete.

Sui segnali trasmessi da ogni agente introduciamo le seguenti operazioni assumendo una funzione s_(·) comune a tutti.

Definition 1 (Estrazione dei vicini di primo grado in G). Il nodo i `e in grado di estrarre i vicini di primo grado del nodo j ∈ Ni dal segnale s_j(t) (se j /∈ Ni il nodo i non riceverebbe il segnale di j) analizzando i picchi in frequenza presenti nel segnale s_j(t) ed estraendo quelli il cui modulo supera un dato valore, comune a tutti e dipendente da s(·) e da a, eventualmente togliendo il picco di frequenza massimo che corrisponde alla frequenza del nodo j.

E1 : s_j(·) −→V s⁰_j = S(E1)

(8) dove E1 indica l’operazione di estrazione sopra definita e s⁰_j `e il segnale costruito come in 7.

Definition 2 (Estrazione dei vicini comuni a due nodi in G). Il nodo i `e in grado di individuare i vicini di primo grado del nodo j ∈Ni che sono anche vicini di primo grado del nodo k ∈ Ni dai segnali s_j(t) e s_k(t) effettuando una convoluzione nel tempo (o moltiplicazione in frequenza) tra s⁰_j(t) e s⁰_k(t).

Pij = E1(s⁰_j(t) ⊗ s⁰_k(t)) (9) dove con ⊗ si `e indicato il simbolo di convoluzione nel tempo.

(11)

Definition 3 (Determinazione degli edges). Un nodo i individua gli edges di cui è un estremo effettuando una convoluzione nel tempo tra il segnale s(f_i) e i segnali s^∗_j ricevuti dai vicini; come per l’estrazione lo stesso risultato può ottenersi da una moltiplicazione in frequenza dei due segnali. Se il risultato di questa operazione è il segnale nullo allora l’edge (i, j) non è presente, altrimenti si avrà come risultato un segnale di frequenza f_i.

s(f_i) ⊗ s^∗_j 6= 0 ⇔ (i, j) ∈E^∗ (10) dove con E^∗ si `e indicato l’insieme degli edges di G^∗, e con s^∗_j il segnale ricevuto da j e costruito secondo le connessioni presenti in G^∗.

Definition 4 (Determinazione dei Triangoli di Connessione). Un nodo i determina i triangoli formati dagli edges di cui `e estremo estraendo i vicini di primo grado comuni ai nodi i e j nel grafo G^∗. La determinazione dei triangoli `e riferita al grafo G^∗, nelle operazioni utilizzaremo quindi i segnali s^∗_(·).

T r :E^∗ →V^∗

Ni,j^∗ = T r((i, j)) = E1(s⁰_i^∗(t) ⊗ s⁰_j^∗(t)) ⊂V^∗

(11)

L’operazione di inserimento di un nodo (k) viene effettuata dagli estremi del- l’edge a cui vogliamo connetterlo e consiste nel sommare ai segnali s_i e s_j un termine del tipo s(fk), con fk ricavabile univocamente dall’identificativo dell’agente. Il nodo k riconoscer`a la propria frequenza analizzando i segnali trasmessi dai nodi i e j e accetter`a le nuove connessioni inserendo nel suo segnale le frequenze f_i e f_j.

Ad ogni edge sono associati dei campi di forza di modulo e verso dipen- denti dalla posizione dell’agente rispetto alla retta passante per gli estremi dell’edge. Il versore dei campi di forza `e diretto perpendicolarmente al- l’edge mentre il modulo varia come l’inverso del quadrato della distanza tra il velivolo e la retta.

|Vj,k| =







k

d²_i−jk if d_i−jk< d^∗ 0 otherwise

(12)

dove d²_i−jk `e la distanza del nodo i dalla retta passante per i nodi (j,k). La forza esercitata sull’agente da un edge `e sempre repulsiva.

Non tutti gli edge della rete eserciteranno dei campi di forza sui nodi, solamente quelli che definiamo edges affluenti al nodo possono generare delle azioni di repulsione sul velivolo in questione.

(12)

Definition 5 (Edges Affluenti ad un Nodo). Un edge si definisce affluente al nodo i se i suoi estremi (j, k 6= i) sono vicini di primo grado del nodo i.

H^∗i = {(j, k) ∈E^∗ | j ∈N^∗i , k ∈N^∗i} (13) Il campo di forza risultante sar`a dato dalla somma dei campi di forza eserci- tati dagli edge affluenti al nodo:

Vi = X

(j,k)∈Hi^∗

V~jk(pi) (14)

Utilizzando i segnali s_j ricevuti dagli agenti vicini ogni nodo `e in grado di determinare gli edges affluenti e, nota la posizione degli estremi (che per definizione di edges affluenti sono anche vicini del nodo), pu`o calcolarsi in modo decentralizzato i campi di forza virtuale presenti utilizzando semplici formule di intersezione tra rette e distanza di un punto da una retta.

Analizzando l’andamento del campo di forza attorno ad ogni agente notiamo la presenza di forze repulsive che costituiscono termini di collision avoidance tra velivoli. Il modulo di questa forza tende all’infinito quando la distanza tra due agenti tende a zero.

Il problema di formazione che ci proponiamo di risolvere `e contenere tutti i velivoli all’interno di un’area circolare, di dato centro e raggio, e di imporre che il baricentro della formazione coincida con il centro del cerchio.

La formazione pu`o essere specificata con soli due parametri (R^d, C^d) che assumiamo noti a tutti gli agenti.

Ogni agente determina se `e nodo esterno o interno confrontando il numero di nodi vicini e il numero edges affluenti. Per costruzione della rete un nodo esterno ha sempre un numero di edges affluenti minore del numero dei vicini di primo grado.

Applicando forze di chiusura ed espansione gli agenti esterni controllano il perimetro della formazione facendo si che il cerchio desiderato rappresenti un’approssimazione per eccesso dell’area occupata dai velivoli; l’effettiva area di contenimento sar`a determinata dalla posizione relativa dei nodi esterni ed in particolare dagli edges che li collegano.

I nodi interni utilizzano le forze di chiusura per posizionarsi all’interno del- l’area di contenimento desiderata, quindi uniformano la densit`a interna applicando forze in direzione del baricentro dei vicini di primo grado.

Nel descrivere le forze presenti utilizzeremo la funzione vers(v) per estrarre il versore (a norma unitaria) dal vettore v.

Per tutti i nodi assumiamo che esista una forza radiale virtuale (calcola- ta da ogni agente) diretta dal nodo al baricentro qualora il nodo si trovi

(13)

all’esterno della circonferenza di raggio desiderato e di centro il baricentro della formazione.

F~_close = k_closevers(C^cons− p_i) if |C^cons− p_i| > R^d

0 otherwise (15)

dove C^cons `e la stima del baricentro con algoritmi di consensus e k_close > 0.

Durante l’operazione di espansione agisce una forza sui nodi pi`u esterni opposta alla forza di chiusura:

F~expand = −k_expvers(C^cons− pi) if |C^cons− pi| < R^d

0 otherwise (16)

con k_exp > 0.

La posizione del baricentro `e controllata con un semplice controllore proporzionale applicato ad ogni velivolo:

F~_CM = k_CMvers(C^d− C^cons) (17) dove C^d`e il centro desiderato.

Agli agenti interni associamo una forza diretta verso il baricentro dei vicini, utile per uniformare la densit`a della formazione:

C^neigh= _|_N¹

i|

P

j∈Nip_j F~_neigh= k_nvers(C^neigh− p_i)

(18)

(14)

Conclusioni

La validit`a del meccanismo di coordinazione proposto `e stata verificata in simulazione.

Gli agenti occupano l’area circolare assegnata distribuendosi quasi uniforme- mente ed evitando le collisioni.

E’ possibile effettuare manovre di obstacle avoidance assegnando agli ostacoli forze virtuali di repulsione. Il comportamento della formazione `e determinato dal raggio di comunicazione e dalla grandezza dell’ostacolo.

(15)

Bibliografia

[1] R.A. Freeman, P. Yang, K.M. Lynch: Distributed Estimation and Control of Swarm Formation Statistics, American Control Conference, 2006.

[2] Demetri P. Spanos, Reza Olfati-Saber, Richard M. Murray:

Dynamic consensus on mobile networks in Proceedings of the 2005 IFAC World Congress, Prague, 2005.

[3] C. Belta and V. Kumar: Abstraction and control for groups of robots, IEEE Transactions on Robotics, vol. 20, no. 5, pp. 865.875, Oct. 2004.

[4] Reza Olfati-Saber, Shawn C. Shadden, Jerrold E. Marsden, Dong Eui Chang: Collision Avoidance for Multiple Agent Systems, CDC December 2003.