基于改進(jìn)雞群優(yōu)化算法的食品揀取機(jī)器人路徑規(guī)劃

劉 芙

陳宏明2

(1. 江蘇省淮陰商業(yè)學(xué)校，江蘇 淮安 223003；2. 淮陰工學(xué)院，江蘇 淮安 223003)

隨著機(jī)械工業(yè)技術(shù)的快速發(fā)展，機(jī)器人在食品自動(dòng)化分揀領(lǐng)域得到了廣泛應(yīng)用[1]，有效改變了傳統(tǒng)人工分揀效率低、強(qiáng)度大、易損耗的缺陷[2]。運(yùn)用移動(dòng)機(jī)器人對(duì)存放在不同點(diǎn)位上的食品原材料進(jìn)行高效揀取，是食品企業(yè)節(jié)約成本、提高效益的重要研究方向[3]。

當(dāng)前，關(guān)于食品揀取機(jī)器人自身涉及的技術(shù)研究較多，但是對(duì)多點(diǎn)位食品分揀領(lǐng)域的研究相對(duì)較少。余曉蘭等[4]對(duì)食品分揀機(jī)器人視覺技術(shù)進(jìn)行研究，提出了一種改進(jìn)BP神經(jīng)網(wǎng)絡(luò)的伺服控制方法，該方法能夠以較快速度將機(jī)器人帶到預(yù)定位置；張好劍等[5]對(duì)生產(chǎn)線單個(gè)點(diǎn)位分揀路徑規(guī)劃問題進(jìn)行研究，提出了一種基于改進(jìn)遺傳算法的分揀路徑優(yōu)化方法，提升了分揀效率，但是改進(jìn)遺傳算法收斂性能和運(yùn)算效率值得進(jìn)一步研究；Vafadar等[6]考慮機(jī)器人最小移動(dòng)次數(shù)和最小姿態(tài)變化，提出了一種最優(yōu)路徑規(guī)劃方法，仿真試驗(yàn)證明了該方法的有效性，但是該方法忽略了抓取點(diǎn)位物品空間位置信息；郝琳等[7]對(duì)食品分揀控制系統(tǒng)進(jìn)行研究，設(shè)計(jì)了一套包含機(jī)器人、工業(yè)相機(jī)等設(shè)備的分揀系統(tǒng)，試驗(yàn)結(jié)果也證明了該系統(tǒng)具有較好的穩(wěn)定性。

研究擬以移動(dòng)機(jī)器人在多工位食品揀取中的應(yīng)用為研究背景，提出基于改進(jìn)雞群優(yōu)化算法[8](Improved Chicken Swarm Optimization，ICSO)的食品揀取機(jī)器人路徑規(guī)劃方案，通過構(gòu)建多工位食品揀取機(jī)器人路徑規(guī)劃雙層模型，并設(shè)計(jì)改進(jìn)的雞群優(yōu)化算法對(duì)雙層模型進(jìn)行求解，優(yōu)化食品揀取和機(jī)器人移動(dòng)路徑，以期縮短移動(dòng)路徑，提升食品揀取效率。

1 食品揀取機(jī)器人路徑規(guī)劃模型構(gòu)建

1.1 食品揀取機(jī)器人工作流程

以某大型食品加工企業(yè)為例，存在多個(gè)食品原料供應(yīng)商，該企業(yè)根據(jù)產(chǎn)能、移動(dòng)機(jī)器人裝載量等因素，將食品原料存放倉庫劃分為多個(gè)大小相等的區(qū)域。在每個(gè)存放區(qū)域內(nèi)，為供應(yīng)商指定食品卸載點(diǎn)工位，并設(shè)置工位開放權(quán)限，只有供應(yīng)商獲得該區(qū)域?qū)?yīng)工位權(quán)限后，才能卸載食品原材料。為便于食品揀取規(guī)劃化、流程化管理，企業(yè)為供應(yīng)商提供不同大小的食品箱，供應(yīng)商根據(jù)食品原材料特性放置于不同型號(hào)的食品箱內(nèi)，并將食品原材料信息錄入對(duì)應(yīng)食品箱電子標(biāo)簽中，供應(yīng)商到達(dá)存放倉庫后，按照權(quán)限，依次填滿每個(gè)存放區(qū)域內(nèi)對(duì)應(yīng)工位。一個(gè)食品揀取移動(dòng)機(jī)器人對(duì)應(yīng)一個(gè)或多個(gè)食品存放區(qū)域，當(dāng)食品存放區(qū)域所有工位滿載時(shí)，移動(dòng)機(jī)器人按照路徑規(guī)劃方案，依次揀取所有工位上的食品。每個(gè)存放區(qū)域食品清空后，對(duì)供應(yīng)商開放權(quán)限，進(jìn)入下一輪食品揀取流程，圖1為食品揀取機(jī)器人工作示意圖。

圖1 食品揀取機(jī)器人工作示意圖Figure 1 The working diagram of food picking robot

1.2 路徑規(guī)劃模型構(gòu)建

以某個(gè)食品原材料存放區(qū)域滿載為例，建立單個(gè)工位機(jī)器人最優(yōu)揀取位置和多工位機(jī)器人移動(dòng)最短距離雙層路徑規(guī)劃模型。

圖2 食品揀取機(jī)器人路徑規(guī)劃示意圖Figure 2 Path planning diagram of food picking robot

(1)

式中：

Li——第i個(gè)工位機(jī)械臂從抓取到放置所用總路徑；

d(a,b)——兩點(diǎn)間的距離。

(2)

從式(2)可知，不同的作業(yè)點(diǎn)位，其作業(yè)總路徑也是不同的，采用雞群優(yōu)化算法對(duì)第i個(gè)工位的最佳作業(yè)點(diǎn)位Pbest,i(xbest,i,ybest,i)進(jìn)行求解，進(jìn)而得到第i個(gè)工位的

最佳抓取路徑Li,best：

(3)

1.2.2 多工位機(jī)器人移動(dòng)最短距離模型 機(jī)器人需要游歷遍N個(gè)工位，移動(dòng)過程中盡可能選擇最短移動(dòng)距離的同時(shí)也需要規(guī)避障礙物，為此將機(jī)器人在工位間的路徑規(guī)劃劃分為兩個(gè)階段，第一階段，將機(jī)器人游歷{(xbest,1,ybest,1),…,(xbest,N,ybest,N)}過程等效為經(jīng)典旅行商問題(Traveling Salesman Problem，TSP)[9-10]，采用雞群優(yōu)化算法對(duì)該問題進(jìn)行求解，得到機(jī)器人訪問工位序列{(x1,y1),…,(xN,yN)}；第二階段，對(duì)兩工位間機(jī)器人移動(dòng)路徑進(jìn)行規(guī)劃，建立如圖2(b)所示的路徑規(guī)劃模型：在點(diǎn)Pi=(xi,yi)和點(diǎn)Pi+1=(xi+1,yi+1)(i=1,…,N-1)間找到M個(gè)節(jié)點(diǎn)(k=1,…,M)L，依次連接Pi、X1、…、XM、Pi+1，得到機(jī)器人移動(dòng)路徑Z(Pi→Pi+1)：

Z(Pi→Pi+1)=Z(Pi,X1,…,XM,Pi+1)。

(4)

r=d(Pi,Pi+1)/(M+1)。

(5)

在極坐標(biāo)空間內(nèi)依次選取M個(gè)點(diǎn)Xi(ρi,θi)，其中ρ=ir(i=1,…,M)、θ隨機(jī)設(shè)定，這M個(gè)點(diǎn)位即為機(jī)器人移動(dòng)路徑Z(Pi→Pi+1)內(nèi)的節(jié)點(diǎn)，Xi(ρ,θ)到二維平面坐標(biāo)系Xi(xi,yi)轉(zhuǎn)換公式為：

(6)

式中：

聯(lián)立式(4)～式(6)，可以得到Z(Pi→Pi+1)的長度：

(7)

只需要得到(θ1,…,θM)就可以得到LPi,Pi+1，因此，兩點(diǎn)間機(jī)器人路徑規(guī)劃問題轉(zhuǎn)化為求解最短路徑問題：

(8)

s.t.X1,…,XM?W1,…,WM。

(9)

式(9)為式(8)的約束條件，即Z(Pi→Pi+1)上的所有節(jié)點(diǎn)不在任一食品放置區(qū)域內(nèi)，保障了機(jī)器人能夠避開障礙物。采用雞群優(yōu)化算法對(duì)式(8)優(yōu)化問題進(jìn)行求解，從而得到兩工位間機(jī)器人最佳移動(dòng)距離。

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

2.1 改進(jìn)雞群優(yōu)化算法

雞群優(yōu)化算法(CSO)隸屬于智能啟發(fā)式計(jì)算技術(shù)范疇，其在解空間內(nèi)初始隨機(jī)部署一定規(guī)模的種群，種群內(nèi)個(gè)體相互間通過協(xié)同信息交流完成迭代更新，個(gè)體在解空間內(nèi)分布越廣泛、種群多樣性越高，算法找到全局最優(yōu)解的可能性就越大。為此，提出改進(jìn)雞群優(yōu)化算法(ICSO)：采用密度峰值聚類算法(density peak clustering，DPC)對(duì)種群進(jìn)行聚類分析，在此基礎(chǔ)上將種群劃分為不同子種群，并設(shè)計(jì)新的個(gè)體更新進(jìn)化機(jī)制(CSO基本原理不在此贅述)。

2.1.1 DPC種群進(jìn)行聚類分析 DPC是2014年才被提出的一種新的聚類算法，研究[11-14]表明，該算法對(duì)任意數(shù)據(jù)都有良好的適用性。對(duì)于包含Q個(gè)個(gè)體的CSO種群，采用DPC對(duì)CSO種群{X1,…,XQ}進(jìn)行分析，對(duì)于個(gè)體Xi，如果其局部密度ρi高于周圍其他個(gè)體，且具有較大最近點(diǎn)距離δi，DPC則認(rèn)為該個(gè)體為潛在的聚類中心：

(10)

式中：

dij——Xi與Xj的距離；

dc——人為設(shè)定的截?cái)嗑嚯x。

(11)

式中：

Xbest——種群目標(biāo)函數(shù)值最優(yōu)個(gè)體。

(12)

式中：

Xmin、Xmax——個(gè)體空間極限。

(13)

式中：

從式(11)～式(13)可以看出，公雞個(gè)體反向進(jìn)化，增加了算法跳出局部極值的概率；小雞直接優(yōu)秀個(gè)體進(jìn)行學(xué)習(xí)，加速了算法收斂速度；母雞選擇與自己空間差異性較大的個(gè)體進(jìn)行信息交互，擴(kuò)展了種群搜索空間，使得算法收斂精度更高。

2.2 路徑規(guī)劃實(shí)現(xiàn)

2.2.1 單工位最優(yōu)揀取位置模型求解 每個(gè)工位上、下、左、右4個(gè)區(qū)域?yàn)闄C(jī)器人潛在的作業(yè)區(qū)域，為提高算法運(yùn)行速度，可以采用信息傳遞接口(Massage Passing Interface，MPI)并行框架[15-17]，每個(gè)線程執(zhí)行一個(gè)方位的最佳位置求解進(jìn)程，最終獲得單工位最優(yōu)揀取位置(xbest,i,ybest,i)。對(duì)于單工位最優(yōu)揀取位置模型求解問題，定義種群個(gè)體編碼為X=(xr,i,yr,i)，目標(biāo)函數(shù)f(X)定義為：

(14)

ICSO循環(huán)迭代進(jìn)化，最終得到每個(gè)工位的最優(yōu)揀取位置Pbest,i(xbest,i,ybest,i)和最佳抓取路徑Li,best。圖3(a)給出了ICSO優(yōu)化單工位最優(yōu)揀取位置流程圖。

2.2.2 多工位機(jī)器人訪問順序模型求解 對(duì)于多工位機(jī)器人訪問順序優(yōu)化問題，定義種群個(gè)體編碼為X=(x1,…,xN)，其中xi=1 or 2…orN、xi≠xj(i,j=1,…,N)，若xi=K(K=1,…,N)，則表示機(jī)器人第i個(gè)順位訪問第K個(gè)工位。目標(biāo)函數(shù)f(X)定義為：

(15)

從個(gè)體編碼可以看出，多工位機(jī)器人訪問順序優(yōu)化問題為離散優(yōu)化問題，若仍采用連續(xù)進(jìn)化方式，會(huì)產(chǎn)生大量不符合要求的解。為此，對(duì)于個(gè)體Xi，若選取Xj為學(xué)習(xí)進(jìn)化對(duì)象，則個(gè)體進(jìn)化機(jī)制定義為，隨機(jī)選取Xj內(nèi)β個(gè)編碼位替代Xi內(nèi)對(duì)應(yīng)編碼位，并將Xj內(nèi)剩余編碼位內(nèi)編碼隨機(jī)相互調(diào)換后，替代Xi內(nèi)相應(yīng)編碼位，該過程描述為：

Xi,new=β(Xj→Xi)

(16)

式中：

βmax、βmin——最大值和最小值；

Tmax——最大迭代次數(shù)；

λ——比例系數(shù)且0≤λ≤1。

(17)

(18)

(19)

ICSO循環(huán)迭代進(jìn)化，最終得到最優(yōu)工位訪問順序Xbest=(x1,best,…,xN,best)，圖3(b)給出了ICSO優(yōu)化工位訪問順序流程圖。

2.2.3 工位間路徑規(guī)劃模型求解 對(duì)于工位間路徑規(guī)劃優(yōu)化問題，定義種群個(gè)體編碼為X=(θ1,…,θM)，目標(biāo)函數(shù)f(X)定義為：

(20)

式中：

d(pi,pM)——式(4)～式(7)列舉的移動(dòng)路徑內(nèi)節(jié)點(diǎn)。

ICSO循環(huán)迭代進(jìn)化，最終得到工位間最優(yōu)路徑{Lx1,best,x2,best,…,LxN-1,best,xN,best,LxN,best,x1,best}，圖3(c)給出了ICSO優(yōu)化工位間路徑規(guī)劃流程圖。

圖3 食品揀取機(jī)器人路徑規(guī)劃實(shí)現(xiàn)流程圖Figure 3 Implementation flow chart of path planning of food picking robot

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

3.1 驗(yàn)證試驗(yàn)

以某食品加工生產(chǎn)企業(yè)為例，每個(gè)存放區(qū)域?yàn)?0 m×80 m正方形區(qū)域，某個(gè)存放區(qū)域設(shè)定6個(gè)工位，每個(gè)工位邊長10 m，設(shè)定食品箱規(guī)格為1.2 m×0.8 m、0.9 m×0.6 m、0.5 m×0.5 m 3種類型，供應(yīng)商根據(jù)原材料特性，選取食品箱類型，并裝載到指定工位。該存放區(qū)域在坐標(biāo)(28,40)、(50,40)、(25,23)處有3個(gè)半徑為3 m的圓形立柱，存放區(qū)域工位空間信息及ICSO參數(shù)設(shè)置如表1所示。

表1 工位空間信息及ICSO參數(shù)設(shè)置Table 1 Station space information and ICSO parameter setting

采用ICSO算法對(duì)食品揀取機(jī)器人路徑規(guī)劃進(jìn)行求解，圖4給出了ICSO優(yōu)化單點(diǎn)位揀取最優(yōu)位置(以第1個(gè)工位為例)、工位訪問順序和兩工位間路徑規(guī)劃(以第1工位到第2工位間移動(dòng)路徑為例)函數(shù)收斂曲線，圖5給出了食品揀取機(jī)器人路徑規(guī)劃結(jié)果，表2給出了路徑規(guī)劃具體參數(shù)結(jié)果。

圖4 ICSO函數(shù)收斂曲線Figure 4 ICSO function convergence curve

圖5 ICSO優(yōu)化食品揀取機(jī)器人路徑規(guī)劃結(jié)果Figure 5 ICSO optimized path planning results offood picking robot

從仿真結(jié)果可以看出，研究提出的基于ICSO的雙層路徑規(guī)劃方案能夠找出每個(gè)工位最佳揀取位置，得到的移動(dòng)路徑最短，而且能夠避開障礙物。此外，從表2可以看出，每個(gè)工位機(jī)器人移動(dòng)機(jī)械臂總移動(dòng)距離達(dá)到了150 m 以上，接近了機(jī)器人總的移動(dòng)距離，可見，對(duì)每個(gè)工位抓取距離進(jìn)行優(yōu)化，能夠提高機(jī)器人食品揀取效率。

表2 路徑規(guī)劃具體參數(shù)結(jié)果?Table 2 Specific parameter results of path planning

3.2 對(duì)比試驗(yàn)

為進(jìn)一步驗(yàn)證所提方案有效性，設(shè)定存放區(qū)域?yàn)?00 m×300 m正方形區(qū)域，并將區(qū)域均等劃分為邊長20 m×20 m的225個(gè)網(wǎng)格，隨機(jī)選取每行內(nèi)2個(gè)網(wǎng)格為工位，共計(jì)30個(gè)工位，工位區(qū)域邊長仍為10 m×10 m。采用基本CSO算法、布谷鳥算法(Cuckoo Search Algorithm，CSA)[18]、細(xì)菌覓食算法(Bacterial foraging optimization algorithm，BFOA)[19]以及文獻(xiàn)[20]提出的路徑優(yōu)化方案進(jìn)行對(duì)比試驗(yàn)，每種算法獨(dú)立運(yùn)行30次，結(jié)果取均值。圖6給出了4種算法函數(shù)收斂曲線，表3給出了路徑規(guī)劃具體參數(shù)對(duì)比結(jié)果。

從圖6可以看出，對(duì)于單工位最優(yōu)揀取位置、多工位訪問順序以及兩工位間路徑規(guī)劃問題，ICSO無論是收斂精度還是收斂速度都要優(yōu)于其他3種算法，這是因?yàn)椋捎肈PC對(duì)種群進(jìn)行聚類分析，個(gè)體在選取學(xué)習(xí)進(jìn)化對(duì)象時(shí)更有針對(duì)性和合理性，而且為公雞、母雞、小雞分別設(shè)計(jì)不同的進(jìn)化公式，兼顧了收斂速度和收斂精度，使得ICSO具有更好的全局尋優(yōu)能力。從表3可以看出，無論是在移動(dòng)距離還是在周期運(yùn)行時(shí)間上，基于ICSO的路徑規(guī)劃方案優(yōu)于其他4種方案，總路徑縮短了7.3%～16.7%，運(yùn)行時(shí)間減少了8.14%～39.33%；文獻(xiàn)[20]所提方案性能次之，基于CSO的方案表現(xiàn)最差，表明提出的基于改進(jìn)雞群優(yōu)化算法的食品揀取機(jī)器人路徑規(guī)劃方案能夠給出合理的食品機(jī)器人揀取路徑規(guī)劃方案，提高了食品分揀機(jī)器人路徑規(guī)劃效率，具有較好的實(shí)際應(yīng)用價(jià)值。

圖6 4種算法優(yōu)化食品揀取機(jī)器人路徑規(guī)劃結(jié)果Figure 6 Path planning results of food picking robot optimized by four algorithms

表3 不同方案路徑規(guī)劃參數(shù)結(jié)果Table 3 Path planning parameter results of different schemes

4 結(jié)束語

對(duì)食品揀取機(jī)器人路徑優(yōu)化問題進(jìn)行研究，提出了基于改進(jìn)雞群優(yōu)化算法的路徑規(guī)劃方案，通過建立雙層路徑規(guī)劃模型，利用密度峰值聚類算法對(duì)種群聚類分析，重新定義個(gè)體編碼方式和更新機(jī)制，提升了改進(jìn)雞群優(yōu)化算法的全局優(yōu)化能力，最后采用改進(jìn)雞群優(yōu)化算法對(duì)雙層模型進(jìn)行求解，得到的路徑規(guī)劃長度更短，運(yùn)行效率更高。下一步將結(jié)合物聯(lián)網(wǎng)技術(shù)，動(dòng)態(tài)實(shí)現(xiàn)機(jī)器人食品揀取路徑規(guī)劃研究。