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

ماشین های کشاورزی

Article 14, Volume 8, Issue 1 - Serial Number 15, 2018, Pages 171-183   

Document Type: Research Article

DOI: 10.22067/jam.v8i1.58398

Authors

R. Goudarzi¹; H. Sadrnia^{* 1}; A. Rohani¹; M. Nouribaygi²

¹Department of Biosystems Engineering, Faculty of Agriculture, Ferdowsi University of Mashhad, Mashhad, Iran

²Department of Computer Engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran

Abstract

Introduction
The 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 Methods
Generally, 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 Discussion
Based 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 doesn't 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).
Conclusion
In 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).

Keywords

Agricultural vehicles; Boustrophedon decomposition algorithm; Flat fields; Field configuration; Path planning

References

1. Ali, O., B. Verlinden, and D. Van Oudheusden. 2009. Infield logistics planning for crop-harvesting operations. Engineering Optimization 41: 183-197.

2. Bochtis, D. D., C. G. C. Sørensen, and P. Busato. 2014. Advances in agricultural machinery management: A review. Biosystems Engineering 126: 69-81.

3. Bochtis, D. D., and C. G. Sørensen. 2009. The vehicle routing problem in field logistics part I. Biosystems Engineering 104: 447-457.

4. Bochtis, D. D., and C. G. Sørensen. 2010. The vehicle routing problem in field logistics: Part II. Biosystems engineering 105 (2): 180-188.

5. Bochtis, D. D., C. G. Sørensen, P. Busato, and R. Berruto. 2013. Benefits from optimal route planning based on B-patterns. Biosystems Engineering 115: 389-395.

6. Bochtis, D. D., S. Vougioukas, C. Tsatsarelis, and Y. Ampatzidis. 2007. Optimal dynamic motion sequence generation for multiple harvesters. In Proceedings of the Automation Technology for Off-road Equipment (ATOE) 2006 Conference, Bonn, Germany (pp. 33-40).

7. Choset, H. 2000. Coverage of known spaces: The boustrophedon cellular decomposition. Autonomous Robots 9 (3): 247-253.

8. Choset, H. 2001. Coverage for robotics–A survey of recent results. Annals of mathematics and artificial intelligence 31 (1-4): 113-126.

9. Driscoll, T. M. 2011. Complete coverage path planning in an agricultural environment. Graduate Theses and Dissertations. Paper 12095. Faculty of computer. Iowa state University. USA.

10. Edwards, G., and M. A. F. Jensen. 2013. Real Time Optimisation of Field Coverage Route Planning with Limited Capacitance Machinery and Spatial Variability. International Commission of Agricultural and Biological Engineers, Section V. CIOSTA XXXV Conference “From Effective to Intelligent Agriculture and Forestry”, Billund, Denmark, 3-5 July 2013.

11. Hameed, I. A., D. D. Bochtis, and C. G. Sørensen. 2013. An optimized field coverage planning approach for navigation of agricultural robots in fields involving obstacle areas. International Journal of Advanced Robotic Systems 10 (231): 1-9.

12. Hameed, I. A., D. D. Bochtis, C. G. Sørensen, and M. Nøremark. 2010. Automated generation of guidance lines for operational field planning. Biosystems Engineering 107: 294-306.

13. Hofstee, J. W., L. E. E. M. Spätjens, and H. Ijken. 2009. Optimal path planning for field operations. In Proceedings of the 7th European conference on precision agriculture Precision Agriculture 09 (pp. 521-529). Netherlands: Wageningen.

14. Jensen, M. A. F., D. Bochtis, C. G. Sørensen, M. R. Blas, and K. L. Lykkegaard. 2012. In-field and inter-field path planning for agricultural transport units. Computers & Industrial Engineering, 63: 1054-1061.

15. Jin, J., and L. Tang. 2010. Optimal coverage path planning for arable farming on 2D surfaces. Transactions of the ASABE, 53 (1): 283-295.

16. Moon, S. W., and D. H. C. Shim. 2009. Study on path planning algorithms for unmanned agricultural helicopters in complex environment. International Journal of Aeronautical and Space Sciences 10 (2): 1-11.

17. Murphy, R. 2000. Introduction to AI robotics. MIT press.

18. Oksanen, T., and A. Visala. 2009. Coverage path planning algorithms for agricultural field machines. Journal of Field Robotics 26 (8): 651-668.

19. Ryerson, A. F., and Q. Zhang. 2006. Vehicle path planning for complete field coverage using genetic algorithms. Vehicle path planning for complete field coverage using genetic algorithms. In Proceedings of the Automation Technology for Off-road Equipment (ATOE) 2006 Conference, Bonn, Germany (pp. 309-317).

20. Taïx, M., P. Souères, H. Frayssinet, and L. Cordesses. 2006. Path planning for complete coverage with agricultural machines. In Field and service robotics pp. 549-558. Springer Berlin Heidelber.

21. Zhou, K., A. Leck Jensen, C. G. Sørensen, P. Busato, and D. D. Bochtis. 2014. Agricultural operations planning in fields with multiple obstacle areas. Computers and Electronics in Agriculture 109: 12-22.