A Travelling Salesman Problem Approach to Efficiently Navigate Crop Row Fields with a Car-Like Robot
Keywords:
Autonomous Navigation, Robot Simulation, Precision Agriculture, Agricultural Robotics, Travelling Salesman ProblemAbstract
In recent years, interest in the use of mobile robots in the agricultural industry has increased, both to address labor shortages in rural areas and to increase food production in a more sustainable way. In order to have an efficient navigation system to cover long crop row fields, a path planner algorithm must consider maneuvering restrictions of the targeted robot. Most state-of-the-art works in agricultural navigation systems are intended for robots with a high degree of maneuverability that can typically make in-place turnings. This work aims to fill the gap in terms of the development of an efficient navigation system for car-like robots with limited turning radius in crop row fields. For this, we combine the global path planner A* and the local trajectory planner Timed Elastic Band (TEB). Additionally, we state the problem of finding an optimal path that covers the entire field as a Travelling Salesman Problem (TSP) that is based on the different turning maneuvers the robot can perform at field headlands. The solution of the TSP results in a time efficient coverage strategy that aligns with the robot's kinematics. Experiments performed in the Gazebo simulation environment show a reduction in field completion times of up to 20%, compared to trivial coverage paths. On the other hand, deviation of the robot with respect to the center of the field furrows was in all cases less than 10cm, which proves that the entire system operates with sufficient accuracy to avoid damaging the crops.
Downloads
References
S. Vougioukas, “Agricultural Robotics,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 2, no. 1, pp. 365–392, 2019.
J. Lowenberg-DeBoer, I. Huang, V. Grigoriadis, and S. Blackmore, “Economics of robots and automation in field crop production,” Precision Agriculture, pp. 278–299, 5 2020.
Y. Lu and S. Young, “A survey of public datasets for computer vision tasks in precision agriculture,” Computers and Electronics in Agriculture, vol. 178, p. 105760, 2020.
K. Jha, A. Doshi, P. Patel, and M. Shah, “A comprehensive review on automation in agriculture using artificial intelligence,” Artificial Intelligence in Agriculture, vol. 2, 6 2019.
A. Kamilaris and F. X. Prenafeta-Boldú, “Deep learning in agriculture: A survey,” Computers and Electronics in Agriculture, vol. 147, pp. 70–90, 2018.
M. Saleem, J. Potgieter, and K. Arif, “Automation in Agriculture by Machine and Deep Learning Techniques: A Review of Recent Developments,” Precision Agriculture, vol. 22, 4 2021.
G. Zhang, X. Chen, L. Zhang, B. Feng, X. Guo, J. Liang, and Y. Zhang, “STAIBT: Blockchain and CP-ABE Empowered Secure and Trusted Agricultural IoT Blockchain Terminal,” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 7, 9 2022.
Q. Ding and X. Xu, “Improved GWO Algorithm for UAV Path Planning on Crop Pest Monitoring,” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 7, pp. 30–39, 2022.
S. Bonadies and S. A. Gadsden, “An overview of autonomous crop row navigation strategies for unmanned ground vehicles,” Engineering in Agriculture, Environment and Food, vol. 12, no. 1, pp. 24–31, 2019.
P. Maini, B. M. Gonultas, and V. Isler, “Online Coverage Planning for an Autonomous Weed Mowing Robot With Curvature Constraints,” (IEEE) Robotics and Automation Letters, vol. 7, no. 2, pp. 5445–5452, 2022.
D. Ecobichon, “Pesticide use in developing countries,” Toxicology, vol. 160, no. 1, pp. 27–33, 2001.
K. Lewis, J. Tzilivakis, D. Warner, and A. Green, “An international database for pesticide risk assessments and management,” Human and Ecological Risk Assessment: An International Journal, vol. 22, no. 4, pp. 1050–1064, 2016.
M. Tudi, H. Daniel Ruan, L. Wang, J. Lyu, R. Sadler, D. Connell, C. Chu, and D. T. Phung, “Agriculture development, pesticide application and its impact on the environment,” International Journal of Environmental Research and Public Health, vol. 18, no. 3, 2021.
T. Pire, M. Mujica, J. Civera, and E. Kofman, “The Rosario dataset: Multisensor data for localization and mapping in agricultural environments,” Intl. Journal of Robotics Research, vol. 38, pp. 633–641, 2019.
M. Kloetzer, C. Mahulea, and R. Gonzalez, “Optimizing cell decomposition path planning for mobile robots using different metrics,” in 2015 19th International Conference on System Theory, Control and Computing (ICSTCC), pp. 565–570, 2015.
J. Sun, J. Tang, and S. Lao, “Collision Avoidance for Cooperative UAVs With Optimized Artificial Potential Field Algorithm,” IEEE Access, vol. 5, pp. 18382–18390, 2017.
M. Luo, X. Hou, and J. Yang, “Surface Optimal Path Planning Using An Extended Dijkstra Algorithm,” IEEE Access, vol. 8, pp. 147827–147838, 2020.
F. Duchoň, A. Babinec, M. Kajan, P. Beňo, M. Florek, T. Fico, and L. Jurišica, “Path Planning with Modified a Star Algorithm for a Mobile Robot,” Procedia Engineering, vol. 96, 12 2014.
X. Wang, X. Luo, B. Han, Y. Chen, G. Liang, and K. Zheng, “Collision-Free Path Planning Method for Robots Based on an Improved Rapidly-Exploring Random Tree Algorithm,” Applied Sciences, vol. 10, p. 1381, 2 2020.
L. Qiao, X. Luo, and Q. Luo, “An Optimized Probabilistic Roadmap Algorithm for Path Planning of Mobile Robots in Complex Environments with Narrow Channels,” Sensors, vol. 22, no. 22, 2022.
L. Kenye and R. Kala, “Optimistic Motion Planning Using Recursive Sub-Sampling: A New Approach to Sampling-Based Motion Planning,” International Journal of Interactive Multimedia and Artificial Intelligence, vol. 7, pp. 87–99, 2022.
J. Han, M. Cui, Y. Lv, K. Liu, Q. Dai, and H. Guo, “Moving Horizon path planning for intelligent vehicle oriented to dynamic obstacle avoidance,” in 2022 6th CAA International Conference on Vehicular Control and Intelligence (CVCI), 2022.
R. Bijay, M. Amarendra, and D. Asim, “Steer Guidance Of Autonomous Agricultural Robot Based On Pure Pursuit Algorithm And LiDAR Based Vector Field Histogram,” Journal of Applied Science and Engineering, vol. 26, pp. 1363–1372, 1 2023.
D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robotics & Automation Magazine, vol. 4, no. 1, pp. 23–33, 1997.
S. Quinlan and O. Khatib, “Towards real-time execution of motion tasks,” in Experimental Robotics II, pp. 239–254, Springer Berlin Heidelberg, 1993.
C. Rösmann, W. Feiten, T. Wosch, F. Hoffmann, and T. Bertram, “Efficient trajectory optimization using a sparse model,” in European Conf. on Mobile Robots (ECMR), pp. 138–143, 9 2013.
C. Rösmann, F. Hoffmann, and T. Bertram, “Online Trajectory Planning in ROS Under Kinodynamic Constraints with Timed-Elastic-Bands,” in Robot Operating System (ROS): The Complete Reference (Volume 2), (Cham), pp. 231–261, Springer Verlag, 5 2017.
T. Bakker, K. van Asselt, J. Bontsema, J. Müller, and G. van Straten, “Autonomous navigation using a robot platform in a sugar beet field,” Biosystems Engineering, vol. 109, no. 4, pp. 357–368, 2011.
M. Post, A. Bianco, and X.-T. Yan, “Autonomous Navigation with Open Software Platform for Field Robots,” in Informatics in Control, Automation and Robotics, (Cham), pp. 425–450, Springer Verlag, 1 2020.
J. Chen, H. Qiang, J. Wu, G. Xu, Z. Wang, and X. Liu, “Extracting the navigation path of a tomato-cucumber greenhouse robot based on a median point Hough transform,” Computers and Electronics in Agriculture, vol. 174, p. 105472, 2020.
F. B. Malavazi, R. Guyonneau, J.-B. Fasquel, S. Lagrange, and F. Mercier, “LiDAR-only based navigation algorithm for an autonomous agricultural robot,” Computers and Electronics in Agriculture, vol. 154, pp. 71–79, 2018.
J. Iqbal, R. Xu, S. Sun, and C. Li, “Simulation of an Autonomous Mobile Robot for LiDAR-Based In-Field Phenotyping and Navigation,” MDPI Robotics, vol. 9, no. 2, 2020.
D. Aghi, V. Mazzia, and M. Chiaberge, “Local Motion Planner for Autonomous Navigation in Vineyards with a RGB-D Camera-Based Algorithm and Deep Learning Synergy,” Machines, 5 2020.
P. Ruangurai, M. N. Dailey, M. Ekpanyapong, and P. Soni, “Optimal vision-based guidance row locating for autonomous agricultural machines,” Precision Agriculture, 2 2022.
R. Linker and T. Blass, “Path-planning algorithm for vehicles operating in orchards,” Biosystems Engineering, vol. 101, no. 2, pp. 152–160, 2008.
R. F. Carpio, C. Potena, J. Maiolini, G. Ulivi, N. B. Rosselló, E. Garone, and A. Gasparri, “A Navigation Architecture for Ackermann Vehicles in Precision Farming,” (IEEE) Robotics and Automation Letters, vol. 5, no. 2, pp. 1103–1110, 2020.
B. Cybulski, A. Wegierska, and G. Granosik, “Accuracy comparison of navigation local planners on ROS-based mobile robot,” in 12th International Workshop on Robot Motion and Control (RoMoCo), pp. 104–111, 7 2019.
A. Filotheou, E. Tsardoulias, A. Dimitriou, A. Symeonidis, and L. Petrou, “Quantitative and Qualitative Evaluation of ROS-Enabled Local and Global Planners in 2D Static Environments,” Journal of Intelligent & Robotic Systems, vol. 98, 6 2020.
P. Marı́n, A. Hussein, D. Martı́n Gómez, and A. de la Escalera, “Global and Local Path Planning Study in a ROS-Based Research Platform for Autonomous Vehicles,” Journal of Advanced Transportation, vol. 2018, 2 2018.
N. Koenig and A. Howard, “Design and use paradigms for Gazebo, an open-source multi-robot simulator,” in IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems (IROS), vol. March, pp. 2149–2154, 2004.
M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, and A. Ng, “ROS: an open-source Robot Operating System,” ICRA Workshop on Open Source Software, vol. 3, 1 2009.
J. Crowley, “Navigation of an Intelligent Mobile Robot,” IEEE Journal of Robotics and Automation, vol. RA-1, pp. 31–41, 4 1985.
D. Bochtis and S. Vougioukas, “Minimising the non-working distance travelled by machines operating in a headland field pattern,” Biosystems Engineering, vol. 101, pp. 1–12, 9 2008.
D. Bochtis, S. Vougioukas, and H. W. Griepentrog, “A Mission Planner for an Autonomous Tractor,” Transactions of the ASABE, vol. 52, 9 2009.
G. Laporte, “The traveling salesman problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, no. 2, pp. 231–247, 1992.
