多移動機器人路徑規劃研究算法
——基于分布式實時仿真系統

周瑩瑩,張東濤,張玉華

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

0 引言

分布式并行計算實時仿真系統可以方便地模擬機器人的作業情況,這是由于其采用網格計算架構可以實現大規模存儲和多計算機協同計算。該方法通過因特網進行互聯后,用戶可以同時在統一的Web界面上使用多臺計算機進行計算,從而充分利用計算機資源,有效提高了計算效率。在多采摘機器人路徑規劃的仿真模擬時,要求系統具有較高的計算效率和計算精度,而分布式實時仿真系統可以滿足這個要求,將其引入到采摘機器人路徑規劃仿真系統中,對于采摘機器人路徑規劃和自主導航的研究具有重要的意義。

1 采摘機器人路徑規劃實時仿真系統

在采摘機器人設計過程中,路徑規劃系統的設計非常重要,直接影響采摘機器人自主導航的精度,進而影響采摘的準確性和效率。分布式實時仿真系統具有較高的計算效率,由于路徑規劃的計算量較大,特別是在多采摘機器人協同作業時計算較為復雜,因此可以借助分布式實時仿真系統。分布式實時仿真系統可以采用網格計算體系結構和無縫連接技術,集成了計算機協作環境,共由4個層次組成,包括應用層、開發層、中間件層和本地資源層,如圖1所示。

圖1 網格計算體系框架Fig.1 The framework of grid computing architecture

網格計算體系是實現分布式實時計算的基礎,其最重要的部分是資源層部分。該層次包含了很多基礎硬件資源,包括計算機資源和網絡資源等。利用網格計算體系,可以架構分布式協同實時仿真系統。分布式實時仿真系統可以同時完成用戶提出的多種任務,采用并行計算的原理提高計算能力,將同構、異構及計算機能力不同的計算機或者服務器進行集成,在充分利用計算資源的同時提高了計算效率。

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

圖2 分布式實時仿真系統基本框架Fig.2 The basic framework of distributed real-time simulation system

2 基于智能算法的多采摘機器人路徑規劃

隨著通信技術和計算技術的不斷發展,采摘機器人的路徑規劃和自主導航技術得到了迅速的發展,將傳統的路徑規劃算法和智能算法相結合,可以提高采摘機器人在未知環境中的路徑規劃效果。在機器人智能化規劃算法中,常用的主要有5種,包括遺傳算法、模糊算法、神經網絡算法、蟻群算法和粒子群算法等。無論是在已知環境還是未知環境,這些算法都發揮著非常重要的作用。

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

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

3) 神經網絡算法。神經網絡算法模擬神經細胞的生物學規律,通過權重的設定可以對樣本數據進行訓練,最終輸出理想的結果。神經網絡算法的實現較為簡便,因此在路徑規劃中經常被采用。

4)蟻群算法。蟻群算法是受到螞蟻群體行為的啟發提出的一種算法,主要依據采摘作業環境的路徑距離指標進行規劃,將不規則的螞蟻路徑拉伸為直線段,從而找到最短的路徑。螞蟻算法可以模擬計算群體路徑行為,對于多采摘機器人協同作業時的路徑規劃具有重要的指導意義。

5)粒子群算法。粒子群算法是在鳥群捕食行為的啟發下提出來的,通過初始空間粒子的優化,然后不斷迭代計算,最后得到全局優化結構。其算法效率較高,計算精度好,在進行應用時也展現了非常好的應用效果。

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

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

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

(2)

(3)

(4)

蟻量系統模型可以表示為

(5)

蟻密系統模型可以表示為

(6)

其中,Lk表示總的節點距離,Q表示信息素。由模型公式可以看出:蟻量系統和蟻密系統都是在完成一步后對信息素進行更新,而蟻周系統是完成一個循環后更新信息素,因此選擇蟻周系統模型更加具有可靠性。

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

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

圖3中,首先m臺采摘機器人放在待采摘初始位置,以初試位置為依據,通過螞蟻算法策略確定規劃路徑;通過仿真計算得到m個采摘機器人的路徑,在m個機器人路徑中有最快的路徑,可以選擇最快到達目標點的作為最優路徑,分配給第1臺采摘機器人,然后第2到達的分配給第2臺采摘機器人;以此類推,最后實現采摘機器人群體的路徑規劃。

3 采摘機器人路徑規劃性能測試

為了驗證蟻群算法在多采摘機器人協同路徑規劃中應用的可行性,在采摘機器人路徑規劃系統中引入了蟻群算法,以多采摘機器人協同工作為模擬場景,采用分布式實時仿真系統對算法進行驗證。

在農忙時節,由于待采摘的水果量較大,往往會投入多臺采摘機器人進行協同化工作,其作業場景如圖4所示。以此作業場景為模擬背景,采用分布式實時仿真系統首先對機器人機器人接近目標是對準確度進行仿真模擬。

圖4 多采摘機器人協同化作業場景Fig.4 The cooperative work scene of multi-picking robots

如圖5所示,在長和寬分別為10m的空間內對機器人接近待采摘果實目標的準確程度進行了仿真測試。結果表明:在沒有采用蟻群算法時,路徑規劃搜索目標時的準確度不高,路徑與待采摘目標有一定的距離。

如圖6所示,采用蟻群算法后,路徑規劃搜索目標時的準確度有了較大幅度的提高,路徑與待采摘目標非常接近,可以滿足采摘機器人自主導航和路徑規劃的需要。

圖6 蟻群算法運算結果Fig.6 The result with ant colony algorithms

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

表1 采摘機器人群體路徑規劃計算時間對比表Table 1 The computational time comparison table for group path planning of picking robots s

為了進一步驗證蟻群算法的優越性,采用分布式實時仿真系統對兩種算法的路徑規劃準確率進行了對比,如表2所示。

表2 采摘機器人群體路徑規劃計算準確性對比表Table 2 The comparing table of accuracy of collection path planning for picking robots %

對比結果表明:采用蟻群算法的路徑規劃準確率要高于遺傳算法,從而驗證了算法的可靠性。

4 結論

為了提高采摘機器人的路徑規劃和自主導航能力,將蟻群算法引入到了采摘機器人控制系統中,根據蟻群算法的路徑規劃原理,實現了采摘機器人群體路徑規劃。采用分布式實時系統對采摘機器人路徑規劃系統進行了仿真測試,結果表明:采用蟻群算法不僅可以有效提高采摘機器人群體路徑規劃的準確性,且計算效率也較高,可以滿足采摘機器人自主導航系統的設計需求。