Improved genetic algorithm based on bi-level co-evolution for coverage path planning in irregular region

摘要

Irregular region coverage path planning has been widely applied in robot search tasks and has attracted a lot of attention. This study proposes an improved genetic algorithm based on bi-level co-evolution for coverage path planning (IGA-CPP) in irregular region. The processes of the method are region decomposition, sub-region selection and coverage path generation. The difficult problem is to plan the coverage path of sub-regions after decomposition. The key idea is to design a bi-level co-evolutionary strategy for planning optimized order and coverage path of sub-regions. The genetic algorithm has been improved by introducing the bi-level co-evolutionary strategy into the genetic framework and linearly reducing the population size in each iteration to achieve fast convergence. The improved genetic algorithm is used as computing engine for path length optimization. The performance of IGA-CPP is evaluated by simulation experiments. Optimal control parameters are obtained through multiple comparison experiments. Statistical analysis with other algorithms shows that IGA-CPP is more efficient. It can be concluded that IGA-CPP is workable to obtain optimized coverage path of irregular region.