Coverage path planning algorithms for agricultural field machines

Abstract In this article, a coverage path planning problem is discussed in the case of agricultural fields and agricultural machines. Methods and algorithms to solve this problem are developed. These algorithms are applicable to both robots and human‐driven machines. The necessary condition is to cover the whole field, and the goal is to find as efficient a route as possible. As yet, there is no universal algorithm or method capable of solving the problem in all cases. Two new approaches to solve the coverage path planning problem in the case of agricultural fields and agricultural machines are presented for consideration. Both of them are greedy algorithms. In the first algorithm the view is from on top of the field, and the goal is to split a single field plot into subfields that are simple to drive or operate. This algorithm utilizes a trapezoidal decomposition algorithm, and a search is developed of the best driving direction and selection of subfields. This article also presents other practical aspects that are taken into account, such as underdrainage and laying headlands. The second algorithm is also an incremental algorithm, but the path is planned on the basis of the machine's current state and the search is on the next swath instead of the next subfield. There are advantages and disadvantages with both algorithms, neither of them solving the problem of coverage path planning problem optimally. Nevertheless, the developed algorithms are remarkable steps toward finding a way to solve the coverage path planning problem with nonomnidirectional vehicles and taking into consideration agricultural aspects. © 2009 Wiley Periodicals, Inc.