除草機器人定位系統設計
——基于跳距修正粒子群優化和WSN

唐 林,劉 通

(重慶工程職業技術學院,重慶 402260)

0 引言

隨著環境污染的加重,全國各個城市正在提高城市綠化程度,大量的綠化草皮、球場草坪等綠地被建設。這些綠地需要進行雜草清除維護,而該項工作非常繁重,不僅枯燥,而且重復性強,往往需要耗費大量勞動力。另外,為了實現農業的可持續發展,不斷強調避免使用除草劑,使得智能化的全自動除草機器人得到了迅猛發展。為此,提出了一種基于跳距修正粒子群優化和WSN的除草機器人定位系統,可以實現除草機器人定位和路徑規劃,對于草坪維護工作有重要意義。

1 WSN技術

WSN是一種由廉價的微小型傳感器組網的通信網絡,包括傳感器、處理器、無線通訊和能量供應等多個模塊。WSN定位過程中,會根據節點類型確定節點定位分布狀況。WSN主要由錨節點和未知節點組成,錨節點一般是位置已知的信標節點,而未知節點則是位置還不明確的節點。WSN節點分布如圖1所示。

WSN定位的首要目標是求出目標對象的位置坐標信息,其定位計算方式主要有三邊測量、三角測量和極大似然估計等。本文研究的除草機器人定位系統采用三邊測量方法,其三邊是指待定位節點與錨節點的距離值。三邊測量法需要獲得至少3個未知節點和錨節點的距離,才能計算出待測節點的位置信息。三邊定位測量示意如圖2所示。

圖2 三邊定位測量示意圖Fig.2 The schematic diagram of trilateral positioning measurement。

圖2中,設A(xa,ya)、B(xb,yb)和C(xc,yc)為3個錨節點,D為未知節點,A、B、C到D的距離分別為da、db和dc,可以得到方程式為

(1)

式(1)進行變換后可以得到

(2)

將式(2)轉化為AX=B的形式,其中

(3)

(4)

由X=A-1B,可以求出D點的坐標為

(5)

WSN節點定位在計算三邊距離時,常常會存在一定的偏差,即會導致三邊為半徑的圓無法交于一點,直接影響定位的精度,因此需要對定位結果進行優化修正。本文采用AOA(Angle-of-Arrival)定位方法對WSN節點定位進行修正。AOA主要是在三邊測量中,加入測量信號和節點間的角度,采用距離和角度的方法實現未知節點的定位。AOA定位方法需得到未知節點和錨節點A、B間的角度,如圖3所示。

圖3 AOA定位算法Fig.3 AOA localization algorithm。

假設A(x1,y1)和B(x2,y2)為錨節點,N(x,y)為未知節點,可以得出兩個角度的表達式,即

(6)

則可以得出N點的位置為

(7)

2 基于跳距修正粒子群優化的定位算法

盡管WSN定位算法采用三邊測量和AOA算法相結合的方式實現除草機器人的定位,但由于除草機器人工作環境復雜,常常會有障礙物遮擋錨節點和未知節點的信號,導致定位精度較低。為了解決WSN定位算法精度低的問題,將在WSN定位的基礎上采用跳距修正粒子群對其進行優化。

2.1 跳距定位算法

跳距定位算法實質是DV-Hop算法,該方法和網絡距離向量路由機制類似,未知節點會先計算和錨節點的最小跳數,并求出每跳的平均距離,然后再結合三邊距離計算未知節點的坐標。DV-Hop算法的求解流程如下:

Step1:錨節點進行廣播分組。這一過程是錨節點以廣播的形式給周邊的節點發送一個數據分組,讓所有的周邊節點獲取到錨節點的位置信息。錨節點發送的數據分組的信息如圖4所示。

圖4 錨節點數據分組信息Fig.4 Anchor node data grouping information。

Step2:計算和廣播校正值。當相鄰節點收到錨節點的廣播信息后,會對跳數和坐標信息進行計算,并根據計算結果對值進行校正,計算公式為

(8)

其中,HopSize為錨節點i每跳的距離;hij為錨節點i和j的最小跳數。

為了保證每個錨節點接到的廣播信息是離其最近的,所有節點只接受第1個收到的校正值。

Step3:定位計算。未知節點根據前兩步收到和計算的最小跳數,得到其與多個錨節點的距離信息,然后結合前面的WSN定位算法求出未知節點的定位坐標。

跳距定位算法原理示意如圖5所示。其中,A、B、C等3點為錨節點,M為未知節點。根據DV-Hop算法的前兩步,可以計算出AB間為2跳,BC為5跳,AC為6跳。

圖5 跳距定位算法原理示意圖Fig.5 The schematic diagram of hop location algorithm。

根據Step2可以計算出A、B、C間每跳的實際距離,即

(9)

(10)

(11)

由圖5可以看出:未知節點M和A、B、C間的跳數分別為3、2、2,其與B最近。因此,M的平均每跳距離會選擇B的值。那么,M與A、B、C之間的距離分別為3HopSizeB、2HopSizeB和3HopSizeB,可以根據WSN的三邊測量方法和AOA定位算法進行出未知節點M的準確坐標。

2.2 粒子群優化

由于無線傳感節點的信號強度容易受空氣、天氣和其他環境等外界因素的影響,導致測距值和實際距離值會有偏差,因此采用粒子群進行算法優化。

設粒子i位置和速度向量為Xi=(xi1,xi2,…,xiD)和Vi=(vi1,vi2,…,viD),其當前最優和粒子群最優的位置分別為Pi=(pi1,pi2,…,piD)和Pg=(pg1,pg2,…,pgD),則第(k+1)時刻該粒子的位置和速度計算表達式為

(12)

粒子群慣性權重ω的線性方程式為

(13)

粒子群最優位置更新為

(14)

f(Pg)=min{f(Pi)}

(15)

本文選擇螞蟻算法與粒子群算法進行對比,在求解目標函數過程中兩種算法的變化曲線如圖6所示。

圖6 兩種算法的求解曲線Fig.6 The solving curves of two algorithms。

由圖6可以看出,粒子群算法收斂速度和迭代次數明顯優于螞蟻算法。

3 除草機器人定位系統的應用

前面對除草機器人定位算法進行了介紹和研究,本章主要說明該方法的應用。除草機器人定位系統主要是為了實現除草機器人的路徑規劃,與一般移動機器人路徑規劃不同,除草機器人一般需要其運動軌跡充滿整個工作區域。

3.1 除草機器人路徑規劃

除草機器人路徑規劃是整個系統的核心環節,與除草機器人的工作效率具有非常大的關系。合理的路徑規劃可以降低除草機器人的工作時間,大大提高其工作效率。除草機器人的運動路徑主要有直線運行方式和邊界跟蹤運行兩種策略,如圖7所示。

圖7 除草機器人的兩種運動路徑Fig.7 Two kinds of motion paths of weeding robot。

采用直線除草過程中,除草機器人在轉向時往往出現路徑重疊的情況,會增加總行駛路程;采用邊界跟蹤除草,則除草機器人需要不斷地進行轉彎處理,大大降低了機器人的平均行駛速度,路徑控制難度較大。為了使除草機器人的路徑簡單化和規范化,本文使用直線除草方式。當除草機器人的傳感器感覺到了邊界后,除草機器人自動后退半個車身,做180°的掉頭,然后繼續工作。這樣往返行進,就可以做到整個工作區域的全覆蓋。

3.2 邊界區域的處理流程

除草機器人在邊角處移動時,最容易出現問題,不合理的路徑規劃策略會導致除草機器人跑到非工作區域,所以會在除草機器人上安裝多個感測傳感器去判斷區域邊角的移動策略。除草機器人邊界移動如圖8所示。

圖8 除草機器人邊界移動示意圖Fig.8 The sketch diagram of edge movement of weeding robo。

圖8中,當除草機器人傳感器A4或A3檢測到邊界L1時,以直線除草的方式應該是先后退,然后再右轉。正常情況下,走這種角落會先檢查到L1,然后后退半個車身,再右轉向180°;在轉彎時,傳感器會檢測到L2,如果沒有指定特定的路徑優化策略,則又后退半個車身,再右轉向180°,這樣會導致機器人的方向混亂。要避免以上情況的出現,則應該用軟件對這種事件進行特別的優化,當在轉彎過程中檢測到邊界時原路回轉過去,在原位上進行180°的左轉向,開始從這個區域的向另外一端的循環遍歷。

4 試驗與結果分析

為了驗證基于跳距修正粒子群優化和WSN的除草機器人定位系統的準確性和可靠性,在一塊六邊形的草坪進行了割草測試。除草機器人行走路徑如圖9所示。

圖9 試驗結果圖Fig.9 The result diagram。

試驗結果表明:該除草機器人路徑規劃非常有條理,實現了整個六邊形草坪的割草作業,沒有留下死角區域,對于多個邊界的位置也能處理得很好,且除草機器人行走路徑最短,定位精度高,具有較高的實時性和可靠性。

5 結論

從除草機器人的實際需求出發,結合現有除草機器人產品的特點,提出了一種定位精度高、路徑優化能力強、結構簡單及成本較低的除草機器人定位方案。該方案采用跳距修正粒子群優化和WSN定位技術,可以實現除草機器人的定位和路徑規劃。試驗結果表明:該除草機器人路徑規劃非常有條理,實現了整個六邊形草坪的割草作業,沒有留下死角區域,且除草機器人行走路徑最短,定位精度高,具有較高的實時性和可靠性。