郝 杰 唐葉劍

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

1.2 多點位路徑規(guī)劃模型建立

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

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

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

(3) 點位間移動路徑優(yōu)化。設點位xi-1、xi的揀取位置為xi-1,a、xi,b，在xi-1,a與xi,b連線空間內找到n個點y1,…,yn，依次連接這些點得到點位間路徑節(jié)點集合X3(xi-1,a,y1,…,yn,xi,b)，此時節(jié)點間路徑距離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。

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

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)和路徑平滑度(°)。

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

2 多點位路徑規(guī)劃模型求解

2.1 麻雀搜索算法

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

(7)

(8)

(9)

式中：

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

q——服從正態(tài)分布的隨機數(shù)；

L——單位向量；

R2——預警值；

ST——安全值；

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

β——控制系數(shù)；

ξ——極小常數(shù)。

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

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

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

(10)

式中：

dij——Xi與附近數(shù)據(jù)點的距離，m。

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

(11)

(12)

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

(13)

(14)

式中：

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

2.3 DSSA求解多點位路徑規(guī)劃模型實現(xiàn)

(15)

式中：

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

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

圖2 麻雀編碼含義示意圖

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

(16)

(17)

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

圖3 DSSA優(yōu)化食品揀取機器人多點位路徑規(guī)劃問題實現(xiàn)流程圖

3 仿真試驗與結果分析

3.1 DSSA性能驗證

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

圖4 4種算法函數(shù)收斂曲線

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

3.2 路徑規(guī)劃驗證

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

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

表2 食品揀取機器人路徑規(guī)劃結果

圖5 食品揀取機器人路徑規(guī)劃圖

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

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

表3 不同方法路徑規(guī)劃結果對比

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

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

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

4 結束語

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