Frontiers in Computing and Intelligent Systems ISSN: 2832-6024 | Vol. 4, No. 1, 2023 39 Global Path Planning Method for Parks based on Complete Coverage Cleaning Task Xiaoke Ming *, Shaodong Jiang, Yue Duan School of Automotive and Transportation Engineering, Hefei University of Technology, Hefei 230009, China Abstract: In this paper, based on a small driving sanitation platform of an enterprise, the global path planning method in the unmanned decision system is studied and designed for the characteristics of the park environment and the task requirements. The operation space of the sanitation platform is divided into rectangular square cleaning area and lane cleaning area based on the task demand of full coverage of the park. For the sweeping task of the lane area, multiple parallel sweeping reference paths are generated by raster erosion of the lane map; for the sweeping task of the rectangular square, this paper proposes an improved bow-shaped full coverage algorithm combining forward and reverse based on the steering capacity constraint of the sanitation vehicle. Finally, the path articulation algorithm is used to connect the sweeping paths of suboperating areas to form a global reference path for the sweeping operation of the park. Keywords: Low Speed Driverless Technology; Complete Coverage Path Planning; Park Sanitation. 1. Introduction The research and exploration of driverless technology in low-speed scenarios has the advantages of low testing risk and low testing cost, which helps accelerate the development of driverless technology for passenger cars. As a pragmatic field for the landing of driverless technology, the sanitation industry can significantly reduce industry costs, liberate sanitation workers in hot, cold and dusty operating environments, and reduce the occurrence of traffic accidents, which has important research value and practical significance. The task of the unmanned sanitation platform in the park is to complete the garbage cleaning and environmental maintenance of the park without an operator, and the specific method design logic is to achieve full coverage of the park road surface: not only to achieve full coverage of the rectangular square area, but also to complete full coverage of the lane area under the constraints of traffic rules. Complete coverage path planning is different from "point to point" path planning, the final result is to plan a continuous path that starts from the starting position and traverses the whole operation area to the end position, and the path evaluation index is usually the area coverage. The key problem to be solved by full-coverage path planning is to traverse the free area (non-obstacle area) in the operation area to the maximum extent, and effectively avoid all obstacles in the traversal process to achieve no collision[1]. The current mainstream complete coverage path planning methods are reciprocal rule-based[2], spiral rule-based complete coverage methods[3] and artificial intelligence- based complete coverage path planning algorithms[4], which are usually applied to mobile robots for different purposes. When applied to sanitation platforms with larger vehicles and lane environments with traffic rule constraints, the traditional coverage algorithms generate paths that usually have local retrograde and traversal characteristics and do not comply with the constraints of lane traffic rules, while the operational complexity is high and the coverage is insufficient. The design of coverage algorithms for unmanned sanitation platforms in parks needs further research. 2. Methodology 2.1. Environmental Modeling The raster map, also called occupancy raster map, divides the operation space of the unmanned sanitation platform into a series of discrete rasters of the same size, coordinates the discrete rasters in a two-dimensional array, and each raster has an attribute value indicating the probability that the raster is occupied, and when the occupation probability is greater than a certain threshold, the point is an obstacle point, and vice versa, it is a free space[5]. The raster is used to express the environmental information of the operation space, and then the model construction of the whole environment is completed. After finishing the environment modeling, the path planning problem is transformed into: seeking a line from the starting raster to the ending raster without passing through the obstacle raster in between; and the full-coverage traversal problem is transformed into covering the traversal of all the free-space rasters. The raster representation is simple, easy to express, and easy to save data, which is conducive to subsequent algorithm design and map data update, so it is widely used in the field of intelligent vehicles for environmental modeling. In order to reduce the difficulty of environment modeling, the irregular obstacles in the operation space are regularized in this paper, and the specific transformation is as follows: (1) Where, occupancy indicates the ratio of obstacle to the area of this raster; Ratio is the threshold value of occupancy set in this paper. After the above processing, the whole environment map consists of obstacle raster and free raster. In this paper, we study the full-coverage traversal of the sweeping task, so the grid needs to record the coverage information. According to whether the grid is covered or not, the grid can be divided into "covered grid" and "uncovered grid", and there are three types of grid: free uncovered space, free covered space and obstacle area, as shown in Table 1. The specific coding situation is shown in Table 1. 40 Table 1. Grid state coding table Free Grid Obstacle Grid Uncovered 0 2 Covered 1 The rasterized environment modeling process of the operation space is shown in Figure 1, with the initial environment map on the left and the rasterized map on the right. The numerical matrix corresponding to the map in Fig. 1 is shown in Fig. 2. In the initial case, the sanitation platform has not started to cover the operation space for cleaning, and there is no covered raster in the environment, so the digital matrix of the rasterized map in the initial case is shown in Figure 2 on the left. When the full coverage of the operation space is completed, the uncovered grids all become covered grids, and the numerical matrix of the grid map is shown in the right figure of Fig. 2 at this time. Figure 1. Environmental map gridding 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2 2 0 0 2 2 0 0 2 0 2 2 0 0 2 2 2 0 2 0 2 2 0 0 2 2 2 0 0 0 0 0 0 0 2 2 2 2 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 2 1 1 2 2 1 1 2 1 2 2 1 1 2 2 2 1 2 1 2 2 1 1 2 2 2 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Figure 2. Grid map digital matrix 2.2. Complete Coverage Path Generation Method for Lane Area based on Raster Erosion In order to meet the task demand of lane coverage, this paper proposes a global path generation algorithm with inward scaling along the lane boundary to the lane centerline, which can effectively avoid the retrograde and traverse characteristics of the path generated by traditional coverage algorithms, and the main ideas are: (1) The lane shape is a circular loop, including an outer contour line and an inner contour line. (2) The discrete point data of latitude and longitude of the lane boundary and the centerline of the lane are obtained through map acquisition, and the contour lines of the inner and outer boundaries of the lane are obtained through multi-point interpolation, and the contour line data points of the lane boundary are transformed into a raster map; (2) Considering the size of the sanitation platform and the cleaning margin, the outer lane boundary contour line is inwardly expanded by a certain distance along the lane normal direction to generate a line parallel to the outer lane boundary, which is the initial cleaning path of the outer circle of the sanitation platform; similarly, the inner lane boundary contour line is outwardly expanded by a certain distance along the lane normal direction to generate a line parallel to the inner lane boundary, which is the initial reference path of the inner circle of the sanitation platform. path, thus generating the sweeping path of the sanitation platform "sweeping along the edge", which is located in the outermost and innermost circles of the global reference path; (3) Repeat step (2), in which the overlap of the sweeping range is considered, i.e. the repetition margin of the coverage area, until the trajectory is extended to the center line of the lane, and the complete coverage of the lane is completed; (4) Consider the traffic direction constraint of two lanes in both directions, reasonably select the path connection point of the inner and outer lanes, and make reasonable turnaround and lane change planning. Figure 3. Runge phenomenon In the process of inward scaling along the lane normal direction, the tangent function of the lane boundary should be clarified first, but the lane boundary is often irregularly connected segments instead of smooth curves due to the influence of the acquisition accuracy, and in the process of fitting the path function by constructing polynomial interpolation with uniform nodes, as the number of fitted 41 points n increases, the middle part still has a good fitting accuracy, but at the two ends of the interpolation interval The Runge phenomenon is mainly due to the propagation of the error from the higher order derivatives in the error term. is large, the acquisition accuracy is difficult to be guaranteed[6]. In order to realize the algorithmic idea of inward scaling along the lane normal direction, the collected lane boundary information has to be processed appropriately, and this paper uses digital image processing to realize the above requirements. Since global path planning is generally static based on a priori map information, digital image processing is considered to generate the initial global path. "Erosion" is a digital image processing approach in digital morphology, which is generally used to process grayscale maps. A grayscale map has 256 gray levels, where 0 means all black and 255 means all white; a binary image is an image with only two gray levels, i.e., all pixels in the image have only two gray values, 0 and 255, which are black and white, respectively, and a raster map is a typical binary image. Erosion is used to enlarge dark areas in digital image processing problems[7]. The erosion operation requires the provision of the image to be processed as well as the design structure elements, as follows: 12 112 111 234 112 195 215 202 45 12 31 15 56 123 122 75 Figure 4. Digital matrix to be processed (1) Given a numerical matrix, i.e., the image to be processed, as shown in Figure 4, the matrix value is the grayscale value of the pixel; (2) Design a structure element, as shown in Figure 5, which is also called a "nucleus" and determines the local erosion per pixel point; the structure element can be rectangular, elliptical, or cross-shaped. In this paper, we design a 3 × 3 matrix inside the cross-hatch structure element, the centered pixel is the pixel we want to process; 0 0 1 1 1 1 0 0 1 Figure 5. Structural unit (3) Overlaying the structural element into the original image, as shown in Figure 6, after the convolution calculation, the value of the pixel point is rewritten to the minimum value within a 3 × 3 cross-cross neighborhoods centered on the pixel point, and the dark region is expanded; (4) Change the number of iterations, i.e., perform multiple erosion operations on the current image in the scale range. (5) Change the shape or scale size of the structural element, that is, change the range of erosion operations, for example, a rectangular 4 × 4 structural element indicates that the value at the pixel point to be processed is rewritten to the minimum value within the 4 × 4 rectangular neighborhoods. 12 112 111 234 112 195 215 202 45 12 31 12 56 123 122 75 12 112 111 234 112 195 215 202 45 12 31 15 56 123 122 75 Figure 6. Grid corrosion process and results It can be easily seen from the figure that the dark area is expanded after the convolution calculation, which rewrites the value of the pixel point to the minimum value in the range of the structural element neighborhood where the pixel point is located. In case of raster maps, the image to be processed has only two gray values, 0 and 255, and the erosion means that the black area is expanded. The main purpose of the gradient calculation is to display the edge information, calculated by: corroded image - the original image; the outer circle image minus the inner circle image, the obtained is the edge information. Based on the above raster erosion function to achieve lane boundary processing to obtain multi-lap paths is as follows: (1) The lane is initially rasterized, as shown in Figure 7, the upper and lower boundaries of the lane are outside the obstacle area, which is the black inaccessible area, and the middle area is the lane, which is the white passable area. (b) Due to the specificity of the lane clearing environment, the lane area in the a priori map does not have an obstacle, i.e., a black raster, present; Figure 7. Lane original grid diagram (2) Firstly, the acquisition of the first lap path is performed: Erosion operation is performed on the lower boundary black raster toward the lane, and an expanded black point can be obtained in the lane area, as shown in Figure 8. The outermost circle of the white raster of the lane continues to traverse the operation, that is, to complete the corrosion of the 42 outermost circle of the raster of the lane, turning it all to black, as shown in Figure 9. Figure 8. Preliminary corrosion schematic diagram of lane grid map Figure 9. The first circle path diagram of lane grid map Select the appropriate number of iterations, that is, the appropriate corrosion scale, comprehensive consideration of the sanitation platform body size and sweeping margin, and continue to traverse the operation; perform gradient calculation, you can get the edge information that we require for the first circle path; (3) Continue to perform the above steps, in the corrosion iteration process, consider the repeat margin of the sanitation platform sweeping area, select the appropriate number of iterations, as shown in Figures 10 and 11, you can get the corresponding second circle path; Figure 10. The second circle path acquisition process of lane grid map Figure 11. The second circle path schematic diagram of lane grid map (4) Repeat the above steps, if the generated path crosses the center line of the lane, the corrosion operation of the lane is terminated; (5) From the upper border of the lane black raster to the inner lane area to perform corrosion operations, repeat the above steps, that is, to obtain the cover path of the upper lane, as shown in Figure 12, and finally get the entire path of the lane area after the raster corrosion. Figure 12. All path diagram of the lane area after grid corrosion Connection between different circles of paths: distinguish the connection between different sub-regions, set the starting point of the outermost circle, the starting point of the path of the next circle is set similar to the starting line setting of different circles of the circular runway, consider the path advance of the different circles of the sanitation platform path articulation, and so on; the inner and outer circle paths on both sides of the centerline of the lane are articulated through the path fitting method below. 2.3. Rectangular Square Area Coverage Path Generation Method based on Improved Bowtie Rule The park environment usually has rectangular square area for crowd gathering in addition to the lane area, and the square area is rasterized to obtain a local rectangular-shaped raster map. The bow-shaped coverage algorithm is usually applied to the robot coverage scene, because the robot and the micro sweeper are small in size, while the steering mode is omnidirectional and not constrained by the steering capacity of the steering mechanism, the inner area of the arc corresponding to the minimum turning radius r is the area that cannot be covered by the steering body of this vehicle, so it is directly applied to the sanitation platform, and when driving to the area boundary "U U-turn" turnaround, as shown in Figure 13, due to the large turning radius, it is difficult to complete full coverage of the area. 43 Figure 13. U-shaped turning diagram In this paper, an improved "bow-shaped" coverage algorithm is proposed to generate coverage paths under the constraint of minimum turning radius to improve the coverage of turnaround areas. The specific idea is to apply two bow-shaped paths in opposite directions. Firstly, we increase the running step of the turnaround operation in the secondary operation direction to generate the bow offset distance in the secondary operation direction adaptively and reserve the embedding space for the reverse bow path. Travel to the end position, take the end point as the starting point and execute the reverse bowtie operation to embed between two adjacent forward bowtie paths in the primary direction. According to the calculation of the minimum turning radius of the sanitation platform, the width between the two U- shaped adjacent covered paths is greater than the width of the vehicle, and the reverse path is difficult to cover the restricted area on the inside of the turnaround arc. In order to solve this problem, the real-life narrow road turnaround will first adopt the strategy of pre-reverse steering wheel driving for a distance to increase the turning radius, effectively completing the narrow road turnaround operation and reducing the burden on the steering mechanism. In this paper, we use Dubins curve interpolation[8] to simulate the above process and fit the trajectory of the turnaround to solve the problem that the reverse path is difficult to cover the inner area of the turnaround arc. As shown in Figure 14. 0 X Y Start Goal C1 p1 C2 p2 C3 p3 pt2pt1 θ Figure 14. The U-turn path fitted by Dubins The turnaround path fitted from the Dubins curve is calculated as follows: Based on the mathematical relationship, it is obtained that | | 2 | | 2 3 | | 2 4 Let be the angle between and . The lengths of the three sides of the triangle are known, and according to the cosine theorem 4 5 The final result can be obtained as 2 , 2 6 The midpoints of vectors , are the curvature circle tangent points , , and the turnaround path curve can be obtained by connecting the circumferential arc from start to , the circumferential arcs of and , and the circumferential arc from to Goal. Accordingly, an improved bow-shaped coverage algorithm is designed: firstly, the rectangular square area is swept along the edge, and the distance from the top of the arc of the turnaround path curve is calculated based on the minimum turning radius of the sanitation platform, leaving a margin of 180 degree turnaround turns for the following coverage algorithm. The area to be operated by the improved algorithm is thus a reduced rectangular area or U-shaped area. In the rectangular square raster map, (0,0) is the raster coordinate of the lower left corner of the rectangular region, the length of the rectangular square region along the primary operation direction of the sanitation platform is , the width of the secondary operation direction is , and the vehicle width of the sanitation platform is . (1) First, determine the number of round-trip sweeping of the unmanned sanitation platform in the main operation direction: for the square area reserved for two circles of cleaning along the edge, the number of round-trip sweeping of the sanitation platform in the main operation direction 4 2 7 1, 2, 8 (2) Next, determine the starting and ending positions for performing forward bow sweep: starting position , and ending position , . , 2 , 2 9 , 4 , 2 , , 2 , 10 The specific algorithm principle is as follows: Step1: Initialize the starting coordinates of the rectangular area to be cleared as , ; Step2: Judge the parity of /2 , if it is odd, 1 ; if it is even, 1 ; the vertical coordinates remain unchanged; Step3: Judge whether x= / 4 is equal 44 to 0 or 1. If it is equal to 0 or 1, continue to judge whether the current , is , , if it is, turn to Step6 for execution; if it is not, turn to Step4 for execution; if it is not equal to 0 or 1, turn to Step2 for execution; Step4: 1 , the horizontal coordinate remains unchanged; Step5: Determine whether (y-y_1)/2d is an integer? If yes, go to Step2 and continue, otherwise go to Step4 and continue; Step6: y=y-1 with the same horizontal coordinate; Step7: Determine whether /2 is an integer? If yes, go to Step8, otherwise go to Step6 to continue the execution; Step8: Determine the parity of /2 ? If it is even, 1 ; if it is odd, 1 ; the vertical coordinates remain unchanged; Step9 : Determine whether / 4 is equal to 0 or 1; if it is, continue to determine y=y+1; if so, exit the loop; if not, return to Step6; if it is not equal to 0 or 1, return to Step8; Step10: Use Dubins curve for path smoothing; Finally get the schematic diagram of the full coverage of the rectangular area as shown in Figure 15. Figure 15. Improved boustrophedon complete coverage path planning diagram 2.4. Sub-area Articulation Design The park environment is divided into a lane area and a rectangular plaza area, and the two sub-areas are connected to accomplish the final goal of full park coverage. The connection between the sub-areas can be considered as a "point-to-point" spatial shortest path planning. The shortest path search between two sub-regions is the key to improve the cleaning efficiency when the sanitation platform ends the coverage task of the previous sub-region and starts the coverage task of the next sub-region. The articulation task between sub-operating areas includes two parts: determining the starting end of sub-operating areas and designing the articulation method of sub-operating areas. Firstly, we divide different operation areas according to the sweeping task, and choose the covering methods of the last two sections respectively, determine the vehicle orientation of the sanitation platform at the beginning and end of the task in different operation areas according to different task logics, and choose a suitable pathfinding algorithm for the connection.Hybrid A* algorithm is a kind of improvement of the standard A* algorithm, by which can make the path planned by A* algorithm meet the vehicle kinematics. 3. Results and Discussion 3.1. Experimental Program Design Experimental purpose: To verify whether the global reference path results output by the global path planning module are correct and reasonable, and to evaluate the coverage index of the global path. Experimental apparatus and equipment: Modified small driving sanitation platform with the previous sensor selection: multi-line LIDAR + millimeter wave radar + ultrasonic radar + Mobileye + inertial guidance + embedded platform, the experimental platform is shown in Figure 16. Figure 16. Experimental platform Experimental protocol: Before the experiment starts, the road network file of the park environment to be cleared needs to be provided. The GPS points of the road are sampled according to the GPS positioning information, and the sampling frequency is 10HZ. The collected path points include latitude and longitude information, a priori obstacle information, and obstacle type information, which are stored in the road network file with the information of the structure. The sanitation platform will automatically generate the global reference path and load the global path file when carrying out the unmanned cleaning task. The environment sensing module will fuse the real-time positional information, environmental obstacle information and global reference path into a sensing map based on the sanitation platform. Meanwhile, in order to verify the rationality of the decision logic of the behavior decision module, several different working conditions are designed based on different driving states, and the performance of the behavior decision module is analyzed according to the decision results. The fixed operating speed of the sanitation platform in this experiment is 6km/h, the warning braking distance is 2m, and the decision moment interval is 100ms. 3.2. Global Path Planning Module Output Records The satellite view of the experimental site is shown in Figure 17. Figure 18 shows the global reference path results of the unmanned sanitation platform performing a full-coverage autonomous cleaning task in the park. In the lane area, the sanitation platform at right-angle turns is limited by its own vehicle size and steering capacity, making it difficult to completely cover the dead-end area. The overall coverage rate is 98.6%. 45 Figure 17. Satellite map of experimental site Figure 18. Global path coverage results In the rectangular square area, the sanitation platform performs 180-degree turnaround at the sweeping boundary, and the steering restricted area on the inside of the turn formed by three arcs is not completely covered, and the overall coverage rate is 99.4%. The connection area between the rectangular square area and the lane area is not constrained by traffic rules, and the coverage of the connection area can be achieved by reciprocating sweeping in the actual cleaning process. The reference path is smooth overall, with smooth connection and suitable curvature, which is easy for the control system to track and execute. The path repetition redundancy rate for performing the full coverage task is 5.2%, which effectively completes the full coverage cleaning task of the park. 4. Conclusion This chapter is the design of the global path planning module of the decision system of the unmanned sanitation platform. Unlike the "point-to-point" driving task, the unmanned sanitation platform performs the task of cleaning the park, i.e., completing the regional traversal of the park road, so the main body of the global path planning is the design of the full-coverage path algorithm. Firstly, the environment modeling of the operation environment is carried out, and the raster map is selected to model the environment map, and the 3D environment is transformed into a 2D raster map to effectively characterize the operation environment. Then, the research work is carried out for the sweeping task and the difficulty of sweeping in the lane area and the rectangular square area. For the sweeping task in the lane area, the traditional coverage algorithm generates paths based on the requirement of the shortest local path or the highest coverage, thus it is difficult to avoid local retrograde and crossing behaviors, which do not comply with the constraints of lane traffic rules. Considering the static characteristics of the global reference path, the lane map is rasterly eroded with digital image processing to generate multiple parallel lane sweeping reference paths, followed by path smoothing considering the kinematic constraints of the car body; for the sweeping task of rectangular squares, an improved bow-shaped coverage algorithm is proposed, which calculates the adaptive reverse bow offset distance by analyzing the structural features of the area to be cleared The proposed algorithm is to calculate the adaptive bowtie offset distance by analyzing the structural features of the area to be cleared, leaving the vehicle embedding width of the reverse bowtie path, and using Dubins curve to connect the turnaround position point traces at the end of the cleared area to achieve the coverage of the steering restricted area so that it meets the constraint of the minimum turning radius of the vehicle. Finally, Hybrid A* algorithm is used for sub-region articulation to complete the global path generation for the park sweeping task. References [1] Choset H. Coverage for robotics–a survey of recent results[J]. Annals of mathematics and artificial intelligence, 2001, 31: 113-126. [2] Choset H, Pignon P. Coverage path planning: The boustrophedon cellular decomposition[C]//Field and service robotics. Springer London, 1998: 203-209. [3] Choset H. Coverage of known spaces: The boustrophedon cellular decomposition[J]. Autonomous Robots, 2000, 9: 247- 253. [4] Kyaw P T, Paing A, Thu T T, et al. Coverage path planning for decomposition reconfigurable grid-maps using deep reinforcement learning based travelling salesman problem[J]. IEEE Access, 2020, 8: 225945-225956. [5] Boschian V, Pruski A. Grid modeling of robot cells: A memory-efficient approach[J]. Journal of Intelligent and robotic Systems, 1993, 8: 201-223. [6] Han L, Yashiro H, Nejad H T N, et al. Bezier curve based path planning for autonomous vehicle in urban environment [C]// 2010 IEEE intelligent vehicles symposium. IEEE, 2010: 1036- 1042. [7] Zhang S, Wu Y, Ogai H. Spatial attention for autonomous decision-making in highway scene[C]//2020 59th Annual Conference of the Society of Instrument and Control Engineers of Japan (SICE). IEEE, 2020: 1435-1440. [8] Shkel A M, Lumelsky V. Classification of the Dubins set[J]. Robotics and Autonomous Systems, 2001, 34(4): 179-202.