Welcome to Smart Agriculture 中文
Special Issue--Artificial Intelligence and Robot Technology for Smart Agriculture

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

  • ZHOU Longgang , 1, 2 ,
  • LIU Ting , 2 ,
  • LU Jinzhu 1, 2
Expand
  • 1. School of Mechanical Engineering, Xihua University, Chengdu 610039, China
  • 2. Research Institute of Modern Agricultural Equipment, Xihua University, Chengdu 610039, China
LIU Ting, E-mail:

Received date: 2023-07-28

  Online published: 2023-10-11

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)

Copyright

copyright©2023 by the authors

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 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.

Cite this article

ZHOU Longgang , LIU Ting , LU Jinzhu . Traversal Path Planning for Farmland in Hilly Areas Based on Floyd and Improved Genetic Algorithm[J]. Smart Agriculture, 2023 , 5(4) : 45 -57 . DOI: 10.12133/j.smartag.SA202308004

0 引 言

中国丘陵山区县耕地面积约占全国的34.62%,播种面积占全国的34.20%。该地区的农业发展对于中国农产品供给和农民脱贫致富至关重要1, 2。然而,丘陵地区的农田结构与平坦地区存在明显差异。丘陵地区田块小、分布密集、无规律且存在田埂阻隔,这给农机的作业带来了一系列挑战,使农业机械化和智能化发展受到严重阻碍。因此,发展适合丘陵山区的智能农机装备,是提高作业能力和质量、降低成本、保障国家粮食安全以及缓解农村劳动力不足的重要途径3, 4
路径规划作为智能农业系统中的关键组成部分,可以优化农机的行驶路线,最大程度地减少重复作业和时间浪费5, 6。通过合理的路径规划,使农机能够高效地覆盖农田,确保作物得到充分的耕作和管理,提高农作物产量和质量7, 8。在农业生产中,覆盖路径规划生成的覆盖田块的路径用于农机执行特定操作。例如,收获、播种和施肥等。对于单个田块的覆盖路径规划主要分为两个部分,首先根据农田数据以及农机参数生成一组平行的来回直线轨迹;其次连接平行轨迹,以形成由圆弧连接的最佳轨迹序列9。Nilsson和Zhou10将农田的覆盖轨迹表示为主要作业区域轨迹、地头通道以及转弯轨迹以构建虚拟路网图,最后基于图进行覆盖路径规划,实验证明该方法对于各类型田块都具有普适性。陈凯等11利用模拟退火算法获得最优路径集,并且通过单元拆解及合成的方式求解全覆盖遍历顺序,相对传统规则遍历方式,有效处理了不同边界约束,大幅减少了作业消耗。Vahdanjoo等12考虑到田块周围存在多个用于农机补货的仓库,设计了用于连接仓库、地头通道和覆盖路径的连接路径,并且采用模拟退火算法求解覆盖路径间的遍历顺序,相较于传统方法非工作行驶距离减少20%。
对于多田块现有相关研究集中于将大规模复杂形状农田按一定规律方法分解为若干形状简单的子农田,再利用智能算法基于相关遍历指标实现子农田的最优遍历排序。马全坤等13提出一种记忆模拟退火与A*算法相结合的遍历算法,首先通过记忆模拟退火算法搜索出任务最优目标点行走顺序,然后使用A*算法进行跨区域衔接路径规划。该算法规划的遍历路径曼哈顿距离比传统模拟退火算法减少9.4%,遍历路径覆盖率能达到100%,重复率控制为4.2%。Shen等14考虑到丘陵地区农田的坡度影响,基于农机的能耗消耗模型获取作业能耗最优的行驶角度,然后使用遗传算法获得多田块最优遍历次序,结果表明该方法能最大限度减少农机的能耗。
综上,现有的研究大多针对单个大田块的覆盖路径规划,而少数对于多田块遍历路径规划的研究中,通常采用直线距离作为距离代价。例如,以两个田块间覆盖路径终点与起点间的直线距离或田块间中心基点间的直线距离作为距离代价,进一步求算遍历各田块所需的总代价。然而这种方法未考虑实际田块间田埂对于农机转移路线的影响,可能导致距离代价与田块间实际的转移距离存在较大的误差,进而影响遍历路径规划效果。丘陵地区的农田田块小、分布密集且存在田埂阻隔。农机在单个田块内的覆盖路径规划相对容易解决,但面临着需要频繁进行田块间转移的问题。由于受田埂阻隔使田块间缺乏明确的连通关系,导致田块之间无法形成连续的行驶路线,需要反复寻找合适的位置进行转移,这样就增加了作业时间和成本。
针对以上问题,本研究旨在探讨适用于丘陵地区的农机田间路径规划方法。通过实地调查和数据收集,对丘陵地区的农田进行了详尽的研究,设计了一种用于建立田块间连通关系的方法,预测农业机器人在完成一个田块的覆盖路径后如何转移到下一个田块。同时提出了一种改进遗传算法与Floyd算法相结合的遍历算法。基于田块间的路网图,采用Floyd算法获得任意两个田块间覆盖路径端点距离,以该距离作为田块间转移所需的距离代价,经遗传算法得到多田块的最优遍历顺序,最后使用Floyd算法进行跨田块衔接路径规划,从而实现多田块农业机器人遍历路径规划。本研究旨在为农机在丘陵地区实现连续大面积作业提供理论指导和技术支持,从而提高作业效率和农业生产水平。

1 环境建模

1.1 结构空间法构建农田作业环境模型

本研究采用结构空间法15对田块进行环境建模,将农机工作环境的几何特征通过点、线、面映射到几何空间中进行描述。在实际作业中需要根据农机参数和作业参数预留转弯空间及地头区域。因此,田块被划分为两个功能区域:地头区域和主要作业区域。地头区域用于满足农机掉头和换行;主要作业区域由一系列的平行直线轨迹构成,农机在该区域进行耕作、播种等操作。地头区域宽度 W h计算方法如公式(1)所示。
W h = r + ω 2 + r × c o s φ
式中:表示农机的最小转弯半径,m; ω表示作业幅宽,m; φ表示作业方向与农田边界的夹角,°。根据该计算方式构建出农田的地头区域与主要作业区域,如图1(a)所示。
地头是紧邻田块边界的区域,专门用于农机进行转弯操作。在地头执行转弯时,农机不会进行具体的作业。这意味着在主要作业区域完成田块的覆盖工作后,农机可以在地头区域进行移动,以便顺利转移到下一个田块。这样的安排能够保证农机在田块间的移动更加高效和流畅。本研究在地头空间中设计了地头路径以及一些关键节点,如图1(b)所示,以预测农机如何转移到下一个田块。
图1 结构空间法构建田块仿真环境

Fig. 1 Structural space method to build field simulation environment

1.2 田间转移道路网的设计

农机在完成一个田块的覆盖路径后,需要根据每个田块的先后顺序,从当前田块进入到下一个田块。丘陵地区的田块小、分布密集且田块间受到田埂阻隔,田块间没有明确的连通关系,因此需要设计用于农机在田块间转移的路网。

1.2.1 建立田块间的连通关系

为建立两个相邻田块间的连通关系,本研究以各个多边形田块的中心基点代表该田块,设当前田块的中心点为P,以其为中心,向外扩展一个半径为R的圆,将包含在内的其他田块作为与其建立连接关系的候选田块,以此筛选出与当前田块可能相邻的田块。再以当前田块的地头路径拐角处的节点向相邻田块的地头路径每一个线段进行垂直投影,取垂直投影距离最短的线段为田块间候选的连通路径,以得到两个田块间可能存在的连接关系。建立田块间连接关系算法流程如图2所示。
图2 建立田块间连通关系的算法流程框图

Fig.2 Algorithm flowchart for establishing field block connectivity

其中,当前田块地头路径拐点与候选田块的地头路径进行垂直投影时,存在以下两种情况:
1)过地头路径拐角节点(Np )所作垂直投影点(Ni )的坐标落在相邻的田块地头路径上。此时田块间的连通关系如图3(a)所示。
2)过地头路径拐角节点(Np )所作垂直投影点(Ni )的坐标落在相邻的田块地头路径外。此时田块间为无效的连通关系如图3(b)所示。
图3 地头路径拐点与候选路径的关系

Fig. 3 The relationship between field boundary waypoints and candidate paths

1.2.2 连接关系的校验

通过以上方法得到的用于连接两个田块的路径可能会出现一些冗余的线段或者冗余的节点。因此在建立田块间的连接关系之前,需要对地图进行预处理,以修正其中的错误。
对于冗余节点,情况如图4(a)所示,在实际的道路网络中,当3条独立线段的各自端点(Q1、Q2、Q3)在一个较小的范围内汇集时,应该将这3个点视为一个点来处理。这种点的汇集使得道路网的拓扑关系能够更准确地表示和分析。又如图4(b)所示,ab两点为两个相邻田块地头路径上的拐点,过两点进行垂直投影得到直线L1和L2,两条地头路径在一个较小的区域内有多条连接它们的线段时,为了简化路网,只需要保留其中一条线段即可,可以将多余的连线去掉。
图4 田块间连接路径中的节点冗余与线段冗余

Fig. 4 Node redundancy and line segment redundancy in connection paths between field blocks

2 多田块间衔接路径规划

上一节提出了一种用于建立田块间连接关系的方法,以获得相邻田块间可能存在的连通路径。通过该方法可以构建出多个田块间的路网图16,如图5中红色和绿色虚线以及一些节点构成了两个田块的路网图。为了降低遍历路径的重复率并提高整体效率,本研究采用了经典的图算法——Floyd算法17, 18来解决所有田块间节点对之间的最短路径问题。通过该方法获得任意两个田块覆盖路径端点间的最短路径和距离,从而确定农机应该选择的最短路径。
图5 田块间的路网图

Fig. 5 Road network map between fields

2.1 田块间节点信息存储与初始化

在建立田块间的连接关系并进行校验后,每个田块的地头路径都具备了明确的连接关系(图5绿色虚线所示),同时知道节点之间的距离和节点之间的邻接关系。因此,整个路网可以被抽象为一个带有权重的无向图19图6(a)),同时利用距离矩阵(图6(b))来存储节点之间的邻接关系和距离信息。在对距离矩阵初始化时,不直接相连的节点间的距离用一个合适的较大整数N代替(I=500),同时对田块间连接路径的距离进行了适当增大(本研究对每一个连接路径的距离都增加10个单位)。这一措施旨在增大相连田块间的转移成本以避免产生过于复杂的田块间的转移路径。例如,一个田块转移到另一个田块需要经过第3个田块的情况。
图6 田块地头路径节点间的赋权无向图和距离矩阵

Fig. 6 Weighted undirected graph and distance matrix among headland path nodes within the fields

2.2 Floyd算法仿真试验

本小节旨在探讨Floyd算法的基本原理和步骤,并应用于解决实际田块间转移的最短路径问题。它的目的是找到从一个田块的覆盖路径终点到另一个田块的覆盖路径起点的最短路径,但它不仅限于两个节点间的最短路径,而是计算所有节点对之间的最短路径20

2.2.1 迭代计算

通过多次迭代来更新距离矩阵中的值,以逐步求得所有节点对之间的最短路径。在每一次迭代中,选择一个中间节点k,遍历每一对节点(ij), d i s t i j表示节点i与节点j之间的距离。比较距离矩阵中的值 d i s t i j d i s t i k + d i s t k j的大小,如果 d i s t i j > d i s t i k + d i s t k j则更新矩阵中 d i s t i j的值为 d i s t i k + d i s t k j,否则不更新距离矩阵中的值。在遍历完每一个节点时,算法停止迭代。此时,距离矩阵中的值已经收敛,表示所有节点对之间的最短路径已经计算完成。
通过多次迭代过后得到图5中各个节点间最短路径矩阵(图7),其中矩阵中元素的值代表对应节点间的最短路径距离。
图7 田块地头路径节点间的最短路径矩阵

Fig. 7 Shortest path matrix among headland path nodes within the fields

2.2.2 路径重构

在Floyd算法中,通过迭代计算和更新最短路径矩阵来获得所有节点对之间的最短路径。最短路径矩阵中的每个元素 d i s t i j表示从节点i到节点j的最短路径的长度,并不能直接找到从起点到终点所要经过的具体节点。因此,在执行Floyd算法时,除了计算每对节点之间的最短距离外,还需要维护一个记录中间节点的矩阵,记作path_matrix。在Floyd算法完成后,可以通过回溯的方式从起点到目标节点,重构最短路径节点序列。具体步骤如下:
1)从起始节点i开始,沿着path_matrixi][j]的信息从ij的下一个节点。假设这个节点为k,将i更新为k(即i=k)。
2)重复步骤1),直到i等于j,表示已经到达目标节点。
3)在回溯过程中,将每个经过的节点(包括ij)添加到一个路径列表中。该路径列表即为从节点i到节点j的最短路径节点序列。
图5为例,假设农机从左侧田块的覆盖路径终点(序号4)转移到右侧田块的覆盖路径起点(序号9)。经过路径重构过后的具体节点序列为4、5、12、11、10、9,路径总长度为132(dist[4][9]=142)。具体路径如图8黄色线段所示。
图8 田块间的最短转移路径

Fig. 8 Shortest transfer path between fields

3 田块间遍历顺序规划

旅行商问题(Traveling Salesman Problem,TSP)21,旨在找到一个最短的闭合回路,使得能够访问给定一组城市并返回起始城市,同时确保每个城市仅被访问一次。在农业机器人的场景中,田块可以视为城市,机器人需要覆盖每个田块一次,并以最短路径完成遍历任务。因此,可以将农业机器人的路径规划问题转化为TSP的求解,以获得最优路径。这个最优路径将确保农业机器人每次只访问每个田块一次,减少了冗余遍历,从而提高了整体效率。本研究借助遗传算法和优化技术来解决田块间遍历顺序这一商旅问题,达到优化农业机器人遍历路径的目标。

3.1 建立田块间的距离矩阵

在田块间的路径规划中,田块间的转移距离指的是从一个田块的覆盖路径终点到下一个覆盖路径的起点的最短路径的距离。不同于常规方法将田块中心点之间的直线距离或者田块间覆盖路径进出终点的直线距离作为优化代价。本研究采用Floyd算法来生成田块路网节点的最短路径矩阵(图7)。该矩阵中存储了任意两个田块间的最短路径距离,可以通过查询矩阵中的值来获取从一个田块的覆盖路径终点到另一个田块的覆盖路径起点的最短距离。该方法能更准确地评估田块间的实际距离,从而为多田块遍历顺序规划提供更精确和可行田块间距离代价。

3.2 基于改进遗传算法的多田块遍历顺序规划

遗传算法22, 23的基本思想是通过模拟自然界中的生物进化过程,利用遗传操作(选择、交叉、变异)对种群进行演化和优化,以找到问题的最优解或近似最优解。但遗传算法有可能在迭代的过程中过早地收敛到局部最优解,而无法找到全局最优解。针对遗传算法在路径规划中存在参数设置困难、收敛速度慢和易陷入局部最优解等问题,本研究采用了一种自适应的策略来优化算法性能。根据上一代种群适应度情况动态调整本代交叉概率和变异概率;同时通过自适应方式调整本代中保留父代数目和产生子代数目的比例以增加种群的多样性,并有效防止算法陷入局部最优解,提高算法效率。

3.2.1 遗传编码

本研究采用排列编码的方式将田块的遍历顺序问题表示为一串元素的排列顺序。设有N个田块,排列编码可以表示为一个长度为N的随机整数数组 P = { p 1 ,   p 2 ,   p 3 , , p n },其中 p i表示田块的序号, p i的取值如公式(2)所示:
p [ i ] = - N     p i   N , p i 0 , p i p j , i = 1,2 , , N                 i = 1,2 , , N                 i j , i , j = 1,2 , , N
式中:元素pi]的取值范围是从-N~N的整数,且排列编码中的所有元素都不为零,并且互不相同;数组P表示一种可能的田块遍历顺序,pi]的正负表示当前田块覆盖路径起点和终点位置的两种分布状态,因此,根据pi]的正负值可进一步解码得到对应田块遍历顺序下每个田块覆盖路径起点与终点的排列,即P=[(s1e2 ),(s2e2 ),(s3e3 ),…,(snen )],其中,(siei ) 表示第i个田块的覆盖路径的起点和终点节点序号。通过查找最短路径矩阵即可得到单个个体所需的总的距离代价L(由公式(3)可得),将该距离代价作为变量带入遗传算法中进行求解,从而得到优化过后的田块遍历顺序以及每个田块的进出口分布。因此,对于种群数量为M的种群可以表示为由M个行向量 P 组成的M×N的矩阵,以表示M种可能的田块遍历顺序。
L = i = 1 n d i s t e i s i + 1
式中: d i s t e i s i + 1表示当前田块覆盖路径终点与下一个田块覆盖路径起点间的最短距离。

3.2.2 适应度函数的设计

遗传算法的稳定性和收敛性与适应度函数密切相关。一般情况下,适应度值越高的个体表示其对于问题的解决方案越好,同时更有可能被选择为父代,通过遗传操作来产生下一代。相邻田块间的转移距离可通过最短距离矩阵得到,则种群中每一个个体的适应度由公式(4)得到:
F = α i = 1 n d i s t e i s i + 1      
式中: α表示惩罚系数,用于惩罚田块间没有直接连通关系需要经过第3个田块中转的情况,以筛选出连续的田块遍历顺序。

3.2.3 遗传操作

遗传操作包括选择、交叉和变异,以下为本研究中这些操作的具体步骤。
1)选择。本研究采用精英保留策略与轮盘赌选择策略相互结合的方式设计选择算子。将所有个体适应度值排序,从而筛选出 n 1个优秀个体,并让这些个体直接进入子代种群,而非通过遗传方式;随后采用轮盘赌选择策略,在 n 1个优秀个体中选择用于进行交叉和变异的父代,以产生足够的子代数目 n 2个,其中( n 1 + n 2 = M)。对于 n 1 n 2的数目分配,本研究采用一种自适应策略,具体表达如公式(5)~(8):
n 1 ' = s u m F > T × F a v g
n 2 ' = M - n 1 '
n 1 = n 2 ' ,    n 1 ' > n 2 ' n 1 ' ,    n 1 ' n 2 '
n 2 = n 1 ' ,    n 1 ' > n 2 ' n 2 ' ,    n 1 ' n 2 '
式中: F = F 1 , F 2 , F 3 , , F M,表示种群中每个个体的适应度集合; F a v g表示种群的平均适应度值; T 0 < T < 1)表示适应度阈值; n 1 '表示种群中适应度高于适应度阈值的个体数量; n 2 '表示适应度低于或等于阈值的个体数量。根据适应度高于阈值的个体数量和适应度低于或等于阈值的个体数量,来动态调整 n 1 n 2的数目。具体的设定规则如下:
如果适应度高于阈值的个体数量较多,意味着种群中有相当一部分个体的适应度较好,算法容易过早收敛导致早熟。适当降低 n 1和增大 n 2,通过增加遗传和变异的次数来保证种群多样性,避免陷入局部最优解。
如果适应度低于阈值的个体数目较多,意味着种群中有相当一部分个体的适应度较差,算法的收敛速度较慢且易陷入局部最优解。适当增大 n 1和减小 n 2,以便在下一代引入更多的多样性,使得种群更有可能逃离局部最优解,并加速全局搜索的过程。
2)交叉。从父代中随机选取两个个体进行顺序交叉操作,即先从一个父代个体中选择一个子序列,并保留其顺序不变;然后,按照另一个父代个体中未被选择的顺序,将子序列中的元素填充到子代个体的相应位置。具体操作如图9所示,选取父代P1中一段子序列(黄色片段),再将P2中未选中的部分(绿色片段)按照顺序插入到子序列中去,从而得到新的子代P3。
图9 田块遍历顺序研究中的交叉操作

Fig. 9 Crossbreeding operation in the study of field traversal sequence

3)变异。将经过交叉操作得到子代进行随机变异操作,即在田块序号的排列中随机选择两个位置,并交换这两个位置上的元素。为保证田块进出口位置的多样性,本研究对排列中的整数进行随机的取反操作。具体操作如图10所示,随机选取子代P3中两个元素交换位置得到P4,再对P4中的元素随机取反得到最后的变异个体P5。
图10 田块遍历顺序研究中的变异操作

Fig. 10 Mutation operation in the study of field traversal sequence

4)交叉和变异的自适应调整。交叉概率 P c和变异概率 P m对于算法的性能和运行效果有至关重要的影响。如果交叉概率过低或变异概率过高,种群的探索性会减弱,可能导致算法陷入局部最优解。而如果交叉概率过高或变异概率过低,种群的利用性会减弱,可能导致算法收敛速度较慢,需要更多的迭代次数才能达到较优解。基于以上情况,本研究设计了自适应的交叉概率和遗传概率,具体表达如公式(9)和(10)所示:
P c = P c ' × k 1 ,      n 1 ' > n 2 ' P c ' × k 2 ,      n 1 ' n 2 '
P m = P m ' × k 2 ,    n 1 ' > n 2 ' P m ' × k 1 ,    n 1 ' n 2 '
式中: P c ' P m '表示上一代种群的交叉概率和变异概率; k 1 ( 0 < k 1 < 1 ) k 2 1 < k 2)分别表示缩小系数和放大系数。根据适应度高于阈值的个体数量和适应度低于或等于阈值的个体数量,来动态调整交叉概率 P c和变异概率 P m,具体的设定规则如下:如果适应度高于阈值的个体数量较多,意味着种群中有相当一部分个体的适应度较好,算法容易陷入局部最优解中。适当增加变异概率并降低交叉概率可以增加种群多样性和减少优秀个体的信息交叉,避免过早陷入局部最优解的同时加速搜索过程。如果适应度低于阈值的个体数目较多,意味着种群中有相当一部分个体的适应度较差,算法的收敛速度较慢且易陷入局部最优解。适当增大交叉概率并减小变异概率有助于将优秀个体的优点组合起来,产生更优秀的后代个体,从而加速算法收敛。图11为本研究提出的改进遗传算法流程。
图11 田块遍历顺序研究中改进的遗传算法流程图

Fig. 11 Improved genetic algorithm flowchart for field traversal sequence study

3.3 改进遗传算法的田块遍历顺序仿真试验

为了验证在改进遗传算法下的遍历顺序规划效果,通过MATLAB仿真软件将改进遗传算法与传统遗传算法进行仿真试验,比较两种算法的遍历路径长度以及达到最短路径的迭代次数,以验证该算法的优化效果。
放大系数与缩小系数的目的是对变异概率与交叉概率进行轻微调整,变化过大会导致算法收敛速度过快,可能陷入局部最优解;变化过小会导致算法收敛速度过慢,可能无法在合理时间内找到有效解。根据多次试验分析,放大系数为1.05,缩小系数为0.95时,遗传算法在处理本研究问题时表现出较为优越的性能。表1为两种算法的主要参数设置。得到试验环境与参数后,将两种算法进行仿真试验,得到如图12所示的遍历顺序规划图,以及如图13所示的迭代曲线图。在经过20次仿真试验后,对各指标求平均值,所得试验数据如表2所示。
表1 田块遍历顺序研究中的两种算法主要参数设置

Table 1 Main parameter settings for two algorithms in field block traversal sequence research

算法

种群

大小

迭代

次数

交叉

概率

变异

概率

放大

系数

缩小

系数

适应度阈值
传统遗传算法 20 200 0.9 0.1 —— —— ——
改进遗传算法 20 200 0.9 0.1 1.05 0.95 0.8

注:“——”表示无该项参数。

图12 传统遗传算法与改进遗传算法的遍历顺序规划图

Fig. 12 Traversal sequence planning diagrams of traditional genetic algorithm and improved genetic algorithm

图13 传统遗传算法与改进遗传算法的迭代曲线图

Fig. 13 Iteration curve graphs of traditional genetic algorithm and improved genetic algorithm

表2 平均最短路径长度与平均收敛迭代次数仿真结果对比

Table 2 Comparison of simulation results for average shortest path length and average converged iterations

算法 平均最短路径长度/m 平均收敛迭代数/次
传统遗传算法 742.2 153
改进遗传算法 639.6 95
通过图12图13的对比结果可知,采用改进遗传算法在遍历顺序规划方面表现出更强的跳出局部最优解的能力,提高了解的质量。由表2中的数据可以看出,本研究改进的遗传算法相较于传统遗传算法具有更少的收敛迭代次数,使路径平均长度缩短13.8%。这进一步证明了本研究改进的遗传算法在优化问题中的有效性。

4 遍历路径规划仿真

为了验证本研究多田块路径规划方法下的农业机械覆盖路径的效果,利用真实的农田数据和田间作业参数进行仿真试验。仿真试验在MATLAB 2019a编程环境中进行。选择实际作业位于经纬度(103.61°E,30.47°N)的区域作为仿真对象,卫星图像如图14所示,作业区域由10组田块组成,除5号田块外其余田块边界轮廓不规整,各田块的数据参数如表3所示。农机的作业参数为:最小转弯半径1.5 m,作业幅宽2 m。
图14 遍历路径规划仿真试验的田块卫星图像

Fig. 14 Satellite images of field blocks for traversal path planning simulation experiments

表3 遍历路径规划仿真试验的田块数据参数

Table 3 Parameters of field data for traversal path planning simulation experiments

田块序号 面积/m2 周长/m 边界点数目/个
田块1 921 132 8
田块2 1 775 182 10
田块3 1 047 153 9
田块4 1 139 148 10
田块5 1 013 137 7
田块6 1 097 138 8
田块7 2 032 178 16
田块8 2 807 242 9
田块9 5 655 305 12
田块10 715 122 10
对于单个田块的覆盖路径规划,本研究采用往复式覆盖作业方式。该方式尽管在地头转弯区域的转弯方式难度较大,但在形状复杂农田作业环境中,作业方式易实现且具有作业覆盖率较高的优势24, 25。以平行于田块边界每条边的方向作为作业方向,遍历所有边界方向生成对应覆盖路径,最后保留覆盖路径最短的路径。田块1~10的覆盖路径仿真结果如图15所示。得到每个田块的覆盖路径起点及终点坐标后,按照本研究第2节中的方法建立田块间的连通关系路网,如图16所示。通过Floyd算法获得任意两个田块间转移所需要的距离,并将该距离作为距离代价。经遗传算法得到田块间的最优遍历顺序,然后使用Floyd算法进行跨田块衔接路径规划,使农业机器人能够以最小的移动损耗遍历所有目标点。
图15 田块遍历路径规划试验中作业区域田块覆盖路径仿真结果

Fig. 15 Simulation results of field block coverage paths in the field block traversal path planning experiment

图16 田块遍历路径规划试验中田块间的连通关系路网图

Fig. 16 Road network map of the connectivity between field blocks in the field block traversal path planning experiment

通过上述算法,得到作业区域案例遍历路径规划如图17所示,其中蓝色路径为覆盖路径起点和终点连接起来的;黄色路径为遍历路径。文献[13]提出以田块间中心基点间的直线距离作为距离代价,在每个田块内,选取离上一个田块覆盖路径终点最近的覆盖路径端点作为这个田块覆盖路径的起点。通过该方法得到作业区域案例遍历路径规划如图18所示。文献[14]以任意两个田块间覆盖路径终点与起点间的直线距离作为遗传算法中的距离代价,进一步求算遍历各田块所需的总代价,以此实现遍历次序的寻优,以该方法得到作业区域案例遍历路径规划如图19所示。将本研究与其余两种方法下田块遍历顺序、遗传编码、路径重复率和路径长度的对比记录在表4中。
图17 本算法下的多田块遍历路径规划仿真结果

Fig. 17 Simulation results of multi-field traversal path planning under the proposed algorithm in this paper

图18 文献[13]算法下多田块遍历路径规划仿真结果

Fig. 18 Simulation results of multi-field traversal path planning under the algorithm in reference[13

图19 文献[14]算法下多田块遍历路径规划仿真结果

Fig. 19 Simulation results of multi-field traversal path planning under the algorithm in reference [14

表4 三种多田块遍历路径规划方法对比

Table 4 Comparison of three multi-field traversal path planning methods

方法 遍历顺序 遗传编码 路径重复率/% 转移路径长度/m
本研究 1-2-3-4-5-6-7-8-9-10 1,-2,-34,-5,-678,-9,-10 0.00 417.41
文献[13 1-10-9-8-7-6-5-4-3-2 [-1,-10,-9,-8,-7,-6,5,4,-3,2] 1.05 483.20
文献[14 1-2-3-4-5-6-7-8-9-10 1,-2,-34,-5,-6789,-10 0.00 430.31
通过图17~图19表4可以看出,本研究提出算法相较于文献[13]算法和文献[14]算法转移路径长度分别缩短了15.8%和3.1%。试验结果表明,上述3种方法得到的田块遍历顺序以及进出口的排布,在路径长度和路径重复率方面,本方法表现出更为优越的性能,田块遍历顺序和进出口的安排能够有效地降低路径长度和路径的重复率。

5 结论与展望

为解决丘陵地区农田环境下农业机器人遍历多个田块的遍历路径问题,本研究提出了一种结合Floyd算法和改进遗传算法的遍历路径规划方法,主要结论如下。
1)针对丘陵地区的田块小、分布密集且田块间由田埂阻隔,田块间没有明确的连通关系等问题,本研究提出了用于建立田块间连通关系的方法,以预测农业机器人在完成一个田块的覆盖路径过后如何转移到下一个田块。
2)针对田块遍历顺序规划问题,本研究提出了一种改进的遗传算法。通过自适应策略,本算法根据上一代种群适应度情况,动态调整了本代的交叉概率和变异概率,以适应问题特性。同时动态调整本代中保留父代和产生子代的比例,增加了种群多样性,提高了全局解搜索能力。MATLAB仿真试验结果显示,采用改进的遗传算法的平均遍历路径距离相较传统遗传算法减少13.8%。
3)针对农业机器人多田块的覆盖路径规划,提出了一种改进遗传算法与Floyd算法相结合的遍历算法。基于田块间的路网图,采用Floyd算法获得任意两个田块间覆盖路径端点距离,以该距离作为田块间转移所需的距离代价,经遗传算法得到多田块的最优遍历顺序。通过试验对比分析,通过本方法得到的田块遍历顺序和进出口的安排能够有效地降低路径的长度和路径的重复率,证明了所提出方法的优越性和可行性,同时算法输出的轨迹坐标能为农机驾驶员或无人农机大面积作业提供路径参考。
在未来的研究中将着重解决智能算法在实际应用中所面临的挑战,特别是关于导航系统的在线实时性和卡尔曼线性滤波等方面的问题。同时,将进一步研究其他因素,如处理高田埂情况下的遍历路径规划,考虑覆盖路径规划中的封边操作以及开发新的覆盖路径规划方法,以更好地满足实际生产需求。

利益冲突声明

本研究不存在研究者以及与公开研究成果有关的利益冲突。

1
张宗毅. “十四五”期间丘陵山区农田宜机化改造若干重大问题与举措[J]. 中国农村经济, 2020(11): 13-28.

ZHANG Z Y. Some important problems and measures of farmland construction suitable for mechanization in hilly and mountainous areas during the 14th five-year plan period[J]. Chinese rural economy, 2020(11): 13-28.

2
徐峰, 朱慧琴, 程胜男, 等. 大田无人农业发展现状与实现路径[J]. 农业工程, 2021, 11(3): 11-14.

XU F, ZHU H Q, CHENG S N, et al. Development status and realization path of unmanned agriculture in field[J]. Agricultural engineering, 2021, 11(3): 11-14.

3
张雁. 水田环境下的无人农机自动驾驶与作业系统研究[D]. 上海: 上海交通大学, 2019.

ZHANG Y. Research on automatic driving and working control system of unmanned agricultural machinery in paddy field[D]. Shanghai: Shanghai Jiao Tong University, 2019.

4
兰玉彬, 赵德楠, 张彦斐, 等. 生态无人农场模式探索及发展展望[J]. 农业工程学报, 2021, 37(9): 312-327.

LAN Y B, ZHAO D N, ZHANG Y F, et al. Exploration and development prospect of eco-unmanned farm modes[J]. Transactions of the Chinese society of agricultural engineering, 2021, 37(9): 312-327.

5
刘成良, 林洪振, 李彦明, 等. 农业装备智能控制技术研究现状与发展趋势分析[J]. 农业机械学报, 2020, 51(1): 1-18.

LIU C L, LIN H Z, LI Y M, et al. Analysis on status and development trend of intelligent control technology for agricultural equipment[J]. Transactions of the Chinese society for agricultural machinery, 2020, 51(1): 1-18.

6
LI S C, XU H Z, JI Y H, et al. Development of a following agricultural machinery automatic navigation system[J]. Computers and electronics in agriculture, 2019, 158: 335-344.

7
周俊, 何永强. 农业机械导航路径规划研究进展[J]. 农业机械学报, 2021, 52(9): 1-14.

ZHOU J, HE Y Q. Research progress on navigation path planning of agricultural machinery[J]. Transactions of the Chinese society for agricultural machinery, 2021, 52(9): 1-14.

8
罗锡文, 廖娟, 胡炼, 等. 我国智能农机的研究进展与无人农场的实践[J]. 华南农业大学学报, 2021, 42(6): 8-17, 5.

LUO X W, LIAO J, HU L, et al. Research progress of intelligent agricultural machinery and practice of unmanned farm in China[J]. Journal of South China agricultural university, 2021, 42(6): 8-17, 5.

9
JEON C W, KIM H J, YUN C, et al. Design and validation testing of a complete paddy field-coverage path planner for a fully autonomous tillage tractor[J]. Biosystems engineering, 2021, 208: 79-97.

10
NILSSON R S, ZHOU K. Method and bench-marking framework for coverage path planning in arable farming[J]. Biosystems engineering, 2020, 198: 248-265.

11
陈凯, 解印山, 李彦明, 等. 多约束情形下的农机全覆盖路径规划方法[J]. 农业机械学报, 2022, 53(5): 17-26, 43.

CHEN K, XIE Y S, LI Y M, et al. Full coverage path planning method of agricultural machinery under multiple constraints[J]. Transactions of the Chinese society for agricultural machinery, 2022, 53(5): 17-26, 43.

12
VAHDANJOO M, ZHOU K, SØRENSEN C A G. Route planning for agricultural machines with multiple depots: Manure application case study[J]. Agronomy, 2020, 10(10): ID 1608.

13
马全坤, 张彦斐, 宫金良. 基于记忆模拟退火和A*算法的农业机器人遍历路径规划[J]. 华南农业大学学报, 2020, 41(4): 127-132.

MA Q K, ZHANG Y F, GONG J L. Traversal path planning of agricultural robot based on memory simulated annealing and A* algorithm[J]. Journal of South China agricultural university, 2020, 41(4): 127-132.

14
SHEN M W, WANG S Z, WANG S A, et al. Simulation study on coverage path planning of autonomous tasks in hilly farmland based on energy consumption model[J]. Mathematical problems in engineering, 2020, 2020: 1-15.

15
申梦伟. 丘陵山地田间作业路径规划研究与试验[D]. 北京: 中国农业科学院, 2021.

SHEN M W. Research and experiment of field work path planning in hilly and mountainous regions[D]. Beijing: Chinese Academy of Agricultural Sciences, 2021.

16
HU X Z, JIANG Z H, XU C C. Vehicle path planning fusion algorithm based on road network[C]// 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). Piscataway, New Jersey, USA: IEEE, 2020: 98-102.

17
LYU D S, CHEN Z W, CAI Z S, et al. Robot path planning by leveraging the graph-encoded Floyd algorithm[J]. Future generation computer systems, 2021, 122: 204-208.

18
WANG L N, WANG H J, YANG X, et al. Research on smooth path planning method based on improved ant colony algorithm optimized by Floyd algorithm[J]. Frontiers in neurorobotics, 2022, 16: ID 955179.

19
LEI T, LUO C M, BALL J E, et al. A graph-based ant-like approach to optimal path planning[C]// 2020 IEEE Congress on Evolutionary Computation (CEC). Piscataway, New Jersey, USA: IEEE, 2020: 1-6.

20
AJEIL F H, IBRAHEEM I K, AZAR A T, et al. Grid-based mobile robot path planning using aging-based ant colony optimization algorithm in static and dynamic environments[J]. Sensors, 2020, 20(7): ID 1880.

21
周庆特. 考虑时变性的车辆与无人机联合配送路径规划问题[D]. 北京: 清华大学, 2019.

ZHOU Q T. The time dependent traveling salesman problem with drone[D]. Beijing: Tsinghua University, 2019.

22
李艳生, 万勇, 张毅, 等. 基于人工蜂群-自适应遗传算法的仓储机器人路径规划[J]. 仪器仪表学报, 2022, 43(4): 282-290.

LI Y S, WAN Y, ZHANG Y, et al. Path planning for warehouse robot based on the artificial bee colony-adaptive genetic algorithm[J]. Chinese journal of scientific instrument, 2022, 43(4): 282-290.

23
圣文顺, 徐爱萍, 徐刘晶. 基于蚁群算法与遗传算法的TSP路径规划仿真[J]. 计算机仿真, 2022, 39(12): 398-402, 412.

SHENG W S, XU A P, XU L J. Simulation of traveling salesman path planning based on ant colony algorithm and genetic algorithm[J]. Computer simulation, 2022, 39(12): 398-402, 412.

24
申航宇. 灾害情况下无人机与车辆协同路径规划研究[D]. 成都: 西华大学, 2021.

SHEN H Y. Research on collaborative path planning of UAV and vehicle in disasters[D]. Chengdu: Xihua University, 2021.

25
邵敏. 面向智能农机作业的全覆盖路径规划研究[D]. 合肥: 安徽农业大学, 2021.

SHAO M. Research on complete coverage path planning for intelligent agricultural machinery[D]. Hefei: Anhui Agricultural University, 2021.

Outlines

/