Abstract: Most of the sweeping robots have the problems of high repetition rate and low coverage rate. When planning the full coverage path and encountering dense and scattered obstacle areas, the route planning is messy and even can’t be covered. Therefore, this paper designs a full coverage path planning algorithm based on divide and conquer idea. By constructing a number of line segments on the map, the local path segments are connected according to the principle of minimum Manhattan distance between the endpoints of line segments to form a number of arcuate circuit blocks. Then, divide and conquer algorithm is used to realize the global matching of the nearest end points of each bow block and connect them. A full coverage route with uniform path is generated. Compared with the cow tillage unit decomposition combined with bio inspired neural network coverage algorithm, the analysis shows that in the dense and scattered obstacle areas, the algorithm can plan a neat and smooth passable path, the coverage rate can reach 91.3%, the repetition rate is reduced by 39.3%, and the time cost is reduced by 28.1%.

Key words: full coverage path planning, manhattan distance, divide and conquer algorithm, line sequence, sweeping robot