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

Area of Science:

• Robotics and Automation
• Computational Geometry

Background:

• Large-scale environments like public spaces require efficient path planning for tasks such as cleaning and disinfection.
• Existing Covered Path Planning (CPP) methods face challenges in complex, obstacle-ridden environments.

Purpose of the Study:

• To develop an optimized Covered Path Planning (CPP) method for large, complex environments.
• To significantly reduce the computational time of path planning algorithms.

Main Methods:

• Improvement upon the SCAN-STC (Spanning Tree Coverage) algorithm.
• Optimization of the backtracking module by introducing optimal backtracking points.
• Secondary coding to express STC solutions as continuous, cuttable global paths.

Main Results:

• Reduced computational complexity by sacrificing spatial complexity.
• Demonstrated generalization ability through proof of backtracking necessity.
• Successfully generalized to Multi-robot Covered Path Planning (MCPP) to avoid path conflicts and ensure balanced path assignments.
• Achieved an 82.47% reduction in computational time compared to advanced methods.

Conclusions:

• The proposed optimized STC method is effective for path planning in diverse and complex environments.
• The method offers significant computational efficiency gains.
• The approach is scalable and applicable to multi-robot systems.