Graph methods in Multi Agent Systems Coordination and Social Network Analysis

DOTTORATO DI RICERCA

in Ingegneria Elettroni a e Informati a

Ci lo XXVI

TITOLO TESI

Graph methods in Multi Agent Systems oordination and

So ial Network Analysis.

Settore s ienti o dis iplinare di aerenza

ING-INF/04 LAutomati a

Presentata da: Daniele Rosa

Coordinatore Dottorato: Prof. Fabio Roli

Tutor: Prof. Alessandro Giua

Ph.D. in Ele troni and Computer Engineering

Dept.of Ele tri al and Ele troni Engineering

University of Cagliari

Graph methods in Multi Agent

Systems oordination and

So ial Network Analysis.

Daniele Rosa

Advisor: Prof. Alessandro Giua.

Curri ulum: ING-INF/04 Automati a

XXVI Cy le

Mar h2013

DanieleRosa gratefullya knowledges SardiniaRegional Governmentforthe nan ial

support of his PhD s holarship (P.O.R. Sardegna F.S.E. Operational Programme of

the Autonomous Region of Sardinia, European So ial Fund 2007-2013 - Axis IV

In this thesis several results on two main topi s are olle ted: the

oordination of networked multi agents systems and the diusion of

innovationof so ialnetworks. The resultsare organized intwo parts,

ea h one related with one of the two main topi s. The ommon

as-pe t of allthe presented problems is thefollowing: allthe system are

represented by graphs.

Two are the main ontributions of the rst part.

•

A formation ontrolstrategy, based on gossip,whi hleads a set of autonomous vehi les to onverge to a desired spatial

dispo-sition in absen e of a ommon referen e frame. If the vehi les

have ommondire tion,weprovethatthe proposed algorithmis

robust against noise ondispla ementmeasurement.

•

The formalization of the Heterogeneous Multi Vehi le Routing Problem, whi h an be des ribed as follows: given an

hetero-geneous set of mobile robots, and a set of task to be served

randomly displa ed in a 2D environment, nd the optimal task

assignment to minimize the servi e ost. We rstly

hara ter-ize the optimal entralized solution, and then we propose two

distributed algorithms, based on gossip, whi h lead the system

to asub-optimal solutionsand are signi antly omputationally

more e ient than the optimal one.

The ontributions of the se ond part are the following.

•

Adoptingthe Linear ThresholdModel,weproposean algorithm based on linear programming whi h omputes the maximal

solution: the Inuen e Maximization Problem in Finite Time

and the diusion of innovationover a targetset.

•

We hara terize the novel Non Progressive Linear Threshold Model,whi hextends the lassi alLinearThreshold Model. We

formalizethemodelandwegivea hara terizationofthenetwork

At the end of these three years, I want to thank all the people that

haveshared the importantmomentsof this experien e.

First,I would liketothank allthe peoplewith whom I have

ollabo-rated,thathelpedandsupportedmeinmys ienti work: myadvisor

Prof. Alessandro Giua, Prof. Carla Seatzu, Mauro Fran es helliand

Prof. Fran es o Bullo.

Aspe ial thankgoestomy Lab-friends: Mar o, Stefano,Mehranand

Alessandro. Thank youguys and..."PRIMO!!".

A huge thank to my family, for their en ouragement during all these

years.

Finally,I thank Romina...youhave been always newt to me.

Introdu tion 1

Introdu tiontothe thesis . . . 1

Part1: Coordination of multi-agent systems through onsensus . . . . 2

Part2: Diusion of innovation inSo ialNetworks . . . 3

I Coordination of Multi-Agent Systems 5 1 Using onsensusto oordinatemulti-agentsystems: introdu tion and literature overview. 7 1.1 Formation ontrol formultivehi le systems . . . 8

1.2 The HeterogeneousMulti Vehi les RoutingProblem . . . 10

2 Formation Control Strategy 13 2.1 Preliminaries . . . 13

2.1.1 Coordinatesystems . . . 15

2.2 Formation ontrol strategy . . . 16

2.2.1 Position update rule . . . 17

2.2.2 Consensus onthe network entroid . . . 19

2.2.3 Formation ontrolstrategy . . . 20

2.2.3.1 Case I: stati topology . . . 21

2.2.3.2 Case II: time-varying topology. . . 22

2.2.4 Chara terizationof the robustness of the approa h . . . . 23

2.2.5 Convergen e speed . . . 25

2.3 Formation ontrol strategy inabsen e of a ommonreferen e frame 26 2.3.1 A hieving onsensus ona ommonreferen e dire tion . . . 27

2.3.3 Formation ontrolstrategy . . . 29

2.4 Simulationresults . . . 29

2.4.1 Agentswith a ommonreferen e dire tion . . . 30

2.4.2 Agentsin absen e of ommon referen edire tion. . . 31

2.5 Con lusions . . . 33

3 The Heterogeneous Multi Vehi le Routing Problem 35 3.1 Problemstatement . . . 35

3.2 Optimal entralizedsolution . . . 37

3.3 De entralized solution basedon optimallo altaskassignment . . 42

3.3.1 MILP Gossip algorithm . . . 42

3.3.2 Computational omplexity of the lo aloptimization . . . . 42

3.3.3 Finitetime and almost sure onvergen e . . . 47

3.3.4 Performan e hara terization of the MILP algorithm . . . 49

3.3.5 Asymptoti behavior . . . 54

3.4 Anheuristi gossip algorithm . . . 55

3.4.1 Computational omplexity of the lo aloptimization . . . . 56

3.4.2 Chara terizationsof the heuristi solution . . . 59

3.5 Numeri alsimulations . . . 61

3.6 Con lusionsand future work . . . 65

II Graph methods for diusion of innovation in so ial networks 69 4 Mathemati al models for the diusion of innovation in so ial networks: Introdu tion and literature overview. 71 5 DiusionofinnovationintheProgressiveLinearThresholdModel 77 5.1 Network representation and referen emodel . . . 77

5.1.1 Network stru ture. . . 77

5.1.2 Linear threshold model . . . 78

5.1.3 Other mathemati alresults . . . 78

6.1 The Inuen e Maximizationin FiniteTime Problem (IMFTP). . 87

6.2 Diusionof innovation overa target set . . . 91

6.3 Numeri alresults . . . 93

6.4 Con lusions . . . 94

7 A Non-Progressive instan e of the Linear Threshold Model 97 7.1 Ba kground . . . 97

7.2 Non-Progressive Linear Threshold Model . . . 98

7.2.1 System des ription . . . 98

7.2.2 Update rule . . . 98

7.3 Cohesive and Persistent Sets . . . 99

7.4 System's dynami . . . 100

7.4.1 Evolution duringthe seedingtime:

0

≤ t ≤ T

s

. . . 102

7.4.2 Evolution afterthe seedingtime:

t > T

s

. . . 103

7.4.3 Someexamples . . . 106

7.5 Con lusions . . . 110

8 Con lusions 111 A Appendix 115 A.1 Algebrai graph theory . . . 115

Introdu tion to the thesis

This thesis olle ts several results on two main topi s: the oordination of

net-worked multi agents systems and the diusion of innovation of so ial networks.

Bothtopi shave beenwidely studiedinliteratureinre ent years andindierent

elds,sin e it isevident innature the enormouspowerof the olle tivityrespe t

to a single individual: the more a group of individuals is organized, the more it

grows up and generate well-beingto ea h member. Moreover, ithas always been

evident thatmanytarget an bebetterrea hedbya oordinated groupofpeople

thanasingleindividual,and insome ases ooperationisne essary. At thesame

time, there are some phenomena in whi h some individuals (or group of them)

have a greater inuen e in the ommunity than others. Thus, in the last two

de ades, resear hers of dierentelds have been attra ted by su h on epts:

so- iology,biology,informati s,ele troni s,arti ialintelligen eand ontroltheory.

In this manus riptweaddress dierent problems hara terizedby some

om-mon aspe ts:

•

allthe onsideredthesystemsaresetsofsimpleautonomoussystems(agents orindividuals),whi hare onne tedtogether by a network;

•

in ea h system the behaviour of ea h agent is inuen ed by the behaviour of inter onne ted agents;

•

all the des ribed systems an be represented using graphs, thus all the mathemati alresults of this thesis are based ongraph theory.

The thesisisorganized intwo parts,ea hone fo usedononeof the twomain

onsensus

Intherstpartwefo usonthe oordinationofmultivehi lesystems. Givenaset

ofautonomousvehi le,whi h anex hangeinformationthrougha ommuni ation

network, we propose several solutionsof problems whi h were largely studied in

literature in the re ent years. All the results presented in this part are based

ondistributed onsensus algorithm: agentsex hange informationa ording to a

ommonproto olinordertorea hanagreementona ertainquantityofinterest.

In parti ular, most of the proposed solutions are based on gossip algorithms,

whi hare hara terizedby the following:

•

the ommuni ation s heme involve onlya oupleof agents atea h step;

•

the ommuni ation steps between ouple of agentsare asyn hronous. The ontributionof the rst part are the following.

(1) Aformation ontrolstrategy. Weproposeanovelde entralized oordination

strategy, based on gossip, that allows a dynami multi-agent system, in

absen eofa ommonreferen eframe,toestimatea ommonorientationand

a hieve arbitrary spatial formations with respe t to the estimated frame.

We assume that the agents are mobile point-mass vehi les that do not

havea ess toabsolutepositions(GPS). Tothe best ofour knowledgethis

strategyextends thestate ofart sin eit simultaneouslysolvestwoproblem

whi h are ommonly onsidered separately:

•

the a hievement of an agreement on a ommon referen e frame in absen e of it;

•

the a hievement of a desiredspatial disposition.

The method is robust against measurement noise of odometry or inertial

navigation.

(2) Distributed solutions for the heterogeneous multi-vehi le routing Problem.

We fo uson problemsof MTSP (MultiTravellingSalesman Problem),and

problemof MTSPistooptimallyassignnodes, whi hhavetobevisited, to

thedierentvehi les,inordertominimizethesumofthe ostsofthepaths.

TheproblemofMVRPrepresentsanextensionoftheMTSPinwhi hother

variables are taken into a ount su h as the apa ity of vehi les or osts

assignedtothenodes. Weextendthe stateofartsin ewe onsider the ase

wherea set of heterogeneous tasks arbitrarilydistributed ina planehas to

be servi ed by a set of mobile robots, ea h with a given movement speed

andtask exe utionspeed. Ourgoalistominimizethe maximum exe ution

time of robots. We propose two distributed algorithms based on gossip

ommuni ation: the rst algorithm is based on a lo al exa t optimization

and the se ond isbased on alo alapproximate greedy heuristi .

Part 2: Diusion of innovation in So ial Networks

Inthese ondpartwefo usonthediusionofinnovationinso ialnetworks. Whit

the expression so ialnetwork we identify a group of people whi h are onne ted

together by some types of relationship: friendship, love, business. In parti ular

we fo us on the study of the me hanism whi h onvin e people to adopt an

idea oran innovation,and how the behaviour ofea h individualis inuen ed by

the behaviourof the onne ted individualsorgroups. Followingthe trend of the

ontrol ommunity,westudyme hanismsofinnovationspreadinSo ialNetworks

in order to fore ast, optimize, ontrol some diusion behaviours. Our referen e

mathemati almodelisthe so alledlinear threshold model, and the ontribution

of this thesis are the following.

(1) Analysis and ontrol of the diusion of innovation in the Linear Threshold

Model. Weadoptthe lassi allinearthresholdmodel,whi his hara terized

asfollows:

•

at ea h individual is assigned a threshold value, whi h is a value in

[0, 1]

;

•

a node adopts the innovation as soon as the ratio of its neighbours who have already adopted it isabove itsthreshold value;

•

the innovation isin epted in the network by a seed set of individuals. A ording to this model, we rstly present an integer programming

prob-lemand aniterativealgorithmbasedonlinear programmingwhi htake as

input the set of innovators and ompute the maximal ohesive set of the

omplement of the seed set. The output of these algorithms an be used

to ompute the set of nal adopters in the network. We extend the state

of art by proposing a way to ompute the maximal ohesive set in a given

so ialnetwork,whi hwas justdened sofar, tothe best of our knowledge.

Then we introdu eand formalizewith integer programmingtwoproblems.

The "inuen e maximization in nite time problem (IMFT)" is that of

ndinga seed set of

r

individuals that maximizesthe spreadof innovation in the network in

k

steps. This problem represent an extension of the lassi al inuen e maximizationproblem, whi h onsiders an innite time

horizon.

The se ondoneis thatof ndingaseed set ofwhose ardinalityisminimal

whi h diuses the innovationto adesired set of individual ink steps.

(2) A novelnon-progressive instan e of the linear threshold model. The

lassi- al linear threshold model has a progressive nature, i.e., anindividual an

adopt the innovation if it hasn't adopted yet, but on e adopted it annot

abandon it. We extend the lassi al model by proposing a novel model in

whi h ea h individual in the so ialnetwork is inuen ed by the behaviour

of its neighbours, and atea h steps it de ideseither toadopt, abandon or

maintain the innovation by followinga threshold me hanism.

We assume that the innovation is in epted inthe network by a seed set of

individualswhi hare assumed tomaintain theinnovationindependentlyof

the state of their neighbours for a nite time. We identify all the possible

evolution of the network under the proposed model, and we des ribe in

details the evolution of the system in terms of two parti ular type of

Coordination of Multi-Agent

Using onsensus to oordinate

multi-agent systems: introdu tion

and literature overview.

Multi Agent Systems (MAS) are a lass of systems hara terized by a set of

entities , agents, whi h intera t in a shared environment to a hieve a ommon

target. Su h systems have attra ted the attention of many resear hers from

dif-ferentelds inthe lastde ades: e onomy,so iology , philosophy, and, of ourse,

omputer s ien eand automation.

In the ontroltheory ommunity the termagent identify anautonomous

sys-tem, with a simple dynami , whi h intera t with the environment where it

op-erates and takes autonomous de ision to rea h a given target. A Networked

Control System (NCS) is a system omposed by a set of agents whi h ex hange

informationthrough a ommuni ation network, and take de isionsinuen ed by

neighbours to rea h a ommon target. These system presents many advantages

with respe t toisolated systems.

•

InaMAS agents an exe uteinparallelsub-tasks ofasingle omplex task: that redu es the totalexe ution time and the omputational oasts.

•

Theabsen e of asingle de ision enter makesthe system morereliableand robustto failures.

Re ently, in literature this on epts have been applied toproblemsu h as:

•

oordination of autonomousvehi les;

•

environmental monitoring;

•

lo alizationsystems;

•

oordination of mobilerobots.

Typi almethodsrelatedwithMASarebasedondistributed onsensusalgorithms:

agentsex hangelo alinformationtorea hanagreementona ertainquantityof

interests. These algorithmshave been applied to problems su h as rendez-vous,

o king or intrusion dete tion. When the state of the agents onverge to the

average of their initialstates werefer toit asaverage onsensus.

Inthe next haptersweapply onsensus algorithmstotwodierentproblems.

In Chapter 2 wepresent a novel formation ontrolstrategy, based on

onsen-sus, whi hleads a set of autonomous vehi lesto onverge to adesired formation

in absen e of a ommon referen e frame. In Chapter 3 we use gossip algorithms

tosolvea parti ular instan e of the MultiVehi leRouting Problem.

All the presented approa hes are based on a spe ial type of onsensus

al-gorithms, , namely gossip algorithms. Gossip algorithms are hara terized by

an asyn hronous pairwise ommuni ation s heme: at ea h step only two agents

ex hange informationindependently of the rest of the agents.

In the next se tions weintrodu ethe two studiedproblems indetails.

1.1 Formation ontrol for multi vehi le systems

Multi-agentsystems onsistinginanetworkofautonomousvehi lesbenetgreatly

fromthe globalpositioningsystem (GPS)inthat itallows to losefeedba k

on-trol loops on estimated positions in a global referen e frame ommon to every

vehi le, enabling several ontrol tasks su h as surveillan e, patrolling,

forma-tion ontrol or sear h and res ue missions to be performed. Unfortunately su h

a powerful tool may not always be exploited for several reasons: for instan e

vulnerable tojamming atta ks. Furthermore, if the desired s ale of relative

dis-tan es between the vehi les is of the order of meters, the a ura y provided by

the GPS system might not be enough. The problem of how to oordinate a

network of agents in absen e of absolute position information has thus re eived

great attention from the ontrol theory ommunity (1, 2, 3). Furthermore, it is

usually assumed that the full network topology is not known by the agents and

that only lo al point-to-point ommuni ation or sensing are available to model

sensorswithlimited apabilities. In (4)atheoreti alframeworkand amethodto

a hieve o king in a multi-agent system is proposed based on the famous three

rules of o king by Reynolds (5) and on lo al intera tion rules based on virtual

potentials that allow the a hievement of o king as global emergent behaviour.

In (6, 7, 8,9) the onsensus problem,i.e., the problem of howto make the state

ofa set ofagents onvergetoward a ommonvalue, waspresented regarding also

theappli ationofmulti-agent oordination. Inparti ular ontrolstrategiesbased

on onsensus algorithmswere des ribed inthese papers asafundamentaltoolto

a hieve syn hronization of velo ities, dire tions or the attainment of onstant

relativedistan es between the agents.

Inourapproa hweassumethatea hagentestimatesrelativepositionswithits

neighbours initsown lo alreferen e frame entered onit. A similarassumption

wasmadein(10),whereaNyquist riteriontodeterminetheee tofthetopology

of a multi-agentsystem performing formation ontrolwas proposed; in this ase

theagentswere assumedtohavea ommon oordinatesystem butnota ommon

origin. Furthermore we rstly assume that ea h agent has anonboard ompass,

whi h allows allthe lo al frames to have the same orientation. Then we remove

this assumption.

Many formation ontrolstrategies arebasedonLeader-basedapproa hes (11,

12),whi hrequire thenetwork ofvehi lestoproperlyfollowoneormore leaders,

possibly ontrolled by a pilot, satisfyingeventually some onstraints. Also some

formation ontrolstrategies intheliterature take advantage fromthepresen e of

leadersexploiting network properties su h asgraph rigidity(13).

InChapter2wedesigna oordinationstrategyforpoint-massagentsinwhi h

leadersare not required,and the desiredformationisexpressed with oordinates

againstmeasurementnoise. The on ept ofover ompensationispresented inthe

followingse tions.

In (14) a de entralized algorithm to make a network of agents agree on the

lo ation of the network entroid in absen e of ommon referen e frames was

presented; the algorithmis based ongossip (onlyrandom asyn hronous pairwise

ommuni ations) and assumes stati agents displa ed in a

3

-d spa e. In (15) a de entralized algorithm based on gossip to make a network of agents agree on

a ommon referen e point and frame was proposed, assuming stati agents in

a

2

-d plane. Our approa h diers from (14, 15) in that we onsider dynami agents that move while the the estimation pro ess is exe uted, we assume that

all the agents lo al referen e frames are oriented in the same dire tion and that

noise isae ting the relativeposition measurements. Furthermore, the proposed

approa h isused to implementformation ontrol.

Summarizing, the following are the main ontributions of Chapter2.

•

A novel lo al intera tion proto ol that a hieves robust estimation of the network entroid robustto parameter un ertainties.

•

A method to a hieve provably robust formation ontrol with respe t to parameter un ertainties inthe agents'dynami s.

•

Anextended methodtoa hieverobustformation ontrolwithformationsof arbitraryshapebyperformingagreementona ommonreferen eframe. We

providesimulationsto orroboratethedes riptionofthisextended method.

1.2 TheHeterogeneous Multi Vehi les Routing

Prob-lem

The travelling salesman problem (TSP) is a well known topi of resear h and

an be stated asfollows: nd the Hamiltonian y le of minimum weight to visit

all the nodes in a given graph. Instru tive surveys an be found in (16, 17, 18).

This problem has re eived great attention for both its theoreti al impli ations

and itsseveral pra ti al appli ations. The Vehi le Routing Problem (VRP) is a

of nding

n

tours tovisit alllo ations inminimum time.

Several extensionsofthe TSPandtheVRPhavebeenproposedtobettersuit

pra ti alappli ationsbyintrodu ingseveraladditional onstraintsandobje tives

su h asa variable number of vehi les,a nite load apa ity, a ost asso iated to

ea h node whi h represents the demand of the ostumer, servi e time windows

and several more. Numerous extensions are well summarized in (20, 21, 22).

Finally, several extensions explore a dynami setting in whi h multiple vehi les

serve adynami numberof tasksas dis ussed in (23).

Multi-vehi leroutingproblemshavea ombinatorialnature,asallthepossible

tours must be explored to nd the optimal onguration. Exa t algorithmi

formulations are based, for example, on Integer Linear Programming (ILP) as

des ribed in (22, 24). General ILP solvers are hara terized by an exponential

omputational omplexity,thusinthe lastde adesmanyapproximatealgorithms

havebeenproposedwhi hare hara terizedbyalower omputational omplexity.

Examples of heuristi s and approximate algorithmsare presented in (21, 25, 26,

27, 28,29).

Weare interested in aninstan e of the VRP, alled the Heterogeneous Multi

Vehi le Routing Problem (HMVRP), with the following properties: the number

n

of vehi les is given a priori, a set

K

is given ontaining

k

tasks arbitrarily distributed in a plane, to ea h task is assigned a servi ing ost, ea h vehi le is

hara terized by a movementspeed and a taskexe ution speed.

Ithas beenshownin(30)thatwhen omparingthelengthofthe optimaltour

of one vehi le that visits all tasks lo ations with the multiple vehi le ase, the

maximum lengthof the tours for the multiple vehi le ase isproportional tothe

tourlength ofthe singlevehi le ase and proportionallyinverse tothe numberof

vehi les. Both upper and lowerbounds with su hs aling were given.

In Chapter 3 we extend the result in (30) by onsidering exe ution times

instead of tour lengths to a ount for vehi les of dierent speeds, tasks with

arbitrary exe ution osts and vehi les with dierent task exe ution speeds. We

provideupperand lowerboundsto theoptimal solutionasfun tion ofthe single

vehi le optimaltourlengthtoputineviden ehowtheperforman e isae tedby

the number of vehi les.

between pairs of vehi les(31), the se ond one is based onlo altask ex hange of

assignedtasks, oneby one,between ouplesof vehi les(32). Forbothalgorithms

weprovidedeterministi bounds totheirperforman e. The proposedapproa hes

to the HMVRP are distributed algorithms easy to implement in a networked

system and have favorable omputational omplexity with respe t to the ratio

k/n

between the number of tasks and vehi les instead of

k

as inthe entralized approa h.

Notethat the onsidered problem an alsobeseen asa parti ularinstan e of

a min/max VRP problemwhose main feature is the heterogeneity of the speed

and the tasks exe ution speed of the vehi les. Related works on the min/max

VRP problemin lude (33, 34, 35).

Summarizing, the following are the main ontributions of Chapter3.

•

We formalize the entralized problem in terms of a mixed integer linear programming(MILP)problemandextend thebounds in(30)forthe multi

TSP to the HMVRP.

•

We propose a rst distributed algorithm, based on gossip ommuni ation and on the solution of lo al MILP, to solve the HMVRP and hara terize

some of itsproperties.

•

We propose a se ond distributed algorithm to solve HMVRP, based on gossip ommuni ation and on lo altask ex hanges, hara terized by a low

omputational omplexity.

•

We provide simulations that show that the proposed algorithms attain a onstant fa tor approximation of the optimal solution with respe t to the

number of vehi les. A detailed omparison amongthe performan es of the

Formation Control Strategy

This hapter is organized as follow. In Se tion 2.1 we present the onsidered

systemandthesetofassumptionsadopted. InSe tion2.2weproposeaformation

ontrol strategy whi h is hara terize by a parallel appli ation of two dierent

de entralizedalgorithms: alo aldispla ement ontrolrulewhi hmoveea hagent

toward atargetpoint anda onsensus algorithmwhi hallowsagentstorea han

agreementona ommonreferen eframe. The on eptofover ompensationishere

presented. InSe tion2.2.4therobustnessoftheproposedstrategyisinvestigated

and anoptimal hoi e of the algorithmparameters is dis ussed.

2.1 Preliminaries

Leta network of agents be des ribed by a time-varying undire ted graph

G

(t) =

{V, E(t)}

,where

V =

{1, . . . , n}

is the set of nodes (agents),

E

⊆ {V × V }

isthe set ofedges

e

ij

representing point-to-pointbidire tional ommuni ation hannels available to the agents,

E

(t) : R

+

_{→ E}

is the set of edges being a tive at time

t

. Given a time interval

T

, the jointgraph

G

([t, t + T ))

is the union of graphs

G

(t)

inthe time interval

[t, t + T )

dened as

G

([t, t + T )) =

{V, E([t, t + T )))}

, where

E

_{([t, t + T )) = E(t)}

[

E

_{(t + 1)}

[

_{. . .}

[

E

_{(t + T )}

A node

u

∈ V

is said to be rea hable from

v

∈ V

if there exists a path in the graphfrom

v

to

u

. Node

u

∈ V

is saidto bea enter node if itisrea hable from any node in

V

. In a onne ted undire ted graph all the nodes are enter nodes.

A node

u

∈ V

is said to be aperiodi if the greatest ommon divisor of all the possible path length from

u

to

u

is

1

.

The state of ea h agent

i

is hara terized by its absolute position

x

i

, an estimation of the origin of the ommon referen e frame

s

i

∈ R

2

and an angle

θ

i

whi h represents the orientation of the

x

-axis of the lo al referen e frame with respe t to the

x

-axisof the global referen e frame.

Let

N

i

(t) =

{j : e

ij

(t)

∈ E(t)}

be the set of agents that send and re eive informationtoagent

i

attime

t

,these agentsare alled neighbors of agent

i

. We denethedegree ofagent

i

as

δ

i

(t) =

|N

i

(t)

|

where

|N

i

(t)

|

denotesthe ardinality ofset

N

i

(t)

. Theelementsof theLapla ianmatrix

L

ofgraph

G

(t)

are dened as

l

ij

=











−1, if (i, j) ∈ E(t)

δ

i

(t).

if i = j

0

otherwise

Given a generi square matrix

M

n×n

, the asso iated graph

G

M

=

{V

M

, E

M

}

is omposed asfollow:

• G

M

has

n

nodes, with index

i

∈ [1, n]

,so

V

M

=

{1, . . . , n}

;

• G

M

has anedge

e

ij

if the entry

m

ij

∈ M

isnonzero, so

E

M

=

{(i, j)|m

i,j

6=

0

}

If

M

has non zero diagonal entry

m

ii

, than node

i

∈ G

M

has a self loop. If

M

is symmetri then

G

M

isan undire ted graph. For atime-varying square matrix

M(t)

the asso iated graphis denoted as

G

M

(t) =

{V

M

, E

M

(t)

}

.

A square matrix

A

is sto hasti if its elements are non-negative and the row sumsequalsone. Asto hasti matrixsaidtobeergodi if

rank lim

k→∞

A

k

_{= 1}

.

An ergodi matrix

A

isSIA (sto hasti , inde omposableand aperiodi ) if

lim

k→∞

A

k

_{= 1}

n

π

T

,

where

π

isthe left eigenve tor of

A

orresponding to the unitary eigenvalue and

1

_n

is the n-element ve tor of ones. Given two matri es

A

(m×n)

and

B

(p×q)

, the Krone ker produ t is denoted as

A

⊗ B

(mp×nq)

.

In our dis ussion we onsider the followingworking assumptions: i. Agents

are modelled by dis rete time single integrators; ii. Neighboring agents

know the oordinatesystem of others.

2.1.1 Coordinate systems

A

2

-dreferen e frame

Σ

′

_{= (o}

′

_{, θ}

′

₎

is anorthogonal oordinate system

hara ter-ized by an origin

o

′

_{∈ R}

2

and orientation of the

x

-axis

θ

′

_{∈ [0, 2π)}

respe t to a

global oordinatesystem

Σ

dened by

o = (0, 0)

and

θ = 0

. We deal with three kindsof oordinate systems, whi h are showed inFig. 2.1.

Figure 2.1: Coordinate systems.

•

Global oordinatesystem: isthereferen eframeusedtodes ribethesystem from the point of view of an external observer. We denote it with

Σ

, and the urrent position of agent

i

spe ied in

Σ

is

x

i

∈ R

2

.

•

Lo al oordinate system: ea h agent owns a lo al referen e frame entered onit. The lo al oordinatesystem of agent

i

is denoted with

Σ

i

_{= (x}

i

, θ

i

)

,

where

x

i

is the position of agent

i

in

Σ

and

θ

i

is the angle between the x-axis of

Σ

and the x-axis of

Σ

i

. We denotethe position of ageneri point

j

with respe t to

Σ

i

as

x

i

j

. Therefore, the positionof

j

is

x

j

= R

i

x

i

j

+ x

i

where

R

i

=

"

cos θ

i

− sin θ

i

sin θ

i

cos θ

i

#

is arotationmatrix asso iated to the angle

θ

i

.

•

Estimated oordinate system: ea h agent keeps a lo al estimation of the ommon referen e frame. With respe t to

Σ

the estimated ommon ref-eren e frame by agent

i

is denoted with

Σ

i,es

_{= (s}

i

, θ

i

)

, where

s

i

is the estimated referen e enter and

θ

i

isthe estimated anglebetween the x-axis of the ommon referen e frame and the x-axis of

Σ

. Note that the orien-tation ofthe lo alestimated referen e frameisthe same asthe orientation

od

Σ

i

. We denote the position of a generi point

j

with respe t to

Σ

i,es

as

x

i,es

_j

. The position of agent

j

in frame

Σ

i

is:

x

i

j

= x

i,es

j

+ s

i

i

.

2.2 Formation ontrol strategy

Inthisse tionwepresentade entralized ontrolstrategywhi hallowsanetwork

of mobile agents in a

2

-D spa e to rea h an agreement on a ommon referen e frame and simultaneously onverge to a desired formation. Here we assume

that allthe agents have a ompass onboard, whi hallows themhave a ommon

referen e dire tion. In parti ular,we assume that

∀i ∈ V

,

θ

i

= 0

. The state of

i

-thagent is hara terized by a position

x

i

∈ R

2

and a variable

s

i

∈ R

2

whi h represents the estimated enter of the ommon referen e frame. When referring tothe state of the agent inits own referen e frame

Σ

i

we denote

its urrentestimation as

s

i

i

∈ R

2

.

Our strategy involvesthree lo al state updaterules:

•

A rule to update the position of the agents;

Ea hagent ismodeledby dis rete time single integratordynami s

x

i

(t + 1) = x

i

(t) + qu

i

(t),

(2.1)

where

x

i

∈ R

2

is the agent position,

u

i

∈ R

2

is the ontrola tion representing a

displa ement and

q

∈ R

+

is a gain. Ea h agent has to rea h a onstant target

position

D

i

∈ R

2

with respe t to its estimated ommon referen e frame. The

targetposition

d

i

i

(t)

with respe t to

Σ

i

attime

t

an be omputed as

d

i

i

(t) = s

i

i

(t) + D

i

.

In the ommon referen eframe

Σ

the target position of agent

i

is

d

i

(t) = x

i

(t) + d

i

i

(t) = x

i

(t) + (s

i

i

(t) + D

i

).

(2.2) Therefore, ea h agent drives itself toward its target position

d

i

i

(t)

with the following state update

x

i

(t + 1)

− x

i

(t) = q (d

i

(t)

− x

i

(t))

(2.3) with respe t to

Σ

. By repla ing equation (2.2) in (2.3) we nd the following position update rule:

x

i

(t + 1) = (1

− q)x

i

(t) + q(s

i

(t) + D

i

)

(2.4) Thereferen eframeof agent

i

thusmovingrigidlywithit,displa eits urrent estimation of the ommon referen e point. Therefore, the agent attempts to

ompensate this displa ement by updating its estimation of the position of the

ommonreferen epointasfollowsInotherwords,be ausetheagents'lo alframe

is entered on

x

i

and moves rigidlywith it, ea h agent

i

needsto update

s

i

i

, and onsequently

d

i

i

.

s

i

_i

(t + 1) = s

i

_i

(t)

_{− q s}

i

_i

(t) + D

i

(2.5) whi h, with respe t to referen e frame

Σ

, keeps the absolute position of the estimated point onstantin time

To implement these updates, however, a perfe t knowledge of parameter

q

is required whi h orresponds toan exa t measurement ofthe movementor

a tua-tors with perfe t pre ision.

Sin e measurements may beae ted by disturban eand a tuators subje ted

to malfun tioning, we introdu e a dierent state update rule, whi h we prove is

robust against un ertainties in the parameter

q

of any agent. We all this state update as over ompensation be ause it ee tively moves the urrent estimation

further away than ne essary, as follows:

s

i

_i

(t + 1) = s

i

_i

(t)

_{− k s}

i

_i

(t) + D

i

(2.6)

Equation (2.6)represents aover ompensation of agentdispla ementbasedon

parameter

k

,whi h ontrolshowmu htheagents ompensatetheirdispla ement. Using equation (2.4) and equation (2.6) in terms of

s

i

(t)

, we an express the generalupdate rule asfollow:

(

x

i

(t + 1) = x

i

(t) + q((s

i

(t) + D

i

)

− x

i

(t))

s

i

(t + 1) = s

i

(t)

− k((s

i

(t) + D

i

)

− x

i

(t)) + q((s

i

(t) + D

i

)

− x

i

(t))

(2.7)

We an set

h = k

− q

and rewriteequation (2.7) asfollows:

(

x

i

(t + 1) = x

i

(t) + q((s

i

(t) + D

i

)

− x

i

(t))

s

i

(t + 1) = s

i

(t)

− h((s

i

(t) + D

i

)

− x

i

(t))

(2.8)

(

x

i

(t + 1) = (1

− q)x

i

(t) + qs

i

(t) + qD

i

s

i

(t + 1) = (h)x

i

(t) + (1

− h)s

i

(t) + (

−h)D

i

(2.9) Note that:

•

if

h =

−q

(

k = 0

) the distan e ve tor

d

i

(t)

− x

i

(t)

is onstant, thusthere is no ompensation;

•

if

−q < h < 0

(

0 < k < q

),

d

i

(t)

translate in the same dire tion of

x

i

(t)

and

|d

i

(t + 1)

− x

i

(t + 1)

| < |d

i

(t)

− x

i

(t)

|

, thus there is only a partial ompensation;

•

if

h = 0

(

k = q

)the targetposition

d

i

(t)

is onstant,thusthe ompensation is perfe t;

•

if

h > 0

, (

k > q

)

d

i

(t)

moves toward

x

i

(t)

, thus an over ompensation is made.

Ea hagent has a lo alestimate

s

i

i

(t)

whi h onsiders as the enter of a ommon estimated frame. By ex hanging this lo al informationwith neighbours, agents

are abletorea hanagreementona ommonreferen e enter, whi hmeansthat:

∀i, j ∈ V,

lim

t→∞

ks

i

(t)

− s

j

(t)

k = 0

At ea h time step agent

i

re eives the value

s

j

j

from ea h agent

j

∈ N

i

(t)

. In Figure 2.2 it is shown how agent

i

is able to determine the orre t value

s

i

j

of agent

j

with respe t to

Σ

i

by only knowing

x

i

j

and the re eived value

s

j

j

. The

Figure 2.2: Informationex hange between agent

i

and

j

.

update rule for the lo alestimate is:

s

i

_i

(t + 1) = s

i

_i

(t) + ε

X

j∈N

i

(t)

(s

j

_j

(t) + x

i

_j

(t)

_{− s}

i

_i

(t))

(2.10)

with

0 < ε

≤ |N

i

(t)

|

. The same rule ould be writtenwith respe t to

Σ

:

s

i

(t + 1) = s

i

(t) + ε

X

j∈N

i

(t)

With respe t to

Σ

the overall estimate update rule ould be expressed as follow:

s(t + 1) = (P (t)

_{⊗ I}

2×2

)s(t)

(2.12)

where

P (t)

∈ P

is a time-varying matrix whi h depends on network topology at time

t

and

ε

, and

P

is the set of all possible matri es representing the system update dened in (2.11). Due to the update rule denition all matri es

P (t)

∈

P

are sto hasti . Note that equation (2.12) an represent both deterministi syn hronous onsensus algorithms and randomized gossip algorithms. At ea h

t

, algorithm(2.12) an be represented by the asso iated graph

G

P

(t)

. If

∀t > 0

there exists a

T > 0

su h that

G

P

([t, t + T ))

is onne ted, than

lim

t→∞

s

1

(t) =

. . . = lim

t→∞

s

n

(t)

, where

G

P

([t, t + T ))

isthe union of graphs

G

P

(t)

in the time interval

[t, t + T )

(7)(8).

2.2.3 Formation ontrol strategy

Let us dene olumn ve tors

x(t) =

{x

1

(t), . . . , x

n

(t)

}

,

s(t) =

{s

1

(t), . . . , s

n

(t)

}

and

D =

{D

1

, . . . , D

n

}

. Note that

D

represents the desired formationrespe t to a ommon enter. By summing the ontributions of equations (2.8) and (2.12)

the overall formation ontrolstrategy ouldbeexpressed as follow:

"

x(t + 1)

s(t + 1)

#

= (M(t)

_{⊗ I}

2×2

)

"

x(t)

s(t)

#

+

"

qD

−hD

#

(2.13) where

M(t) =

"

(1

_{− q)I}

n×n

qI

n×n

hI

n×n

(P (t)

− hI

n×n

)

#

(2.14)

For all

t

,

M(t)

∈ M

, where

M

is the set of all possible matri es of type (2.14) orresponding to dierent

P (t)

∈ P

. A given formation is onsidered to be a hieved if

• x(t) = s(t) + D

;

• ∀i, j ∈ V, ks

i

(t)

− s

j

(t)

k = 0

Lemma 2.2.1 Considersystem (2.13). If

lim

t→∞

(M(1)M(2) . . . M(t)

⊗ I

2×2

)

"

x(0)

s(0)

#

= c1

2n

(2.15)

• lim

t→∞

x(t) = s(t) + D,

• ∀i, j ∈ V,

lim

t→∞

ks

i

(t)

− s

j

(t)

k = 0.

Thus the desired formation is asymptoti ally a hieved.

Proof: Condition (2.15) implies that system (2.13) is stable. At the

equilib-rium

x(t + 1) = x(t)

and

s(t + 1) = s(t)

. From the rst equation of (2.13) we nd:

(1

_{− q)Ix(t) + qIs(t) + qID = x(t)}

x(t) = s(t) + D

By substituting in the se ond equation:

P s(t) = (I

_{− εL)s(t) = s(t)}

whi h implies

s(t) = c1

, where

c

∈ R

isa onstant.



Convergen e of the proposed strategy toward the desired formation an thus be

addressed by studying the stability of the followinglinear time-varying system

"

x(t + 1)

s(t + 1)

#

= (M(t)

_{⊗ I}

2×2

)

"

x(t)

s(t)

#

(2.16)

2.2.3.1 Case I: stati topology

Ifthe network topology isstati and onne ted, than

M(t) = M,

∀t

.

Lemma 2.2.2 (Lin,(36)) A sto hasti matrix M is SIA if and only if the

asso- iated graph

G

M

has a entre node whi h isaperiodi .



Nowwe are able to prove the followingresult.

Theorem 2.2.1 Consider a network of agents with a stati onne ted topology.

Given system (2.16) with

M(t) = M

, if

0

_{≤ h ≤ 1 − εδ}

max

(2.17)

where

δ

max

= max

{δ

1

,

· · · , δ

n

}

represents the maximum degree for the network, then

lim

t→∞

"

x(t)

s(t)

#

= c1

2n

,

where

c

∈ R

isa onstant.

Proof If ondition (2.17) holds

M

is sto hasti as all entries are non negative and row sums are equal to 1. Now we have to prove that

M

is SIA. We an representsystem (2.16)usingaundire tedgraph

G

M

asso iatedtomatrix

M

. In this graph ea hagent

i

isrepresented by two nodes:

•

one asso iated tothe agent position

x

i

,that we allpositionnode;

•

one asso iated tothe agent estimate

s

i

, that we allestimatenode.

Forea hagentthetwoasso iatednodesare onne tedtogetherbyabidire tional

edge, as the position update depends on the position estimate and vi e versa.

The onne tions between agents depend on matrix

P

− hI

. In parti ular, given a ouple of agents

(i, j)

there exists an edge between their estimation nodes if the

p

ij

entry of

P

is non zero. As the network is onne ted and undire ted by assumption, the graph

G

M

is onne ted as well and ea h node is a enter node. More, as all diagonal entries in

(1

− q)I

are nonzero, ea h position node in the asso iatedgraphhas aselfloop,so

G

M

isaperiodi . ItfollowsfromLemma 2.2.2 that matrix

M

is SIA, so

lim

t→∞

M

t

"

x(0)

s(0)

#

= c1

2n

where

c

is a onstant.



2.2.3.2 Case II: time-varyingtopology.

Inordertoprovetherobustnessof(2.16)weneedrsttopresentsomepreliminary

notions.

Lemma 2.2.3 (Jadbabaieetal.,(8)) Let

{M

1

, M

2

, . . . , M

m

}

beasetof sto hasti matri esofthesameordersu hthatthejointgraph

{G(M

1

)

S G(M

2

)

S . . . S G(M

m

)

}

is onne ted. Then the matrix produ t

M

1

M

2

. . . M

m

isergodi .



Lemma 2.2.4 (Wolfowitz,(37)) Let

{M

1

, M

2

, . . . , M

m

}

be a set of ergodi ma-tri es with thepropertythatforea hsequen e

M

i

1

, M

i

2

, . . . , M

i

j

of positivelength

j

the matrix produ t

M

i

1

M

i

2

. . . M

i

j

is ergodi . Then for ea h innite sequen e

M

i

1

, M

i

2

, . . .

there existsa rowve tor

c

su hthat

lim

j→∞

M

i

1

M

i

2

. . . M

i

j

= 1c. 

Nowwe an state the following theorem

Theorem 2.2.2 Consider a network of agents with time-varying topology

de-s ribed by (2.16). Let us assume that

∀t > 0

there exists a

T > 0

su h that

G

_P

_{([t, t + T ))}

is onne ted. Thefollowing ondition is su ientfor the systemto onverge to the desired formation:

0

_{≤ h ≤ 1 − εδ}

max

(2.18)

Proof Let

M

c

bethe set ofallpossible produ t matri esin

M

of length

T

su h that the joint graph

G

P

([t, t + T ))

is onne ted. In the theorem we assume that for ea h time interval

[t, t + T )

the matrix

M(t)M(t + 1) . . . M(t + T )

∈ M

c

Thus we an represent the evolution of the system as a produ t of matri es

M

c

(t)

∈ M

c

. If ondition (2.18)holds,then allmatri es

M(t)

∈ M

are sto hasti asshowed inthe proofofTheorem2.2.1,and itfollowsfromLemma2.2.3thatall

matri es

M

c

(t)

∈ M

c

are ergodi aswell asall produ tsin

M

c

. Finally it follows fromLemma 2.2.4 that:

lim

t→∞

(M

c

(1)M

c

(2) . . . M

c

(t)

⊗ I

2×2

)

"

x(0)

s(0)

#

= c1

2n



2.2.4 Chara terization of the robustness of the approa h

The proposed oordination strategy des ribed in se tion 2.2 an be ae ted by

errorsduetotheodometryorinertialnavigationsystem. Inparti ularthedesired

displa ementthatthegeneri agent

x

i

(t)

shoulda hievewithinonesampleoftime isas follows

wherethe time-varyingparameter

q

i

(t) = q + ∆

i

(t)

modelsarandomerrorinthe position update attime

t

.

Thus, the proposed lo alintera tion rule be omes











x

i

(t + 1) = (1

− q

i

(t))x

i

(t) + q

i

(t)s

i

(t)

s

i

(t + 1) = h(t)(x

i

(t)

− s

i

(t))

+(s

i

(t) + ε

P

_j∈N

_i

l

ij

(s

j

(t)

− s

i

(t)))

(2.20) where

h

i

(t) = h

− ∆

i

(t)

.

Let

Q(t)

and

H(t)

be

n

× n

diagonalmatri eswhere

Q

ii

= q

i

(t)

and

H

ii

(t) =

h

i

(t)

. The global system dynami sare thusdes ribed by

"

x(t + 1)

s(t + 1)

#

= (M

∆

(t)

⊗ I

2×2

)

"

x(t)

s(t)

#

(2.21)

M

∆

(t) =

"

I

_{− Q(t)}

Q(t)

H(t)

P (t)

− H(t)

#

(2.22)

Forall

t

,

M

∆

(t)

∈ M

∆

,where

M

∆

isainnitesetofmatri es

M

∆

(t)

hara terized by dierent values of

q(t)

,

h(t)

and

P (t)

. Now we hara terize the robustness of the proposed strategy with respe t tomeasurement noise.

Theorem 2.2.3 Consider a system as in eq. (2.21). Let us assume that

∀t > 0

there exists a

T > 0

su h that

G

P

([t, t + T ))

is onne ted . If the measurement noise

∆

i

(t)

is bounded by

h + εδ

max

− 1 ≤ ∆

i

(t)

≤ min{h, (1 − q)}, ∀i, t

(2.23) then

lim

t→∞

"

x(t)

s(t)

#

= c1

2n

where

c

is a onstant.

Proof The diagonalentries of the matri es

I

− Q(t)

and

P (t)

− H(t)

are

[I

− Q(t)]

ii

= 1

− q − ∆

i

(t)

We an assumethat

q > ∆

i

(t)

. If ondition (2.23)hold, then allmatri esin

M

∆

are sto hasti , be ause all entries are non negative and row sums equal to one.

Thus, the proof follows asin theorem 2.2.2.



Notethat

∆(t)

ould be positive ornegative.

We now dis uss what is the best parameter hoi e to a hieve maximum

ro-bustness. Given a xed value of

q

, the optimum value of

h

is the one whi h maximizesthe following obje tive fun tion:

max

h

{min{h, (1 − q), |h + εδ

max

− 1|}}

Bysubstitution it holds

•

If

1

_{− εδ}

max

2

≤ (1 − q)

theoptimumvalue of

h

is

h =

1−δ

max

2

thusthebound (2.23)be omessymmetri

−

1

− εδ

max

2

≤ ∆

i

(t)

≤

1

_{− εδ}

max

2

,

∀i, t

•

If

1

_{− εδ}

max

2

> (1

− q)

the optimumvalue of

h

is

h = (1

− q)

. It holds

εδ

max

− q ≤ ∆

i

(t)

≤ 1 − q, ∀i, t



2.2.5 Convergen e speed

Wenow hara terizethe onvergen e speed ofthe proposedstrategy inthe

time-invariant ase

M(t) = M

and

P (t) = P

. Let

Λ

M

bethe set of the

2n

eigenvalues of

M

. As

M

isSIA,

λ = 1

isasimple eigenvalue of

Λ

M

,andallothereigenvalues have moduleless than

1

. The onvergen e speed of (2.16)dependsonthese ond biggest module eigenvalue

λ

2

∈ Λ

, whi h is alled algebrai onne tivity. By knowing the eigenvalues of

P

,

Λ

M

an be determined.

Theorem 2.2.4 Let

M

be a

2

× 2

blo k matrix as in eq. (2.16). Let

Λ

P

=

{λ

p1

, λ

p2

, . . . , λ

pn

}

be theset of the

n

eigenvalues of

P

. The

2n

eigenvaluesof

M

are fun tion of the eigenvalues of

P

as follows:

λ

m

i1,2

=

(λ

p

+ 1

− h − q)

2

±

p(λ

p

+ 1

− h − q)

2

_{− 4((1 − q)λ}

p

− h)

2

(2.24)

Where

λ

m

i1,2

∈ Λ

M

are the two eigenvalues orresponding to

λ

pi

∈ Λ

P

Proof Followingthe work in(38)on howto ompute the determinant of

2

× 2

blo kmatri esasfun tionoftheblo ks,we omputetheeigenvaluesof

M

solving

det (M

_{− λ}

m

I) = 0

.

Sin e

(1

− q)hI = h(1 − q)I

det (M

− λ

m

I) = det ((1

− q − λI)(P − hI − λI) − hqI) ,

by some manipulations

det (λ

2

I

_{− λ(P − hI − qI + I) + (1 − q)P − hI)}

= 0,

putting

(1

− q − λ)

in eviden e:

(1

− q − λ)

n

_det((

λ

2

I

− λ(1 − h − q)I − hI)

1

_{− q − λ}

+ P ))) = 0

for

(1

− q − λ) 6= 0,

det((

λ

2

_I

_{− λ(1 − h − q)I − hI)}

1

_{− q − λ}

+ P ))) = 0.

Now, let

λ

p

=

−

λ

2

_{−λ(1−h−q)−h)}

1−q−λ

. Sin e

λ

p

is the solution of

det(λ

p

− P ) = 0

, the eigenvalues of

M

as fun tion of the eigenvalues of

P

are, after trivial manipula-tions, the solutionsof

λ

2

− λ(1 − h − q + λ

p

) + (1

− q)λ

p

− h = 0

whose solutionsare (2.24).



2.3 Formation ontrol strategy in absen e of a

ommon referen e frame

In the previous parts we have assumed that all the agents have a ompass on

board,whi hallowsthemtomaintaina ommonorientationofthelo alreferen e

frame. In this se tion we remove this assumption, thus ea h agent

i

belongs to a lo al referen e frame

Σ

i

=

{x

i

, θ

i

}

entered on it, where

x

i

is he position of

the agent

i

and

θ

i

is the orientation of the x-axes with respe t to the x-axes of the global referen e frame. Under this new assumption the state of ea h agent

i

is des ribed by the three state variables

{x

i

, s

i

, θ

i

}

. We modify the formation ontrolstrategyproposedinse tion2.2whi hisnotsuitableanymoreto orre tly

ontrolthe system, byintrodu inganalgorithmwhi hleadsthe agenttorea h a

ommonreferen edire tion. Thenew formation ontrolstrategyis hara terized

by:

(1) arule to a hieve agreement ona ommonreferen e dire tion;

(2) arule toupdate the position of the agents;

(3) arule to a hieve agreement ona ommonreferen e point.

Alltheresultsinthisse tionarepresented withrespe toftheglobalreferen e

frame

Σ

, and we assume that the agents are able toex hange lo alinformation. An interesting method whi h allows the agent to ex hange lo al estimates of

pointsanddire tionsinabsen e ofa ommonreferen eframeispresentedin(14),

thuswe anassumethatthe agentsex hangeinformationbyusingit. Underthis

assumption, we don't need to modify the onsensus algorithm on the network

entroid, whilethepositionupdateruleneedstotakeintoa ountthe variability

of the target point due to the variability of the orientation of the orientation of

the lo al referen e frame.

This se tion isorganized as follows: inthe rst part we hara terize rule (1),

thenwe hara terizerule (2), by modifyingtherule presented inse tion2.2,and

we point out the dependen e of these rules from (1). Finally we des ribe the

globalformation ontrolstrategy.

2.3.1 A hieving onsensus ona ommonreferen e dire tion

Inordertolead theagentstorea ha onsensus ona ommonreferen edire tion,

weuseAlgorithm1,originallyproposedin(39),whi hallows thesystemtorea h

aglobalsyn hronizationona ommonheading. Algorithm1isbasedonaGossip

ommuni ation s heme: atea h

t

a ouple of nodes

(i, j)

su h that

(i, j)

∈ E(t)

is randomlysele ted, and the sele ted nodes syn hronize the orientationof their

(i) Attime

t

ar h

(i, j)

∈ E(t)

is randomly sele ted.

(ii) Agents

i

and

j

updatetheorientationoftheirlo alreferen eframeasfollows:

•

if

max

{θ

i

(t), θ

j

(t)

} − min{θ

i

(t), θ

j

(t)

} ≤

π

2

θ

i

(t + 1) = θ

i

(t + 1) =

θ

i

(t) + θ

j

(t)

2

•

if

max

{θ

i

(t), θ

j

(t)

} − min{θ

i

(t), θ

j

(t)

} >

π

2

θ

i

(t + 1) = θ

i

(t + 1) =

θ

i

(t) + θ

j

(t)

2

+

π

2

•

Forea h

a

∈ V

su h that

a

6= i

and

a

6= j

:

θ

a

(t + 1) = θ

a

(t)

(39) a onvergen e analysis of Algorithm 1is alsoprovided: applying Algorithm

1 the set of agents globallyasymptoti allysyn hronize with probability

1

.

2.3.2 Position update rule

The positionupdaterule proposedinse tion2.2doesn't onsiderthe orientation

of the lo al referen e frame

θ

i

(t)

for ea h agent

i

, whi h may hange among the time a ording to Algorithm1. For ea h

i

∈ V

, the estimated target point

d

i

(t)

andof theestimated ommonreferen e enter

s

i

(t)

inglobal oordinates, attime

t

, depend on

θ

i

(t)

as follows:

s

i

(t) = x

i

(t) + R

i

(θ

i

(t))s

i

i

(t)

(2.25) and

d

i

(t) = x

i

(t) + R

i

(θ

i

(t))(s

i

i

(t) + D

i

) = s

i

(t) + R

i

(θ

i

(t))D

i

(2.26) where

R

i

(θ

i

(t)) =

"

cos(θ

i

(t))

− sin(θ

i

(t))

sin(θ

i

(t))

cos(θ

i

(t))

#

.

(2.25)and (2.26), we obtain the followingposition update rule:

(

x

i

(t + 1) = (1

− q)x

i

(t) + qs

i

(t) + qR

i

(θ

i

(t))D

i

s

i

(t + 1) = (h)x

i

(t) + (1

− h)s

i

(t) + (

−h)R

i

(θ

i

(t))D

i

(2.27)

2.3.3 Formation ontrol strategy

Letus denenow the olumn ve tor

D(θ)

asfollows:

D(θ) =







R

1

(θ

1

(t))D

1

. . .

R

n

(θ

n

(t))D

n







as the ve tor of the target point, whi h depend on the orientations of the lo al

frames. The new formation ontrolstrategy an beexpressed as follows:

"

x(t + 1)

s(t + 1)

#

= (M(t)

_{⊗ I}

2×2

)

"

x(t)

s(t)

#

+

"

qD(θ)

−hD(θ)

#

(2.28)

A ording tothe assumptions madein this se tion, agiven formation is

on-sideredto be a hieved if

• ∀i, j ∈ V, θ

i

(t) = θ

j

(t)

• x(t) = s(t) + D

;

• ∀i, j ∈ V, ks

i

(t)

− s

j

(t)

k = 0

The onvergen e of the agents to the desired formation depends on the

onver-gen e of Algorithm 1: a given formation annot be a hieved until all the lo al

frames onverge toa ommonorientation. Inse tion 2.4weprovideaset of

sim-ulations whi h are useful to understand the behaviour of the system under the

assumption madein this se tion.

2.4 Simulation results

Inthispartwepresenttheresultsofsomesimulationswithtwopurpose: validate

the analyti al results obtained in se tions 2.2 and 2.2.4, and introdu e some

onje tures about thebehavior ofthe system inthe s enariodes ribed inse tion

−4

−3

−2

−1

0

1

2

3

4

−4

−3

−2

−1

0

1

2

3

4

(a)Initial positions (b)Evolution

−4

−3

−2

−1

0

1

2

3

4

−4

−3

−2

−1

0

1

2

3

4

( ) Finalformation

Figure 2.3: Exampleof formation

2.4.1 Agents with a ommon referen e dire tion

In Fig 2.3 an example of a hievement of a desired formation using formation

ontrol strategy (2.13) is presented. The system is omposed by a set of agents

with a ommon referen e dire tion, that are initially randomly s attered in a

2-D spa e as in Fig 2.3a. They ex hange lo al information through a gossip

ommuni ation s heme, and for all of them

q = 0.1

and

h = 0.05

. The agents rea h the desired formation (a rux shape) by following the traje tories showed

in Fig 2.3b. The red lines represent the traje tories of the estimated ommon

ontrol strategy (2.13), in a system of agent with a ommonreferen e dire tion,

thedesiredformationisrea hedforea hvalueof

h

in

−q < h < 0

,i.e., forvalues of

h

that donot respe t ondition (2.18). In other words, a small ompensation isenough for the system to onverge to the desired formation.

−0.05

−0.045

−0.04

−0.035

−0.03

−0.025

−0.02

−0.015

−0.01

−0.005

0

0.94

0.95

0.96

0.97

0.98

0.99

1

1.01

1.02

Value of h

Value of |

λ

2

|

n=10

n=100

n

Figure 2.4: Value of

|λ

2

|

for

q

= 0.15

,

−0.15 < h < 0

and

n

∈ [10, 100]

Fig 2.5 shows the the value of

|λ

2

|

, i.e., the module of the se ond largest eigenvalue of the matrix

M

, of a system of agents with

q = 0.15

, omputed for

−q < h < 0

and

n

∈ [10, 100]

. For all the simulations the topology of the networkis onne ted andrandomlygenerated. It an beobserved that in ase of

no ompensation, i.e., for

h =

−q

,

|λ

2

| = 1

, and the system is not stable, while for

−q < h < 0

the se ond largest eigenvalue of

M

has a module smaller than one, and the system onverge to the desiredformation.

2.4.2 Agents in absen e of ommon referen e dire tion

Let us now onsider the ase of absen e of ommon referen e frame. In

Se -tion 2.3 we have hara terized the algorithmwhi h lead the agents to rea h the

targetformation. Wehavesupposedthattheagentslo allyintera tandex hange

informationusing the methodproposed in(14)whi hisbased onthe

determina-tionoftherelativepositions,i.e.,relativedistan eandangles,andthe orre tness

behaviorofthesystemfordierentvaluesoftheerror. Theagentsex hange

infor-mationfollowingagossip ommuni ations heme. The estimationsoftherelative

distan e

d

andtherelativeangleofview

γ

areae tedbyauniformlydistributed random error with a maximum amplitude

|∆d

m

| = α

d

d

and

|∆γ

m

| = α

γ

γ

. In Fig. 2.5is represented a system of 13 agents with a triangle-shape target

forma-tion. In Fig. 2.5a is

α

d

= α

γ

= 0.01

, while in Fig. 2.5b is

α

d

= α

γ

= 0.02

. It anbeobserved thatea hagentmakesarandomwalkarounditstargetposition.

The amplitude of the random walkgrows as:

• α

d

and

α

γ

grow;

•

thedistan eofthetargetpointfromtheestimated ommonreferen e enter grows.

−4

−3

−2

−1

0

1

2

3

4

−4

−3

−2

−1

0

1

2

3

4

(a)

|∆d

m

| = 0.01d

,

|∆γ

m

| =

0.01γ

−5

0

5

−2

−1

0

1

2

3

4

5

(b)

|∆d

m

| = 0.02d

,

|∆γ

m

| =

0.02γ

Figure 2.5: Exampleof formation

The same behavior an be observed in Fig 2.6, where the average amplitude

of the random walk is reported for dierent values of

α

d

and

α

γ

. Ea h value is the average of 20 simulations, and for ea h simulation the initialpositions and

the lo alorientationsof the agents were randomly generated. Moreover, Fig 2.6

showthatinabsen e of errorsinthe relativelo alization,the system onverge to