智慧农业（中英文）2023，Vol.5Issue(4)：45-57,13.DOI:10.12133/j.smartag.SA202308004
基于Floyd和改进遗传算法的丘陵地区农田遍历路径规划
Traversal Path Planning for Farmland in Hilly Areas Based on Floyd and Improved Genetic Algorithm
摘要
Abstract
[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 head-land 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 se-quence 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 al-gorithm,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 genet-ic 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 ge-netic 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 preserva-tion to offspring generation in the current generation,enhancing population diversity and improving global solution search capabili-ties.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 dis-tances between field blocks obtained through the Floyd algorithm were incorporated as variables into the genetic algorithm for optimi-zation.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 algo-rithm with the traditional genetic algorithm.After 20 simulation experiments,the average traversal path length and the average conver-gence iteration count of the two algorithms were compared.The simulation results showed that,compared to the traditional genetic al-gorithm,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 simula-tion subject.The operating area consisted of 10 sets of field blocks,with agricultural machinery operating parameters set at a mini-mum 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 agricul-tural machines in multiple fields,and the output trajectory coordinates of the algorithm can serve as a reference for both human opera-tors and unmanned agricultural machinery during large-scale operations.In future research,particular attention will be given to ad-dressing 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.关键词
丘陵地区/农业机器人/遍历路径规划/Floyd算法/改进遗传算法Key words
hilly terrain/agricultural robots/traversal path planning/Floyd algorithm/improved genetic algorithm分类
信息技术与安全科学引用本文复制引用
周龙港,刘婷,卢劲竹..基于Floyd和改进遗传算法的丘陵地区农田遍历路径规划[J].智慧农业（中英文）,2023,5(4):45-57,13.基金项目
四川省科技厅重点研发项目(2021YFN0020) （2021YFN0020）
西华大学重点基金项目(Z202132) （Z202132）
四川省现代农业装备工程技术研究中心(XDNY2021-004) （XDNY2021-004）
成都市科技局技术创新研发项目(2022-YF05-01127-SN)Sichuan Provincial Department of Science and Technology Key Research and Development Project(2021YFN0020) （2022-YF05-01127-SN）
Key Fund Project of Xihua University(Z202132) （Z202132）
Sichuan Modern Agricultural Equipment Engineering and Tech-nology Research Center(XDNY2021-004) （XDNY2021-004）
Chengdu Science and Technology Bureau Technology Innovation Research and Develop-ment Project(2022-YF05-01127-SN) （2022-YF05-01127-SN）
