Change search
ReferencesLink to record
Permanent link

Direct link
Consensus Algorithms - Flocking and Swarms.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2011 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

An interesting eld of mathematics is the study of swarming and ocking.

By using graph theory, one can describe a system of agents that transfer

information between each other. With the help of certain algorithms it

is possible to update the agent's information in order to reach consensus

between the agents. If the information relates to the position, the velocity,

or the acceleration of each agent, a behaviour similar to that of animals

ocks or insect swarms is observed. Several other applications also exist,

for example in systems of multiple robots when no central coordination is

possible or simply not desired.

In this paper dierent algorithms used to change the agent's information

state will be studied and researched in order to determine the requirements

under which the entire set of agents achieve consensus. First the

case where agents receive information from a non-changing set of agents

will be studied. Specically a particular algorithm, where each agent's information

is determined by a linear function depending on the information

state of all other agents from which information is received, will be considered.

A requirement for this particular algorithm to reach consensus is

that every agent both receives information and also sends information to

every other agent, directly or indirectly through other agents. If all information

transfers are weighed equally, the consensus achieved will be the

average of all initial information states. Consensus can also be reached

under looser conditions where there exists an agent that sends information

to every other agent, directly or indirectly.

The changes of the system's behaviour when one uses dierent consensus

algorithms will be discussed, and computer simulations of these will

be provided. An interesting case is where the information (often referring

to location, velocity or acceleration) is received only from agents within a

given distance and thus the information is received from dierent agents

at dierent times. This results in nonlinear algorithms and mostly simulations

and interpretations will be given. An observation is that whether

consensus is achieved or not depends partially on the initial information

states of the agents and the maximum distance for information transfer.

Abstract [sv]

Ett intressant omrade inom matematiken ar att beskriva fenomenet

med ockar och svarmar. Med hjalp av grafteori kan man beskriva ett

system av agenter som skickar information mellan varandra och med hjalp

av algoritmer som beskriver hur varje agents informationen ska uppdateras

sa att konsensus nas.

Om informationen beskriver en position eller foryttning i rummet

kan man observera ett beteende som liknar det hos djurockar eller insektssv

armar. Manga andra tillampningsomraden nns ocksa, till exempel

i system av robotar nar det saknas central styrning och internt beslutstagande

ar onskvart.

I denna rapport kommer olika algoritmer for att uppdatera en agents

status att undersokas for att bestamma vilka krav som nns for att konsensus

skall nas. Forsta delen kommer att behandla ett enklare fall dar

varje agent tar emot information fran en oforanderlig uppsattning agenter.

Specikt sa kommer en algoritm, dar en agents status bestams av

en linjar funktion som beror pa statusen hos de agenter fran vilka information

mottages, att studeras. Ett krav for att denna algoritm ska na

konsensus ar att varje agent bade skickar och tar emot information fran

samtliga ovriga agenter, direkt eller indirekt via andra agenter. Om alla informations

overforingar vags lika sa kommer alla agenter na medelvardet

av agenternas initialvarden. Konsensus kan ocksa nas under mindre restriktiva

villkor, om det nns en agent som skickar information till alla

andra noder (direkt eller indirekt).

Forandringar av systemets beteende vid olika uppdateringsalgoritmer

kommer att studeras och datorsimuleringar av dessa fenomen kommer att

ges. Ett intressant fall ar da informationen (ofta position, hastighet eller

acceleration) endast kan tas emot fran de agenter som nns inom ett givet

avstand. darmed forandras den uppsattning agenter med vilka information

overfors med tiden. Detta resulterar i olinjara algoritmer och framforallt

kommer simulationer och tolkningar av dessa att ges. En observation ar att

om konsensus nas eller inte beror starkt pa densiteten bland agenterna i

utgangslaget samt det maximala avstand vid vilket informationsoverforing

kan ske.

Place, publisher, year, edition, pages
National Category
Engineering and Technology
URN: urn:nbn:se:kth:diva-105773OAI: diva2:572052
Available from: 2012-12-17 Created: 2012-11-26 Last updated: 2014-07-18Bibliographically approved

Open Access in DiVA

fulltext(910 kB)403 downloads
File information
File name FULLTEXT01.pdfFile size 910 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 403 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 111 hits
ReferencesLink to record
Permanent link

Direct link