除草機(jī)器人定位系統(tǒng)設(shè)計(jì)
——基于跳距修正粒子群優(yōu)化和WSN

唐 林,劉 通

(重慶工程職業(yè)技術(shù)學(xué)院,重慶 402260)

0 引言

隨著環(huán)境污染的加重,全國(guó)各個(gè)城市正在提高城市綠化程度,大量的綠化草皮、球場(chǎng)草坪等綠地被建設(shè)。這些綠地需要進(jìn)行雜草清除維護(hù),而該項(xiàng)工作非常繁重,不僅枯燥,而且重復(fù)性強(qiáng),往往需要耗費(fèi)大量勞動(dòng)力。另外,為了實(shí)現(xiàn)農(nóng)業(yè)的可持續(xù)發(fā)展,不斷強(qiáng)調(diào)避免使用除草劑,使得智能化的全自動(dòng)除草機(jī)器人得到了迅猛發(fā)展。為此,提出了一種基于跳距修正粒子群優(yōu)化和WSN的除草機(jī)器人定位系統(tǒng),可以實(shí)現(xiàn)除草機(jī)器人定位和路徑規(guī)劃,對(duì)于草坪維護(hù)工作有重要意義。

1 WSN技術(shù)

WSN是一種由廉價(jià)的微小型傳感器組網(wǎng)的通信網(wǎng)絡(luò),包括傳感器、處理器、無(wú)線通訊和能量供應(yīng)等多個(gè)模塊。WSN定位過(guò)程中,會(huì)根據(jù)節(jié)點(diǎn)類型確定節(jié)點(diǎn)定位分布狀況。WSN主要由錨節(jié)點(diǎn)和未知節(jié)點(diǎn)組成,錨節(jié)點(diǎn)一般是位置已知的信標(biāo)節(jié)點(diǎn),而未知節(jié)點(diǎn)則是位置還不明確的節(jié)點(diǎn)。WSN節(jié)點(diǎn)分布如圖1所示。

WSN定位的首要目標(biāo)是求出目標(biāo)對(duì)象的位置坐標(biāo)信息,其定位計(jì)算方式主要有三邊測(cè)量、三角測(cè)量和極大似然估計(jì)等。本文研究的除草機(jī)器人定位系統(tǒng)采用三邊測(cè)量方法,其三邊是指待定位節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離值。三邊測(cè)量法需要獲得至少3個(gè)未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的距離,才能計(jì)算出待測(cè)節(jié)點(diǎn)的位置信息。三邊定位測(cè)量示意如圖2所示。

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

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

(1)

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

(2)

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

(3)

(4)

由X=A-1B,可以求出D點(diǎn)的坐標(biāo)為

(5)

WSN節(jié)點(diǎn)定位在計(jì)算三邊距離時(shí),常常會(huì)存在一定的偏差,即會(huì)導(dǎo)致三邊為半徑的圓無(wú)法交于一點(diǎn),直接影響定位的精度,因此需要對(duì)定位結(jié)果進(jìn)行優(yōu)化修正。本文采用AOA(Angle-of-Arrival)定位方法對(duì)WSN節(jié)點(diǎn)定位進(jìn)行修正。AOA主要是在三邊測(cè)量中,加入測(cè)量信號(hào)和節(jié)點(diǎn)間的角度,采用距離和角度的方法實(shí)現(xiàn)未知節(jié)點(diǎn)的定位。AOA定位方法需得到未知節(jié)點(diǎn)和錨節(jié)點(diǎn)A、B間的角度,如圖3所示。

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

假設(shè)A(x1,y1)和B(x2,y2)為錨節(jié)點(diǎn),N(x,y)為未知節(jié)點(diǎn),可以得出兩個(gè)角度的表達(dá)式,即

(6)

則可以得出N點(diǎn)的位置為

(7)

2 基于跳距修正粒子群優(yōu)化的定位算法

盡管WSN定位算法采用三邊測(cè)量和AOA算法相結(jié)合的方式實(shí)現(xiàn)除草機(jī)器人的定位,但由于除草機(jī)器人工作環(huán)境復(fù)雜,常常會(huì)有障礙物遮擋錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的信號(hào),導(dǎo)致定位精度較低。為了解決WSN定位算法精度低的問(wèn)題,將在WSN定位的基礎(chǔ)上采用跳距修正粒子群對(duì)其進(jìn)行優(yōu)化。

2.1 跳距定位算法

跳距定位算法實(shí)質(zhì)是DV-Hop算法,該方法和網(wǎng)絡(luò)距離向量路由機(jī)制類似,未知節(jié)點(diǎn)會(huì)先計(jì)算和錨節(jié)點(diǎn)的最小跳數(shù),并求出每跳的平均距離,然后再結(jié)合三邊距離計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。DV-Hop算法的求解流程如下:

Step1:錨節(jié)點(diǎn)進(jìn)行廣播分組。這一過(guò)程是錨節(jié)點(diǎn)以廣播的形式給周邊的節(jié)點(diǎn)發(fā)送一個(gè)數(shù)據(jù)分組,讓所有的周邊節(jié)點(diǎn)獲取到錨節(jié)點(diǎn)的位置信息。錨節(jié)點(diǎn)發(fā)送的數(shù)據(jù)分組的信息如圖4所示。

圖4 錨節(jié)點(diǎn)數(shù)據(jù)分組信息Fig.4 Anchor node data grouping information。

Step2:計(jì)算和廣播校正值。當(dāng)相鄰節(jié)點(diǎn)收到錨節(jié)點(diǎn)的廣播信息后,會(huì)對(duì)跳數(shù)和坐標(biāo)信息進(jìn)行計(jì)算,并根據(jù)計(jì)算結(jié)果對(duì)值進(jìn)行校正,計(jì)算公式為

(8)

其中,HopSize為錨節(jié)點(diǎn)i每跳的距離;hij為錨節(jié)點(diǎn)i和j的最小跳數(shù)。

為了保證每個(gè)錨節(jié)點(diǎn)接到的廣播信息是離其最近的,所有節(jié)點(diǎn)只接受第1個(gè)收到的校正值。

Step3:定位計(jì)算。未知節(jié)點(diǎn)根據(jù)前兩步收到和計(jì)算的最小跳數(shù),得到其與多個(gè)錨節(jié)點(diǎn)的距離信息,然后結(jié)合前面的WSN定位算法求出未知節(jié)點(diǎn)的定位坐標(biāo)。

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

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

根據(jù)Step2可以計(jì)算出A、B、C間每跳的實(shí)際距離,即

(9)

(10)

(11)

由圖5可以看出:未知節(jié)點(diǎn)M和A、B、C間的跳數(shù)分別為3、2、2,其與B最近。因此,M的平均每跳距離會(huì)選擇B的值。那么,M與A、B、C之間的距離分別為3HopSizeB、2HopSizeB和3HopSizeB,可以根據(jù)WSN的三邊測(cè)量方法和AOA定位算法進(jìn)行出未知節(jié)點(diǎn)M的準(zhǔn)確坐標(biāo)。

2.2 粒子群優(yōu)化

由于無(wú)線傳感節(jié)點(diǎn)的信號(hào)強(qiáng)度容易受空氣、天氣和其他環(huán)境等外界因素的影響,導(dǎo)致測(cè)距值和實(shí)際距離值會(huì)有偏差,因此采用粒子群進(jìn)行算法優(yōu)化。

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

(12)

粒子群慣性權(quán)重ω的線性方程式為

(13)

粒子群最優(yōu)位置更新為

(14)

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

(15)

本文選擇螞蟻算法與粒子群算法進(jìn)行對(duì)比,在求解目標(biāo)函數(shù)過(guò)程中兩種算法的變化曲線如圖6所示。

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

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

3 除草機(jī)器人定位系統(tǒng)的應(yīng)用

前面對(duì)除草機(jī)器人定位算法進(jìn)行了介紹和研究,本章主要說(shuō)明該方法的應(yīng)用。除草機(jī)器人定位系統(tǒng)主要是為了實(shí)現(xiàn)除草機(jī)器人的路徑規(guī)劃,與一般移動(dòng)機(jī)器人路徑規(guī)劃不同,除草機(jī)器人一般需要其運(yùn)動(dòng)軌跡充滿整個(gè)工作區(qū)域。

3.1 除草機(jī)器人路徑規(guī)劃

除草機(jī)器人路徑規(guī)劃是整個(gè)系統(tǒng)的核心環(huán)節(jié),與除草機(jī)器人的工作效率具有非常大的關(guān)系。合理的路徑規(guī)劃可以降低除草機(jī)器人的工作時(shí)間,大大提高其工作效率。除草機(jī)器人的運(yùn)動(dòng)路徑主要有直線運(yùn)行方式和邊界跟蹤運(yùn)行兩種策略,如圖7所示。

圖7 除草機(jī)器人的兩種運(yùn)動(dòng)路徑Fig.7 Two kinds of motion paths of weeding robot。

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

3.2 邊界區(qū)域的處理流程

除草機(jī)器人在邊角處移動(dòng)時(shí),最容易出現(xiàn)問(wèn)題,不合理的路徑規(guī)劃策略會(huì)導(dǎo)致除草機(jī)器人跑到非工作區(qū)域,所以會(huì)在除草機(jī)器人上安裝多個(gè)感測(cè)傳感器去判斷區(qū)域邊角的移動(dòng)策略。除草機(jī)器人邊界移動(dòng)如圖8所示。

圖8 除草機(jī)器人邊界移動(dòng)示意圖Fig.8 The sketch diagram of edge movement of weeding robo。

圖8中,當(dāng)除草機(jī)器人傳感器A4或A3檢測(cè)到邊界L1時(shí),以直線除草的方式應(yīng)該是先后退,然后再右轉(zhuǎn)。正常情況下,走這種角落會(huì)先檢查到L1,然后后退半個(gè)車身,再右轉(zhuǎn)向180°;在轉(zhuǎn)彎時(shí),傳感器會(huì)檢測(cè)到L2,如果沒(méi)有指定特定的路徑優(yōu)化策略,則又后退半個(gè)車身,再右轉(zhuǎn)向180°,這樣會(huì)導(dǎo)致機(jī)器人的方向混亂。要避免以上情況的出現(xiàn),則應(yīng)該用軟件對(duì)這種事件進(jìn)行特別的優(yōu)化,當(dāng)在轉(zhuǎn)彎過(guò)程中檢測(cè)到邊界時(shí)原路回轉(zhuǎn)過(guò)去,在原位上進(jìn)行180°的左轉(zhuǎn)向,開(kāi)始從這個(gè)區(qū)域的向另外一端的循環(huán)遍歷。

4 試驗(yàn)與結(jié)果分析

為了驗(yàn)證基于跳距修正粒子群優(yōu)化和WSN的除草機(jī)器人定位系統(tǒng)的準(zhǔn)確性和可靠性,在一塊六邊形的草坪進(jìn)行了割草測(cè)試。除草機(jī)器人行走路徑如圖9所示。

圖9 試驗(yàn)結(jié)果圖Fig.9 The result diagram。

試驗(yàn)結(jié)果表明:該除草機(jī)器人路徑規(guī)劃非常有條理,實(shí)現(xiàn)了整個(gè)六邊形草坪的割草作業(yè),沒(méi)有留下死角區(qū)域,對(duì)于多個(gè)邊界的位置也能處理得很好,且除草機(jī)器人行走路徑最短,定位精度高,具有較高的實(shí)時(shí)性和可靠性。

5 結(jié)論

從除草機(jī)器人的實(shí)際需求出發(fā),結(jié)合現(xiàn)有除草機(jī)器人產(chǎn)品的特點(diǎn),提出了一種定位精度高、路徑優(yōu)化能力強(qiáng)、結(jié)構(gòu)簡(jiǎn)單及成本較低的除草機(jī)器人定位方案。該方案采用跳距修正粒子群優(yōu)化和WSN定位技術(shù),可以實(shí)現(xiàn)除草機(jī)器人的定位和路徑規(guī)劃。試驗(yàn)結(jié)果表明:該除草機(jī)器人路徑規(guī)劃非常有條理,實(shí)現(xiàn)了整個(gè)六邊形草坪的割草作業(yè),沒(méi)有留下死角區(qū)域,且除草機(jī)器人行走路徑最短,定位精度高,具有較高的實(shí)時(shí)性和可靠性。