Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Drones without a master: Resource efficiency in consensus-reaching topologies
KTH, School of Electrical Engineering and Computer Science (EECS).
KTH, School of Electrical Engineering and Computer Science (EECS).
2019 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Drönare utan mästare : Resurseffektiva konsensustopologier (Swedish)
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.

Place, publisher, year, edition, pages
2019. , p. 29
Series
TRITA-EECS-EX ; 2019:394
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-259356OAI: oai:DiVA.org:kth-259356DiVA, id: diva2:1351129
Supervisors
Examiners
Available from: 2019-09-13 Created: 2019-09-13 Last updated: 2019-09-13Bibliographically approved

Open Access in DiVA

fulltext(1044 kB)4 downloads
File information
File name FULLTEXT01.pdfFile size 1044 kBChecksum SHA-512
814f1527f93828c95704096c770354bfeb626068b2d21683ffc572c61c2e0c697da171db8c7cf7b1c7bd371380df722fd1fdd58977c46754b9b0fdd11302dd3d
Type fulltextMimetype application/pdf

By organisation
School of Electrical Engineering and Computer Science (EECS)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 4 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

urn-nbn

Altmetric score

urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf