基于改進雞群優化算法的食品揀取機器人路徑規劃

劉 芙

陳宏明2

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

隨著機械工業技術的快速發展，機器人在食品自動化分揀領域得到了廣泛應用[1]，有效改變了傳統人工分揀效率低、強度大、易損耗的缺陷[2]。運用移動機器人對存放在不同點位上的食品原材料進行高效揀取，是食品企業節約成本、提高效益的重要研究方向[3]。

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

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

1 食品揀取機器人路徑規劃模型構建

1.1 食品揀取機器人工作流程

以某大型食品加工企業為例，存在多個食品原料供應商，該企業根據產能、移動機器人裝載量等因素，將食品原料存放倉庫劃分為多個大小相等的區域。在每個存放區域內，為供應商指定食品卸載點工位，并設置工位開放權限，只有供應商獲得該區域對應工位權限后，才能卸載食品原材料。為便于食品揀取規劃化、流程化管理，企業為供應商提供不同大小的食品箱，供應商根據食品原材料特性放置于不同型號的食品箱內，并將食品原材料信息錄入對應食品箱電子標簽中，供應商到達存放倉庫后，按照權限，依次填滿每個存放區域內對應工位。一個食品揀取移動機器人對應一個或多個食品存放區域，當食品存放區域所有工位滿載時，移動機器人按照路徑規劃方案，依次揀取所有工位上的食品。每個存放區域食品清空后，對供應商開放權限，進入下一輪食品揀取流程，圖1為食品揀取機器人工作示意圖。

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

1.2 路徑規劃模型構建

以某個食品原材料存放區域滿載為例，建立單個工位機器人最優揀取位置和多工位機器人移動最短距離雙層路徑規劃模型。

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

(1)

式中：

Li——第i個工位機械臂從抓取到放置所用總路徑；

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

(2)

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

最佳抓取路徑Li,best：

(3)

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

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

(4)

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

(5)

在極坐標空間內依次選取M個點Xi(ρi,θi)，其中ρ=ir(i=1,…,M)、θ隨機設定，這M個點位即為機器人移動路徑Z(Pi→Pi+1)內的節點，Xi(ρ,θ)到二維平面坐標系Xi(xi,yi)轉換公式為：

(6)

式中：

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

(7)

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

(8)

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

(9)

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

2 路徑規劃模型求解

2.1 改進雞群優化算法

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

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

(10)

式中：

dij——Xi與Xj的距離；

dc——人為設定的截斷距離。

(11)

式中：

Xbest——種群目標函數值最優個體。

(12)

式中：

Xmin、Xmax——個體空間極限。

(13)

式中：

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

2.2 路徑規劃實現

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

(14)

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

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

(15)

從個體編碼可以看出，多工位機器人訪問順序優化問題為離散優化問題，若仍采用連續進化方式，會產生大量不符合要求的解。為此，對于個體Xi，若選取Xj為學習進化對象，則個體進化機制定義為，隨機選取Xj內β個編碼位替代Xi內對應編碼位，并將Xj內剩余編碼位內編碼隨機相互調換后，替代Xi內相應編碼位，該過程描述為：

Xi,new=β(Xj→Xi)

(16)

式中：

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

Tmax——最大迭代次數；

λ——比例系數且0≤λ≤1。

(17)

(18)

(19)

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

2.2.3 工位間路徑規劃模型求解 對于工位間路徑規劃優化問題，定義種群個體編碼為X=(θ1,…,θM)，目標函數f(X)定義為：

(20)

式中：

d(pi,pM)——式(4)～式(7)列舉的移動路徑內節點。

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

圖3 食品揀取機器人路徑規劃實現流程圖Figure 3 Implementation flow chart of path planning of food picking robot

3 仿真試驗與結果分析

3.1 驗證試驗

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

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

采用ICSO算法對食品揀取機器人路徑規劃進行求解，圖4給出了ICSO優化單點位揀取最優位置(以第1個工位為例)、工位訪問順序和兩工位間路徑規劃(以第1工位到第2工位間移動路徑為例)函數收斂曲線，圖5給出了食品揀取機器人路徑規劃結果，表2給出了路徑規劃具體參數結果。

圖4 ICSO函數收斂曲線Figure 4 ICSO function convergence curve

圖5 ICSO優化食品揀取機器人路徑規劃結果Figure 5 ICSO optimized path planning results offood picking robot

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

表2 路徑規劃具體參數結果?Table 2 Specific parameter results of path planning

3.2 對比試驗

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

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

圖6 4種算法優化食品揀取機器人路徑規劃結果Figure 6 Path planning results of food picking robot optimized by four algorithms

表3 不同方案路徑規劃參數結果Table 3 Path planning parameter results of different schemes

4 結束語

對食品揀取機器人路徑優化問題進行研究，提出了基于改進雞群優化算法的路徑規劃方案，通過建立雙層路徑規劃模型，利用密度峰值聚類算法對種群聚類分析，重新定義個體編碼方式和更新機制，提升了改進雞群優化算法的全局優化能力，最后采用改進雞群優化算法對雙層模型進行求解，得到的路徑規劃長度更短，運行效率更高。下一步將結合物聯網技術，動態實現機器人食品揀取路徑規劃研究。