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

郝 杰 唐葉劍

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

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

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

1 問題描述與模型建立

1.1 問題描述

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

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

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

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

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

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

(1)

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

(2)

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

(3)

式中：

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

對(duì)點(diǎn)位間移動(dòng)路徑優(yōu)化的目的是在確保移動(dòng)安全的同時(shí)，使得點(diǎn)位間路徑更短和更加平滑。綜上3層優(yōu)化問題，建立基于總移動(dòng)距離D(X1,X2,X3)、點(diǎn)位間路徑平滑度φ(X1,X2,X3)和移動(dòng)安全度S為評(píng)價(jià)指標(biāo)的食品揀取機(jī)器人路徑規(guī)劃模型，目標(biāo)優(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)——起始點(diǎn)到第1個(gè)訪問點(diǎn)位的路徑距離(m)和路徑平滑度(°)；

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

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

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

2.1 麻雀搜索算法

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

(7)

(8)

(9)

式中：

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

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

L——單位向量；

R2——預(yù)警值；

ST——安全值；

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

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

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

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

2.2 DSSA種群聚類分析與迭代進(jìn)化方式改進(jìn)

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

(10)

式中：

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

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

(11)

(12)

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

(13)

(14)

式中：

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

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

(15)

式中：

(x1,…,xN)——機(jī)器人訪問點(diǎn)位順序集合；

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

圖2 麻雀編碼含義示意圖

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

(16)

(17)

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

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

3 仿真試驗(yàn)與結(jié)果分析

3.1 DSSA性能驗(yàn)證

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

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

表1 不同評(píng)價(jià)指標(biāo)對(duì)比結(jié)果

3.2 路徑規(guī)劃驗(yàn)證

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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