Coverage path planning algorithms for agricultural field machines. (English) Zbl 1176.68216
Summary: 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.
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.
MSC:
| 68T40 | Artificial intelligence for robotics |
| 93C85 | Automated systems (robots, etc.) in control theory |
References:
| [1] | Acar, Morse decompositions for coverage tasks, International Journal of Robotics Research 21 (4) pp 331– (2002) |
| [2] | Acar, Path planning for robotic demining: Robust sensor-based coverage of unstructured environments and probabilistic methods, International Journal of Robotics Research 22 (7-8) pp 441– (2003) |
| [3] | Aichholzer, A novel type of skeleton for polygons, Journal of Universal Computer Science 1 (12) pp 752– (1995) |
| [4] | Arkin, E. M., Fekete, S., & Mitchell, J. (1993, August). The lawnmower problem. In Proceedings of 5th Canadian Conference Computational Geometry, Waterloo, Canada (pp. 461-466). |
| [5] | Arkin, Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics 55 (3) pp 197– (1994) · Zbl 0819.90115 |
| [6] | Balch, T. (2000, May). The case for randomized search. IEEE International Conference on Robotics and Automation Workshop on Sensors and Motion, San Francisco, CA. |
| [7] | Bochtis, D., Vougioukas, S., Tsatsarelis, C., & Ampatzidis, Y. (2006, September). 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). |
| [8] | Cao, Region filling operations with random obstacle avoidance for mobile robotics, Journal of Robotic Systems 5 (2) pp 87– (1988) |
| [9] | Choi, H. I., Han, C. Y., Choi, S. W., Moon, H. P., Roh, K. H., & Wee, N.-S. (2001a). Two-dimensional offsets via medial axis transform I: Mathematical theory. Preprint. Available at http://newton.kias.re.kr/swchoi/homepage/offset_theory.pdf. Accessed 9 August 2007. |
| [10] | Choi, H. I., Han, C. Y., Choi, S. W., Moon, H. P., Roh, K. H., & Wee, N.-S. (2001b). Two-dimensional offsets via medial axis transform II: Algorithm. Preprint. Available at http://newton.kias.re.kr/swchoi/homepage/offset_alg.pdf. Accessed 9 August 2007. |
| [11] | Choset, Coverage for robotics-A survey of recent results, Annals of Mathematics and Artificial Intelligence 31 pp 113– (2001) · Zbl 1314.68317 |
| [12] | Choset, H., & Pignon, P. (1997, December). Coverage path planning: The boustrophedon cellular decomposition. In International Conference on Field and Service Robotics, Canberra, Australia. |
| [13] | Felkel, P., & Obdrzalek, S. (1998, April). Straight skeleton implementation. In Proceedings of Spring Conference on Computer Graphics, Budmerice, Slovakia (pp. 210-218). |
| [14] | Hansen, Modeling and analysis of row crop harvesting patterns by combines, Transactions of the ASABE 50 (1) pp 5– (2007) · doi:10.13031/2013.22397 |
| [15] | Hunt, Farm power and management (2001) |
| [16] | Latombe, Robot motion planning (1991) · doi:10.1007/978-1-4615-4022-9 |
| [17] | Liu, Efficient field courses around an obstacle, Journal of Agricultural Engineering 44 pp 87– (1989) |
| [18] | Maciejowski, Predictive control with constraints (2002) · Zbl 0978.93002 |
| [19] | Noguchi, N., Reid, J. F., Zhang, Q., & Will, J. D. (2001, July). Turning function for robot tractor based on spline function. In ASAE Annual Meeting 2001, Sacramento, CA (ASAE Paper No. 011196). |
| [20] | Oksanen, T., & Visala, A. (2004, October). Optimal control of tractor-trailer system in headlands. Proceedings of the Automation Technology for Off-road Equipment (ATOE) 2006 Conference, Kyoto, Japan (pp. 255-263). |
| [21] | Oksanen, T. (2007). Path planning algorithms for agricultural field machines. Doctor of Science in Technology Dissertation, Automation Technology Laboratory, Helsinki University of Technology, Espoo, Finland. |
| [22] | Palmer, Energex proceedings (1984) |
| [23] | Palmer, Efficient path generation for field operations (Rept.) (1988) |
| [24] | Palmer, Improving the efficiency of field operations, Biosystems Engineering 84 (3) pp 283– (2003) |
| [25] | Pandey, Analytical determination of an optimum mechanical harvesting pattern for high field efficiency and low-cost of operation, Journal of Agricultural Engineering Research 36 (4) pp 261– (1987) |
| [26] | Ryerson, A. E., & Zhang, Q. (2006, September). 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). |
| [27] | Sorensen, AgEng 2004 (2004) |
| [28] | Stoll, A. (2003, June). Automatic operation planning for GPS-guided machinery. In Proceedings of 4th European Conference on Precision Agriculture, Berlin, Germany (pp. 657-664). |
| [29] | Witney, Choosing and using farm machines (1996) |
| [30] | Yang, S.-N., & Huang, M.-L. (1993). A new offsetting algorithm based on tracing technique. In Proceedings of the Second ACM Symposium on Solid Modeling and Applications (pp. 201-210). Association for Computing Machinery. |
| [31] | Yang, A neural network approach to complete coverage path planning, IEEE Transactions on Systems, Man and Cybernetics 34 (1) pp 718– (2004) |
| [32] | Zelinsky, A., Jarvis, R. A., Byrne, J. C., & Yuta, S. (1993, November). Planning paths of complete coverage of an unstructured environment by a mobile robot. In Proceedings of International Conference on Advanced Robotics, Tokyo, Japan (pp. 533-538). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
