Welcome to Smart Agriculture

Smart Agriculture ›› 2023, Vol. 5 ›› Issue (4): 45-57.doi: 10.12133/j.smartag.SA202308004

• Special Issue--Artificial Intelligence and Robot Technology for Smart Agriculture • Previous Articles     Next Articles

Traversal Path Planning for Farmland in Hilly Areas Based on Floyd and Improved Genetic Algorithm

ZHOU Longgang1,2(), LIU Ting2(), LU Jinzhu1,2   

  1. 1. School of Mechanical Engineering, Xihua University, Chengdu 610039, China
    2. Research Institute of Modern Agricultural Equipment, Xihua University, Chengdu 610039, China
  • Received:2023-07-28 Online:2023-12-30
  • corresponding author:
    LIU Ting, E-mail:
  • About author:

    ZHOU Longgang, E-mail:

  • Supported by:
    Sichuan Provincial Department of Science and Technology Key Research and Development Project(2021YFN0020); Key Fund Project of Xihua University(Z202132); Sichuan Modern Agricultural Equipment Engineering and Technology Research Center(XDNY2021-004); Chengdu Science and Technology Bureau Technology Innovation Research and Development Project(2022-YF05-01127-SN)


[Objective] To addresses the problem of traversing multiple fields for agricultural robots in hilly terrain, a traversal path planning method is proposed by combining the Floyd algorithm with an improved genetic algorithm. The method provides a solution that can reduce the cost of agricultural robot operation and optimize the order of field traversal in order to improve the efficiency of farmland operation in hilly areas and realizes to predict how an agricultural robot can transition to the next field after completing its coverage path in the current field. [Methods] In the context of hilly terrain characterized by small and densely distributed field blocks, often separated by field ridges, where there was no clear connectivity between the blocks, a method to establish connectivity between the fields was proposed in the research. This method involved projecting from the corner node of the headland path in the current field to each segment of the headland path in adjacent fields vertically. The shortest projected segment was selected as the candidate connectivity path between the two fields, thus establishing potential connectivity between them. Subsequently, the connectivity was verified, and redundant segments or nodes were removed to further simplify the road network. This method allowed for a more accurate assessment of the actual distances between field blocks, thereby providing a more precise and feasible distance cost between field blocks for multi-block traversal sequence planning. Next, the classical graph algorithm, Floyd algorithm, was employed to address the shortest path problem for all pairs of nodes among the fields. The resulting shortest path matrix among headland path nodes within fields, obtained through the Floyd algorithm, allowed to determine the shortest paths and distances between any two endpoint nodes in different fields. This information was used to ascertain the actual distance cost required for agricultural machinery to transfer between fields. Furthermore, for the genetic algorithm in path planning, there were problems such as difficult parameter setting, slow convergence speed and easy to fall into the local optimal solution. This study improved the traditional genetic algorithm by implementing an adaptive strategy. The improved genetic algorithm in this study dynamically adjusted the crossover and mutation probabilities in each generation based on the fitness of the previous generation, adapting to the problem's characteristics. Simultaneously, it dynamically modified the ratio of parent preservation to offspring generation in the current generation, enhancing population diversity and improving global solution search capabilities. Finally, this study employed genetic algorithms and optimization techniques to address the field traversal order problem, akin to the Traveling Salesman Problem (TSP), with the aim of optimizing the traversal path for agricultural robots. The shortest transfer distances between field blocks obtained through the Floyd algorithm were incorporated as variables into the genetic algorithm for optimization. This process leads to the determination of an optimized sequence for traversing the field blocks and the distribution of entry and exit points for each field block. [Results and Discussions] A traversal path planning simulation experiment was conducted to compare the improved genetic algorithm with the traditional genetic algorithm. After 20 simulation experiments, the average traversal path length and the average convergence iteration count of the two algorithms were compared. The simulation results showed that, compared to the traditional genetic algorithm, the proposed improved genetic algorithm in this study shortened the average shortest path by 13.8%, with fewer iterations for convergence, and demonstrated better capability to escape local optimal solutions. To validate the effectiveness of the multi-field path planning method proposed in this study for agricultural machinery coverage, simulations were conducted using real agricultural field data and field operation parameters. The actual operating area located at coordinates (103.61°E, 30.47°N) was selected as the simulation subject. The operating area consisted of 10 sets of field blocks, with agricultural machinery operating parameters set at a minimum turning radius of 1.5 and a working width of 2. The experimental results showed that in terms of path length and path repetition rate, the present method showed more superior performance, and the field traversal order and the arrangement of imports and exports could effectively reduce the path length and path repetition rate. [Conclusions] The experimental results proved the superiority and feasibility of this study on the traversing path planning of agricultural machines in multiple fields, and the output trajectory coordinates of the algorithm can serve as a reference for both human operators and unmanned agricultural machinery during large-scale operations. In future research, particular attention will be given to addressing practical implementation challenges of intelligent algorithms, especially those related to the real-time aspects of navigation systems and challenges such as Kalman linear filtering. These efforts aim to enhance the applicability of the research findings in real-world scenarios.

Key words: hilly terrain, agricultural robots, traversal path planning, Floyd algorithm, improved genetic algorithm

CLC Number: