关键词: 全区域覆盖路径规划, 遗传算法, 矩形分解法, 模板算法

Abstract: A special kind of path planning is complete coverage path planning.There are a lot of algorithms on this problem have been developed，e.g.template based，cellular decomposition.But these algorithms just cover the complete area；they are not designed to optimize the process.This paper presents a method of complete coverage path planning based on genetic algorithms，which combine the advantages of cellular decomposition and template algorithm.The environment is divided in sub-regions as in rectangular decomposition method，and then Genetic Algorithms（GA） is used to compute and find the order of the sub-regions and the appropriate template for each region. The algorithm is tested in the virtual environment；the simulation results confirm the feasibility of this method.

Key words: complete coverage path planning, Genetic Algorithms（GA）, rectangular decomposition method, template algorithm