| The problem of finding a collision-free path through a region has garnered a lot of research over the years. One branch of this is the problem of finding a path that completely covers a region. Solutions to the complete coverage path planning problem have applications in many different areas, such as search and rescue, automotive painting, and agriculture. In many cases, it is not sufficient to find any route that completely covers the field. It is desired that the path also be optimal so as to minimize certain costs. This is especially true in the agricultural environment. In the area of precision farming alone, the complete coverage path planning problem exists while performing many different operations, such as harvesting, seeding, spraying, applying fertilizer, and tillage. The fundamental concern of farmers is reducing the costs of running the farm. Since most farming costs ultimately depend on time in the field and area covered, the more efficient an operation can be completed, the lower the costs. Optimality is thus typically in terms of finding the shortest complete coverage path through the field. In this paper, we present an O(n 2) algorithm for solving the optimal complete coverage problem on a field boundary with n sides. This multi-phase algorithm makes use of a plane-sweep algorithm to subdivide the field into smaller, trapezoidal regions. The optimal paths through the subregions are then calculated. Finally there is a merge phase where it is determined whether neighboring regions can be more efficiently covered if they were merged together than if they were left separate. |
