An Improved STC-Based Full Coverage Path Planning Algorithm for Cleaning Tasks in Large-Scale Unstructured Social Environments

Chao Wang, Wei Dong, Renjie Li, Hui Dong, Huajian Liu, Yongzhuo GaoSensors 2024 · DOI

TL;DR

This paper introduces an improved Spanning Tree Coverage (STC) algorithm for cleaning robots in large, complex environments. By optimizing the backtracking process with "superior backtracking points," the algorithm significantly reduces computation time while maintaining high coverage, making it more practical for real-world applications like disinfection.

What Problem Does This Paper Address?

Cleaning and disinfection tasks in large, unstructured social environments (like hotels or amusement parks) pose significant challenges for robots. These environments are often vast, cluttered with obstacles, and populated by humans, requiring robots to navigate efficiently and safely. Traditional coverage path planning (CPP) methods struggle with these complexities, leading to long task times, excessive redundant coverage (wasting resources and potentially causing wear), and difficulties in handling dynamic obstacles or human presence. Furthermore, extending these methods to multi-robot systems (MCPP) introduces further complications like path conflicts and load balancing. This paper aims to address these issues by developing a more computationally efficient and robust CPP algorithm suitable for such demanding scenarios.

Methods

The core of this work is an enhanced Spanning Tree Coverage (STC) algorithm, specifically building upon the SCAN-STC method. The key innovation lies in optimizing the backtracking module.

  • Optimized Backtracking: Instead of a generic backtracking approach, the paper introduces the concept of "superior backtracking points." These are strategically identified points that allow the algorithm to resume coverage more efficiently after encountering a deadlock. This optimization aims to reduce the number of backtracking steps, thereby decreasing computational complexity. The authors prove the necessity of backtracking in certain scenarios to achieve full coverage.
  • Explicit Global Path: The STC solution is then converted into an explicit, continuous, and "cuttable" global path using secondary coding. This makes the path more amenable to practical deployment and distribution.
  • Multi-Robot Generalization: The explicit global path is designed to be easily adaptable for Multi-robot Covered Path Planning (MCPP). This allows for balanced task assignment among multiple robots and helps avoid path conflicts.
  • Feasibility Framework: A ROS-based framework is proposed for deploying the algorithm on a differential-drive robot, integrating with navigation modules like DWA.

Datasets

The paper does not explicitly mention training datasets. For evaluation, the authors generated 10 random maps for each of several environment sizes (40x40, 80x80, 120x120, 160x160, 250x250, and 400x400) to simulate various obstacle configurations. They also conducted experiments on a real robot in a constructed scene model near the HIT-BIT building.

Key Insights and Ideas

  • Backtracking is Inevitable: The paper rigorously proves that for complete coverage without secondary coverage, backtracking is sometimes unavoidable in STC-based methods, especially in complex environments. This justifies the focus on optimizing this process.
  • "Superior Backtracking Points" are Key: The introduction of "superior backtracking points" is a novel approach to significantly speed up the backtracking process. By intelligently choosing where to resume coverage, the algorithm avoids inefficient exploration.
  • Spatial Complexity for Computational Efficiency: The method intentionally sacrifices some spatial complexity (e.g., by maintaining additional lists) to achieve a substantial reduction in computational complexity. This is a crucial trade-off for real-time applications.
  • Explicit Paths for Practicality: Converting the STC solution into a continuous, explicit path simplifies deployment and enables easier integration with existing robot navigation systems and MCPP strategies.

Key Results

  • Significant Time Reduction: The proposed method achieved a reduction in computational time of up to 82.47% compared to advanced methods in the literature.
  • High Coverage Rate: The algorithm maintains a high coverage rate, with the DARP method achieving 100% coverage in simulations, while the proposed method also demonstrates excellent coverage.
  • Low Secondary Coverage: The method effectively minimizes secondary coverage, which is critical for efficiency and reducing wear on cleaning robots.
  • Effective in Complex Environments: Simulations and real-world tests demonstrated the algorithm's effectiveness in various random environments with different obstacle densities and sizes.
  • Improved Re-planning: The method enhances the robot's path re-planning ability, crucial for navigating dynamic social environments.

Limitations and Future Work

  • Spatial Complexity Trade-off: The authors acknowledge that their method increases spatial complexity to reduce computational complexity. While beneficial for speed, this might have implications for memory usage in highly constrained systems.
  • Future Work: The authors plan to optimize data synchronization between robots for system information sharing and further improve the algorithm's robustness against external environmental interference, particularly for outdoor uneven terrain. They also aim to enhance the robot's dynamics for better performance in challenging conditions.

Summary updated

Abstract

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%.
BibTeX
@inproceedings{wang2024improved,
  author = {Chao Wang and Wei Dong and Renjie Li and Hui Dong and Huajian Liu and Yongzhuo Gao},
  title = {{An Improved STC-Based Full Coverage Path Planning Algorithm for Cleaning Tasks in Large-Scale Unstructured Social Environments}},
  booktitle = {Sensors},
  year = {2024},
  doi = {10.3390/s24247885},
}
Figure