A Framework for Coverage Path Planning of Outdoor Sweeping Robots Deployed in Large Environments

Outdoor sweeping is a tedious and labor-intensive task essential for maintaining the cleanliness of public spaces such as gardens and parks. Robots have been developed to address the limitations of traditional methods. Coverage Path Planning (CPP) is a critical function for these robots. However, existing CPP methods often perform poorly in large environments, where such robots are typically deployed. This paper proposes a novel CPP framework for outdoor sweeping robots operating in expansive outdoor areas, defined as environments exceeding 1000 square meters in size. The framework begins by decomposing the environment into smaller sub-regions. The sequence in which these sub-regions are visited is then optimized by formulating the problem as a Travelling Salesman Problem (TSP), aiming to minimize travel distance. Once the visiting sequence is determined, a boustrophedon-based CPP is applied within each sub-region. We analyzed two decomposition strategies, Voronoi-based and grid-based, and evaluated three TSP optimization techniques: local search, record-to-record travel, and simulated annealing. This results in six possible combinations. Simulation results demonstrated that Voronoi-based decomposition achieves higher area coverage (average coverage of 95.6%) than grid-based decomposition (average coverage 52.8%). For Voronoi-based methods, local search yielded the shortest computation time, while simulated annealing achieved the lowest travel distance. We have also conducted hardware experiments to validate the real-world applicability of the proposed framework for efficient CPP in outdoor sweeping robots. The robot hardware experiment achieved 84% coverage in a 19 m × 17 m environment.