Abstract
This paper presents a novel approach to Coverage Path Planning (CPP) for complex 3D surfaces and 2D domains with obstacles. By leveraging intrinsic surface geometry through holomorphic quadratic differentials, the method decomposes intricate topologies into simple patches. This transformation enables efficient "zig-zag" coverage, converting an NP-hard optimization problem into a computationally tractable task.
Introduction
Coverage Path Planning (CPP), often referred to as the "vacuum cleaner problem," involves determining a path that allows a robot to pass over every point in a target area while minimizing redundant movement. Traditional approaches typically rely on extrinsic Euclidean coordinates and cell decomposition. However, these methods struggle with complex 3D terrains or surfaces with non-trivial topology (e.g., holes), often resulting in inefficient decompositions and NP-hard pathfinding challenges like the Hamiltonian path problem.
Methodology
The core innovation of this work is the use of intrinsic geometry—specifically holomorphic quadratic differentials—to establish a global coordinate system ($uv$-coordinates) that naturally conforms to the surface's shape.
The algorithm proceeds through several key stages:
- Strebel Differentials: The authors utilize Strebel differentials to ensure that "horizontal trajectories" on the surface form closed loops. This guarantee allows a robot to cover the surface in "rings," returning to its starting point after each circuit.
- Surface Decomposition: By slicing the surface along "critical trajectories" (paths connecting singular points), the algorithm divides complex topologies, such as multi-holed donuts, into topological cylinders or simply-connected patches.
- Euler Cycle Optimization: To avoid the NP-hard Hamiltonian path problem, the authors double the edges of the cell adjacency graph. This allows for the discovery of an Euler cycle in polynomial time. By visiting each cell twice with an interlaced zig-zag pattern, the robot achieves high coverage with minimal redundant overlap.
Experimental Evaluation
The proposed method was evaluated on several mathematically challenging geometric models, including a genus-3 "three-hole donut," a non-convex 2D domain with four holes, and a 3D terrain mesh featuring "lakes" as topological holes.
The results demonstrate that the algorithm successfully generates continuous, non-intersecting paths for high-genus surfaces that would be nearly impossible for standard "lawnmower" algorithms to handle efficiently. Analysis of the relationship between the density step ($\epsilon$) and the robot's radius ($\delta$) showed that while smaller steps improve coverage, they also increase the overlap rate, presenting a tunable trade-off for specific applications.
Discussion and Conclusion
By treating geometry as a map rather than forcing a rigid grid onto curved surfaces, the authors create paths that are inherently "natural" to the shape. This topology-aware approach seamlessly handles obstacles by treating them as part of the surface's intrinsic structure.
Despite its strengths, the method currently operates "offline," requiring a complete 3D mesh prior to path execution. Future work may address real-time adaptation to unknown obstacles and the integration of robot dynamics, such as momentum and turning radius constraints, to enhance applicability in high-speed real-world scenarios. Additionally, improving numerical stability around coordinate singularities remains a priority for handling lower-precision meshes.
In summary, the use of quadratic differentials offers a robust mathematical foundation for solving complex coverage problems, significantly reducing computational complexity while improving path quality on non-Euclidean domains.
Summary updated