Research On Coverage Path Planning Algorithm

With the continuous improvement of automation technology,it is particularly important to plan reasonable paths for mobile devices under automation technology.The coverage path planning algorithm is a branch of automation technology.It requires the planned path to cover all locations in a given area,and a better path can further save resources and improve efficiency.Most of the existing coverage path planning algorithms plan paths on a grid map,and most algorithms only consider four directions when planning paths according to the priority of directions in a grid map.In view of these problems,this paper proposes different coverage algorithms on the two maps,and summarizes four performance metrics to measure the performance of the algorithm: the percentage of coverage,the percentage of duplicate path,the number of turns and the total travelled distance.The two algorithms proposed in this paper are as follows:(1)DHPF(Direction-Highest-Priority First)algorithm for coverage path planning based on grid maps.This paper sets different priorities for cells in different states and different directions in the grid map,and expands the four adjacent directions into eight directions,and the priorities of the eight directions will change when the mobile device moves.When selecting the next cell to move,it needs to calculate the respective priority of all adjacent cells according to the state and direction firstly,and then selects the cell with the highest priority to move.When the mobile device enters the dead zone,this paper proposes flood-theta* algorithm to plan the shortest escape route while looking for the nearest uncovered cell,reducing the percentage of duplicate paths in the escape process.Experiments show that the algorithm in this paper achieves complete coverage and has certain advantages in the total travelled distance and the percentage of duplicate path.(2)Coverage path planning algorithm based on geometric feature map.Based on the traditional decomposition method,this paper proposes the Contour-Boustrophedon algorithm to decompose the geometric feature map.This algorithm decomposes the working area containing obstacle areas into multiple sub-areas without obstacle areas;then the path of traversing all the sub-areas is converted into the traveling salesman problem(TSP),and this paper proposes the C2O(Christofides-2-optimization)hybrid algorithm to plan a short path to traverse all the sub-areas in a short time;finally,the Dijkstra algorithm is used to plan the connection path between the sub-areas,and the line-of-sight algorithm is proposed to optimize the connection path,reducing the length of the connection path.Experiments show that the path planned by the algorithm can achieve complete coverage of the area,and can reduce the total travelled distance and the percentage of duplicate path.