# Research on the Cleaning Method of Unmanned Sweeper Based on Target Distribution Situation Analysis
## 3 Proposed Methodology
### Optimal Sweeping Path Planning Based on Simulated Annealing Algorithm
#### 3.2.2 Path Planning for a Single Convex Hull Set  
Then, full-coverage path planning for a single Convex Hull set of garbage regions is performed. Depending on the size of the convex Hull, there will be different sweeping strategies as shown in Figure 11. For long striped areas, the paths are straight lines. For oval areas, the paths are zigzags, and for large polygonal areas, the paths are bow ties. The sweeping task can be described in two dimensions, and the size of the camera footprint, i.e., the area of the ground captured in one frame, is \(L\times W\), as shown in Figure 11, where \(l\) and \(w\) are the length and width of the sweeper. Assuming that there is no forbidden area to visit in the target area, we assume that the unmanned sweeper will travel to the location \(p_{0}\) or \(p_{1}\) after completing the sweeping work in this camera frame. Therefore, the goal of the TSP-CPP problem considered here is to find the best path that traverses all garbage points so that the unmanned sweeper will sweep the garbage along the path and minimize the total travel cost. The back-and-forth pattern can generate a back-and-forth pattern path (BFPs) for covering a single convex polygon region. Back-and-forth-CPP (BF-CPP) greatly simplifies path design and is easy to implement, so it is adopted by many CPP methods. As shown in Figure 11a, the BFP of a convex polygonal region can be found by a set of parallel lines of support (LOS). The distance between the two lines of support becomes the span of the convex polygon region. The direction of path generation, i.e., the direction of the sweep line, is the forward direction of the sweeper. As shown in Figure 11d, a rectangular area to be swept has been identified according to the previous steps, and given the direction of sweeping, where W is the width of the area to be swept and w is the width of the sweeper, the minimum number of flight lines to completely cover the area is \(\frac{W}{w}\). Then, cell decomposition is executed to decompose the region into a set of sub-regions along the flight line. Then, rectangular cells that only cover the sub-regions are constructed. To ensure full coverage, we set the width of the first and last cell to w and the width of the middle cell to \(\frac{(w+d)}{2}\), with \(d\) being the distance between the two flight lines, where  
\[d=\frac{W-w}{[\frac{W}{w-1}]} \tag{1}\]  
Since the frequent acceleration and deceleration of the sweeper tend to increase the travel time and travel cost, the algorithm of this module needs to reduce the number of turns of the BFPs as much as possible. As shown in Figure 11a, the width of the convex polygon is smaller than the width \(w\) of the sweeper when the minimum number of turns is \(1\). As shown in Figure 11b-d, the number of turns of the BFP is \(2(\frac{W}{w}-1)\) when the width of the garbage area \(W>w\). The exact computation progress is described in Algorithm 2. Figure 10: Transformation of garbage regions into Convex Hull sets. Where (**a**) represents the set of points to be included. (**b**) represents the Convex Hull by using the Graham scanning method. The optimal travel path is constrained by the order of visiting individual garbage areas as well as the entry and exit locations, and although a BFP can be found within a single area with a minimum number of turns, its combination with other areas may not lead to the optimal travel path. Therefore, we tend to pre-select 2-4 feasible BFPs with lower travel costs when CPP is performed for a single area. \(q_{0},q_{1},q_{2},q_{3}\) are all possible starting points for travel paths as shown in Figure 11d, and the exact choice of which one  
Figure 11: **Left**: Two-dimensional spatial description of the cleaning task. **Right**: Coverage path planning schematic for a single garbage area. Where (**a**) is straight lines. (**b**) is zigzag, (**c**,**d**) are bow ties. And the arrows show the direction of the sweeper’s progress, the dots show the start and end points.