Simulation and Evaluation of Swarm Bug Algorithms

Sammanfattning

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.