Path Optimization for Mobile Robots using Genetic Algorithms

Abstract

This article proposes a path planning strategy for mobile robots based on image processing, the visibility graphs technique, and genetic algorithms as searching/optimization tool. This proposal pretends to improve the overall execution time of the path planning strategy against other ones that use visibility graphs with other searching algorithms. The global algorithm starts from a binary image of the robot environment, where the obstacles are represented in white over a black background. After that four keypoints are calculated for each obstacle by applying some image processing algorithms and geometric measurements. Based on the obtained keypoints, a visibility graph is generated, connecting all of these along with the starting point and the ending point, as well as avoiding collisions with the obstacles taking into account a safety distance calculated by means of using an image dilation operation. Finally, a genetic algorithm is used to optimize a valid path from the start to the end passing through the navigation network created by the visibility graph. This implementation was developed using Python programming language and some modules for working with image processing ang genetic algorithms. After several tests, the proposed strategy shows execution times similar to other tested algorithms, which validates its use on applications with a limited number of ob-stacles presented in the environment and low-medium resolution images.