Path generation device using a genetic algorithm and its operating method

Device for generating paths using a genetic algorithm based on a node probability model

This technology builds a node probability model by analyzing the frequency of nodes in dominant individuals from previous generations when generating robot paths based on a genetic algorithm. It then uses this model to generate paths for the next generation and optimizes obstacle-avoidance paths using edge information.

Conventional path generation methods using genetic algorithms require numerous parameters, such as crossover and mutation rates, to derive an optimal path. Furthermore, because the differences in information between generations are small, they require significant computational power and time to reach convergence.

This technology selects dominant individuals based on the evaluation values of paths from previous generations and determines a node probability model based on the inclusion ratio of nodes within those paths, thereby increasing the probability of successful path generation. Additionally, it defines node pairs without obstacles as "edge information" to reset the node connection sequence, which skips the obstacle-checking phase and improves computational efficiency.

‍

‍

Key Features:

• A path generation device that creates paths over N generations using a genetic algorithm
• A node probability model determination unit that uses paths from previous generations to determine the probability model for nodes to be included in the current generation's paths
• A path generation unit that creates the current generation's paths using the determined node probability model
• A path generation unit that determines nodes to be included in a path using a node probability model and generates paths using edge information of node pairs that are free of obstacles

‍