Aplicação de algoritmos genéticos ao problema de planejamento de caminhos com a abordagem de decomposição em células convexas para o caso aproximado

Abstract

This work presents an application of Genetic Algorithms (GA) to solve the path planning problem using the approximate convex cell decomposition method. The algorithm is used to determine the shortest path between the origin and destination points in the connectivity graph generated by the cell decomposition method. The main objective of this study is the evaluation of the performance in the use of the GA of heuristic or adaptive criterion in relation to the use of the algorithm with greedy criterion, Djikstra. Computer simulations using the C language show tests to verify the influence of factors on the computational cost such as population size and the chromosome initialization method. The graphical observation of the configuration space and generation of the trajectory is obtained through an application in SCILAB. For experimental validation of the algorithm, a mobile robotic platform with differential drive was developed that receives the points of the trajectory through a radio link