Some 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: STC; back tracking; coverage path planning; multi-robot; social environments.