Simulation and Evaluation of Swarm Bug Algorithms
2025 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE credits
Student 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
2025-08-182025-08-112025-08-18Bibliographically approved