Genetic Algorithm-Based Robot Path Planning with the Extraction of Topological Map
Zhen Liu, Jinglue Xu, Hitoshi Iba · 2024
Genetic algorithm (GA) is a common approach for multi-objective path planning. However, conventional GA performs poorly on large-scale complex maps due to the lack of an efficient initialization method and the infeasible solutions generated during the GA search. In this paper, first, we propose an innovative initialization method. The proposed method extracts the division points of the map and constructs a topological map, allowing the initialization of feasible paths based on the fitness function. Second, we calculate the estimated fitness value of each path in the topological map. Paths with low estimated fitness values will not be initialized, reducing the search space. In addition, we improve the crossover of GA, preventing the generation of infeasible paths by utilizing the topological map. The proposed method is compared against Theta*, A *(adjusted to consider smoothness), and conventional genetic algorithms on small and large-scale maps. The proposed method has outperformed previous methods regarding fitness value, reducing the runtime by more than 37% on large-scale maps.