自動翻曬谷物機器人的全覆蓋路徑規劃研究

王溫鑫

（仰恩大學 工程技術學院，福建泉州，362000）

0 引言

谷物干燥是谷物收獲后需要處理的重要步驟，不僅保證了谷物的品質而且能夠提高谷物的出谷率。因氣候原因，谷物可能由于沒有曬干達不到安全水分的要求，導致其產量受到損失，因此對谷物進行翻曬使其充分干燥，將損失降低到最低點是谷物生產、豐收的重要保障。目前谷物翻曬主要有兩種方式：一是人工翻曬，該方案不僅勞動強度大且易受天氣的影響；二是使用大型機械設備進行烘干，該方法成本高且產生的廢氣會對空氣造成一定的污染。因此為了減少翻曬勞動力和降低干燥成本，研發一款小型自動翻曬谷物機器人是非常有價值的。隨著精準農業的大力推廣，全覆蓋路徑規劃是翻曬谷物機器人對谷物進行全面均勻翻曬的研究重點。在國外，Khan A 等人利用在線牛耕分解法對未知工作空間進行區域劃分，并利用所提出的雙向鄰近搜索算法，使用回溯技術完成區域全覆蓋[1]；Hong 等人利用啟發式模板規則并結合貪心準則的回溯機制實現區域全覆蓋[2]；Ma 等人提出一種高精度定位、低分辨率柵格建模方法，并利用生物激勵網絡實現移動機器人的全覆蓋路徑規劃[3]。在國內，聶楊利用無標識工作區域的邊界建立和識別方法，引導機器人完成草坪邊界信息的采集，然后將A*算法與往復式算法相結合實現割草機器人的全區域覆蓋路徑規劃[4]；李楷提出一種起始點方向優先的局部區域覆蓋算法，然后結合改進的theta*算法進行子區域間的銜接，實現全覆蓋路徑規劃[5]；周琳娜等人提出利用牛耕分解法對環境地圖進行劃分，然后將生物激勵神經網絡算法與深度優先算法相結合完成作業區域全覆蓋[6]。

為了使谷物機器人對谷物實現全面的均勻翻曬，提高谷物翻曬效率。本文提出一種基于改進A*算法的全覆蓋路徑規劃方法。首先，設計了面向谷物翻曬機器人的環境建模方法和區域劃分策略。接著根據谷物機器人的作業能量消耗與實際需求，利用沿長邊行走的弓子型往返式路徑規劃方法，實現子區域全覆蓋。其次，通過貪婪算法與距離公式相結合的方式，對下一個子區域的起點進行選擇。然后，利用優化后的A*算法和Bezier 曲線（B-A*）實現區域銜接，通過仿真分析可知，B-A*算法可減少節點搜索時間，規劃出的路徑更加平滑、安全。最后，利用上述全覆蓋路徑規劃策略進行仿真實驗，實驗結果表明該方案可實現全覆蓋，說明了該方案的有效性和可行性。

1 翻曬谷物機器人全覆蓋路徑規劃性能指標

翻曬谷物機器人全覆蓋路徑規劃并不是點到點的路徑規劃，而是通過點到線，再從線到面，最終將規定區域內所有的空白區域全部覆蓋完畢。本文對翻曬谷物機器人的全覆蓋路徑性能指標主要有以下幾方面：

（1）機器人能夠避開行走過程中的所有障礙物，并遍歷完工作區域內的其他所有地方。

（2）為了利于實際機器人的行駛，應盡量使用直線、曲線這樣的運動軌跡。

（3）翻曬谷物機器人應當盡量減少整個遍歷過程中的能量消耗。

全覆蓋路徑規劃的含義可由以上幾個方面的指標所體現，覆蓋率越高，機器人轉彎次數越少、能量消耗越低越能體現算法的優越性。全覆蓋路徑規劃算法還有一個重要指標為重復率，由于本文是針對翻曬谷物機器人對谷物進行翻曬作業，可在機器人行駛過程中對谷物進行重復翻曬，因此本文不考慮重復率這一指標。

2 翻曬谷物機器人全覆蓋路徑規劃

2.1 環境建模

本文利用柵格法[7～8]創建作業環境模型，單位柵格長度為機器人的尺寸大小。在柵格法中，每個柵格都會通過一個值來衡量該柵格的可行率，一般來說，使用0 來代表可行柵格，即機器人可通過該柵格區域；使用1 來代表障礙柵格，即機器人不可移動的區域。由于本文研究的是全覆蓋路徑規劃算法，所以柵格也需要記錄自身是否已經被機器人所覆蓋的信息。根據柵格是否已覆蓋，又可將柵格劃分為已覆蓋柵格和未覆蓋柵格。根據以上信息的組合后，柵格有以下三種狀態：可通行并未覆蓋區域、可通行但已覆蓋區域、障礙物，具體的數字編碼情況如表1 所示。根據柵格法，對環境進行相應的建模，結果如圖1 所示。空白柵格代表可通行區域，黑色柵格代表障礙物。

圖1 環境地圖柵格化

表1 柵格數字編碼情況

2.2 區域分割

區域分割是將作業環境根據障礙物分布情況，利用相關算法將工作環境劃分為多個子區域，使得各個子區域內不再包含障礙物。傳統區域分割法是梯形分解法[9～11]，牛耕分解法[12]在梯形分解法基礎上進行相應的改進，該方法通過一條垂直線從左到右按照平移方向掃過具有多邊形障礙物的區域，每遇到障礙物頂點可上下延伸的臨界點進行分割，最終作業環境被分割成多個不含障礙物的子區域，其示意圖如圖2 所示。相比梯形分解法，該方法產生更少的子區域，可減少機器人作業時對地圖環境的分解時間，提高機器人的工作效率，因此本文采用牛耕分解法作為區域劃分方法，進而為后續機器人進行全覆蓋路徑規劃做準備。

圖2 牛耕分解法示意圖

2.3 子區域內部遍歷算法

利用牛耕分解法對環境地圖進行分區后，關鍵步驟是完成對子區域內部的遍歷。針對內部區域遍歷主要有往返式弓子形和螺旋式路徑規劃，基于同一區域，文獻[13]對兩種路徑規劃方法在路徑長度和轉彎次數兩方面進行實驗對比，發現弓子形路徑更優。另外針對往返式弓子型路徑規劃，需要對谷物機器人的行走方向進行確定。在同一區域，機器人分別沿著長邊和短邊行走，發現直線行駛距離以及轉彎次數各不相同，這將導致其在區域內的行走軌跡以及對整個區域覆蓋所消耗的能量也會產生一定的差異，文獻[14]討論了機器人在相同區域內，分別沿著不同方向進行弓子形路徑規劃行走軌跡，發現沿長邊行走機器人的轉彎次數較少，能量消耗較小，因此本文選用沿長邊行走的往返式弓子形遍歷規則實現對子區域的全覆蓋。

2.4 子區域銜接起點的選擇

當完成對谷物翻曬場劃分為一系列簡單的無障礙子區域，并對當前的子區域完成全覆蓋后，需要規劃出一條路徑對下一個子區域進行銜接，然后結合弓子型路徑完成對下一個子區域進行順序覆蓋。在進行區域銜接路徑規劃時，需要尋找到下一個區域的起點。為了減少內存的消耗以及搜索時間，對于起點的選取，本文在算法程序中：

（1）只記錄區域在進行劃分過程中，與障礙物、區域邊界交點所產生的頂點信息。通過這種方式可減少起點的數量，進而減少完成整體全覆蓋路徑規劃所需要的時間。

（2）下一個區域的起點與上一個區域的終點之間的距離應最小，這樣可減少谷物機器人行走的路徑長度，降低消耗的能量。

為此針對如何選取下一個區域的起始點，本文利用貪婪算法與曼哈頓距離公式相結合的方式，以曼哈頓距離公式作為貪婪算法的選擇策略，每次選取與當前位置最近的區域頂點作為下一個區域的起點，算法描述如下：

其中，tn表示當前區域的終點，n表示下一個區域的起點。則所有可選擇的起點可表示為：

式中，nmin為選擇出的下一個覆蓋區域的起點。

2.5 子區域銜接路徑規劃

2.5.1 傳統A*算法

翻曬谷物機器人的全覆蓋路徑算法即機器人從起始點出發，通過對翻曬環境進行區域劃分、進行子區域全覆蓋、對下一個子區域的起點進行選取、建立子區域間的路徑銜接最終完成整個工作環境的全覆蓋路徑規劃。本文選擇以當前區域的終點為起點，以下一個區域的起點為目標點利用A*算法[15～17]實現區域銜接路徑規劃。另外A*算法也可作為在整個環境地圖中避障算法。

A*算法是利用啟發式函數來進行搜索路徑，主要通過代價函數進行路徑規劃，從起點位置向附近的子節點進行擴展，評價函數根據子節點距離代價值最小的節點選為下一父節點，重復此過程直到完成路徑規劃，生成最終路徑。

啟發式函數的一般表達式為：

式中，F（n） 表示從起始點經過任意節點n到達目標點的總代價值，g（n） 為從起始點到任意節點n的實際距離評估值，h（n） 為從任意節點n到達目標點的估計值。

根據對傳統A*算法進行尋路過程的研究發現，若將該算法直接應用于實際中的翻曬谷物機器人進行全覆蓋路徑規劃，其還存在一定的缺陷，需要對其進行優化，以便更好地完成任務。本文將從以下兩個關鍵問題對傳統A*算法進行優化和改進：

①從A*算法的啟發函數來看，g（n） 為定值，因此對其進行修改所起到的作用不明顯。估計函數h（n） 才是啟發函數的靈魂所在，因此估計函數的優劣會決定A*算法能否高效、準確地判斷出下一個節點。在傳統的A*算法進行節點搜索的過程中，會搜索大量不必要的節點，導致搜索時間變長，增加計算量，使路徑規劃效率變低。

②平滑度差。傳統A*算法的節點搜索方向僅限于柵格之間的相交位置，使得規劃出來的路徑轉折點多，搜索方向易受到谷物機器人轉彎半徑的影響，不利于實際機器人的行駛，另外實際中多次轉彎的代價會影響谷物機器人的運行效率。

2.5.2 改進A*算法

傳統的A*算法在節點搜索的過程中會產生大量的不必要節點，從而導致搜索時間長，路徑規劃效率低。為了使算法在搜索的過程中，能夠盡快地朝向目標點前進，本文對估價函數h（n）進行優化和改進，該函數對于A*算法的運行速度有著非常重要的影響，現對估價函數h（n） 和代價函數g（n）之間的關系對A*算法的影響進行討論：

①當h（n） = 0時，只有g（n）起作用，A*算法將會演變為Dijkstra 算法，該算法是一種盲目式搜索算法，因此會擴展更多無用節點，搜索效率低。

②當h（n） ＜g（n）時，此時可找到一條最短路徑，但隨著搜索不斷地向終點靠近，h（n）不斷地減少，此時會使得A*算法搜索擴展的節點變多，搜索時間變長，導致機器人尋徑效率變低。

③當h（n） =g（n）時，A*算法將會僅僅尋找最佳路徑上的節點，不會擴展別的任何節點，此時運行速度最快。

④當h（n） ＞g（n）時，此種狀態會比②時的速度快，搜索節點減小，運行效率變高，但不能保證搜索得到最優路徑。

⑤當h（n） ＞＞g（n）時，此時只有h（n） 起作用，該算法演變為BFS 算法，該算法是一種啟發式搜索算法，利用啟發函數使得擴展節點變少，搜索效率高，但不一定能搜索到最短路徑。

因此在設計估價函數時，應保證g（n） 和h（n） 最好能在同一個數量級，避免出現極端情況的出現。

本文選用歐幾里得距離公式作為估價函數，A*算法在傳統的估計函數的影響下，只會單一地進行往返搜索生成大量的搜索節點，而在實際情況中當前節點到目標節點之間的距離一定會大于實際路徑的消耗值，因此需要加快當前節點向目標節點的收斂速度，即增大估價函數h（n） 的權重。該權值的選擇應滿足當h（n） 較大時，當前節點遠離目標點，應增大權重，此時A*算法能盡快地向目標點擴展，搜索速度會較快，當h（n） 較小時，也即擴展節點接近目標點，權重應減小，此時A*算法更傾向于搜索最優路徑。因此本文引入以指數形式的權重因子h（n）e對傳統A*算法的表達式進行改進，公式修改為：

h（n）估計值應始終大于0，eh（n）的圖像如圖3 所示，從圖中可知，當h（n） 減小時，eh（n）也在不斷地減小，當h（n）等于0，也即當前節點到達目標點時，eh（n）為1，整體不發生改變，符合上述改變權值的要求。

圖3 h（ n）e 變化圖像

2.5.3 貝塞爾曲線優化

A*算法本身存在著許多的不足：在柵格環境下A*算法規劃出的路徑往往存在許多的轉折點，累積轉折角度大，在后期應用于實際谷物機器人中時會不利于機器人的行駛，存在過多轉彎現象，運行效率低等問題。于是本文在對改進后A*算法規劃出的路徑進行平滑處理，減少因路徑轉折點過多而降低機器人工作效率。

Bezier 曲 線[18]由 伯 恩 斯 坦 多 項 式（Bernstein polynomial）演化而來，其受曲線上控制點數目的影響。伯恩斯坦多項式的第n階項有如下形式：

其中i= 0,1,… ,n，而：

一般伯恩斯坦多項式可以表示為：

其中，βi為伯恩斯坦系數。當伯恩斯坦系數是二維平面中的一系列固定點時，伯恩斯坦多項式就演變成為Bezier 曲線。

將Bezier 曲線與A*算法（B-A*）相結合，A*算法生成路徑點的總控制點個數為n+ 1，βi伯恩斯坦系數為A*算法生成的第i個路徑點Pi，其中i= 0,1,… ,n。則通過公式 （7）計算可得B0…Bn，即可得到平滑后的曲線路徑。

根據Bezier 曲線的性質可知，規劃所得曲線路徑不會與控制點連接而成的多邊形外部障礙物發生碰撞，但會有與內部障礙物發生碰撞的可能，在實際工作中該種情況會使谷物機器人陷入工作死區對自身造成一定的損壞，所以需對Bezier 曲線進行一定的優化。對Bezier 曲線進行優化的思想，是將兩個相鄰節點中插入一定的點，將插入的點共同作為控制點，以此增加控制點的數量。合適的控制點會使得曲線接近拐點，以此盡量向規劃的路徑上靠攏，進而增大與障礙物之間的距離，躲避障礙物。增多控制點思想的偽代碼如下：

for i=1:1:pointnum-1

%pointnum 所需插入點的個數

D（ai+i,:）=（（B - C）./pointnum*i ）+ C;

%B 和 C 為相鄰控制點，D 所分控制點坐標

end

ai=ai+pointnums;

2.6 仿真實驗

2.6.1 改進A*算法對比分析

在翻曬谷物時，一般會盡可能地選取寬敞且障礙物較少的場地進行翻曬，為了驗證A*算法作為從當前區域到下一個區域銜接路徑規劃算法的有效性，隨機在柵格環境中選定起始點與目標點。改進的A*算法主要是減少擴展節點，縮短節點搜索時間，沒有對路徑長度進行改進。因此本文以15×15 和30×30 兩個不同柵格大小的障礙物地圖作為仿真實驗環境，通過Matlab 軟件分別對Dijkstra 算法、A*算法以及改進的A*算法進行實驗對比分析，仿真結果如圖4所示。

圖4 15×15 環境地圖仿真圖

圖4 中，黑色柵格代表障礙物，白色柵格代表可通行柵格，灰色柵格代表所搜索的節點，五角星代表起點，圓圈代表終點，從起點到終點的線段為規劃出的路徑。從圖中可以看到通過三種方法都能成功地從起始點搜索出一條路徑達到目標點，但改進的A*算法相對于Dijstra 算法和標準A*算法搜索節點大大減少，從表2 中也可以看到，改進后的A*算法在尋路時間和遍歷節點數的性能指標上都得到了很大的提升。為了進一步驗證改進A*算法的有效性，擴大地圖環境，以30×30 環境地圖再次進行仿真實驗，結果如圖5 所示，從仿真結果與表3 都能再一次看到經過改進后的A*算法性能更優，達到實驗要求。

表3 30×30柵格地圖環境

2.6.2 路徑平滑對比分析

通過Bezier 曲線對30×30 環境地圖下改進A*算法規劃出的路徑進行平滑處理，得到圖6 仿真圖，其中Bezier曲線中的控制點即為最優路徑中的節點，虛線曲線為通過改進A*算法所規劃出的最優路徑經過平滑優化后的曲線，從圖中可以看到，在對節點進行Bezier 曲線優化時，①和②處能觸碰到障礙物，在實際工作中該種情況會使谷物機器人對自身造成一定的損壞，所以需對Bezier 曲線進行一定的優化。

圖6 改進A*算法Bezier 曲線優化處理

對上述經過Bezier 曲線平滑后的路徑再次通過增加控制點的方式進行優化，在本次實驗中將相鄰的兩個控制點增加3 個點再次進行平滑處理得到如圖7 仿真圖，圖7（a）和圖7（b）中的圓圈構成的曲線為圖6 中①和②所示經過平滑后的曲線，從圖中可以看出，該曲線能一定程度地躲避障礙物，避免了實際谷物機器人在工作過程中觸碰到障礙物，減少了對自身的損壞。圖7（c）為完整的平滑曲線圖，通過對曲線進行優化處理，路徑更加順暢，使得谷物機器人在實際工作中移動得更加流暢，仿真結果表明了本算法對路徑平滑的可行性和有效性。

圖7 優化Bezier 曲線對改進A*算法平滑處理

2.6.3 全覆蓋路徑規劃仿真實驗

前面詳細介紹了翻曬谷物機器人基于柵格地圖的全覆蓋路徑規劃基本步驟，要想完成一個完整的區域全覆蓋，首先需要對工作環境地圖進行建模，然后在有障礙物的區域根據障礙物頂點進行區域劃分得到多個子區域，其次對子區域設計遍歷算法，最終根據區域銜接路徑規劃完成整個工作區域的全覆蓋。下面以30×30 障礙物環境地圖進行全覆蓋路徑規劃仿真，以此驗證本文設計的全覆蓋路徑規劃的可行性和有效性，仿真結果如下。圖8 為通過牛耕分解法對30×30 環境地圖下進行區域劃分的結果圖。通過仿真圖可知，該地圖被分成①～⑥6 個子區域，驗證了牛耕分解法的有效性。

圖8 30×30 牛耕分解結果圖

接下來對子區域分別進行弓子型區域覆蓋，仿真結果如圖9 所示。其中五角星表示機器人的起始點，實心圓圈表示當前區域的終點，空心圓圈表示下一個子區域起點。直線表示子區域內進行往返式弓子型路徑，曲線表示區域間的銜接路徑。從 30×30 全覆蓋路徑規劃仿真圖中可以看出，經過本文設計的算法策略均可以實現柵格地圖的100%覆蓋，驗證了本文提出的全覆蓋路徑規劃算法是可行且有效的。

圖9 30×30 全覆蓋路徑規劃仿真實驗

3 總結

本文提出一種改進A*算法的全覆蓋路徑規劃方案，利用柵格法、牛耕分解法、貪婪算法與曼哈頓距離結合策略、往返式弓子型遍歷方法和A*算法分別對機器人工作環境建模、子區域劃分、子區域起點選擇、子區域內部遍歷以及子區域銜接路徑規劃進行求解，實現整個機器人對場地的全覆蓋翻曬。同時對傳統A*算法和Bezier 曲線進行改進，在相同仿真環境下，改進后的B-A*算法使得搜索節點時間縮短，路徑平滑、安全。通過以上策略對環境地圖進行全覆蓋仿真分析，實驗結果表明本文提出的方法可完成100%的覆蓋，表明該方案具有一定的有效性和可適用性。