kth.sePublications KTH
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
Simulation and Evaluation of Swarm Bug Algorithms
KTH, School of Electrical Engineering and Computer Science (EECS).
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Simulering och Utvärdering av Småkrypsalgoritmer för Svärmar (Swedish)
Abstract [en]

Navigation is a major research area within robotics and autonomy. One subproblem of this area is computationally effective algorithms for navigating towards a known target in an unknown environment. A class of algorithms that solve this problem is bug algorithms that have simple rules for navigation and handling unknown obstacles in a two dimensional environment. Lately, these algorithms have seen a renewed interest with the rise of swarm navigation which can more efficiently solve the problem formulation than single agents can. In this thesis, three swarm bug algorithms - SwarmBug1, SwarmAlg1 and SwarmAlg2 - will be simulated and analysed for the purpose of addressing the knowledge gap of practical performance of the algorithms. The goal is to compare the algorithms’ performances in different environments measuring the distributions of travel times and energy consumptions. The implementations are done in the game engine Godot and the experiments are done with a Monte-Carlo simulation, randomising the start and target of each run. The implementations include sensors measurements for positioning and multiple controllers for manoeuvring, aiming to yield realistic results. The results show that the algorithms have different advantages. Swarm-Alg2 exhibits the shortest travel time on average to get one agent to the target while SwarmBug1 proved to be more efficient at getting all the agents to the target. Regarding energy consumption, SwarmAlg2 had the lowest average total energy consumption, and the most even one across the agents, which means that it should be able to travel for the longest time before agents start suffering from energy failure. SwarmBug1’s energy consumption had a higher median but a smaller range of results for each agent.

Abstract [sv]

Navigering är ett stort forskningsområde inom robotik och autonomi. Ett delområde inom navigering är beräkningseffektiva algoritmer för navigering mot ett känt mål i en okänd miljö. Speciellt intressant är algoritmer för svärmar som använder sig av flera agenter (till exempel drönare) som kan kommunicera med varandra för att effektivare lösa problemet samt hantera agentbortfall. Ett exempel på tillämpningsområde för detta är sök- och räddningsinsatser där målet är känt men där det kan finnas hinder på vägen dit som är okända för agenterna. En klass av algoritmer som löser problemet är småkrypslagoritmer som har tagit sin inspiration från hur småkryp rör sig i okända miljöer. I den här rapporten simuleras och analyseras tre småkrypsalgortmer för svärmar - SwarmBug1, SwarmAlg1 och SwarmAlg2 - för att jämföra deras generella tids- och energiåtgång i olika miljöer. Syftet är att bredda förståelsen för algoritmerna, som tidigare endast analyserats teoretiskt. Resultaten visar att de olika algoritmerma har olika styrkor och svagheter. SwarmAlg2 är effektivast på att få fram åtminstone en agent till målet, gällande både tid och energi, medan SwarmBug1 är effektivast på att få samtliga agenter till målet.

Place, publisher, year, edition, pages
2025. , p. 89
Series
TRITA-EECS-EX ; 2025:629
Keywords [en]
Bug Algorithms, Multi-agent Systems, Swarms, Navigation
Keywords [sv]
Småkrypsalgoritmer, Multiagentsystem, Svärmar, Navigering
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-368316OAI: oai:DiVA.org:kth-368316DiVA, id: diva2:1988431
External cooperation
Totalförsvarets Forskningsinstitut (FOI)
Supervisors
Examiners
Available from: 2025-08-18 Created: 2025-08-11 Last updated: 2025-08-18Bibliographically approved

Open Access in DiVA

fulltext(2290 kB)294 downloads
File information
File name FULLTEXT01.pdfFile size 2290 kBChecksum SHA-512
6d4ab8733dfbd585c9022df473df80fd59ded79861a8d50d064cc113187d8db2afe1de9f72a9ab025511754b31ed646d687e5e8c0583bbda3d2b1b76841ef0b8
Type fulltextMimetype application/pdf

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

Search outside of DiVA

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