Bachelor and Master Theses

Title: Using ant colony optimization as pathfinding in a changing environment
Subject: Computer Science
Level: Basic
Description: Ant colony optimization (ACO) is an algorithm that gets its inspiration from the behaviour of real ants, which uses pheromones as an indicator to tell other ants where they have previously walked. The algorithm is not commonly used for pathfinding in a changing environment, but this thesis have investigated if it is a viable option. A* were used for comparison and worked as a reference point as it is the most frequently used algorithm in pathfinding. As such, the goal was to identify if ACO and its characteristics could be used to overcome the weaknesses of A* in conditions where the environment changed in real time. To meet that goal, different methods and variations of ACO was implemented to identify which of them performed better in a changing environment. A backtracking method that makes it easier for the ants to find the goal is also proposed. To test the implementations, three environments were created and used in the experiments. The results showed that A* performed better than all of the other algorithms, in all of the environments, except for its path length. However, even though some of the other algorithms had better path lengths, the other aspects of the results outweighed it. The conclusion drawn, was that the ant based algorithms couldn't overcome the weaknesses of A* and that the speed at which A* can recalculate a path, from scratch, outperforms the ant algorithms even though they have information stored from earlier calculations.
Start date: 2017-03-27
Prel. end date: 2017-06-02
Presentation date: 2017-06-02
Student: Robin Chef
Student: Robin Eriksson
IDT supervisor: Miguel Leon Ortiz
Examinator: Ning Xiong
Ning Xiong, +46-21-151716

Rapport och bilagor


Senaste uppdatering



2017-06-12, 15:22

  • Mälardalen University |
  • Box 883 |
  • 721 23 Västerås/Eskilstuna |
  • 021-101300, 016-153600 |
  • webmaster |
  • Latest update: 2018.08.31