四边形田块下油菜联合收获机全覆盖作业路径规划算法

罗承铭，熊陈文，黄小毛※，丁幼春，王绍帅

（1. 华中农业大学工学院，武汉 430070；2. 农业农村部长江中下游农业装备重点实验室，武汉 430070）

0 引言

随着城镇化进程的不断推进，中国农村劳动力老龄化与短缺问题逐渐凸显，“机器换人”的需求日益增加。近年来随着农机自动导航技术和农用车辆底盘数字化驱动技术的快速发展，智能化的农业装备被广泛应用于农业生产的各个环节，无人农场生产模式正迅速地被广泛接受并进行各种试验示范[1-3]。作业路径是车辆自动导航作业跟踪的依据，作业路径及调度策略一定程度上决定着具体作业条件下的机具、农资消耗总量和利用率。

对比传统农业车辆在作业过程中通过驾驶员主观判断来规划选择作业路径的方式，通过计算机规划算法自动规划路径能够显著提高农机作业效率和质量、节约能源消耗[4]。Palmer等[5]利用车载GPS记录的数据，通过事后分析传统喷雾机作业轨迹发现，作业重叠（13%～27%）和遗漏（0.03%～1.56%）现象严重，而通过提出的路径规划算法，作业距离减少16%，作业消耗减少10%。Bochtis等[6]通过不同形状田块、不同作业参数的288组实例对比研究发现，经过算法优化获得的作业调度方案比传统的逐行调度方案在非有效作业距离上平均降幅达到58.65%，而在地头转弯空间上则平均节约了19.23%。

自动驾驶车辆跟踪的目标路径经历了基于机器视觉目标检测识别在线规划[7]、A-B点示教、全过程示教和全局离线事前规划等几个阶段。Conesa-Muñoz等[8]针对田间精准除草问题，以路径总长度、油箱容量和除草剂补给等为优化目标，考虑农机不同的行进速度与转弯半径，建立多机协同作业路径规划方法。Seyyedhasani等[9]为优化多机协同作业，提出了一种能够动态、实时更新车辆路径的全覆盖路径规划算法。Hameed[10]通过对二维与三维田块进行分析，设计了一种多目标优化的路径规划算法，可减少10%～15%的作业时间。Plessen[11]针对大田植保作业时喷雾机容量较小的问题，提出了基于多次补给作业的区域覆盖路径规划方法。Utamima等[12]以最短路径为优化目标，在农机路径规划中提出了进化混合邻域搜索算法，有效缩短了农机的作业总长度。Nilsson等[13]以田块全覆盖为主要目标，考虑路径长度、作业时间和土壤压实等次要目标，基于人工蜂群算法建立农机路径规划方法。国内对于农机路径规划研究起步较晚，孟志军等[14]针对凸多边形田块，提出了基于不同的路径优化目标，通过计算最优作业角度生成作业路径的方法。刘刚等[15]提出了以农田地势高程分布特征为先决条件，以无效作业状态、转向操作和重复行走距离最少为优化目标的农机全覆盖路径规划方法。

综上，现有研究大多针对轮式拖拉机或收获机展开，针对履带式油菜联合收获机的研究较少，更鲜有考虑油菜联合收获机的分禾竖割刀对作业路径的影响。鉴于此，本研究通过分析长江中下游稻油水旱轮作区油菜作物联合收获过程的作业特点，以最小漏收面积为前提、最短作业总长度为优化目标，针对四边形这一最为常见的田块边界类型条件下的油菜联合收获作业路径问题，分别为单侧竖割刀和双侧竖割刀的油菜联合收获机，提出传统环形路径（轮廓平行路径）和混合路径（先轮廓平行路径、后方向平行路径）的全覆盖作业路径规划算法，以期为长江中下游稻油轮作无人农场中油菜无人化联合收获提供作业路径规划方面的理论与技术支撑。

1 油菜联合收获过程的作业特点及路径要求

中国南方地区农田耕地面积相对较小且分散，尤其在长江中下游稻油水旱轮作区，田块之间的边界界限十分明显，一般都伴随着田埂、沟渠、坡岸等不可跨越的障碍物。因此油菜联合收获机作业时，除了出入口外（有时连出入口也没有，而需借助专用爬梯），田块的边界均为不可跨越，这是长江中下游区域油菜联合收获作业过程的第一个特点。第二，油菜作物植株分叉较多，机械收获时，为减少割台损失，需要在割台侧边加装竖式割刀进行主动分禾[16-17]，有双侧竖割刀和单侧（左或右）竖割刀两种形式。其中双侧竖割刀对收获次序没有要求，而单侧竖割刀则需要按照一定的次序进行收获作业。

油菜为旱地作物，因此南方油菜田内部均设有一定数量的排水沟，为保证机器良好的通过性能，油菜联合收获机一般采用履带式而非轮式底盘。履带式油菜联合收获机通常以差速方式进行转向[18]，利用两侧履带卷绕速度大小或方向上的不同，使机器完成转向和转弯过程。若不考虑土壤地表造成的滑移滑转现象，履带式车辆转向原理按照两侧履带速度方向是否一致可分成两种情形（图1）。当两侧履带速度方向相同时，若速度大小相等（V1=V2）机器会直线前行，而若一侧速度减小且两侧速度比值k保持不变（即k=|V2|/|V1|为定值），则机器会向速度值小的一侧转向，此时机器作回转运动，回转中心O落在机器外部且物理中心O′绕回转中心O作圆周运动，转弯半径一般大于机器宽度的一半（图1a）。当速度方向相反且比值k不变时，机器原地回转，回转中心O落在机器履带中心和物理中心O′之间，即O′绕O作圆周运动，此时转弯半径一般小于机器宽度的一半（图1b）。当V1=-V2时，O′、O重合，转弯半径为R=0，为原地逆差式转向；当V1=0时，图1中两种情形归为一种，为单侧制动式转向。两种情形下，机器的瞬时回转中心O的位置始终保持不变，因此回转中心周围土壤会遭到严重不均匀挤压和破坏。实际操作中，除转弯空间受限时采用原地回转式转弯外，一般多用变速动态式转弯，即边行进、边转弯，此时机器瞬时回转中心的位置和转弯半径的大小会随行进量和速度比值的变化而变化。此外，转弯半径还与履带的滑转率（%）、滑移率（%）等因素相关，实际转弯半径相对于理论转弯半径的修正系数在1.737～2.947之间变化[19]。为简化计算过程，算法设计时假设转弯半径恒定不变，但会取多组不同数值进行验证。

综上，概括长江中下游稻油轮作区油菜联合收获自动化作业过程对所规划作业路径的要求为：

1）遵循以不碾压未收获作物且与田块的刚性边界相适应（机器在田间移动时尤其是地头转弯或转移时不可触碰边界）的总原则，一般执行“先外围、后内部”的田块遍历覆盖总策略，须先采用轮廓平行路径进行作业以腾出足够的地头转弯空间。

2）收获的具体次序要与油菜联合收获机割台上竖割刀的形式相适应：左侧竖割刀的油菜联合收获机，只能相对于田块中心沿逆时针方式作业；右侧竖割刀的油菜联合收获机，只能相对于田块中心沿顺时针方式作业。双侧竖割刀的油菜联合收获机则没有限制。

3）以收获作业路径全覆盖为总前提，以油菜联合收获机最小能耗和最少作业时间为优化总目标，即在基础的有效收获作业路径和无作业的转移衔接路径生成时尽可能使油菜联合收获机的漏收面积最小、总的作业路径最短、转弯次数最少、倒车次数最少。

2 算法基本原理

2.1 田块边界数据定义及算法流程

以多边形表示田块边界，田块边界的顶点可通过人工手持GPS实地打点或地理信息系统（Geographic Information System，GIS）中鼠标选取，经过通用横轴墨卡托（Universal Transverse Mercator，UTM）投影算法[20]进行坐标转换，将GPS坐标数据转化为平面坐标数据，按逆时针方向依次存储在多边形数组中。

以多边形田块边界信息、田块出入口位置和油菜联合收获机的基本参数为输入。算法执行时，首先通过等距偏置处理生成轮廓平行路径，当油菜联合收获机为单侧竖割刀时，生成由轮廓平行路径为主要作业路径的环形路径；当油菜联合收获机具有双侧竖割刀时，则需要再经过多边形扫描线填充算法处理，生成由轮廓平行路径和方向平行路径为主要作业路径的混合路径。算法流程如图2所示。

在混合路径中，油菜联合收获机由入口位置开始作业，先按照轮廓平行路径及其衔接路径完成田块外围区域收割，形成足够的地头转弯空间，再按照方向平行路径及其衔接路径继续作业，直至完成整个田块的收割任务，如图3所示。

2.2 多边形等距偏置处理

多边形等距偏置算法[21]是轮廓平行路径的基础算法，以油菜联合收获机的作业幅宽为偏置距离，将待作业田块的边界轮廓线逐步向内偏置，即可获得一组等距多边形。对于凸多边形而言，其等距多边形可以通过解析法准确求解获得，且不会随着偏置次数的增加而出现“退化现象”（多边形顶点减少或多边形个数增加）[21]。对任意相邻的两边界轮廓线P1P2、P2P3，利用平行线定理可得出等距线AB、BC所在直线的斜截式方程，如式（1）所示，解方程即可得到顶点P2偏置后对应的B点坐标（图4）。以此类推，求出其他各顶点偏置后的坐标，即可得到偏置后的等距多边形。

式中x1、y1分别表示P1的横坐标、纵坐标，m；x2、y2分别表示P2的横坐标、纵坐标，m；W为油菜联合收获机的作业幅宽，m；12ppl、23ppl为边界线段P1P2、P2P3的长度，m。

若田块内部区域的作业路径以方向平行路径为主，则需要先通过轮廓平行路径收获边界附近区域来为方向平行路径的行间调度腾出足够的地头转弯空间。该区域空间的大小取决于实际操作时的转弯类型和机器的物理参数，保证机器顺畅转弯并避免在转弯过程中触碰到田块边界上的潜在障碍物。通过大量测试分析，本研究拟定经验公式来计算实际偏置次数，如式（2）所示。

式中m为偏置次数；表示向上取整；R为油菜联合收获机的转弯半径，m；B为油菜联合收获机的车身宽度，m；LS为安全距离，根据油菜联合收获机的导航精度进行取值，m。

2.3 轮廓平行路径及其衔接路径

按照多边形等距偏置算法，将田块的轮廓边界依次偏置处理m次，偏移距离除第一次偏置为W/2外，后续偏置时的偏置距离均在前一次基础上加W，即可得到初始的轮廓平行路径环组。该路径环组存在2个问题需要进一步进行平滑过渡处理：1）各环之间彼此孤立；2）每环为一组首尾相连的线段，各相邻线段间夹角小于180°。为满足机器行驶要求，需分别进行环间衔接处理和环上拐角处理，获得环间衔接路径和环上拐角衔接路径。

对于轮廓平行路径的环间衔接，根据田块入口相对于所在边位置的不同，又分为两种情况：1）刚好位于所在边一侧；2）处于所在边中间。分别采取两种不同的处理策略，以尽可能获得最优的路径，如图5所示。对于进入点刚好位于所在边一侧且与单侧竖割刀方位属性一致时（左侧竖割刀，逆时针收割，对应所在边右侧；右侧竖割刀，顺时针收割，对应所在边左侧），采用的衔接策略如图5a所示。算法设计时，取当前环的最后一直线段AB和相邻下一环形路径的第一直线段CD，反向延长线段CD，交线段AB于B′点，对∠AB′C进行半径为R的圆角处理，垂足分别为A′和C′。按照“AB直线前进，BA′直线倒车，A′C′圆弧转弯，C′D直线前进”的路径完成衔接。当进入点位于非侧边位置或与竖割刀方位属性不一致时，采用的衔接策略如图5b所示。算法设计时，作入口所在轮廓线的垂线分别交线段AB、线段CD于B点、C点。过B点以O1为圆心做半径为R的圆，同时以O1为圆心做半径为2R的圆，对C点同样处理，圆心位置为O2，其中两个半径为2R的圆交于O3点，并以O3为圆心做半径为R的圆，与前述两个半径为R的圆分别相切于E、F点，此时按照“AB直线前进，BE圆弧转弯，EF圆弧倒车，FC圆弧转弯，CD直线前行”的路径完成衔接。

对于轮廓平行路径的环上拐角衔接，同样存在两种不同的情况及处理策略。对于最外环而言，因为田块边界除入口外多为不可触碰和跨越的“刚性边界”，采用“AB直线前行，BA′直线倒车，A′C′圆弧转弯，C′D直线前行”的衔接路径如图6a所示。对于其它非最外环路径而言，因最外环的收割作业而腾挪出一定的转弯空间，采用“AB直线前行，BE圆弧倒车，EC′圆弧转弯，C′D直线前行”的衔接路径如图6b所示。

2.4 方向平行路径及其衔接路径

当油菜联合收获机仅具有一侧竖割刀时，通过由轮廓平行路径组成的环形路径，即可完成整个田块区域的收割任务，这是最传统也是目前采用最多的一种收割策略。当油菜联合收获机具有双侧竖割刀时，则有更多的选择。当按照轮廓平行路径完成田块外围区域收割后，形成足够的地头转弯空间，剩下的待收获区域，可以采用方向平行路径进行作业，此时的组合路径称为混合路径。

方向平行路径是指机器的有效作业路径线段互相平行，且方向固定地平行于田块的某一条边界。该方向称之为最优作业方向，可按照多边形最小跨度法[22]求解得到，有效作业路径线段为一组间距为W的平行线组，可采用基于活性边表法的扫描线填充算法[23]获得。有效作业路径是彼此孤立的平行线段，同样需要衔接处理，也即是通常意义上的转弯掉头。

当转弯半径大于0时，为使车辆行进顺畅，其转向过程须遵循一定的转弯策略进行平滑过渡。黄小毛等[24]在U型、Ω型和T型等3种常见转弯策略的基础上，提出了长度更短的M型转弯策略和T′型转弯策略。具体选择哪种转弯策略，主要取决于2条方向平行路径间间距（W，m）和最小转弯半径（R，m）之间的关系，同时考虑转弯路径长度、地头空间的大小和作业种类，保证最小的转弯长度和地头空间且不造成作物碾压。通过对比，选取U型转弯策略和T′型转弯策略作为方向平行衔接路径，其转弯过程原理如图7所示。当使用U型转弯时，机器采用“AB直线前行，BH1圆弧转弯，H1H2直线前行，H2C圆弧转弯，CD直线前行”的路径如图7a所示。当使用T′型转弯时，机器采用“AB直线前行，BH2圆弧转弯，H2H1圆弧倒车，H1C圆弧转弯，CD直线前行”的路径如图7b所示。

2.5 方向平行路径调度优化

方向平行路径中有效作业路径的调度次序会极大地影响转弯的路径总长度和效率。传统作业中普遍采取逐行往复式的调度策略，该调度策略配合Ω型转弯策略被广泛使用、操作手法相对容易被接受，但实践证明并非最优策略[25]。通过对方向平行路径进行调度优化，可以有效减少非工作路径的长度。

本研究将该调度问题看作旅行商问题（Travelling Salesman Problem，TSP）[24]并采用Google公司开发的一种用于组合优化问题的开源软件套件OR-Tools进行优化。将每条方向平行路径线段的端点看成一个城市，为确保属于同一条方向平行路径的2个城市以相邻方式依次包含在最终解里面，将对应两点的“名义距离”设置为0。此外考虑到2条方向平行路径衔接时一般按照同侧方式进行转移，因此对于2条方向平行路径AB、CD而言，拟定按照表1方式计算优化时的TSP距离矩阵。

表1 距离矩阵计算方法 Table 1 Calculation method of distance matrix

由于TSP属于典型的组合优化问题，目前尚无可求取准确解的完美算法，该问题也一直是计算机领域的难点问题[26-27]。本研究通过调用OR-Tools软件套件内的路由解算器，完成方向平行路径的调度优化。路径规划算法在执行调度优化前，需先采用距离矩阵计算方法求出方向平行路径各端点之间的距离矩阵。调度优化时，首先使用局部最优路径策略得到调度次序的初始解，再通过引导式局部搜索策略继续求解获得新的调度次序，同时计算每一个调度次序对应的路径总长度，当搜索时间大于设定时间（最大搜索时间设置为4 s）时，输出最小路径总长度所对应的调度次序，即为最优调度次序。

2.6 算法运行环境

本研究的油菜联合收获作业路径规划算法以Python作为编程语言，在PyCharm平台上编程实现，并结合PyQt5开发工具编写路径规划软件。在Inter(R) Core(TM) i5-9400 CPU @ 2.9 GHz、16 GB、Windows10操作系统环境下，运行程序并进行效果测试。

3 实例仿真计算

选取4块典型的四边形实际田块进行算法求解和效率计算分析测试。田块边界数据通过Google Earth软件获取，并以KML格式作为交换格式。其中田块1、2为湖北武汉市实际田块，田块3、4为湖北宜昌市实际田块，田块面积分别为2 033.02、2 571.35、2 784.94和3 329.01 m2。采用星光4LZY-3.5S油菜联合收获机的作业参数，外形尺寸为5.12 m×2.52 m×2.72 m、割幅为W=2.20 m、喂入量为3.50 kg/s。因履带式车辆底盘实际转弯半径受行进速度和土壤特性等多个因素影响无法准确量化，故对该机器分别取R=1.50、1.70、2.00、2.20 m 4个数值进行算法仿真试验。试验中，将路径规划算法规划出的路径按照是否执行收割操作分为作业路径（边行走、边收割）和非作业路径（只行走转移、不收割），求出相应路径总长度，算法耗时为主程序在进行算法求解过程中所消耗的CPU时间。

3.1 环形路径和混合路径的对比仿真试验

对传统环形路径（即轮廓平行路径）算法和混合路径（即先轮廓平行路径、后方向平行路径）算法的求解结果进行对比研究。在算法设计时虽以最小漏收面积为首要满足指标，但由于实际田块边界部分夹角太小，导致尖角处机器无法进入，无法保证绝对不漏收，故对比时忽略一些细小漏收面积的影响。方向平行路径调度时采用传统的逐行调度策略。设定转弯半径为1.50和2.00 m两个水平，采用环形路径算法和混合路径算法对4块实际田块进行仿真试验，试验数据如表2所示，部分算例的完整路径结果如图8所示。其中作业路径由轮廓平行路径中的前行路径部分和方向平行路径组成，非作业路径由轮廓平行路径中的倒车路径、方向平行路径间衔接路径、退出路径3个部分组成。倒车次数优化率γ1= (N1-N2)/N1×100%，其中N1、N2分别是环形路径和混合路径结果中的倒车次数。由表2可知，2种路径算法对应的路径总长度都随田块面积的增加而增大，同时也随转弯半径的增加而增大。其中环形路径的算法耗时为0.17～0.25 s，混合路径的算法耗时为0.38～0.61 s。由图8可知，环形路径算法和混合路径算法获得的路径线基本覆盖整个田块。

表2 不同田块下环形路径和混合路径的对比测试结果 Table 2 Test results comparison of circular parallel path and mixture path for different fields

3.2 方向平行路径调度优化仿真试验

为进一步优化混合路径总长度，在混合路径算法内嵌入OR-Tools软件套件内的路由解算器，对方向平行路径进行调度优化。非作业路径的优化率（ε，%）为OR-Tools调度后混合路径中非作业路径长度（T2，m）相对于逐行调度后混合路径中非作业路径长度（T1，m）的降低幅度，即ε=(T1－T2)/T1×100%，且进一步对比倒车次数减少的幅度，即γ2=(N3-N4)/N3×100%。设定本次试验中油菜联合收获机的转弯半径为1.70 m和2.20 m，采用逐行调度策略和OR-Tools调度策略对4块实际田块进行仿真试验，试验数据如表3所示，部分算例的完整路径结果如图9所示。由表3可知，2种调度策略下混合路径总长度与田块面积、转弯半径呈正相关，其中逐行调度策略的算法耗时为0.38～0.61 s，OR-Tools调度策略的算法耗时为4.42～4.73 s。由图9可知，混合路径在采用OR-Tools调度策略后获得的路径线基本覆盖整个田块。

表3 不同调度策略下混合路径规划算法的测试结果 Table 3 Testing results of mixed path planning algorithms under different scheduling strategies

3.3 仿真试验结果分析

针对四边形边界田块下的油菜收获路径规划问题，提出了环形路径算法与混合路径算法，分别对4组不同面积、不同形状的实际田块进行了仿真试验。由图8和图9可知，环形路径算法和混合路径算法获得的路径线基本覆盖整个田块，满足最小漏收面积要求。由表2和表3中的算法耗时可知，2种路径类型对应的算法在加入调度优化前，算法耗时随田块面积的增大而缓慢增加，但均小于1.00 s；加入调度优化后，因TSP问题求解，算法耗时大幅增加，但也均小于5.00 s。这说明设计的算法稳定、可靠、高效。

对比表2中环形路径总长度和混合路径总长度可知，当转弯半径设定在1.50 m时，混合路径作业总长度较短，而当转弯半径增大至2.00 m时，此时环形路径作业总长度反而要短一些。为了探究这一规律，对实际田块2进行仿真试验，设置转弯半径范围为1.40～2.30 m，间隔0.10 m。2种路径算法下路径总长度结果如图10所示，当转弯半径在1.40～1.70 m时，混合路径总长度较短，当转弯半径在1.80～2.30 m时，环形路径总长度更短。

由表2中作业路径长度和非作业路径长度可知，2种路径下转弯半径增大对作业路径长度影响不大，主要影响非作业路径长度，其中混合路径的非作业路径长度增幅较大，主要原因是混合路径中方向平行衔接路径的长度受转弯半径变化影响较大。此外，从表2倒车次数可知，相比于环形路径，采用混合路径可减少36.36%～40.00%的倒车次数，进而减少了农机作业过程所消耗的时间。

由表3可知，对混合路径进行调度优化后，非作业路径长度优化效果在7.20%～20.23%之间。对比表3中不同转弯半径下的非作业路径长度，可以发现其优化幅度与转弯半径的大小相关，当转弯半径越大时，调度优化的效果越明显。同时对比图9中田块的规整程度可以发现，当田块的形状越接近矩形，以及方向平行路径需要的衔接路径（转弯）次数越多时，调度优化效果就越明显。因调度优化后方向平行衔接路径更多的采用U型转弯，相比未采用调度优化的混合路径，倒车次数减少了33.33%～60.87%，能进一步节省作业时间。

4 结 论

1）针对四边形田块边界类型条件下的油菜联合收获作业路径规划问题，在分析油菜联合收获作业特点的基础上，为单侧竖割刀的油菜联合收获机，提出了全覆盖作业环形路径规划算法；为双侧竖割刀的油菜联合收获机，提出了全覆盖作业混合路径规划算法。

2）对4组实际田块进行仿真测试结果表明，本研究所设计的两种收获作业路径算法满足实际收获过程中的各种要求。在不考虑调度优化的情况下，环形路径的算法耗时为0.17～0.25 s，混合路径的算法耗时为0.38～0.61 s，当转弯半径较小时，混合路径总长度较短，当转弯半径较大时，环形路径总长度较短，在算法输入参数相同的条件下，混合路径相比于环形路径能减少36.36%～40.00%的倒车次数。在对混合路径算法进行调度优化后，其非作业路径长度减少了7.20%～20.23%，倒车次数进一步减少了33.33%～60.87%，相较于环形路径算法更优，此时算法耗时在4.42～4.73 s，满足油菜联合收获机在收获作业准备过程中快速规划路径的需要。

3）本研究为长江中下游区域稻油轮作无人农场中油菜无人化联合收获提供了作业路径规划方面的理论及技术支撑。其中多边形偏置、轮廓平行路径的环上及环间衔接处理、方向平行路径调度优化时距离矩阵等计算方法同样适用于其他非四边形的凸多边形边界田块，但对于凹多边形边界田块，则还需要进一步深入研究。此外，算法中假设车辆转弯半径为某一定值，属于静态规划，因此还需要进一步研究动态转弯特性对路径规划结果的影响。