凸多邊形田塊下油菜聯合直播機組作業路徑規劃

黃小毛 張 壘 王紹帥 羅承銘

(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，滿足農業生產要求。