Complete, Decomposition-Free Coverage Path Planning

Abstract

Coverage Path Planning (CPP) requires planning collision-free paths for a robot that observes all reachable points of interest in an environment. Most popular CPP approaches are hierarchical and decomposition-based, involving three steps: (1) decomposing the environment into sub-regions (rectangles or polygons) that simplify the generation of space-filling paths, (2) determining a visitation order over these sub-regions via graph search or a Traveling Salesman Problem (TSP) solver, and (3) generation of space-filling paths in each sub-region. This approach requires significant processing of the environment and the availability of suitable TSP solvers. Furthermore, step (1) can sometimes fail in non-convex environments or lead to "over-decomposition" in cluttered environments. To the best of our knowledge, existing decomposition-free approaches are heuristic or random, and therefore typically inefficient and probabilistically complete. We present a resolution-complete decomposition-free coverage path planner that effectively folds steps (1) and (2) above into a single online search routine, making it significantly easier to integrate into existing robot architectures and applicable to a larger set of environments. Our approach leverages a precomputed library of space-filling coverage patterns and automatically determines where to apply them. We evaluate our approach on a variety of environments to demonstrate its benefits and provide an open-source implementation at https://github.com/ktushar14/cdf_cpp.