多移動(dòng)機(jī)器人路徑規(guī)劃研究算法
——基于分布式實(shí)時(shí)仿真系統(tǒng)

周瑩瑩,張東濤,張玉華

(1.漯河職業(yè)技術(shù)學(xué)院 信息工程系,河南 漯河 462000;2.漯河食品職業(yè)學(xué)院 信息工程系,河南 漯河 462000)

0 引言

分布式并行計(jì)算實(shí)時(shí)仿真系統(tǒng)可以方便地模擬機(jī)器人的作業(yè)情況,這是由于其采用網(wǎng)格計(jì)算架構(gòu)可以實(shí)現(xiàn)大規(guī)模存儲(chǔ)和多計(jì)算機(jī)協(xié)同計(jì)算。該方法通過因特網(wǎng)進(jìn)行互聯(lián)后,用戶可以同時(shí)在統(tǒng)一的Web界面上使用多臺(tái)計(jì)算機(jī)進(jìn)行計(jì)算,從而充分利用計(jì)算機(jī)資源,有效提高了計(jì)算效率。在多采摘機(jī)器人路徑規(guī)劃的仿真模擬時(shí),要求系統(tǒng)具有較高的計(jì)算效率和計(jì)算精度,而分布式實(shí)時(shí)仿真系統(tǒng)可以滿足這個(gè)要求,將其引入到采摘機(jī)器人路徑規(guī)劃仿真系統(tǒng)中,對(duì)于采摘機(jī)器人路徑規(guī)劃和自主導(dǎo)航的研究具有重要的意義。

1 采摘機(jī)器人路徑規(guī)劃實(shí)時(shí)仿真系統(tǒng)

在采摘機(jī)器人設(shè)計(jì)過程中,路徑規(guī)劃系統(tǒng)的設(shè)計(jì)非常重要,直接影響采摘機(jī)器人自主導(dǎo)航的精度,進(jìn)而影響采摘的準(zhǔn)確性和效率。分布式實(shí)時(shí)仿真系統(tǒng)具有較高的計(jì)算效率,由于路徑規(guī)劃的計(jì)算量較大,特別是在多采摘機(jī)器人協(xié)同作業(yè)時(shí)計(jì)算較為復(fù)雜,因此可以借助分布式實(shí)時(shí)仿真系統(tǒng)。分布式實(shí)時(shí)仿真系統(tǒng)可以采用網(wǎng)格計(jì)算體系結(jié)構(gòu)和無縫連接技術(shù),集成了計(jì)算機(jī)協(xié)作環(huán)境,共由4個(gè)層次組成,包括應(yīng)用層、開發(fā)層、中間件層和本地資源層,如圖1所示。

圖1 網(wǎng)格計(jì)算體系框架Fig.1 The framework of grid computing architecture

網(wǎng)格計(jì)算體系是實(shí)現(xiàn)分布式實(shí)時(shí)計(jì)算的基礎(chǔ),其最重要的部分是資源層部分。該層次包含了很多基礎(chǔ)硬件資源,包括計(jì)算機(jī)資源和網(wǎng)絡(luò)資源等。利用網(wǎng)格計(jì)算體系,可以架構(gòu)分布式協(xié)同實(shí)時(shí)仿真系統(tǒng)。分布式實(shí)時(shí)仿真系統(tǒng)可以同時(shí)完成用戶提出的多種任務(wù),采用并行計(jì)算的原理提高計(jì)算能力,將同構(gòu)、異構(gòu)及計(jì)算機(jī)能力不同的計(jì)算機(jī)或者服務(wù)器進(jìn)行集成,在充分利用計(jì)算資源的同時(shí)提高了計(jì)算效率。

如圖2所示,分布式實(shí)時(shí)仿真系統(tǒng)和傳統(tǒng)的計(jì)算系統(tǒng)具有較大的區(qū)別,最重要的一點(diǎn)是分布式實(shí)時(shí)仿真系統(tǒng)提供了統(tǒng)一的Web界面,并提供中間件層,利用中間件可以將計(jì)算資源集成虛擬到Web界面上,利用兼容性接口屏蔽掉不同計(jì)算機(jī)資源的差異性。該系統(tǒng)與電力系統(tǒng)類似,實(shí)現(xiàn)即插即用,并拓展計(jì)算能力,實(shí)現(xiàn)了協(xié)同計(jì)算。

圖2 分布式實(shí)時(shí)仿真系統(tǒng)基本框架Fig.2 The basic framework of distributed real-time simulation system

2 基于智能算法的多采摘機(jī)器人路徑規(guī)劃

隨著通信技術(shù)和計(jì)算技術(shù)的不斷發(fā)展,采摘機(jī)器人的路徑規(guī)劃和自主導(dǎo)航技術(shù)得到了迅速的發(fā)展,將傳統(tǒng)的路徑規(guī)劃算法和智能算法相結(jié)合,可以提高采摘機(jī)器人在未知環(huán)境中的路徑規(guī)劃效果。在機(jī)器人智能化規(guī)劃算法中,常用的主要有5種,包括遺傳算法、模糊算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法和粒子群算法等。無論是在已知環(huán)境還是未知環(huán)境,這些算法都發(fā)揮著非常重要的作用。

1) 遺傳算法。遺傳算法主要是利用生物學(xué)遺傳規(guī)律,采用交叉和替換的原則進(jìn)行優(yōu)勝劣汰,最終實(shí)現(xiàn)路徑優(yōu)化的方法。該算法在機(jī)器人未知環(huán)境中的路徑規(guī)劃效果非常好,可以解決復(fù)雜環(huán)境下的路徑優(yōu)化問題,但計(jì)算量較大,使用時(shí)需要具有較高計(jì)算能力的硬件支持。

2)模糊邏輯算法。模糊算法主要是一種利用規(guī)則庫數(shù)據(jù)和環(huán)境信息,自主完成路徑規(guī)劃的方法。采用模糊邏輯算法可以改進(jìn)勢場法路徑規(guī)劃的一些不足之處,不過在復(fù)雜多變的未知環(huán)境中模糊邏輯算法也具有一定的局限性。

3) 神經(jīng)網(wǎng)絡(luò)算法。神經(jīng)網(wǎng)絡(luò)算法模擬神經(jīng)細(xì)胞的生物學(xué)規(guī)律,通過權(quán)重的設(shè)定可以對(duì)樣本數(shù)據(jù)進(jìn)行訓(xùn)練,最終輸出理想的結(jié)果。神經(jīng)網(wǎng)絡(luò)算法的實(shí)現(xiàn)較為簡便,因此在路徑規(guī)劃中經(jīng)常被采用。

4)蟻群算法。蟻群算法是受到螞蟻群體行為的啟發(fā)提出的一種算法,主要依據(jù)采摘作業(yè)環(huán)境的路徑距離指標(biāo)進(jìn)行規(guī)劃,將不規(guī)則的螞蟻路徑拉伸為直線段,從而找到最短的路徑。螞蟻算法可以模擬計(jì)算群體路徑行為,對(duì)于多采摘機(jī)器人協(xié)同作業(yè)時(shí)的路徑規(guī)劃具有重要的指導(dǎo)意義。

5)粒子群算法。粒子群算法是在鳥群捕食行為的啟發(fā)下提出來的,通過初始空間粒子的優(yōu)化,然后不斷迭代計(jì)算,最后得到全局優(yōu)化結(jié)構(gòu)。其算法效率較高,計(jì)算精度好,在進(jìn)行應(yīng)用時(shí)也展現(xiàn)了非常好的應(yīng)用效果。

由于本次主要是研究采摘機(jī)器人的群體路徑規(guī)劃行為,因此選用蟻群算法。假設(shè)螞蟻的代號(hào)為k(k=1,2···,m),其所走過的節(jié)點(diǎn)用tabuk(k=1,2,···,m)來記錄,所有節(jié)點(diǎn)組成的表便是禁忌表;禁忌表可以隨著螞蟻群體的運(yùn)動(dòng)動(dòng)態(tài)的進(jìn)行更新,從而對(duì)下一步要走的路徑做出智能化選擇。假設(shè)螞蟻的總體數(shù)量為m個(gè), 節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離為dij(i,j=0,1,...,n-1),在t時(shí)刻節(jié)點(diǎn)i與節(jié)點(diǎn)j連線上的信息素濃度為τij。在算法的剛開始時(shí)刻,螞蟻被隨機(jī)的進(jìn)行放置,因此得到的信息素濃度是相同的。在某一時(shí)刻螞蟻從一個(gè)節(jié)點(diǎn)轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn)的概率為

其中,allowedk={c-tabuk}表示螞蟻所有可以供選擇的可以行走的節(jié)點(diǎn),節(jié)點(diǎn)的結(jié)合用C來表示,信息啟發(fā)因子用α表示,該值的確定主要根據(jù)螞蟻的群體協(xié)作能力在判斷;β表示期望啟發(fā)式因子;ηij表示啟發(fā)函數(shù),通?？梢酝ㄟ^ηij=1/dij來得到。在螞蟻進(jìn)行路徑規(guī)劃過程中會(huì)產(chǎn)生大量的信息素,因此在規(guī)劃一步完成后需要對(duì)信息進(jìn)行更新,以免產(chǎn)生信息冗余。在t+n時(shí)刻,路徑(i,j)規(guī)劃的信息調(diào)整為

τij(t+n)=(1-ρ)×τij(t)+Δτij(t)

(2)

(3)

(4)

蟻量系統(tǒng)模型可以表示為

(5)

蟻密系統(tǒng)模型可以表示為

(6)

其中,Lk表示總的節(jié)點(diǎn)距離,Q表示信息素。由模型公式可以看出:蟻量系統(tǒng)和蟻密系統(tǒng)都是在完成一步后對(duì)信息素進(jìn)行更新,而蟻周系統(tǒng)是完成一個(gè)循環(huán)后更新信息素,因此選擇蟻周系統(tǒng)模型更加具有可靠性。

根據(jù)蟻群算法的基本原理,采摘機(jī)器人的路徑規(guī)劃也類似蟻群算法的流程,如圖3所示。

圖3 路徑規(guī)劃主要流程Fig.3 The main process of path planning

圖3中,首先m臺(tái)采摘機(jī)器人放在待采摘初始位置,以初試位置為依據(jù),通過螞蟻算法策略確定規(guī)劃路徑;通過仿真計(jì)算得到m個(gè)采摘機(jī)器人的路徑,在m個(gè)機(jī)器人路徑中有最快的路徑,可以選擇最快到達(dá)目標(biāo)點(diǎn)的作為最優(yōu)路徑,分配給第1臺(tái)采摘機(jī)器人,然后第2到達(dá)的分配給第2臺(tái)采摘機(jī)器人;以此類推,最后實(shí)現(xiàn)采摘機(jī)器人群體的路徑規(guī)劃。

3 采摘機(jī)器人路徑規(guī)劃性能測試

為了驗(yàn)證蟻群算法在多采摘機(jī)器人協(xié)同路徑規(guī)劃中應(yīng)用的可行性,在采摘機(jī)器人路徑規(guī)劃系統(tǒng)中引入了蟻群算法,以多采摘機(jī)器人協(xié)同工作為模擬場景,采用分布式實(shí)時(shí)仿真系統(tǒng)對(duì)算法進(jìn)行驗(yàn)證。

在農(nóng)忙時(shí)節(jié),由于待采摘的水果量較大,往往會(huì)投入多臺(tái)采摘機(jī)器人進(jìn)行協(xié)同化工作,其作業(yè)場景如圖4所示。以此作業(yè)場景為模擬背景,采用分布式實(shí)時(shí)仿真系統(tǒng)首先對(duì)機(jī)器人機(jī)器人接近目標(biāo)是對(duì)準(zhǔn)確度進(jìn)行仿真模擬。

圖4 多采摘機(jī)器人協(xié)同化作業(yè)場景Fig.4 The cooperative work scene of multi-picking robots

如圖5所示,在長和寬分別為10m的空間內(nèi)對(duì)機(jī)器人接近待采摘果實(shí)目標(biāo)的準(zhǔn)確程度進(jìn)行了仿真測試。結(jié)果表明:在沒有采用蟻群算法時(shí),路徑規(guī)劃搜索目標(biāo)時(shí)的準(zhǔn)確度不高,路徑與待采摘目標(biāo)有一定的距離。

如圖6所示,采用蟻群算法后,路徑規(guī)劃搜索目標(biāo)時(shí)的準(zhǔn)確度有了較大幅度的提高,路徑與待采摘目標(biāo)非常接近,可以滿足采摘機(jī)器人自主導(dǎo)航和路徑規(guī)劃的需要。

圖6 蟻群算法運(yùn)算結(jié)果Fig.6 The result with ant colony algorithms

如表1所示,采用分布式實(shí)時(shí)仿真系統(tǒng),對(duì)采摘機(jī)器人群體路徑規(guī)劃時(shí)的性能進(jìn)行了測試,并將采用蟻群算法和遺傳算法得到的計(jì)算時(shí)間進(jìn)行了對(duì)比。結(jié)果表明:采用蟻群算法的計(jì)算時(shí)間要明顯比遺傳算法少,計(jì)算效率高。

表1 采摘機(jī)器人群體路徑規(guī)劃計(jì)算時(shí)間對(duì)比表Table 1 The computational time comparison table for group path planning of picking robots s

為了進(jìn)一步驗(yàn)證蟻群算法的優(yōu)越性,采用分布式實(shí)時(shí)仿真系統(tǒng)對(duì)兩種算法的路徑規(guī)劃準(zhǔn)確率進(jìn)行了對(duì)比,如表2所示。

表2 采摘機(jī)器人群體路徑規(guī)劃計(jì)算準(zhǔn)確性對(duì)比表Table 2 The comparing table of accuracy of collection path planning for picking robots %

對(duì)比結(jié)果表明:采用蟻群算法的路徑規(guī)劃準(zhǔn)確率要高于遺傳算法,從而驗(yàn)證了算法的可靠性。

4 結(jié)論

為了提高采摘機(jī)器人的路徑規(guī)劃和自主導(dǎo)航能力,將蟻群算法引入到了采摘機(jī)器人控制系統(tǒng)中,根據(jù)蟻群算法的路徑規(guī)劃原理,實(shí)現(xiàn)了采摘機(jī)器人群體路徑規(guī)劃。采用分布式實(shí)時(shí)系統(tǒng)對(duì)采摘機(jī)器人路徑規(guī)劃系統(tǒng)進(jìn)行了仿真測試,結(jié)果表明:采用蟻群算法不僅可以有效提高采摘機(jī)器人群體路徑規(guī)劃的準(zhǔn)確性,且計(jì)算效率也較高,可以滿足采摘機(jī)器人自主導(dǎo)航系統(tǒng)的設(shè)計(jì)需求。