Path Optimization of Moving Object in Presence of Obstacles Using Messy Genetic Algorithm for N-dimensional Space

Abstract

Optimizing the path of the movement of moving objects such as various robots in the industry can have a significant effect on reducing manufacturing and production time and costs. In this research, using a messy genetic algorithm, a new method is presented to optimize the movement path of a mobile object such as a robot in the presence of multiple obstacles. The movement path can be considered two-dimensional or multi-dimensional, and the obstacles in the path are assumed to be circles and spheres. The method used is that first, several chromosomes are created in the zero generation and their fitness is calculated. Then, using competitive selection, the parents of the new generation are created and from there the chromosomes of the next generation are made, and their fitness is calculated. This process continues until the considered condition, i.e. the ratio of the average fitness divided by maximum fitness in each generation is satisfied. Since in the messy genetic algorithm, the length of the chromosome can be variable, the proposed algorithm can examine all types of paths with a variable number of points depending on the existing obstacles and with high efficiency, find the shortest path with an approximate difference of 3.4 percentage compared to the ideal path. This method can optimize even paths with more than three dimensions.