RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Drones without a master: Resource efficiency in consensus-reaching topologies
KTH, Skolan för elektroteknik och datavetenskap (EECS).
KTH, Skolan för elektroteknik och datavetenskap (EECS).
2019 (engelsk)Independent thesis Basic level (degree of Bachelor), 10 poäng / 15 hpOppgaveAlternativ tittel
Drönare utan mästare : Resurseffektiva konsensustopologier (svensk)
Abstract [en]

In this study we have compared five different heuristic algorithms for adding edges to existing graphs with the goal of improving convergence rate for reaching consensus. This while keeping the cost of adding edges, and thus sending more signals, in mind. Finding a suitable algorithm for this purpose would equate to monetary cost savings and inference speed in multi-agent networks. The study found that simulated annealing performed the best with regards to finding the best solution on multiple graphs, performing the best in average and time complexity of finding the solutions. However, it was not by a significant margin but alongside our own heuristic named degree difference, they could in conjunction find the optimal solution in every test and their collective complexity is still feasible. The study did not find any rule of thumb for adding edges, except that disregarding costs and only focusing on improving convergence rate worked well. Future work would be to take more factors into consideration to make the scenarios more realistic, such as avoiding single points of failure in a network.

Abstract [sv]

Den här studien har jämfört fem olika heuristiska algoritmer för att att lägga till kanter till befintliga grafer med målet att förbättra konvergeringshastigheten för att nå konsensus. Samtidigt hålls kostnaden för att lägga till kanter, och därmed sända fler signaler, i åtanke. Att hitta en lämplig algoritm för detta ändamål skulle ge monetära besparingar och slutledningshastighet i multi-agentnät. Studien visade att simulerad härdning gjorde bäst ifrån sig med avseende på att hitta den bästa lösningen på flera grafer, prestera det bästa i genomsnitt och tidskomplexitet att hitta lösningarna. Det var dock inte med en betydande marginal. Vid sidan av vår egen heuristik vid namn degree difference kunde de dock tillsammans hitta den optimala lösningen i varje test och deras kollektiva komplexitet är fortfarande rimlig. Studien hittade inte någon tumregel för att lägga till kanter, förutom att bortse från kostnader och bara fokusera på att förbättra konvergenshastigheten fungerade bra. Framtida arbete skulle vara att ta hänsyn till fler faktorer för att göra scenarierna mer realistiska, till exempel att undvika svaga punkter i ett nätverk.

sted, utgiver, år, opplag, sider
2019. , s. 29
Serie
TRITA-EECS-EX ; 2019:394
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-259356OAI: oai:DiVA.org:kth-259356DiVA, id: diva2:1351129
Veileder
Examiner
Tilgjengelig fra: 2019-09-13 Laget: 2019-09-13 Sist oppdatert: 2019-09-13bibliografisk kontrollert

Open Access i DiVA

fulltext(1044 kB)4 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1044 kBChecksum SHA-512
814f1527f93828c95704096c770354bfeb626068b2d21683ffc572c61c2e0c697da171db8c7cf7b1c7bd371380df722fd1fdd58977c46754b9b0fdd11302dd3d
Type fulltextMimetype application/pdf

Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 4 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 47 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf