A hybrid heuristic method for coverage path planning of the spraying drone in 2D regions with obstacles
摘要
This paper investigates the problem of coverage path planning (CPP) for the spraying drone operating in complex two-dimensional regions with obstacles. The drone must depart from a designated start point, completely cover a region of interest, and land at a specified end point while avoiding collisions. A basic mathematical model for the CPP of the spraying drone is formulated first. Because CPP is a combinatorial optimization problem whose computational cost increases significantly with fine-grained discretization and obstacle density, achieving high-quality solutions within operational time limits requires efficient and scalable computation. To address this challenge, a hybrid heuristic method (HHM) is proposed, which integrates global path construction with local refinement to enable efficient exploration of the solution space while supporting high-performance and real-time execution. The method is evaluated on 44 instances, including convex polygons, concave polygons, and polygons with obstacles. Experimental results demonstrate that HHM consistently outperforms state-of-the-art approaches in solution quality while maintaining short computation times, highlighting its suitability for large-scale and time-sensitive applications.