Path planning has been a challenging task for researchers working towards automation in various fields. The objective of coverage path planning (CPP) is finding a path that covers all the points in the search space, avoiding obstacles. Coverage path planning is a key component in many robotic applications such as and not limited to automated machinery in agriculture, autonomous underwater vehicles, unmanned aerial vehicles, lawn mowers, floor cleaners, and industrial robots. Major research has been done on optimizing the solution for covering path planning algorithms. However, there is no major survey available on the application of coverage path planning in agriculture. This paper aims to fulfill the void by discussing a detailed survey on the techniques, methodology and the performance of covering path planning algorithms applied in the field of agriculture. Finally, various techniques are compared based on the parameters used for validating the performance of the algorithms. This work is aimed to be a starting point for researchers who are initiating their endeavors in coverage path planning to be applied in the field of agriculture. This work is steered in that direction, to provide a comprehensive review of the various CPP algorithms proposed so far, for application in agriculture.

Coverage Path Planning, 3-Dimensional Coverage, Agriculture, Autonomous Systems

[1] Hu Y, Yang SX., “A knowledge based genetic algorithm for path planning of a mobile robot”’. In: Proceedings of the 2004 IEEE, international conference on robotics & automation, New Orleans USA , pp. 4350–4355, 2004
[2] T. Lozano-Perez, M.A. Wesley, “An algorithm for planning collision-free paths among polyhedral obstacles”, ACM Communications, Vol. 2, pp. 959–962, 1979
[3] S.M. LaValle, “Planning Algorithms”, Cambridge University Press, pp. 130–131, 2006.
[4] J.H. Reif, Z. Sun, “An efficient approximation algorithm for weighed region shortest path problem, Algorithmic and Computational Robotics: New Directions, A.K. Peters, pp. 191–203, 2001
[5] Z.L. Cao, Y. Huang, E.L. Hall, “Region filling operations with random obstacle avoidance for mobile robotics”, Journal of Robotic Systems” Vol 5, Issue 2, pp.87–102, 1988
[6] M. Bosse, N. Nourani-Vatani, J. Roberts, Coverage algorithms for an underactuatedcar-like vehicle in an uncertain environment, in: Proc. IEEE Int.Robotics and Automation Conf., 2007, pp. 698–703.
[7] P. Atkar, A.L. Greenfield, D.C. Conner, H. Choset, A. Rizzi, Uniform coverage of automotive surface patches, The International Journal of Robotics Research Vol 24, Issue 11, pp 883–898, 2005
[8] M. Ollis, A. Stentz, First results in vision-based crop line tracking, in:Proc. Conf. IEEE Int. Robotics and Automation, Vol. 1, pp. 951–956, 1996
[9] M. Ollis, A. Stentz, Vision-based perception for an automated harvester, in: Proc. IEEE/RSJ Int. Intelligent Robots and Systems IROS’97. Vol. 3, pp. 1838–1844, 1997
[10] F. Yasutomi, M. Yamada, K. Tsukamoto, Cleaning robot control, in: Proc. Conf. IEEE Int Robotics and Automation, pp. 1839–1841, 1988.
[11] [E.U. Acar, H. Choset, Y. Zhang, M. Schervish, Path planning for robotic demining: robust sensor-based coverage of unstructured environments and probabilistic methods, International Journal of Robotics Research. Vol. 22, Issue 7, pp. 441–466, 2003.
[12] S. Hert, S. Tiwari, V. Lumelsky, A terrain-covering algorithm for an auv, Autonomous Robots , pp 91–119, 1996.
[13] Z.L. Cao, Y. Huang, E.L. Hall, Region filling operations with random obstacle avoidance for mobile robotics, Journal of Robotic Systems Vol 5, Issue 2, 87–102, 1988.
[14] D. MacKenzie and T. Balch, Making a clean sweep: Behavior based vacuuming, in: AAAI Fall Symposium, Instationating Real-World Agents, 1996.
[15] J. Palacin, T. Palleja, I. Valganon, R. Pernia, J. Roca, Measuring coverage performances of a floor cleaning mobile robot using a vision system, in: Proceedings of the 2005 IEEE International Conference on, Robotics and Automation, 2005.ICRA 2005. pp. 4236–4241.
[16] D. Gage, Randomized search strategies with imperfect sensors, in: Proc. SPIE Mobile Robots VIII, Boston, MA (September 1993) pp. 270–279.
[17] T. Balch, The case for randomized search, in: Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation, San Francisco, CA (May 2000).
[18] H. Choset,Coverage for robotics—a survey of recent results, Annals of Mathematics and Artificial Intelligence 31 (2001) 113–126.
[19] EnricGalceran, Marc Carreras, A survey on coverage path planning for robotics, Robotics and Autonomous systems 61 (2013) 1258-1276.
[20] H. Moravec and A. Elfes, High resolution maps for wide angles sonar, in: IEEE Int. Conf. on Roboticsand Automation (1985).
[21] A. Elfes, Sonar-based real-world mapping and navigation, IEEE J. Robotics Autom. 3 (1987) 249–265.
[22] J.S. Oh, Y.H. Choi, J.B. Park, Y. Zheng, Complete coverage navigation of cleaning robots using triangular-cell-based map, IEEE Transactions on Industrial Electronics 51 (3) (2004) 718–726.
[23] A. Zelinsky, R.A. Jarvis, J.C. Byrne and S. Yuta, Planning paths of complete coverage of an unstructured environment by a mobile robot, in: Proceedings of International Conference on Advanced Robotics, Tokyo, Japan (November 1993) pp. 533–538.
[24] O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, Internat. J. Robotics Res. 5 (1986) 90–98.
[25] J. Barraquand and J.-C.Latombe, "Robot Motion Planning: A Distributed Representation Approach", International Journal of Robotics Research Vol. 10 No.6, pp628-649, 1991.
[26] R.A. Jarvis and J.C. Byrne, "Robot Navigation: Touching, Seeing and Knowing", Proceedings of 1st Australian Conference on Artificial Intelligence, November 1986.
[27] V. Shivashankar, R. Jain, U. Kuter, D. Nau, Real-time planning for covering an initially-unknown spatial environment, in: Proceedings of the Twenty- Fourth International Florida Artificial Intelligence Research Society Conference, 2011.
[28] Y. Gabriely, E. Rimon, Spiral-stc: an on-line coverage algorithm of grid environments by a mobile robot, in: Proc. IEEE Int. Conf. Robotics and Automation, ICRA’02, Vol. 1, 2002, pp. 954–960.
[29] E. Gonzalez, O. Alvarez, Y. Diaz, C. Parra, C. Bustacara, Bsa: a complete coverage algorithm, in: Proc. IEEE Int. Conf. Robotics and Automation ICRA 2005, 2005, pp. 2040–2044.
[30] Y.-H. Choi, T.-K.Lee, S.-H.Baek, S.-Y. Oh, Online complete coverage path planning for mobile robots based on linked spiral paths using constrained inverse distance transform, in: Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems IROS 2009, 2009, pp. 5788–5793.
[31] T.-K. Lee, S.-H.Baek, Y.-H.Choi, S.-Y. Oh, Smooth coverage path planning and control of mobile robots based on high-resolution grid map representation, Robotics and Autonomous Systems 59 (10) (2011) 801–812.
[32] L. Hodgkin, A.F. Huxley, A quantitative description of membrane current and its application to conduction and exitation in nerve, Journal of Physics London 117 (1952) 500–544.
[33] C. Luo, S. Yang, A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments, IEEE Transactions on Neural Networks 19 (7) (2008) 1279–1298.
[34] X. Qiu, J. Song, X. Zhang, S. Liu, A complete coverage path planning method for mobile robot in uncertain environments, in: Proc. Sixth World Congress Intelligent Control and Automation WCICA 2006, Vol. 2, 2006, pp. 8892–8896.
[35] L. Paull, S. Saeedi, H. Li, V. Myers, An information gain based adaptive path planning method for an autonomous underwater vehicle using sidescan sonar, in: 2010 IEEE Conference on Automation Science and Engineering, CASE, 2010, pp. 835–840.
[36] L. Paull, S. Saeedi Gharahbolagh, M. Seto, H. Li, Sensor driven online coverage planning for autonomous underwater vehicles, in: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, 2012, pp. 2875–2880.
[37] J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, 1991.
[38] H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementation, The MIT Press, 2005.
[39] F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction (Springer-Verlag, Berlin,1985) pp. 198–257.
[40] J. VanderHeide and N.S.V. Rao, Terrain coverage of an unknown room by an autonomous mobile robot, Technical report ORNL / TM-13117, Oak Ridge National Laboratory, Oak Ridge, TN (1995).
[41] H. Choset, E. Acar, A. Rizzi and J. Luntz, Exact cellular decompositions in terms of critical points of morse functions, in: IEEE International Conference on Robotics and Automation, San Francisco, CA (2000).
[42] H. Choset and P. Pignon, Coverage path planning: The boustrophedon decomposition, in: Proceedings of the International Conference on Field and Service Robotics, Canberra, Australia (December1997).
[43] E.U. Acar, H. Choset, A.A. Rizzi, P.N. Atkar, D. Hull, Morse decompositions for coverage tasks, International Journal of Robotics Research 21 (4) (2002) 331–344.
[44] J. Milnor, Morse Theory, Princeton University Press, 1963.
[45] E.U. Acar, H. Choset, A.A. Rizzi, P.N. Atkar, D. Hull, Morse decompositions for coverage tasks, International Journal of Robotics Research 21 (4) (2002) 331–344.
[46] G. Reeb, Sur les points singuliersd’uneforme de Pfaff complètementintégrableoud’une function numérique, ComptesRendus de l’Académie des Sciences 222 (1946) 847–849.
[47] S.C. Wong, B.A. MacDonald, A topological coverage algorithm for mobile robots, in: Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, IROS 2003, Vol. 2, 2003, pp. 1685–1690.
[48] Z.J. Butler, A.A. Rizzi, R.L. Hollis, Contact sensor-based coverage of rectilinear environments, in: Proc. IEEE Int Intelligent Control/Intelligent Systems and Semiotics Symposium, 1999, pp. 266–271.
[49] L. Xu, Graph Planning for Environmental Coverage, Ph.D. Thesis, Carnegie Mellon University, 2011.
[50] V.J. Lumelsky, S. Mukhopadhyay, K. Sun, Dynamic path planning in sensor based terrain acquisition, IEEE Transactions on Robotics and Automation 6 (4) (1990) 462–472.
[51] T.-S. Lee, J.-S.Choi, J.-H.Lee, B.-H. Lee, 3-d terrain covering and map building algorithm for an auv, in: Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems IROS 2009, 2009, pp. 4420–4425.
[52] P.N. Atkar, H. Choset, A.A. Rizzi, E.U. Acar, Exact cellular decomposition of closed orientable surfaces embedded in r3, in: Proc. ICRA Robotics and Automation IEEE Int. Conf, Vol. 1, 2001, pp. 699–704.
[53] P. Cheng, J. Keller, V. Kumar, Time-optimal uav trajectory planning for 3D urban structure coverage, in: IEEE/RSJ International Conference on, Intelligent Robots and Systems, 2008, IROS 2008, 2008, pp. 2750–2757.
[54] Kanae Tanigaki, Tateshi Fujiura, Akira Akase, Junichi Imagawa, Cherry-harvesting robot, Computers and Electronics in Agriculture 63 (2008) 65-27
[55] Y.Yanwei, Z.Xiaochao, Z.Huaping, Apple harvesting robot picking path planning and simulation, International conference on Information Engineering and Computer Science, 2009, pp. 1-4
[56] E.J. Van Henten, J.Hemmin, B.A.J. Van Tuijl, J.G. Kornet, J. Bontsema, Collision-free Motion Planning for a Cucumber Picking Robot, Biosystems Engineering (2003) 86 (2), 135-144
[57] A. J. Scarfe, R. C. Flemmer, H. H. Bakker and C. L. Flemmer, Development of An Autonomous Kiwifruit Picking Robot, Proceedings of the 4th International Conference on Autonomous Robots and Agents, Feb 10-12, 2009. pp 380-384.
[58] Yael Edan, Member, IEEE, Dima Rogozin, Tamar Flash, and Gaines E. Miles, IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION, VOL. 16, NO. 6, DECEMBER 2000 pp 831-834
[59] Feng Qingchun, Zheng Wengang, Qiu Quan,Jiang Kai, Guo Rui, Study on Strawberry Robotic Harvesting System, IEEE International Conference on Computer Science and Automation Engineering (CSAE), 2012 pp 320-324
[60] G. Muscato, M. Prestifilippo, Nunzio Abbate and Ivan Rizzuto, A prototype of an orange picking robot: past history, the new robot and experimental results, Industrial Robot: An International Journal 32/2 (2005) pp 128-138
[61] Ibrahim A. Hameed, Dionysis Bochtis, and Claus A. Sørensen, An Optimized Field Coverage Planning Approach for Navigation of Agricultural Robots in Fields Involving Obstacle Areas, Int J Adv Robotic Sy, 2013, Vol. 10, 231:2013, pp 1-9
[62] Whitley D (1994) A Genetic Algorithm Tutorial. Statistics and Computing 4(2): 65‐85.
[63] Jung Won Kang, Si Jong Kim and Myung Jin Chung, Path Planning for Complete and Efficient Coverage Operation of Mobile Robots. In Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation. August 5-8, 2007, Harbin, China.
[64] Simon X. Yang and ChaominLuo.A Neural Network Approach to Complete Coverage Path Planning. IEEE Transactions on Systems, Man,and Cybernetics-Part B:Cybernetics, 2004,34(1):718-725.
[65] Yan Ma, Hua-bo Liu and Shu-huaXu. Path Planning Design for Cleaning Robot. Machinery and Electronics, 2008 (7): 64-67.
[66] A.E.F. Ryerson and Q. Zhang. “Vehicle Path Planning for Complete Field Coverage Using Genetic Algorithms”. Agricultural Engineering International: the CIGR Ejournal. Manuscript ATOE 07 014. Vol. IX. July, 2007. pp 1-11
[67] Lin, H.-S., J. Xiao, and Z. Michalewicz. 1994. Evolutionary algorithm for path planning inmobile robot environment. In Proc. IEEE Conference on Evolutionary Computation, 1:211-216. Piscataway, NJ, USA: IEEE.
[68] Hwang Y.K., Ahuja, N. (1992). Gross Motion Planning.A Survey,.ACMComputing Surveys, vol. 24, no. 3, pp. 219-290, (1992).
[69] D.D. Bochtis, C.G. Sorensen, S.G. Vougioukas, Path planning for in-field navigation-aiding of service units, Computers and Electronics in Agriculture 74 (2010) 80-90
[70] K. Zhou, A. Leck Jensen, C.G. Sørensen, P. Busato, D.D. Bothtis, Agricultural operations planning in fields with multiple obstacle areas, Computers and Electronics in Agriculture 109 (2014) pp 12–22
[71] Toussaint, G.T., 1983. Solving geometric problems with the rotating calipers. In:Proc. 2nd IEEE Mediterranean Electrotechnical Conference (MELECON 1983),pp. 1–4.
[72] Dorigo, M., Gambardella, L.M., 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans. Evol. Comput. 1 (1),53–66.
[73] Timo Oksanen and Arto Visala, Coverage Path Planning Algorithms for Agricultural Field Machines, Journal of Field Robotics 26(8), 651–668 (2009) pp 651-668
[74] Felkel, P., &Obdrzalek, S. (1998, April). Straight skeleton implementation. In Proceedings of Spring Conferenceon Computer Graphics, Budmerice, Slovakia (pp. 210– 218).
[75] Bochtis, D.D., Oksanen, T., Combined coverage path planning for field operations, 7th European Conference on Precision Agriculture, Wageningen, the Netherlands.
[76] I. Rekleitis, A. New, E. Rankin, H. Choset, Efficient boustrophedon multirobot coverage: an algorithmic approach, Annals of Mathematics and Artificial Intelligence 52 (2009) 109–142. http://dx.doi.org/10.1007/s10472-009-9120-2.
[77] N. Hazon, G. Kaminka, Redundancy, efficiency and robustness in multi-robot coverage, in: Proceedings of the 2005 IEEE International Conference on, Robotics and Automation, 2005, ICRA 2005, 2005, pp. 735–741.
[78] C. Luo, S. Yang, A real-time cooperative sweeping strategy for multiple cleaning robots, in: Proceedings of the 2002 IEEE International Symposium on, Intelligent Control, 2002, 2002, pp. 660–665.
[79] K. Easton, J. Burdick, A coverage algorithm for multi-robot boundary inspection, in: Proceedings of the 2005 IEEE International Conference on, Robotics and Automation, 2005, ICRA 2005, 2005, pp. 727–734.
[80] M.A. Batalin, G.S. Sukhatme, Spreading out: a local approach to multi-robot coverage, in: Proceedings of the 6th International Symposium on Distributed Autonomous Robotics Systems, 2002, pp. 373–382.
[81] Guoyu Zuo, Peng Zhang, and Junfei Qiao, Path Planning Algorithm Based on Sub-Region for Agricultural Robot, 2010 2nd International Asia Conference on Informatics in Control, Automation and Robotics, pp 197-200
[82] D.D. Bochtis, C.G. Sorensen, S.G. Vougioukas, Path planning for in-field navigation-aiding of service units, Computers and Electronics in Agriculture 74 (2010) 80-90
[83] A. Hameed, Intelligent Coverage Path Planning for Agricultural Robots and Autonomous Machines on Three-Dimensional Terrain, J Intell Robot Syst (2014) 74:965–983
[84] Hameed, I.A., Bochtis, D.D., Sørensen, C.G., Vougioukas, S.: An object oriented model for simulating agricultural in-field machinery activities. Computers and Electronics in Agriculture. 81(1), 24–32 (2012)
[85] Fröba, N., Funk, M.: TeilzeitspezifischeDieselbedarfskalkulationbeiArbeiten in der Außenwirtschaft. KTBL-Arbeitsblatt: Landtechnik und Pflanzenbau Nr. 0255 ‘BenötigteTraktormotornennleistungbeilandwirtschaftlichenArbeiten’ (N. Fröba, 1995)(in Germany) (1995)
[86] Jian Jin and Lie Tang, Coverage Path Planning on Three-Dimensional Terrain for Arable Farming, Journal of Field Robotics 28(3), 424–440 (2011) pp 424-440
[87] Koostra, B. K., Stombaugh, T., Mueller, G. T., & Shearer, A. S.(2006, July). Evaluating the effect of terrain on field area measurements. In 2006 ASABE Annual Meeting. ASABE Paper No. 061045. St. Joseph, MI: ASABE.
[88] Van Doren, A. C., Stauffer, S. R., & Kidder, H. E. Effect of contour farming on soil loss and runoff. Soil Science Society of America Proceedings, 15, 413–417,1950.
[89] Wendt, G. (1998). Guidelines for the use of the revised universal soil loss equation (RUSLE) version 1.06 on mined lands, construction sites, and reclaimed lands. Denver,CO: Peabody Western Coal Company.
[90] Gesch, D. B. (2007). The National Elevation Dataset.In D.Maune (Ed.), Digital elevation model technologies and applications: The DEM users manual, 2nd ed. (pp. 99–118). Bethesda, MD: American Society for Photogrammetry and Remote Sensing.