Efficient Coverage Path Planning via Gradient-Based Rectangular Segmentation

Abstract

Coverage Path Planning (CPP) is the task of finding a route that covers every point in a region or volume (i.e., all reachable cells) while avoiding obstacles. A typical CPP solution proceeds in two main stages: partitioning the environment into subregions, and planning a path within and between these regions. Effective segmentation is critical for smooth and efficient operation. For example, dividing the area into rectangular cells allows a simple back-and-forth (boustrophedon) sweep in each cell, exhaustively covering it without overlap. In this paper, we propose an adaptive, gradient-based rectangular decomposition for CPP. The algorithm analyzes the occupancy map to split free space into oriented rectangles that conform to obstacle boundaries. Within each rectangle, a straight-line sweep path is generated. Compared to conventional methods, our approach produces coverage paths that are smoother and more concise. We demonstrate on real-world maps that the proposed method achieves good coverage with fewer turns, yielding improvements in overall CPP efficiency.