Presentation of a Modified Boustrophedon Decomposition Algorithm for Optimal Configuration of Flat Fields to use in Path Planning Systems of Agricultural Vehicles

IntroductionThe demand of pre-determined optimal coverage paths in agricultural environments have been increased due to the growing application of field robots and autonomous field machines. Also coverage path planning problem (CPP) has been extensively studied in robotics and many algorithms have been provided in many topics, but differences and limitations in agriculture lead to several different heuristic and modified adaptive methods from robotics. In this paper, a modified and enhanced version of currently used decomposition algorithm in robotics (boustrophedon cellular decomposition) has been presented as a main part of path planning systems of agricultural vehicles. Developed algorithm is based on the parallelization of the edges of the polygon representing the environment to satisfy the requirements of the problem as far as possible. This idea is based on "minimum facing to the cost making condition" in turn, it is derived from encounter concept as a basis of cost making factors.
Materials and MethodsGenerally, a line termed as a slice in boustrophedon cellular decomposition (BCD), sweeps an area in a pre-determined direction and decomposes the area only at critical points (where two segments can be extended to top and bottom of the point). Furthermore, sweep line direction does not change until the decomposition finish. To implement the BCD for parallelization method, two modifications were applied in order to provide a modified version of the boustrophedon cellular decomposition (M-BCD). In the first modification, the longest edge (base edge) is targeted, and sweep line direction is set in line with the base edge direction (sweep direction is set perpendicular to the sweep line direction). Then Sweep line moves through the environment and stops at the first (nearest) critical point. Next sweep direction will be the same as previous, If the length of those polygon's newly added edges, during the decomposition, are less than or equal to the base edge, otherwise a search is needed to choose a new base edge. This process is repeated until a complete coverage. The second modification is cutting the polygon in the location of the base edge to generate several ideal polygons beside the base edges. The algorithm was applied to a dataset (including 18 cases, ranging from simple-shaped to complex-shaped polygons) gathered from other studies and was compared with a split-merge algorithm which has been used in some other studies. The M-BCD algorithm was coded in C language using Microsoft Visual Studio 2013 software. Algorithm was run on a laptop with 2.5 GHz Intel(R) core™ i5-4200M CPU, processor with 4 GB of RAM. Also Split-merge algorithm provided by Driscoll (2011) was coded. Two algorithms were applied to the dataset. Cost of coverage plan was calculated using cost function of U-shaped turns in study Jin and Tang (2010). In this paper machine-specific parameters were working width 10 m and minimum turning radius 5 m.
Results and DiscussionBased on the results, the proposed algorithm has low computational time (below 100 ms in dataset and runs many times (on average 75 times) faster than split-merge algorithm. Algorithm resulted in a calculated savings up to 12% and on average 2% than the split-merge algorithm. Another consequence from parallelization method was effectiveness of multi-optimal direction coverage pattern than a single-optimal direction coverage; a calculated savings up to 14% and 2% on average than a single optimal direction achieved. Algorithm was evaluated on several test cases in detail. Based on the results, it is possible to loose optimal solutions especially in the case of simple shaped environments (in terms of number of convex points and internal obstacles), for example case 10 in dataset, is a case with a number of orthogonal edges. Reviewing the algorithm and Figure 4 demonstrate that sweep line moves down from the first longest edge in top of the polygon, and it doesnt stop during the process until the whole area is covered with a single coverage path direction (parallel to the longest edge). As it can be seen, no decomposition is proposed, because sweep line has faced no critical points. Based on the results in Table 2, there is 8% (equal to 88m) more cost (in term of the non-effective distance) in this case than an optimal direction and the split-merge algorithm. There are similar cases in the dataset: number 9, 12 and 13. This condition rarely occurs in complex environments, but in general it can be prevented by using an evaluation step at the end of the decomposition process. Ideally, the cost of coverage plan must be significantly less than related costs of a single optimal direction. Unlike the simple cases, algorithm returns near the optimal solution, especially in the case of complex environments. A good example of this ability of the algorithm can be seen in Figure 6. This field is case 17 in the dataset. It has many edges (almost 90 edges) and several non-convex points and an internal irregular shaped obstacle. M-BCD algorithm in a very short time (87 ms) generated several near to ideal shaped sub-regions around the field. Algorithm resulted in a calculated saving of 5% than an optimal direction with minimum non-effective distance. We can see the solution of split-merge algorithm by Oksanen and Visala (2009) in Figure 6, it can be clearly seen that coverage pattern by M-BCD is very close to the high time-consuming and optimal split-merge algorithm by Oksanen and Visala (2009). It verifies that M-BCD is efficient and optimal. There are similar test cases as hard cases in which considerable savings has been achieved (cases 6, 8 and 14).
ConclusionsIn this paper a modified decomposition algorithm as a main part of path planning systems in agricultural environments was presented. Proposed algorithm uses method of parallelization of the edges of polygon. This method is based on encounter concept and "minimum facing to cost making condition". Although the general problem had been proved to be NP-hard problem, the method has limited the search space correctly and effectively which resulted close to the optimal solutions quickly. Another advantage of the method is suitability of the solutions for any kind of machine and any polygonal flat field (and those which can be considered as flat fields).