Complete Coverage Path Planning Based on Improved Area Division

It is difficult to solve complete coverage path planning directly in the obstructed area. Therefore, in this paper, we propose a method of complete coverage path planning with improved area division. Firstly, the boustrophedon cell decomposition method is used to partition the map into sub-regions. The complete coverage paths within each sub-region are obtained by the Boustrophedon back-and-forth motions, and the order of traversal of the sub-regions is then described as a generalised traveling salesman problem with pickup and delivery based on the relative positions of the vertices of each sub-region. An adaptive large neighbourhood algorithm is proposed to quickly obtain solution results in traversal order. The effectiveness of the improved algorithm on traversal cost reduction is verified in this paper through multiple sets of experiments.