凸多边形田块下油菜联合直播机组作业路径规划

黄小毛 张 垒 王绍帅 罗承铭

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

0 引言

随着农用车辆数字化底盘技术和农机自动导航技术的快速发展，油菜作物种植过程的自动化和智能化也开始提上日程[1-3]。随着无人机技术的成熟，目前油菜飞播、空中植保等作业环节发展迅速，而耕作、播栽、收获等地面机具智能化技术也随无人农场理念兴起而稳步发展。在无人农场模式下，作业机组的自动导航自主作业，是在RTK高精度定位下，根据当前位置姿态与预设值的偏差不断调整转角、速度等控制量，继而完成对预设全局路径的跟踪并同步实施农机具作业的过程。

作为农机自动导航驾驶作业的“使能技术”之一，全局覆盖作业路径规划，不仅是无人农场农机自主作业的先决条件之一，而且路径的好坏还很大程度上决定着机组的作业效率、作业质量和能耗[4-6]。国外OKSANEN等[7-8]基于多边形的梯形分解提出一种作业路径生成算法。HAMEED等[9]对作业方向及行作业的调度方法等进行了系统研究，并对作业过程中的重复面积及时间消耗进行了评估。SPEKKEN等[10]从操作时间角度出发提出一套最优路径规划方法。JESUS等[11]对有能力约束的车辆路径调度问题(Capacitated vehicle routing problem, CVRP)进行了相关研究，提出了Mix-operator路径优化方法。SEYYEDHASANI等[12]采用改进的C-W节约算法解决多机并行作业路径规划问题。AMALIA等[13]对矩形和非凸多边形田块提出了进化混合邻域搜索(Evolutionary hybrid neighbourhood search,EHNS)路径优化方法。国内相关研究主要集中在机具的自动导航跟踪控制上[14-19]，路径规划方面的研究相对较少[20-22]。

以上路径规划方面的研究，大多以北方大田作物为主，目前还没有针对油菜作物播种作业路径规划的研究报道。本文拟针对无人农场模式下油菜联合直播机组作业过程中常见的凸多边形边界田块，提出一种对凸多边形边界田块具有普适意义的油菜联合直播机组全局覆盖作业路径规划算法。

1 作业路径规划基本原理

1.1 油菜联合直播机组作业特点及路径规划要求

常见的油菜播种机工作方式多以四轮拖拉机牵引为主。工作时，靠拖拉机提供动力，通过提升装置放下机具，牵引前进并通过动力输出轴输出的动力进行旋耕、开种沟、播种、施肥、开排水沟、覆土、镇压等多道作业工序；地头转弯或田间转移时，机具则被提升离开地面。播种机工作幅宽一般大于拖拉机机体幅宽，但与拖拉机的最小转弯半径之间存在多种尺寸关系，因此在行间转移时存在多种转弯策略。

一条理想的农机作业路径应该能够使机具以最小的代价(机时和农资消耗)对待作业田块所有区域进行无差别覆盖，且对于播种作业来说只覆盖一次。考虑到机组作业过程中地头转弯和大范围转移等“非作业、但必须”的衔接动作和油菜种植所在区域田块的边界特点，实际规划的油菜播种作业路径应尽可能满足以下要求：①有效作业路径(边行走、边作业)按照“先内部、后外围、不重不漏”的原则对作业田块的每个区域进行尽可能无差别的全覆盖。②与机组的作业参数及特性相匹配，尤其转弯或转移等衔接路径(即非工作路径，只行走、不作业)过渡平滑且最小曲率半径大于等于最小转弯半径(静态规划时暂不考虑转弯时方向盘的动态响应问题)。③旋耕联合直播时尽量避免对已完成的排水沟的二次破坏，免耕联合直播时每一行的排水沟尽可能开到地头。④尽可能避免对已作业区域的二次碾压，即转弯等非工作衔接路径的长度越小越好，或有效工作路径在总路径中的占比越大越好。⑤算法运行稳定高效。

1.2 数据定义及算法流程

对于凸多边形边界田块，用多边形的每一条边分别对应实际田块的每一个边界，以手持GPS人工打点或GIS系统选取作业田块，按逆时针方向依次存储各边界点。用拖拉机几何中心表示机组位置，机组的有效工作路径以虚线的方式表示，衔接转移路径(非工作路径)用实线表示，作业方向与箭头指示方向一致。

以待作业田块边界、机组作业参数为输入，以作业路径为输出，整个算法的流程如图1所示。

该算法主要涉及油菜联合直播有效工作路径及其衔接转移路径的规划。有效工作路径包括方向平行路径和轮廓平行路径，算法生成原理涉及多边形扫描线填充算法和偏置填充算法等计算机图形学[23]知识，本文不再赘述。衔接转移路径是所有有效工作路径之间的过渡路径，包括6种基本类型，是实现全过程无人干预的自动作业的必备环节。衔接转移路径在总的路径中的数量占比与有效工作路径占比是互补关系，越低越好，其生成算法是重点。

1.3 旋耕与免少耕直播路径的区别

油菜是旱地作物，开排水沟是长江中下游地区油菜田的基本要求之一。为充分排水，与方向平行路径平行的排水沟尽可能开到地头边界，同时又要兼顾避免重播和边界碰撞，因此在进行内部区域方向平行路径作业时，可通过倒车和延时转弯等方式，对地头转弯区域先只开沟不播种，而在外围区域轮廓平行路径作业时再进行一次交错方向上的开排水沟。

相对于免少耕对土壤破坏较小，旋耕对土壤破坏较大，外围区域轮廓平行路径作业时若采用旋耕会毁掉先前开好的排水沟。因此油菜旋耕直播与免少耕直播工作路径的主要区别体现在开排水沟路径的规划上：旋耕直播机组在进行内部方向平行路径作业时排水沟不超出该区域，免少耕直播时则会尽可能地将排水沟开到地头边界处。二者的工作路径如图2a、2b所示。对于油菜免少耕联合直播有效工作路径，分为联合直播工作路径和只开排水沟工作路径，而旋耕联合直播作业工作路径只包括联合直播工作路径。机组在联合直播工作路径上作业时同时完成开种沟、播种、施肥、开排水沟等多道工序，而在只开排水沟工作路径上只完成开排水沟作业。

图2 两种不同耕作方式下工作路径的差异Fig.2 Difference of working path between two different tillage methods1.田块边界 2.排水沟 3.播种路径 4.作业行分界线

1.4 衔接路径生成原理

1.4.1行间转移衔接路径

行间转移衔接路径，即地头转弯路径，是指机组从方向平行路径某一作业行转移到下一方向平行路径作业行时的衔接路径，包含机组的2～3次换向过程，累计完成180°调头转弯。

四轮拖拉机行走装置主要由前桥、导向轮、驱动轮、转向器、转向传动机构、差速器等组成，多为后轮驱动、前轮转向，采用阿克曼转向原理，如图3所示。

图3 阿克曼转向原理示意图Fig.3 Schematic of Ackerman steering principle

转向过程时，前内轮与前外轮的转角应满足[24]

(1)

式中β——拖拉机前外轮转角，(°)

α——拖拉机前内轮转角，(°)

K——内外侧车轮轴距，m

L——车辆前后主轴间距，m

在不考虑轮胎打滑的情况下，转向过程中全部车轮绕瞬时中心O做圆周滚动，车辆整体相对于瞬时中心做圆周运动。考虑不同行间距离、首次转向方向和倒车形式，存在如图4所示5种具体转弯策略。

图4 各种转弯策略及其路径生成原理示意图Fig.4 Schematics of different turning strategies and their generation principle

1.4.2区域衔接路径

机组完成田块内部方向平行区域的联合作业后，继续转入外围轮廓平行区域作业。由方向平行路径过渡到轮廓平行路径的转移路径称为区域衔接路径。机组从方向平行路径上的点A转移到轮廓平行路径点B的区域转移路径如图5所示。以最小转弯半径R为半径作圆与方向平行路径、轮廓平行路径分别相切于H1、H2，可得到劣弧H1H2。机组先从点A直线倒车到点H1，到达点H1后，机组沿劣弧H1H2从点H1转移到点H2，接着从点H2直线倒车到点B，完成机组从方向平行路径向轮廓平行路径转移。

图5 区域转移路径Fig.5 Region transferring path

1.4.3跨行衔接路径

根据机组作业幅宽将轮廓平行区域划分成若干作业行，对于油菜播种作业来说，为尽可能避免对已作业区域的二次碾压，一般采取由内向外遍历方式完成轮廓平行区域播种作业，这一过程的衔接路径称为跨行衔接路径。

油菜联合直播机组从最内侧轮廓平行路径上点B转移到其相邻轮廓平行路径作业行上点C的跨行衔接路径如图6所示，过点B机组作所在轮廓平行路径l1与之距离为最小转弯半径R的垂线段BO1,过点O1做半径为最小转弯半径R的圆与直线l2相交于H3,延长O1H3到点O2，使H3O2等于R，过点O2作半径为最小转弯半径R的圆，与直线l3相切于点H4，得到跨行衔接路径。机组首先从点B依次沿劣弧BH3、H3H4前进到点H4，当机组到达点H4时，机组接着以直线倒车的方式运动到点C，完成轮廓平行路径跨行衔接。

图6 跨行衔接路径Fig.6 Swath crossing connection path

1.4.4拐角衔接路径

轮廓平行路径呈螺旋式分布，对于相同偏置次数的轮廓平行路径，从轮廓平行路径拐角的一侧以直线运动的方式运动到相邻拐角的一侧，到达拐角后通过一定衔接方式转移到另一条轮廓平行路径，这一衔接过程的路径称为拐角衔接路径。

油菜联合直播机组的拐角衔接过程如图7所示，过点H1作与直线AH1距离为R的线段OH1，过点O作圆与直线AH1、BH2分别交于点H1、H2，得到劣弧H1H2。机组从点A沿线段AH1从点A运动到点H1，接着沿劣弧H1H2从点H1运动点H2，到达点H2后沿线段H2B，从点H2运动到点B，完成拐角衔接过程。

图7 拐角衔接路径Fig.7 Corner connection paths

1.4.5进入和退出路径

(1)进入路径

机组从入口位置转移到田块的初始播种位置这一过程的路径称为进入路径，进入路径主要受田块边界形状、入口位置与初始播种位置之间距离等因素的影响。本文提出3种不同的进入路径方案，以机组作业安全性为前提，根据路径长短做出相应选择。

直线内切圆式进入路径的原理如图8a所示，机组从点A先直线前进到点B，机组完全进入待作业田块区域，到达点B后，根据机组位置与初始播种位置的几何关系得到劣弧CD，机组先从点B直线前进到点C，到达点C后沿劣弧CD从点C运动到点D，最后机组从点D运动到初始播种位置E。

图8 进入路径Fig.8 Entry paths

两圆公切线式进入路径的原理主要基于两圆公切线原理生成，如图8b、8c所示。其中两圆公切线式进入路径1的运动过程为机组从点A直线运动到点B，机组完全进入田块，根据机组与初始播种位置的几何关系得到劣弧CD、劣弧EF。机组先从点B直线到点C，接着沿劣弧CD运动到点D，然后从点D直线运动到点E，最后沿劣弧EF运动到初始播种位置，完成机组从入口位置转移到初始播种位置。两圆公切圆式进入路径2与两圆公切圆式进入路径1的区别是前者路径DE采用直线倒车行驶从点D运动到点E。

(2)退出路径

当机组作业完田块所有区域时，需要离开田块，从作业完成位置转移到出口位置这一过程的路径称为退出路径。退出路径的生成原理为两圆公切线式进入路径1、两圆公切线式进入路径2原理逆过程，不再赘述。

1.4.6轮廓平行路径偏置次数求解与边界碰撞检测

1.5 方向平行路径作业方向和调度排序优化

采用凸多边形最小跨度法[25]得到方向平行路径的最优作业方向角，计算得到该方向下的方向平行路径后，还需要安排合理的调度次序。将路径端点简化为城市点，该问题转化成用方向平行路径连接属于同一路径城市点、用行间转移衔接路径连接属于同一路径城市点的旅行商(TSP)问题。两条方向平行路径之间采用哪种衔接转弯策略，决定了总的作业效率，主要取决于行间距d，在行间距确定后，本文对不同策略分别进行了测试，并采用贪婪算法和Google OR-Tools进行求解[5]。

2 仿真测试

前述全部算法过程在Sublime Text 3平台上编码实现，在Intel Core i7-1065G7 CPU、1.5 GHz主频、16 GB内存、Windows 10操作系统环境下，对典型机组对象，选取不同功率、最小转弯半径R的拖拉机以及不同播种工作幅宽w的旋耕、免耕播种机具，按照功耗进行配对，形成4套机组如表1所示。选取不同面积及边数的4块典型凸多边形边界实际地块，如图9所示，边界数据通过Google Earth获取并导出为KML文件，算法调用前先经过高斯投影算法进行坐标转换，将GPS坐标转换为平面坐标。

表1 机组信息Tab.1 Unit information

图9 Google Earth软件中选取实际田块的截图Fig.9 Screenshots of selecting actual fields in Google Earth software

2.1 评价指标

除算法耗时外，还需要对所得路径的质量和作业效率进行评价。利用播种覆盖率ξc和重播率ξd评估作业质量，利用总行程长度L、有效工作路径占比ζe评估作业效率。有

ζe=Lw/La×100%

(2)

ξc=(Sd+Sc)/Sa×100%

(3)

ξd=(Sdc+Scc)/Sa×100%

(4)

式中Lw——有效工作路径总长度，m

La——总行程长度，m

Sd——方向平行区域有效播种面积，m2

Sc——轮廓平行区域有效播种面积，m2

Sa——待作业田块总面积，m2

Sdc——方向平行路径播种面积与轮廓平行路径播种面积之间重复播种面积，m2

Scc——轮廓平行路径彼此之间重复播种面积，m2

有效工作路径占比与衔接转移路径在总的路径中的数量占比是互补关系，一定程度反映前述衔接转移路径设计的合理性。

播种覆盖区域通过所有有效工作路径线段覆盖的长方形之间布尔运算并集(求和)得到。播种覆盖率与漏播率之间为互补关系。重播区域则包含2部分：轮廓平行路径部分，通过相邻有效工作路径线段覆盖长方形之间的布尔运算交集得到；方向平行路径部分，通过所有有效工作路径线段覆盖的长方形与方向平行区域多边形的布尔运算差集得到。

除了路径长度外，总的作业耗时是更为直观的效率评价指标。为此将路径按照不同作业状态的速度大小及方向的差异，分为直线工进、直线移进、直线移退、曲线移进和曲线移退5种，分类统计长度，再除以对应的作业速度，求和并加上各状态之间的切换时间，得到预估的作业时长。

2.2 仿真试验测试结果

以机组A、C对小面积田块1、2进行测试，以机组B、D对大面积田块3、4进行测试。作业方向角由最小跨度法得到，方向平行路径的调度由贪婪算法和OR-Tools进行对比测试。作业耗时预估时直线行进速度设定为0.8 m/s，直线移进速度设定为1.0 m/s，直线移退速度设定为0.7 m/s，曲线移进速度设定为0.6 m/s，曲线移退速度设定为0.5 m/s，不同状态路径间切换时间设定为2 s。所得的测试结果如表2所示，计算示例的部分结果截图如图10、11所示。图中，黑色实线为田块边界线，绿色实线为行边界线，蓝色虚线为有效工作路径线，橙色实线为衔接转移路径线，另外排水沟用一组棕色的平行线段表示，黑色、蓝色圆点分别表示方向平行路径、轮廓平行路径中拖拉机车头极限位置，而重漏作业面积示意图中浅绿色区域为油菜种子覆盖区域，深绿色区域表示该区域重播，白色区域表示该区域漏播。

表2 凸多边形边界田块路径规划算法测试结果Tab.2 Test results of path planning algorithm in small convex polygon boundary fields

图10 凸多边形边界小田块部分计算实例结果截图Fig.10 Screenshots of some calculation example results in small convex polygon boundary fields

图11 凸多边形边界大田块部分计算实例结果截图Fig.11 Screenshots of some calculation example results in large convex polygon boundary fields

3 讨论

通过以上对凸多边形边界田块下油菜联合直播机组仿真计算实例可以看出，该算法对于典型凸多边形田块具有较好的适应性，能解决凸多边形边界田块油菜联合直播机组作业路径规划问题。

对于小面积田块，播种覆盖率为95.14%～96.70%，而对于大面积田块，播种覆盖率为98.23%～98.54%，说明小面积田块的漏播面积更为明显。主要原因是相对于一定的机组物理参数而言，小面积田块中，机组无法遍历的“死区”更多，漏播区域更大。

重播导致种子、化肥和燃油等的浪费，算例中小面积田块重播率为1.45%～1.97%，大面积田块重播率为1.05%～2.63%，且田块边界越复杂、偏置次数越多，则重播率相对越大。分析其原因，田块形状越不规则，机组在方向平行路径与轮廓平行路径播种重叠次数越多，重播区域越大；偏置次数增加，轮廓平行路径中拐角衔接次数随之增多，机组在拐角衔接区域播种重叠次数增多，相较于区域划分导致的重播区域减小，田块总体重播区域增大，间接说明方向平行区域设置的必要性。

从作业效率的角度分析，对于小面积田块，有效工作路径占比为57.39%～61.42%，不同状态路径间切换221～241次，预计作业时长2 888.31～5 119.16 s，而对于大面积田块，有效工作路径占比为69.46%～80.86%，不同状态路径间切换307～458次，预计作业时长10 488.58～12 477.62 s，且偏置次数越多，则有效工作路径占比相对越小、不同状态路径间切换次数相对越多、预计作业时长相对越久。分析其原因，偏置次数增加，方向平行区域有效工作路径随之减小，轮廓平行区域有效工作路径虽然增加，但跨行衔接路径、拐角衔接路径的增加比例超过轮廓平行区域有效工作路径增加比例，有效工作路径占比随之减小；由于拐角衔接路径衔接次数与多边形田块顶点数成比例增加，跨行衔接路径衔接次数也随偏置次数增加成比例增加，相较于行间转移衔接路径和方向平行路径之间的衔接次数减少来说，总体上不同状态路径间切换次数增加；与此同时，拐角衔接与跨行衔接过程曲线转移过程较多，故机组预计作业时长增加。

对于同一田块下的同一机组，OR-Tools虽然在部分情况下有效工作路径占比、预计作业时长优于贪婪算法，但提升幅度不大，而多数情况下贪婪算法的优化性能更优，且算法耗时小得多，因此更值得选用。此外，总的算法耗时963～8 003 ms，多次测试结果说明所设计的算法高效、稳定。

4 结论

(1)针对无人农场油菜联合机组全覆盖路径规划问题，根据联合播种机作业特点的不同，根据免耕播种和旋转播种的差异，提出两种不同的路径规划算法，通过仿真试验验证该算法高效、可靠、稳定。

(2)对实际机组进行田块仿真测试结果表明，油菜联合直播机组的播种覆盖率95.14%～98.54%，重播率1.05%～2.63%，有效工作路径占比57.39%～80.86%，不同状态路径间切换221～458次，预计作业时长2 888.31～12 477.62 s，算法耗时963～8 003 ms，满足农业生产要求。