Hierarchical Coverage Path Planning in Complex 3D Environments

Abstract

State-of-the-art coverage planning methods perform well in simple environments but take an ineffectively long time to converge to an optimal solution in complex three-dimensional (3D) environments. As more structures are present in the same volume of workspace, these methods slow down as they spend more time searching for all of the nooks and crannies concealed in three-dimensional spaces. This work presents a method for coverage planning that employs a multi-resolution hierarchical framework to solve the problem at two different levels, producing much higher efficiency than the state-of-the-art. First, a high-level algorithm separates the environment into multiple subspaces at different resolutions and computes an order of the subspaces for traversal. Second, a low-level sampling-based algorithm solves for paths within the subspaces for detailed coverage. In experiments, we evaluate our method using real-world datasets from complex three-dimensional scenes. Our method finds paths that are constantly shorter and converges at least ten times faster than the state-of-the-art. Further, we show results of a physical experiment where a lightweight UAV follows the paths to realize the coverage.