Complete, Decomposition-Free Coverage Path Planning

August 2022

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.
@conference{Kusnur-2022-134555,
author = {Tushar Kusnur And Maxim Likhachev},
title = {Complete, Decomposition-Free Coverage Path Planning},
booktitle = {Proceedings of IEEE 18th International Conference on Automation Science and Engineering (CASE '22)},
year = {2022},
month = {August},
publisher = {IEEE},
keywords = {motion planning, coverage path planning, heuristic search},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.