TITLE:
Complete Coverage Path Planning Based on Improved Area Division
AUTHORS:
Lihuan Ma, Zhuo Sun, Yuan Gao
KEYWORDS:
Generalized Traveling Salesman Problem with Pickup and Delivery, Com-plete Coverage Path Planning, Boustrophedon Cellular Decomposition, Adaptive Large-Neighborhood Search Algorithm, Mobile Robot
JOURNAL NAME:
World Journal of Engineering and Technology,
Vol.11 No.4,
November
30,
2023
ABSTRACT:
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.