Date of Award

2019

Publication Type

Master Thesis

Degree Name

M.Sc.

Department

Computer Science

Supervisor

Dan Wu

Rights

info:eu-repo/semantics/openAccess

Abstract

Path planning is an essential task for the robot to navigate and control its motion in any environment. The optimal path needs to be rerouted each time a new obstacle appears in front of the robot in a dynamic environment. This research focuses on the MAX-MIN Ant System Algorithm(MMAS) which is an Ant Colony Algorithm derived from Ant System(AS) and is different from it in terms of the pheromone deposition. The effectiveness of this algorithm to obtain a near optimal solution is illustrated by the means of experimental study. Using a greedier search than the Ant System algorithm is one of the specific characteristics of the MMAS, which will be studied in the research. The robot environment model is represented by a grid which has obstacles whose positions change in each map that is used. Local search routines and diversification mechanisms introduced by the previous researchers are used to enhance the performance of the MMAS algorithm. To implement the MMAS algorithm used in our research, the experiments are performed in Matlab development environment where a simulation program is designed, and the algorithm is implemented in grid maps of sizes starting from the smallest grid 10x10 to the grid of size 400x400. We implemented and analyzed the performance of the algorithm in larger grid environments to understand how it would perform when the search space is too huge; which would enable researchers to use the MMAS algorithm in experiments involving real-life environments. In our experiments, a new obstacle is added after every iteration of the algorithm which makes it challenging for the robots to find the near-optimal path. The performance evaluation of the MMAS algorithm is studied and is also compared to that of the ACO algorithm when implemented in differently sized grid maps.

Download

Share

COinS