An Improved STC-Based Full Coverage Path Planning Algorithm for Cleaning Tasks in Large-Scale Unstructured Social Environments Authors: Chao Wang, Wei Dong, Renjie Li, Hui Dong, Huajian Liu, Yongzhuo Gao Published: 2024 ABSTRACT AbstractSome large social environments are expected to use Covered Path Planning (CPP) methods to handle daily tasks such as cleaning and disinfection. These environments are usually large in scale, chaotic in structure, and contain many obstacles. The proposed method is based on the improved SCAN-STC (Spanning Tree Coverage) method and significantly reduces the solution time by optimizing the backtracking module of the algorithm. The proposed method innovatively introduces the concept of optimal backtracking points to sacrifice the spatial complexity of the algorithm to reduce its computational complexity. The necessity of backtracking in such environments is proved to illustrate the generalization ability of the method. Finally, based on secondary coding, the STC solution is explicitly expressed as a continuous and cuttable global path, which can be generalized to Multi-robot Covered Path Planning (MCPP) to avoid the path conflict problem in the multi-robot system, and the paths assigned to each robot have good balance. The method of this study is proven to be effective through simulations in various random environments and a real environment example. Compared with the advanced methods, the computational time is reduced by 82.47%.Keywords: social environments, coverage path planning, STC, back tracking, multi-robot 1. Introduction With the increasing severity of virus outbreaks in recent years [1], the demand for cleaning and disinfection work focused on isolating personnel in public spaces has emerged. The development of artificial intelligence technology and the widespread deployment of various robotic products have gradually increased people’s acceptance of using robots to handle tasks such as cleaning and disinfection [2,3,4]. As a result, many social environments have started utilizing robots for routine cleaning and disinfection tasks [5]. System operation efficiency and robustness are significantly improved using multi-robot coverage path planning (MCPP). Problems studied in this area are required to generate a path covering every point within the work area while avoiding obstacles. The common goals of the MCPP method recognized by most scholars are to minimize the total path length, reduce the secondary coverage rate, minimize the number of turns, and reduce the calculation time. The optimization problem of MCPP is a combinatorial optimization problem with high computational complexity, and is considered NP-hard [6]. As the map scale increases and the percentage of obstacles increases, it becomes significantly more challenging. Therefore, it is important to find a feasible MCPP solution with lower computational complexity, reduced secondary coverage, and reduced turns [7,8]. This study focuses on large unstructured social environments, such as luxury hotels and amusement parks [9], where the challenges of cleaning tasks are mainly reflected in three aspects: (1) these environments are unstructured, large in scale, and contain many obstacles. Due to their large scale, it is difficult for a single robot to complete the task within a limited time. The large number of obstacles causes traditional algorithms to generate many sub-areas in the segmentation stage. The scheduling between these sub-areas becomes a Traveling Salesman Problem (TSP), resulting in high computational complexity [10,11]. It is difficult for the Boustrophedon (BP) method to adapt to environments with many obstacles, resulting in a large amount of secondary coverage and an increase in the total path length [12]. (2) These environments often contain many pedestrians and are human–robot coexistence environments. This makes high-complexity computational methods unable to handle the problem of path conflicts with humans due to their insufficient re-planning capabilities [13]. Therefore, the MCPP method based on mixed integers is also not applicable to the environment. (3) Cleaning robots used in industry experience material wear during the cleaning process, such as excessive use of cleaning fluid or brush wear [14]. Therefore, the invalid paths caused by secondary coverage should be reduced as much as possible. Furthermore, their mobile platforms have nonholonomic constraints, meaning they cannot perform lateral movements [15], thus reducing the number of turns; secondary coverage is crucial to minimizing the length of invalid paths. In order to address these challenges and improve the efficiency of coverage path planning (CPP) operations, and to ensure that our method can be extended to multi-robot systems, a method to reduce the computational complexity of STC by optimizing the backtracking module is proposed. In Section 3.1, this study first constructs a mathematical model for solving CPP for a gridded environment to illustrate the input requirements of this method. In Section 3.2, a feasible framework is proposed to illustrate the relationship between the various modules of the proposed method. In Section 3.3, the concept of optimal backtracking points is innovatively introduced. By optimizing the STC backtracking module, the effect of sacrificing the algorithm space complexity to reduce the computational complexity is achieved. In Section 3.4, secondary encoding is used to make the STC solution explicit as a continuous coverage path, and then balanced cutting is performed. Finally, in Section 3.5, the technical solution for deploying the proposed algorithm to actual robots is introduced. The contributions of this study are as follows: (1) An improved STC algorithm is proposed, which reduces the computational complexity of the algorithm by optimizing the backtracking module. And by proving the necessity of backtracking, the generalization ability of the method to random environments is indirectly explained. (2) A method is proposed to explicitly express the solution of STC as a continuous global reference path using secondary coding and then, distribute the path to the multi-robot system through balanced cutting. This method has been proven to obtain the optimal solution for balance. 2. Related Works The requirements of the CPP problem vary in priority depending on the scenario. In some applications, such as perception-based coverage [16], 3D scanning [17] or other tasks that allow for repeated coverage of the same point, increase the total path length; however, the demand on the robot’s perception performance is significantly reduced. On the other hand, for another class of applications, such as agriculture, demining, and 3D printing, secondary coverage of the same point should be avoided to save energy or prevent damage. For example, in agricultural applications like ground leveling, passing over already processed areas could lead to excessive soil compaction [18]. These methods are more effective for small-sized areas or obstacle-free environments. As a classic method for online CPP, the traditional randomly growing STC algorithm is a well-established approach to achieving complete coverage with low secondary coverage rates [19]. After a period of research, scholars have provided feasible solutions for both online and offline settings [20,21]. The advantage of the online spiral STC is that when there are no obstacles around the tree corresponding to the coverage area, new branches are directly generated. This method avoids redundant scanning and reduces the solving time. Such online methods ensure a high path update frequency, allowing the system to avoid dynamic obstacles in the environment. For single-robot system coverage path planning, these methods offer significant advantages in terms of system robustness. Some of the more advanced online path-planning methods are also capable of achieving complete coverage, particularly in narrow or unexplored environments [22,23]. However, they do not consider the potential path conflicts between multiple robots during area scheduling in multi-robot cooperative complete coverage. Some scholars have also used data-driven methods [24], physical model-based methods [25], and artificial intelligence methods to produce valuable results in solving local planning problems [26,27,28,29,30]. The sensitivity of the BP method to obstacles in the environment makes coverage path planning in such settings rely on area segmentation. As the number of obstacles or non-convex polygonal regions in the environment increases, the number of segmented areas also increases, indirectly turning the scheduling between areas into a TSP. In multi-robot systems, there is also the issue of path conflicts during scheduling. To address this, the system often maintains a priority queue for the robots, where the lower-priority robot stops and waits in case of a path conflict. However, this extends the total system operation time. There are also some offline coverage methods that allow for a higher secondary coverage rate. These methods focus on scenarios where the sensor range or the effective working area is large, making secondary coverage inevitable during the complete coverage process, such as signal coverage tasks performed by a group of robots following a moving object. The method based on regional segmentation has also been discussed by many scholars, but it also leads to the problem of scheduling robots between sub-regions [31,32]. For offline methods targeting multi-robot systems, a representative approach is the Mixed Integer-based MSTC [33,34,35]. This method is insensitive to the shape and distribution of obstacles in the environment and can handle weighted scenarios. However, its high computational complexity makes it unsuitable for large-scale environments. 3. Methodology 3.1. Problem Description Suppose we are given a robot tasked with covering a finite environment using a CPP approach, where the environment’s free space is denoted as S, and the robot’s limited coverage footprint is denoted as the side length of the unit grid cell in the map used in this study. We also assume that the robot can determine its position within the environment and is equipped with sufficiently large distance sensors to detect whether neighboring cells are occupied. This allows the robot to avoid obstacles based on its local map when performing cleaning and disinfection tasks, thereby enhancing the system’s robustness against external disturbances. The parameters used in the study are illustrated in Table 1. Table 1Parameters and settings for modeling.ParametersSettings r Set of robots’ labels for CPP task, indexed by r R Set of robot number for CPP task Ih The number of iterations in the algorithm for STC S1 The area that robot number 1 needs to cover Sall The area that all robots in the system need to cover MR The grid-map corresponding to the CPP problem vr Points on the coverage path of robot numbered r wr Total workload of robot numbered r St Maximum threshold of the intersection of the covered areas Gopt The difference between obtained solution and optimal solutionCRepresents the matrix, where C1 denotes matrix numbered as 1 levn The width of the environment under study hevn The length of the environment under study Nobs The number of cells occupied by obstacles in grid map PSTC The real-time STC solution queue Popt-list The real-time updated superior backtracking point list Pboundary-next The obstacle-adjacent point list Mc The cells list which around the vertex vc The current point used in the loop instruction of the algorithm vnext The Adjacent point used in the instructions of the algorithm Vc One end of the vector or line segment Mv Virtual grid map required for balance cut Algorithm Mstc The STC solution map for Algorithm Cinitial Matrix corresponding to the original grid map Cstc Matrix corresponding to the STC grid map Cvirtual Matrix corresponding to the grid map Mv Pobs The grid edges of Cinitial PSTC-vector Vector matrix of each branch of the STC solution Pobs-vector Vector matrix of each branch of Pobs Iov The number of Vector in Pobs-vector Isv The number of Vector in PSTC-vector Imv The number of cells in Mv Isa The number of cells in Sall Pall Feasible solution for a complete coverage path in Mv Ipa The number of cells in Pall Imr The number of cells in MR Vi The points with STC solution explicitization path Pr The coverage path assigned to the robot, indexed by r e1 Global Navigation Path Error Value e2 Local Planning Path Error Value eh1 Permissible Error for Global Navigation Planning eh2 Permissible Error for Local Navigation Planning xglobal Global Target Point coordinate value in the X Direction yglobal Global Target Point coordinate value in the Y Direction xv X Coordinate Value of the Robot in Global Coordinates yv Y Coordinate Value of the Robot in Global Coordinates Nsum Total grid number to be covered for comparison Tstc Solution time of the relatively advanced STC method Tour Solution time of our STC method Tr The solution time reduction percentage Parameters and settings for modeling. Based on the above assumptions, the problem under discussion is to find a solution that minimizes the total time consumed for the coverage task. To simplify the problem, this study does not consider the cases of uneven speed or system restarts due to crashes during the robot’s operation, meaning that the path length is equivalent to the time consumed for the task. To reduce conflicts in the coverage paths of different robots, the study assumes that during the robots’ collaborative work, the spatial intersection of any two robots in the system must not exceed a threshold St. The objective function and constraints of this study are as follows: We summarize the above formulas as follows: Equation (1): Ensure that the solution to the MCPP problem is a near-optimal solution among feasible solutions. Equation (2): Describes the operation time of the MCPP solution, which is the time taken by the robot with the longest operation time in the system. Equations (3)–(5): Ensure that the total coverage area is the sum of the areas covered by each robot, while ignoring redundant paths due to secondary coverage when evaluating the total coverage. Equations (6) and (7): Ensure that each robot can complete its assigned coverage task without path conflicts that could lead to higher-order deadlock in the multi-robot system, causing task failure. In addition to the above constraints, we specify that the robots are ground differential-drive robots with complete kinematic constraints, meaning that the discretized path points can be interpolated to enable accurate tracking. The schematic diagram is shown in Figure 1. Schematic diagram of CPP. 3.2. Proposed Solution Framework To better introduce this method, the basic principles of STC and the terminology used in this study are briefly explained, as shown in Figure 2. In random scenarios where an STC solution is needed, the obstacle distribution and starting point are loaded. Then, the starting point is used as the parent vertex to search for alternative branches in the surrounding area. Feasible branches are determined through evaluation, and the process continues until the entire scene is fully covered. The basic principles of STC and a representation of terms used in this study. The proposed solution is expected to improve solving speed, based on two key ideas: (1) Considering the secondary coverage of the solution at the first, there is no STC method without secondary coverage that can achieve complete coverage in any environment from any starting point without requiring backtracking. We support this with a simple proof, as shown in Proposition 1. The traditional backtracking mechanism involves traversing backward through already searched STC nodes, finding the nearest one to the current point that can generate a new branch, and continuing to expand from there until full coverage is achieved. To address this problem, we implemented a list of alternative backtracking points, allowing us to more quickly find feasible root vertices for new branches, thereby reducing computation time, as shown in Section 3.3. (2) According to Equation (2), the problem can be transformed into minimizing the working time of the robot with the longest operation time in a multi-robot system. A more balanced distribution of the area to be covered can significantly improve this metric, and reducing the rate of double coverage indirectly lowers the overall workload, which is also meaningful. The proposed method introduces a technique for balanced path segmentation after generating explicit coverage paths based on the STC. This method has been proven to achieve a maximum gap of Gopt compared to the optimal solution, as shown in Proposition 2. To account for its deployment in practical applications, a feasibility framework based on the proposed method is proposed, as illustrated in Figure 3, in which the yellow parts are our contributions. A feasibility framework based the proposed method. There is no STC method that can completely cover any environment with any starting point and satisfy the following two constraints. Constraint 1: No backtracking occurs. Constraint 2: No secondary coverage. Assume that there is an STC method that can achieve full coverage from any starting point in any environment and satisfy the above two conditions. To refute this hypothesis, we can find a counterexample, as shown in Figure 4. First, consider the case where quadratic coverage does not occur. After the first part is covered, no matter which of the two available directions in the figure is chosen to expand the tree, a deadlock area will inevitably be formed. If you cover part 1 first and then expand the tree to part 2, a deadlock will occur after covering part 2, and backtracking will be necessary to cover part 3. Considering the case where full coverage is not achieved by backtracking, still referring to the counterexample, based on the STC solution process, it is necessary to re-pass the generated branches, then secondary coverage will occur, which contradicts the hypothesis. Therefore, the hypothesis is not established, and the proposition is proved. □ Illustrative diagram of a case with an inevitable backtracking situation: (a) illustrative diagram of a scenario used as a counterexample; (b) illustrative diagram of a deadlock situation; (c) illustrative diagram of an alternative backtracking method for a deadlock situation; (d) a solution method for the generated tree after backtracking; (e) an example of complete coverage after backtracking; (f) another example of complete coverage after backtracking. The proposed method, when the number of obstacles in the environment, as well as the length and width of the environment’s boundaries, are known, can demonstrate the difference in coverage between its solution and the optimal solution in a grid map. For a grid map where the entire coverage area is connected, the solution obtained by the proposed method can have a maximum difference from the optimal solution, denoted as Gopt which satisfies Equation (8). When the input scene is any form of a grid-based map C1, let its length and width be levn and hevn, respectively. It can be transformed into the input required for the STC algorithm. The implementation method is to complete C1 into a square shape and expand the obstacle regions, converting the original map into a grid map C2 with both levn and hevn being even, as shown in Figure 4a. Then, a trivial solution can be obtained using traditional STC method [19]. Thus, complete coverage of C2 has been achieved. The areas that have not achieved 100% coverage can only exist in six possible scenarios near obstacles or boundaries, as shown in Figure 5a,b. Additionally, there are uncovered regions at the boundaries caused by the parity of the scene dimensions, as illustrated in Figure 5c,d. If the number of occupied grid cells by obstacles is Nobs, then the corresponding uncovered area in C1 does not exceed 3Nobs cells. In the worst-case scenario, as all the obstacles are not adjacent to the boundary, the total uncovered area can be represented as 3Nobs. Similarly, for the boundaries, the worst-case scenario can be calculated as Equation (8). Additionally, complete coverage condition 1 indicates that the obstacle occupancy in the original grid map is consistent with that in the grid map used for STC solving, while complete coverage condition 2 means that the redundancy of obstacles in the four corners should be considered during calculations. The proposition is proven. □ Schematic diagram of the principles behind the occurrence of incomplete coverage: (a) an example scenario; (b) example of situations leading to incomplete coverage when restoring STC grid maps to original grids; (c) a situation where an odd edge size prevents complete coverage by STC; (d) another situation where an odd edge size prevents complete coverage by STC. 3.3. Improved STC Based on Optimized Backtracking Module The STC method has many variations. To reduce the number of turns [36], we improve upon the SCAN-STC method as a reference [37]. The underlying logic of this type of algorithm is similar to traditional methods, continuously updating the parent vertex to find the next branch vertex and improving its random search into a scanning search. This approach reduces the number of turns while ensuring a low rate of double coverage. When the branches of the spanning tree cannot be extended, resulting in a deadlock, a backtrack is performed. This vertex is referred to as a deadlock point in this study, and the partially completed STC solution is termed the STC intermediate solution. The backtracking method involves maintaining a vertex list during the expansion of the spanning tree. When backtracking is necessary, it scans the current tree’s vertices for extensibility in reverse order along the list. When an extendable vertex is found, it is used as the new root vertex for the branch, thus regenerating the tree. This point is called a feasible backtracking point in this study. This point needs to have two properties. The first is that the point must be in the already generated tree, and the second is that a new branch can be generated with this point as the new root point and it does not overlap with the already generated tree. This method not only avoids the issue of the traditional STC method for obtaining optimal solutions, where each expansion requires searching in all four directions, transforming the overall problem into an NP-hard problem, but also retains the advantages of high total coverage and low secondary coverage of the STC, as well as the proximity of the starting and ending points. In a coverage area of the same size, the original backtracking method often encounters backtrack points located near the starting point. When a deadlock occurs, it requires traversing a longer backtrack sub-list to continue expansion. The principle is illustrated in Figure 6. A pattern was observed in the analysis of multiple different STC solutions in a random scene: if a feasible backtracking point can be obtained in a certain way that shortens the number of backtracks, this study refers to it as a superior backtracking point. The principle of STC backtracking: (a) illustrative diagram of the situation after a deadlock occurs; (b) areas that require backtracking for coverage; (c) schematic diagram of the principles behind different backtracking methods leading to varying backtracking counts. This type of backtracking point can be obtained using the following method: if a point is adjacent to an obstacle or boundary and belongs to an uncovered area, it can be connected to the intermediate solution in the reverse direction of the scanning path. The vertex on the connected intermediate solution becomes the superior backtracking point. As illustrated in Figure 6c, the corresponding uncovered points are referred to as backtracking reference points. In contrast, backtracking through non-superior backtracking points can easily lead to additional backtrack counts, as shown in Figure 6a,b. The proposed method optimizes the backtracking module, with the overall idea of increasing spatial complexity and reducing computational complexity. Two additional new lists are maintained in addition to the original algorithm: the obstacle-adjacent point list and the superior backtracking list. The obstacle-adjacent point list is a static list that sequentially adds grid points to be covered around obstacles based on the SCAN-STC scanning direction. The superior backtracking list is derived from the obstacle-adjacent point list and also includes the original backtracking list, which is updated in real time. The update method involves removing duplicate points from the obstacle-adjacent point list during the process of the spanning tree continuously updating the intermediate solution. When a deadlock occurs, the method no longer backtracks point-by-point along the STC intermediate solution. Instead, it directly takes the feasible backtracking point with the smallest index from the latest superior backtracking list as the vertex to initiate the generation of a new branch in the tree. This point is then removed from the superior backtracking list until the backtracking point list is empty, at which point the cycle ends. The pseudocode for this process is shown in Algorithm 1, and it works as follows. The algorithm input includes the scene map and any starting point that is not within an obstacle, and it uses three lists: PSTC, Popt-list, Pboundary-next and Mc. PSTC is the real-time updated STC intermediate solution list, confirmed in lines 18–50. Popt-list is the real-time updated superior backtracking point-list. Pboundary-next is the obstacle-adjacent point-list. Mc is used to store the cells around the real-time parent vertex during the STC solving process, with the labels VL, VU, VR, and VD representing the cells to the left, top, right, and bottom of the parent vertex, respectively. At the initial stage of the algorithm, a grid map MR is initialized to represent the set of space points Sr to be covered, and the occupancy status of each cell is stored and labeled as UNOCCUPIED or OCCUPIED. The STC intermediate solution list starts empty, and as the algorithm iterates, it eventually covers all points in Sr, ultimately outputting the STC solution PSTC. Algorithm 1 Improved SCAN-STC to Cover the AreaInput: Grid-based map MROutput: STC solution: PSTCSr←MR(UNOCCUPIED);Mc←VL, VU, VR, VD; //Four points surrounding the current pointPopt-list← ; //Initialize the superior backtracking list.1:Popt-list←∑Pboundary-next; //Load boundary points into the backtracking list.2:For i=1:n23: Iterate through all points in the scene, set current point as vc; 4: If vc is an obstacle or boundary5: Set the four surrounding points of vc as Mc;6: For vnext←Mc7: If vnext∉Popt-list8: If vnext has not exceeded the boundary9: Add the point to the end of the superior backtracking list; 10: End 11: End 12: End 13: End 14: End 15:Initialize the total number of grid cells in the Sr to be covered as h;16:Initialize the STC iteration threshold Ih=h;17:Update Popt-list;18:Initialize the STC starting point vi;19:Initialize the STC intermediate solution list PSTC;20:While i←h21: Vc← vi;22: Set wt= 0;23: If VU UNOCCUPIED then24: VUVc→ represent the extended branches of PSTC, with VU as parent vertex;25: If VU∉Popt-list26: Add VU to the end of the Popt-list;27: wt=wt+1;28: end 29: Else if VL UNOCCUPIED then30: VLVc→ represent the extended branches of PSTC, with VL as parent vertex;31: If VL∉Popt-list32: Add VL to the end of the Popt-list;33: wt=wt+1;34: end 35: else if VD UNOCCUPIED then36: VDVc→ represent the extended branches of PSTC, with VD as parent vertex;37: If VD∉Popt-list38: Add VD to the end of the Popt-list;39: wt=wt+1;40: end 41: else if VR UNOCCUPIED then42: VRVc→ represent the extended branches of PSTC, with VR as parent vertex;43: If VR∉Popt-list44: Add VD to the end of the Popt-list;45: wt=wt+1;46: end 47: else 48: Vc is the deadlock point;49: end if 50: i=wt;51: Update PSTC;52: Update Popt-list; 53: Remove the points of PSTC from Popt-list;54: Update the point with the end of the Popt-list to the Vc;55: End 56: Update PSTC; 57:Return PSTC 3.4. Balanced Cut of the Explicit Coverage Path for STC To obtain an explicit STC path Pcover for the scene MR and to balance segmentation the Pcover to Solutioncpp= {P1, P2, P3…} for every robot in the system, this study first uses Algorithm 1 to obtain the STC solution on the corresponding map MSTC with dimensions. Its overall process flow is illustrated in Figure 7. Flowchart of explicit STC coverage path. The black background is the real obstacle, and the gray-white background is the free area. In addition, the red line represents the proposed STC solution, the blue line represents the first-type virtual obstacle, the green background represents the second-type virtual obstacle, and the yellow background indicates that it is necessary to judge whether the robot has avoided the first-type virtual obstacle in this area.: (a) flowchart for obtaining the STC solution based on the original grid map; (b) original grid coordinates at the corresponding positions in MR; (c) coordinates at the corresponding positions in the MSTC; (d) illustration of coordinates at corresponding positions in Mv; (e) illustration of the unprocessed Mv with first-type obstacle and second-type obstacle; (f) illustration of Mv after processing with Algorithm 2; (g) reference path list Pcover obtained from solving Mv; (h) path-list Pall obtained by mapping to MR. The method proposed in this study initializes a grid-map, Mv. Let the size of MR be m × n, then the size of MSTC was m/2 × n/2. The corresponding size of Mv is 2m × 2n, where the obstacles in MR are also mapped as obstacles in Mv. We can derive the quantification formulas for the corresponding positions between each matrix through simple scaling of the coordinate system. Additionally, we define the edges of all cells in MR as first-type virtual obstacles mapped to Mv. Furthermore, all STC-generated branches are defined as second-type virtual obstacles. When an edge of a first-type obstacle corresponds to MR, it intersects with a branch corresponding to a second-type obstacle to remove the first-type obstacle. A loop can be obtained, as illustrated in Figure 7. The first-type virtual obstacle is equivalent to the grid being occupied, and the second-type virtual obstacle needs to be maintained in a hash table. Each time a new path point is generated, it is determined whether the line segment corresponding to the path intersects with the virtual obstacle in the hash table. Algorithm 2 Balanced cut of the explicit coverage pathInput: STC solution: PSTCOutput: Coverage path: Solutioncpp={P1, P2, P3…}Sr←MR(UNOCCUPIED); Initialize the Cinitial by MR;//Corresponding to the original grid mapInitialize the CSTC as MSTC;//Corresponding to the STC sulotionInitialize the Cvirtual as Mv;//Matrix containing virtual obstaclesMc←VL, VU, VR, VD; //Four points surrounding the current point1:PSTC-vector← PSTC; //Vector matrix of each branch of the STC2:Pobs← Cinitial; //The grid edges of Cinitial are obstacles of Mv 3:Pobs-vector← Pobs; //Vector matrix of each branch of the Pobs 4:Sum the number of Vector in Pobs-vector as Iov;5:Sum the number of Vector in PSTC-vector as Isv;6:Sum the number of cell in Mv as Imv;7:Sall←Mv(UNOCCUPIED); 8:Sum the number of cell in Sall as Isa;9:For i=1:Isv10: Extract the endpoints and line segments of vector PSTC-vector;11: For j=1:Iov12: If Pobs-vector intersects with PSTC-vector at a point or line segment13: Remove Pobs-vectorfrom Pobs;14: End 15: End 16: End 17:Update Pobs;18:For i=1:Sall19: For j=1:Isv20: If vmv intersects with PSTC-vector at a point or line segment21: Mv(OCCUPIED) ←vmv;22: End 23: End 24: End 25:Update Mv;26:Initialize a random starting point vi in Mv;27:Initialize a path list Mv as Pall;28:While i←Isa29: Vc← vi;30: Set wt= 0;31: If VU UNOCCUPIED and not in the Pall then32: If VUVc→ not intersects with any Vector in Pobs-vector33: Pall ←VU;34: wt=wt+1;35: end 36: Else if VL UNOCCUPIED and not in the Pall then37: If VLVc→ not intersects with any Vector in Pobs-vector38: Pall ←VL;39: wt=wt+1;40: end 41: else if VD UNOCCUPIED and not in the Pall then42: If VDVc→ not intersects with any Vector in Pobs-vector43: Pall ←VD;44: wt=wt+1;45: end 46: else if VR UNOCCUPIED and not in the Pall then47: If VRVc→ not intersects with any Vector in Pobs-vector48: Pall ←VR;49: wt=wt+1;50: end 51: else 52: Vc is the end point of the path;53: end if 54: i=wt;55: Update Pall;56: End 57:Sum the number of cell in Pall as Ipa; 58:Sum the number of cell in MR as Imr; 59:Initialize a path list MR as Pcover; 60:Initialize a starting point Vi in MR; 61:For i=1:Imr 62: For j=1:Ipa 63: If The cells in Pall correspond to the cells in MR at matching positions 64: Pcover ←Vi; 65: End 66: End 67: End 68:Remove duplicate points from Pcover; 69:Update Pcover; 70: Divide the continuous path into R equal parts, as P1 , P2 , P3⋯; 71:Update Solutioncpp={P1, P2, P3…}; 72:Return Solutioncpp={P1, P2, P3…} Additionally, this loop forms a Hamiltonian circuit, allowing coverage of the area starting from any point on the path and ensuring that the endpoint is adjacent to the starting point. This property is particularly advantageous for disinfection and cleaning robots operating in a cyclic mode, which is one of the main reasons why many researchers use the STC method to address such issues [38,39,40,41,42,43]. 3.5. ROS Based Framework for MCPP This study investigated large-scale scenarios for industrial cleaning robots compatible with both indoor and outdoor environments, and found that few products fully implement kinematic constraints. Therefore, a differential-drive robot was designed and built, as shown in Figure 8. It achieves differential driving through two sets of motors, when the component model is ZLIS57C-10 Φ8 (The manufacturer is Shenzhen Zhongling Technology Co., Ltd., located in Shenzhen, Guangdong, China) and 57CLF gearboxes (The manufacturer is Beijing Times 4D Technology Co., Ltd., located in Beijing, China), based on the CANopen protocol. Communication with the motors is handled by the lower-level system, which integrates an STM32F407 chip (STMicroelectronics) and a CTM1051 module (The manufacturer is Zhiyuan Electronics Co., Ltd., located in Guangzhou, Guangdong, China). The upper-level system, consisting of modules like NUC (Intel, Ltd., Santa Clara, CA, USA) and Tenda routers (The manufacturer is Shenzhen Jixiang Tengda Technology Co., Ltd., located in Shenzhen, Guangdong, China), handles the transmission of kinematic commands to the lower system, as well as the collection of sensor information and the deployment of localization algorithms. Differential robot platform for experimental validation. By publishing global path sequence points in real-time within the network via a TOPIC [44], the robot achieves navigation functionality. Cubic spline interpolation is applied to the global path reference points, and the Dynamic Window Approach (DWA) is used to track the smoothed path after interpolation. The robot kinematic interface corresponding to the smooth path deployed on the robot is speed parameter and angular velocity parameter, where the speed is achieved by the rotation of the two driving wheels, and the angular velocity is achieved by the two driving wheels rotating in opposite directions. The kinematic diagram of the robot is shown in Figure 9. Kinematic model of the robot used to validate the method. The black arrow indicates the direction of the robot’s velocity, and the blue line indicates the target posture that needs to be achieved after receiving the deflection command. To implement this framework, we preprocess the constructed map and use Octave to obtain the STC solution, generating explicit discrete global path points. These paths are then published to the differential-drive robot via the ROS Topic functions integrated in Simulink. The differential-drive robot is equipped with a 2D LIDAR and an inertial navigation module, with a cartographer deployed for localization. Using the robot’s coordinates and the upcoming two consecutive discrete global path points, we apply cubic spline interpolation and compute the second derivative along the tangent direction as input for the DWA. When the Manhattan distance to the next global path point e1 is less than eh1, the next global path point is set as the target. If the current point’s error e2 exceeds eh2, the smooth local path is updated until all path points have been traversed. The values e1 and e2 are defined by Equations (9) and (10). When the endpoint is the target point, and only two points remain between the target and the robot’s current location, the previous global path point is used as a supplementary point if the local path needs updating. Based on engineering experience, in this study, we set eh1 = 0.25 m and eh2 = 0.10 m. 4. Experiment and Discussion To verify the effectiveness of the method, this study conducted 210 simulation tests and performed experimental testing on a real robot. Firstly, we set the lower boundary of single-robot operations to the standard size of a classic industrial cleaning robot, with the upper boundary based on the size of Beijing Universal Studios [45]. For different scene sizes, we generated 10 random maps per size based on a random seed, resulting in a total of 180 simulation tests to demonstrate the effectiveness of this study in social environments. For each environment size, a single case was selected to illustrate the effectiveness of the STC solution. Under different environment sizes, obstacles are randomly generated and arranged in them, and then the total number of grids that need to be covered Ssum can be obtained. Tstc represents the solution time of the method in the literature, Tour represents the solution time of the proposed method, and the results of this study are obtained through secondary development, that is, the percentage of calculation time reduction (Tr). The above test results are shown in Table 2. In order to save space, we provide 40 sets of scene data to prove the superiority of our method. Table 2Reduction in computational time by ours in the selected 40 random scenarios.Size of Case Ssum Tstc (s)Tour (s)Tr (%)Size ofCase Ssum Tstc (s)Tour (s)Tr (%) 40 × 4015001.11860.221680.19200 × 20023,764772.9788209.180472.9415081.16690.237279.6724,176597.5242241.951359.5115321.31080.308876.4423,848504.8885214.286757.5615361.27280.269778.8122,628646.2358239.290362.9715241.36390.239082.4724,828759.1654203.226873.2380 × 8060568.26712.207973.29250 × 25038,9722020.1102680.045466.3461205.38401.533971.5137,3601570.5011656.225558.1861046.36082.011768.3737,1801691.3564746.549455.8661045.68261.712069.8738,4481433.5215598.221758.2761046.58642.220166.2939,0121717.2946741.440056.84120 × 12013,63229.605512.703657.09350 × 35075,4283103.91351623.315647.6913,71220.10427.048964.9472,0724022.19561693.325157.9113,73629.387012.286258.1976,7923552.52191680.914352.7013,68422.02938.844059.8576,1564498.89561708.112562.0313,66825.08108.982064.1873,8403049.80121417.401953.55160 × 16024,25287.228634.946959.93400 × 40097,76015,051.12544435.715670.5324,34086.767532.235562.8496,43614,480.53404740.954367.2624,44077.716333.895556.3897,72414,406.00114376.365969.6224,27674.875028.269459.8497,5769805.24504612.152452.9624,40475.968334.113955.0998,1689842.71524616.521453.11 Reduction in computational time by ours in the selected 40 random scenarios. The test results indicate that the proposed method can effectively reduce computation time, achieving a reduction of up to 82.47% in favorable cases. The underlying principles of our method’s superiority have been discussed in detail in Section 3.3. Our method was applied to six scenarios with sizes of 40 × 40, 80 × 80, 120 × 120, 160 × 160, 250 × 250, and 400 × 400, along with the corresponding solution cases, as shown in Figure 10. Environments and solution cases in six conditions, The black part in the figure represents the obstacles, and the red line represents the obtained STC solution: (a) size 40 × 40; (b) size 40 × 40 solution; (c) size 80 × 80; (d) size 80 × 80 solution; (e) size 120 × 120; (f) size 120 × 120 solution; (g) size 160 × 160; (h) size 160 × 160 solution; (i) size 250 × 250; (j) size 250 × 250 solution; (k) size 400 × 400; (l) size 400 × 400 solution. Mainstream methods that consider computational complexity include RW (Random Walk), DFS (Depth First Search) [46], and DARP [47]. Additionally, the BP [48,49] method introduces new TSP issues due to region partitioning and does not address path conflicts between multiple robots. Other offline methods, such as MSTC and MIP, can obtain optimal solutions, but their high computational complexity makes them challenging to apply in large-scale scenarios and, thus, they were not included in the comparisons in this study. We generated 10 random obstacle-containing scenarios of size 80 × 80 and conducted 30 simulation tests using the methods RW, DARP (both effective in obstacle environments), and our proposed method. We compared the results based on three metrics: coverage rate, secondary coverage rate, and system operation time. The results are shown in Table 3. Table 3Comparative simulation testing of different algorithms.Case LabelQuantitative Comparison ItemsRWDFSDARPOurs1Coverage rate90.62%93.98%100%100%Secondary coverage315.21%17.18%0%0%Total path length6283 177415141514Update frequency8.33 Hz5.52 Hz0.03 Hz0.40 Hz2Coverage rate92.49%92.45%100%100%Secondary coverage152.21%21.51%0%0%Total path length0.09 s185915301530Update frequency11.11 Hz4.21 Hz0.05 Hz0.53 Hz3Coverage rate91.11%91.12%100%100%Secondary coverage255.21%32.48%0%0%Total path length5630209315861586Update frequency11.11 Hz5.15 Hz0.19 Hz0.42 Hz4Coverage rate93.10%94.49%100%100%Secondary coverage145.21%42.12%0%0%Total path length3848223015711571Update frequency10.00 Hz2.18 Hz0.14 Hz0.52 Hz5Coverage rate90.98%93.01%100%100%Secondary coverage385.21%35.24%0%0%Total path length7478208115421542Update frequency9.09 Hz3.15 Hz0.03 Hz0.51 Hz6Coverage rate88.34%90.11%100%100%Secondary coverage485.21%25.69%0%0%Total path length8769187314991499Update frequency11.11 Hz6.01 Hz0.05 Hz0.52 Hz7Coverage rate91.28%92.52%100%100%Secondary coverage354.21%46.11%0%0%Total path length6819217715021502Update frequency10.00 Hz3.11 Hz0.05 Hz0.49 Hz8Coverage rate89.05%88.98%100%100%Secondary coverage264.21%19.77%0%0%Total path length5179169314231423Update frequency7.69 Hz2.45 Hz0.05 Hz0.41 Hz9Coverage rate93.31%95.09%100%100%Secondary coverage157.21%45.29%0%0%Total path length3957223315401540Update frequency7.14 Hz2.00 Hz0.16 Hz0.81 Hz10Coverage rate91.22%91.74%100%100%Secondary coverage246.21%46.15%0%0%Total path length4927207914241424Update frequency12.5 Hz4.98 Hz0.09 Hz0.79 Hz Comparative simulation testing of different algorithms. The results show that our method shows significant advantages in terms of secondary coverage and operation time. RW shows considerable advantages in unknown scenarios due to its high frequency of solution updates and ability to be deployed in unknown environments. Its frequent updates to local paths help mitigate path conflicts during multi-robot collaboration by maintaining a priority queue for robots in the cloud. However, in large known scenes, the inherent stochasticity of RW can lead to excessive secondary coverage, resulting in longer overall operation times. The RW and DFS methods have higher quadratic coverage, which indirectly leads to longer total coverage paths. At the same time, the solution of the DARP method does not show obvious advantages in the comparison of multiple groups of random environments. Through the aforementioned simulation tests, the robots deployed in their operational areas for scenarios not exceeding the dimensions of 80 × 80 exhibit a re-planning time of less than 3 s. This means that when the robots navigate between two adjacent global path points that are 1 m apart at a typical operational speed of 0.35 m/s, they can successfully complete the re-planning process when new obstacles appear. This capability meets the demands of practical applications, rendering the DARP method unable to demonstrate a clear advantage in the issues discussed in this study. Finally, we constructed a scene model near the HIT-BIT building and transformed it into a two-dimensional map through processing, as shown in Figure 11. Instance scenario environment construction and grid map conversion. The figure in the lower right corner is a rasterized map of the area to be covered after processing, where the white part represents the area to be covered and the black part represents the obstacles. Based on the framework proposed in Section 3.5, the solved path was published to the differential robot for hardware validation, and the results are shown in Figure 12. Three-robot coverage path generation. After processing the three-dimensional point cloud, a grid map with a resolution of 1 m2 was obtained. The total number of grids that need to be covered in this map is 9500. After being solved by the proposed method, the number of grids assigned to each robot was 3166, 3166, and 3168, respectively, and the solution time was 1.6 s. Based on the robot referenced in this study, when covering the operation at a speed of 0.35 m/s, the passing time between two grids was 2.85 s. If a person or vehicle occupies the next grid in the robot’s global reference path at the next moment, the system can achieve re-planning capability. 5. Conclusions This study first innovatively introduced the concept of superior backtracking points and explained the principle of reducing the number of backtracking times during the backtracking process. Then, based on the original SCAN-STC algorithm, by additionally maintaining two designed data lists, the algorithm starts backtracking from the superior backtracking point in the process of solving the problem, which reduces the algorithm solution time and ultimately achieves the purpose of reducing computational complexity at the expense of space complexity. And through secondary encoding, the STC solution is explicitly represented as a continuous path, and finally the cut is balanced. Finally, a framework is provided to illustrate the method’s input requirements and kinematic requirements for the deployment platform. This study also indirectly illustrates the generalization ability of the method in reducing computational complexity by proving the necessity of backtracking. The effectiveness of the method was proved by simulation tests in a series of random environments with other recent methods in the literature, and the calculation time was reduced by 82.47% in the best case. In 10 random environments containing obstacles, it was compared with the RW and DFS methods, with path planning as the main module, and the DARP method with region segmentation as the main module. The results show that in this type of environment, the RW and DFS methods have high real-time performance, but high quadratic coverage. The solution of the DARP method does not show obvious advantages in the comparison of multiple groups of random environments. Our method achieves a high update frequency while ensuring low quadratic coverage, improving the robot’s path re-planning ability when performing coverage tasks in social environments. With the support of the new project, we will optimize the bandwidth of data synchronization between robots to achieve the ability of system information sharing in hardware. At the same time, by optimizing the robot dynamics, we will further improve the algorithm’s ability to resist interference from the external environment when facing outdoor unevenness, and provide better protection for the online solution of MCPP problems in social environments. Acknowledgments ChatGPT is only used for translation and grammar correction. Author Contributions Designed the research, processed the data, and drafted the manuscript: C.W. and W.D.; designed the experimental platform: R.L.; system communication function: H.L.; optimizing the experiment: Y.G. and H.D. All authors have read and agreed to the published version of the manuscript. Institutional Review Board Statement No ethical approval was required for this study. Informed Consent Statement Not applicable. Data Availability Statement Data sharing is not applicable. Conflicts of Interest The authors declare that they have no known competing financial interest or personal relationships that could have appeared to influence the work reported in this paper. Funding Statement This research received no external funding. Footnotes Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. References Associated Data Data Availability Statement Data sharing is not applicable.