Collision free path planning algorithms for robot navigation problem

Abstract

Path planning problem, including maze navigation is a challenging topic in robotics. Indeed, a significant amount of research has been devoted to this problem in recent years. Genetic algorithm is a popular approach that searches for an optimal solution in given set of solutions. Considering via points as genes in a chromosome will provide a number of possible solutions on a grid map of paths. In this case, path distances that each chromosome creates can be regarded as a fitness measure for the corresponding chromosome. In some cases, a solution path passes through an obstacle. Assuming that the shape of an obstacle is a circle, such random solutions can easily be eliminated by setting-up simple equation between a line created by two via points and the obstacle. The ant colony optimization algorithm is another approach to solve this problem. Each ant drops a quantity of artificial pheromone on every point that the ant passes through. This pheromone simply changes the probability that the next ant becomes attracted to a particular grid point. Since each ant will make a decision at every grid point that it encounters, it is possible that an ant may wander around the grid map or may become stuck among local grid points. In order to prevent this phenomena the proposed solution adapted a global attraction term which guides ants to head toward the destination point. This thesis addresses methods of the path finding problem using these two different approaches. Both algorithms are tested and compared in the result section. The experiment results demonstrate that these two methods have a great potential to solve the proposed problem.