基于密度峰值聚類并行麻雀搜索算法的食品機器人路徑規劃

郝 杰 唐葉劍

(1. 江蘇旅游職業學院，江蘇 揚州 225000；2. 安徽師范大學皖江學院，安徽 蕪湖 241008)

隨著食品工業化進程的不斷加速推進，食品機器人在食品生產、加工等相關領域發揮的作用越來越大[1-2]，中國也相繼在國家科技重大專項、國家髙技術研究發展計劃等重大戰略規劃中提出了機器人研發課題[3]。移動機器人路徑規劃是當前機器人技術研究的熱點之一，同時也涌現出了大量研究成果[4-6]，而機器人在食品分揀領域中的應用研究則相對較少。徐翔斌等[7]對移動機器人揀貨系統進行了綜合論述，并指出基于移動機器人的揀貨系統能夠大幅度提高物品揀選效率。劉芙等[8]以移動最短距離為評價指標，建立了食品揀取機器人雙層路徑規劃模型，并采用改進的雞群優化算法對模型進行求解，得到了總移動距離最優規劃路徑，但是該模型并未考慮路徑的平滑度等因素，路徑可行性需要進一步論證。張好劍等[9]以工位食品揀取順序為優化目標，提出了一種基于遺傳算法的并聯機器人分揀路徑優化方法，有效縮短了分揀行程，但是該算法需要充分考慮算法的運算速度以滿足分揀實時性要求。余曉蘭等[10]、趙相博等[11]、韋洪新等[12]則對食品揀取機器人涉及的視覺伺服控制、運動學基礎和抓取臂空間建模等技術進行了論證研究，這些研究成果進一步推動了揀取機器人在食品領域中的實際應用。

研究擬對多點位食品揀取機器人移動路徑規劃問題進行探索，提出基于密度峰值聚類并行麻雀搜索算法的食品揀取機器人路徑規劃方法，并設計具有較高收斂精度和較快收斂速度的改進麻雀搜索算法[13-14]對模型進行求解，并通過仿真試驗驗證所提方法的可行性。

1 問題描述與模型建立

1.1 問題描述

在某食品生產企業倉庫內，企業根據生產負荷、所需原材料種類、機器人裝載量等因素，對倉庫點位滿載量、點位原材料放置種類利用RFID[15]進行信息識別優化，并將M個食品原材料存放點位劃分為多個原材料揀取區域，每個區域包含N個點位，這N個點位存放的原材料能夠滿足生產一批食品所需物質，而且揀取機器人在一個工作周期內能夠揀取完所有點位上的原材料。以單個原材料揀取區域為例，用序列(1,2,…,N)依次對N個點位進行標注，食品揀取機器人路徑規劃問題可以轉化為：通過對機器人訪問點位順序以及點位間移動路徑進行優化，使得揀取機器人在確保移動安全的同時，移動距離達到最優且移動路徑更加平滑。

1.2 多點位路徑規劃模型建立

由于點位xi(i=1,…,N)的上、下、左、右4個方向都是潛在的機器人揀取位置，為了便于問題描述，取點位四周的中心位置為潛在揀取位置，并描述為xi,1、xi,2、xi,3和xi,4，顯然揀取位置選取不同，點位間的移動路徑也就不同，因此，食品揀取機器人路徑規劃問題不能簡單認為是旅行商問題(TSP)[16]，其包含3層待優化問題：

(1) 訪問點位順序優化。機器人起始點xstar確定，當游歷完所有點位后得到訪問點位順序集合X1(xstar,x1,…，xi,…,xN,xstar)，其中，xi為機器人訪問的第i個點位的標號，顯然訪問點位順序不同，得到的移動路徑也就不同。

圖1 潛在揀取位置確定示意圖

(3) 點位間移動路徑優化。設點位xi-1、xi的揀取位置為xi-1,a、xi,b，在xi-1,a與xi,b連線空間內找到n個點y1,…,yn，依次連接這些點得到點位間路徑節點集合X3(xi-1,a,y1,…,yn,xi,b)，此時節點間路徑距離di-1,i為：

(1)

定義xi-1,a與xi,b間路徑平滑度φi-1,i：

(2)

φi-1,i值越小，表明路徑越平滑。設機器人移動空間內存在m個障礙物，障礙物j最小安全距離為dsafe,j，則定義安全度S：

(3)

式中：

dj——機器人到障礙物j中心的距離，m。

對點位間移動路徑優化的目的是在確保移動安全的同時，使得點位間路徑更短和更加平滑。綜上3層優化問題，建立基于總移動距離D(X1,X2,X3)、點位間路徑平滑度φ(X1,X2,X3)和移動安全度S為評價指標的食品揀取機器人路徑規劃模型，目標優化函數為：

minf=S×[ω1D(X1,X2,X3)+ω2φ(X1,X2,X3)]，

(4)

(5)

0<ω1,ω2<1,ω1+ω1=1，

(6)

式中：

d(xstar,x1)、φ(xstar,x1)——起始點到第1個訪問點位的路徑距離(m)和路徑平滑度(°)；

d(xN,xstar)、φ(xN,xstar)——最后1個訪問點位到起始點的路徑距離(m)和路徑平滑度(°)。

從食品揀取機器人多點位路徑規劃目標優化函數可以看出，機器人揀取路徑與點位訪問順序X1、點位揀取位置X2以及點位間路徑節點集合X3息息相關，采用改進的麻雀搜索算法對模型進行求解，從而獲取最優路徑規劃。

2 多點位路徑規劃模型求解

2.1 麻雀搜索算法

麻雀搜索算法(SSA)[17]是最近才被提出的一種新型群體智能優化算法，其通過模擬麻雀種群群體覓食行為，以實現對優化問題的求解。對于具有Q個體的麻雀種群，SSA算法根據麻雀個體目標函數值f(·)優劣，將麻雀分為發現者XDis、跟隨者XFol和警戒者XVig，并賦予不同的更新進化機制(以最小優化問題為例)，t時刻(最大迭代次數設定為Tmax)有：

(7)

(8)

(9)

式中：

ξ∈(0,1)——均勻分布隨機數；

q——服從正態分布的隨機數；

L——單位向量；

R2——預警值；

ST——安全值；

A——由1、-1組成的向量；

β——控制系數；

ξ——極小常數。

SSA算法有一定的隨機性和盲目性，SSA算法在迭代進化過程中，只選擇種群最優解或者最差解進行學習，雖然加速了算法收斂速度，但是也導致算法種群多樣性降低，容易陷入局部最優。為此設計密度峰值聚類優化麻雀搜索算法(DSSA)，利用改進的密度峰值聚類算法對麻雀種群進行聚類分析，根據聚類結果劃分不同子族群，并重新定義麻雀迭代進化機制和編碼方式。

2.2 DSSA種群聚類分析與迭代進化方式改進

密度峰值聚類算法(DPC)[18]認為，若數據點Xi的局部密度ρi高于附近點，且與具有更高局部密度數據點的距離δi較大，則Xi為可能的聚類中心，人為設定數據點截斷距離dc，則ρi、δi計算公式為：

(10)

式中：

dij——Xi與附近數據點的距離，m。

定義聚類中心判定指標γi=ρiδi，DPC選取γi較大的點為聚類中心。從DPC實現過程可以看出，其參數設置簡單，對數據具有良好的普適性[19]。由于DPC采用歐式距離進行數據點間距離度量，忽略了數據相關性對聚類結果的影響，因此采用協方差距離dD替代傳統歐式距離度量：

(11)

(12)

采用改進的DPC(IDPC)對麻雀種群進行聚類分析，得到C個聚類，每個麻雀個體Xi被劃分到某一分類中，用cXi進行描述(c∈[1,…,C]表示Xi所在分類)，此時同一類個體間具有更多的相似性，不同類個體具有更多的差異性，選取每個分類中目標函數最優的前K個個體組成發現者子族群，最差的U個個體組成警戒者子族群，其余個體為跟隨者子族群。對3個子族群內個體按照目標函數值優劣進行排序，并重新定義進化機制。

(13)

(14)

式中：

警戒者子族群內個體執行基本SSA警戒者更新操作。

2.3 DSSA求解多點位路徑規劃模型實現

(15)

式中：

(x1,…,xN)——機器人訪問點位順序集合；

(x1,a1,…,xi,ai,…,xN,ai)——點位揀取位置集合。

圖2 麻雀編碼含義示意圖

2.3.2 路徑規劃模型求解實現 對于食品揀取機器人多點位路徑規劃問題，采用改進的麻雀搜索算法進行求解，定義目標函數f(X)為：

(16)

(17)

麻雀種群根據編碼定義式(15)，在解空間內隨機產生Q個初始解，每個個體代表問題的一個解，即每個個體編碼確定了機器人點位訪問順序、點位揀取位置以及點位間移動路徑節點。在進化過程中，麻雀個體首先根據(x1,…,xN)、(x1,a1,…,xi,ai,…,xN,ai)信息，迭代進化求解出所有節點間當前最佳移動路徑，然后更新種群信息，并對離散編碼進行更新操作，如此反復最終實現最優解求解，從而得到食品揀取機器人移動路徑。由于算法在每次迭代過程中都需要對Q個點位間路徑以及從起始點出發到回歸起始點路徑進行優化求解，需要消耗大量運算時間，為此搭建MPI并行運算架構，每個線程執行一個節點間路徑節點優化操作，以提升算法運算效率。圖3給出了DSSA優化食品揀取機器人多點位路徑規劃問題實現流程圖。

圖3 DSSA優化食品揀取機器人多點位路徑規劃問題實現流程圖

3 仿真試驗與結果分析

3.1 DSSA性能驗證

從圖4、表1可以看出，在收斂精度上，對于函數f1、f3、f4和f5，DSSA都能以100%的成功率收斂于全局最優解，收斂精度明顯好于其他3種算法；對于函數f3，DA、SSA算法的求解成功率只有91.6%和94.2%，低于其他2種算法；對于函數f4，DA、SSA算法的求解成功率更低，只有37.2%和40.1%，而SSA基本上找不到全局最優解；對于復雜病態函數f2，DSSA求解成功率達到了84.2%，而其他3種算法基本上無法實現全局最優解求解，表明DSSA具有更高的收斂精度。在算法運算時間上，由于DSSA在每次迭代過程中需要利用IDPC對種群進行聚類分析，增加了算法復雜度，因此DSSA算法需要消耗更多的運算時間。DSSA算法之所以具有較高的收斂精度，是因為在每次迭代過程中，都對種群多樣性進行聚類分析，并根據聚類結果選取學習對象進行更新，從而使得算法具有較強的全局搜索能力，收斂精度更高。

圖4 4種算法函數收斂曲線

表1 不同評價指標對比結果

3.2 路徑規劃驗證

3.2.1 實例仿真 某食品生產企業倉庫為40 m×40 m的方形區域，該企業對食品原材料存放點位實行網格化管理，即將倉庫劃分為邊長20 m的網格，因此共有16個點位，每個網格中心40 m×40 m的區域為食品原材料存放點位，距離每個點位邊緣1 m中央處為潛在揀取位置，此外倉庫共有9根半徑為1 m的圓柱。某生產周期內，共有8個點位存放原材料，見圖5(a)；移動機器人從(10,40)處出發，揀取8個點位存放的原材料，采用文中提出的路徑規劃方案進行求解，最終規劃路徑見圖5(b)。表2 給出了規劃結果。

從圖5、表2可以看出，文中提出的基于密度峰值聚類并行麻雀搜索算法的食品機器人路徑規劃方法能夠給出合理的路徑規劃方案，點位間移動路徑曲線較為平滑，有效避開了圓立柱等障礙物，實現了對所有點位的有秩序訪問。說明基于訪問點位順序、潛在揀取位置、點位間移動路徑優化3層路徑規劃的模型，很好地反映了實際應用問題，而且采用DSSA對模型求解，能夠找到合理的規劃路徑方案。

表2 食品揀取機器人路徑規劃結果

圖5 食品揀取機器人路徑規劃圖

3.2.2 對比試驗 為進一步驗證所提方法的性能，采用文獻[8]提出的路徑規劃方法、GWO算法(GWO算法的編碼方式以及并行計算架構參考DSSA)進行對比試驗，倉庫區域設定為100 m×100 m的方形區域，網格大小為20 m×20 m，每個網格的4個角放置半徑為1 m的圓柱。隨機模擬產生3種食品揀取應用場景：① 場景一，隨機選取每列2個網格為放置原材料點位，共計10個待揀取點位；② 場景二，隨機選取每列3個網格為放置原材料點位，共計15個待揀取點位；③ 場景三，隨機選取每列4個網格為放置原材料點位，共計20個待揀取點位。每種算法獨立運行10次，試驗結果取均值，表3給出了對比結果。

從表3可以看出，對于4類應用場景，無論是移動路徑總長度、平滑度還是移動時間，試驗方法得到的優化結果都要優于其他2種算法，路徑總長度縮短了約7.3%～39.2%，移動時間縮短了約26.7%～50.1%，而基于GWO算法得到的結果最差，表明試驗方法得到的食品揀取機器人路徑更優，這是因為：

表3 不同方法路徑規劃結果對比

(1) 文中構建的規劃模型更符合實際問題。文獻[8]在路徑規劃過程中，先確定點位訪問順序，再依次確定兩兩點位間的移動路徑，這種方法得到總移動路徑不一定最優，而試驗方法將3層優化問題統籌考慮，每次迭代過程中同時更新點位訪問順序、點位揀取位置和點位間移動路徑，從而保證了在獲取最優訪問順序的同時，節點間路徑也是最優的。

(2) 文中提出的DSSA具有更優的全局尋優能力。采用IDPC對種群聚類分析，使得麻雀個體在選取進化對象時更有針對性，能夠選擇空間差異性更大的個體進行學習，保證了算法能夠在更廣的空間內進行搜索，提高了算法收斂精度。

(3) 文中設計的路徑模型求解流程效率更高。針對基于3層優化問題建立的路徑規劃模型，重新設計了麻雀個體編碼方式，并將MPI并行運行架構應用于求解過程，更符合模型優化流程，進一步改善了求解結果精度。

4 結束語

對多點位食品揀取機器人路徑規劃問題進行研究，提出了基于密度峰值聚類并行麻雀搜索算法的路徑規劃方法，建立了融合3層優化問題的路徑規劃模型，并采用改進的麻雀搜索算法進行求解，通過引入密度峰值聚類、改進個體更新機制、重新定義編碼方式和搭建并行運行架構，使得獲得規劃路徑總長度更短、更加平滑，具有一定的應用推廣價值。