劉 劍 胡祝兵 趙學超

(1. 河北石油職業(yè)技術(shù)大學，河北 承德 067000；2. 河北農(nóng)業(yè)大學，河北 保定 071001)

食品制造業(yè)作為食品工業(yè)的重要基礎，改進和創(chuàng)新生產(chǎn)流程能夠降低材料消耗、提高效益，為企業(yè)帶來巨大競爭優(yōu)勢[1]，為此，越來越多的食品制造加工企業(yè)將機器人與標準操作程序相結(jié)合[2]，食品機器人在質(zhì)量檢測、食品揀取、碼垛等領域發(fā)揮著重要作用[3-4]。提高食品原料供應標準化、規(guī)范化程度，是食品企業(yè)亟需解決的重大課題之一[5]，傳統(tǒng)人工原料分揀方式效率低、容易出錯、成本很高，因此研究基于機器人的食品揀取方法具有廣闊的應用前景[6-7]。

食品揀取機器人路徑規(guī)劃研究是當前人工智能技術(shù)研究的熱點之一，涉及多學科、多領域。余曉蘭等[8]對食品分揀機器人視覺伺服控制進行研究，利用改進的BP神經(jīng)網(wǎng)絡對系統(tǒng)的靈活性進行優(yōu)化，結(jié)果表明優(yōu)化后的位置精準度更高；趙相博等[9]對食品機器人正逆運動學理論進行研究，得到了搬運路徑角位置、速度、加速度曲線；劉芙等[10]通過建立兩層路徑規(guī)劃模型，采用改進的雞群算法對模型求解，縮短了食品機器人總移動距離；張好劍等[11]以優(yōu)化食品揀取順序為目標，提出基于遺傳算法的分揀路徑優(yōu)化方法。但是這些研究或重點聚焦單個機器人運動軌跡，或只研究單點位或少數(shù)點位間機器人揀取路徑規(guī)劃方法，然而，大規(guī)模網(wǎng)格化食品原材料倉儲已成為發(fā)展趨勢，如何高效實現(xiàn)多機器人協(xié)同食品揀取路徑規(guī)劃具有重要研究意義。

研究以按食品加工配方比例揀取多貨位原材料問題為研究背景，擬提出一種基于離散多目標布谷鳥算法的食品揀取機器人協(xié)同路徑規(guī)劃方法，通過建立多目標食品揀取機器人協(xié)同路徑規(guī)劃模型，設計改進的離散多目標布谷鳥算法(discrete multi-objective cuckoo algorithm，DMCA)和采用改進A*算法對兩兩貨位間最佳移動路徑求解，以獲取多食品揀取機器人協(xié)同最佳路徑規(guī)劃。

1 多目標協(xié)同路徑規(guī)劃模型

(1)

1.1 周期揀取原材料總重量

(2)

此時，一個周期n個機器人協(xié)同揀取的原材料總重量mtime為：

(3)

1.2 周期總移動距離

設定每個機器人從同一位置A出發(fā)，訪問完貨位后再返回A點，第i個(i∈[1,…,N])機器人移動路徑li為：

(4)

式中：

此時，一個周期n個機器人總移動路徑Ltime為：

(5)

1.3 周期總能耗

(6)

圖1 能耗與訪問貨位、移動路徑間的關(guān)系示意圖

Figure 1 Schematic diagram of the relationship between energy consumption and access location and moving path

(7)

Θi反映了機器人裝載重量與里程關(guān)系，也反映了能耗大小，即定義第i個(i∈[1,…,N])機器人移動能耗Ei=β×Θi，其中，β為比例系數(shù)，β與機器人自身物理性能相關(guān)(β采取試驗測定的方式確定取值)。此時，一個周期n個機器人協(xié)同揀取的原材料總能耗Etime為：

(8)

1.4 多目標協(xié)同路徑規(guī)劃模型建立

建立以周期揀取原材料總重量mtime、周期總移動距離Ltime、周期總能耗Etime為評價指標的多目標食品揀取機器人協(xié)同路徑規(guī)劃模型，目標優(yōu)化函數(shù)f(G)為：

(9)

從式(2)～式(8)可以看出，多機器人協(xié)同任務分配方案G(O1,O2,…,On)，即n個機器人訪問貨位路徑規(guī)劃決定了mtime、Ltime和Etime大小。為此，設計離散多目標布谷鳥算法(discrete multi-objective cuckoo algorithm，DMCA)和改進的A*算法，并對多目標協(xié)同路徑規(guī)劃模型進行求解，以獲取最佳規(guī)劃方案。

2 DMCA求解多目標協(xié)同路徑規(guī)劃模型

2.1 DMCA實現(xiàn)

布谷鳥算法(cuckoo algorithm，CA)作為一種新型啟發(fā)式計算技術(shù)，被廣泛應用于多維函數(shù)求解、工程優(yōu)化等領域[13-17]。研究結(jié)合多目標協(xié)同路徑規(guī)劃模型特點，設計離散多目標布谷鳥算法(DMCA)，定義布谷鳥個體編碼Xi為：

(10)

式中：

Gi——第i個路徑規(guī)劃方案；

由于Xi的編碼位是離散變化的，為此，設計突變、同類進化、異類進化3種離散編碼更新機制。

2.1.1 Pareto最優(yōu)解 設定布谷鳥種群規(guī)模為Q，對于個體Xi和Xj，若滿足：

f1(Xi)≤f1(Xj)∧f2(Xi)≤f2(Xj)∧f3(Xi)≤f3(Xj)。

(11)

則認為Xi支配Xj，用Xi?Xj描述。若個體Xi滿足：

(12)

則Xi為Pareto最優(yōu)解X*，由Pareto最優(yōu)解組成的集合為Pareto最優(yōu)解集R*。DMCA每次進化都會產(chǎn)生一個X*(t)，若X*(t)不支配R*中任意個體或不受R*中任意個體支配，則將X*(t)加入R*中。顯然，R*的規(guī)模是不斷擴大的，為控制R*規(guī)模，定義閥值?，當R*規(guī)模超過?時，依次剔除加權(quán)目標函數(shù)F最差的個體，直到滿足?控制要求。

(13)

式中：

ω1、ω2、ω3——加權(quán)系數(shù)。

圖2 突變操作示意圖Figure 2 Schematic diagram of sudden change operation

圖3 同類進化更新操作示意圖Figure 3 Schematic diagram of similar evolution update operation

2.1.4 異類進化更新 對種群內(nèi)剩余個體Xi執(zhí)行異類進化更新操作，即隨機選取個體Xj(Xj?*,Xj≠

圖4 異類進化更新操作示意圖Figure 4 Schematic diagram of heterogeneous evolution update operation

2.2 改進A*算法求解兩兩貨位間路徑

A*算法作為一種啟發(fā)式搜索技術(shù)，利用代價函數(shù)f(V)對當前搜索區(qū)域內(nèi)的節(jié)點進行篩選，以確定下一步路徑節(jié)點，f(V)計算公式為：

f(V)=h(V)+g(V)，

(14)

式中：

V——可擴展節(jié)點；

h(V)——起始節(jié)點到V的實際代價；

g(V)——V到目標點的估計代價。

由于A*算法以當前節(jié)點周圍4個方向的點為潛在節(jié)點，每次迭代過程中都需要對4個節(jié)點進行代價計算，計算復雜度為O(4I)(I為路徑節(jié)點數(shù))，計算復雜度較高。為此，對A*算法進行改進，以得到機器人兩兩貨位間最佳移動路徑。以貨位C、D為例，機器人在網(wǎng)格邊緣進行折線運動，選取貨位C所在網(wǎng)格某一頂點為起始點Cstar，Ci為當前父節(jié)點(取C0=Cstar)，Ci周圍網(wǎng)格頂點為搜索區(qū)域可擴展節(jié)點Ci,1、Ci,2、Ci,3、Ci,4，代價函數(shù)F′(Ci,j)計算公式為：

F′(Ci,j)=d(Cstar,Ci)+d(Ci,Ci,j)+F′(Ci,j)=d(Cstar,Ci)+θ(Ci,j,D)，

(15)

式中：

Ci,j——Ci的可擴展節(jié)點，j=1,2,3,4；

d(Cstar,Ci)——點Cstar到點Ci的實際移動距離，m；

θ(Ci,j,D)——點Ci,j到目標點的估計移動距離，m。

為了加快可擴展節(jié)點搜索速度，定義擴展節(jié)點判定參數(shù)Δ(Ci,j)：

(16)

若Δ(Ci,j)>90°，則認為Ci,j為不可擴展節(jié)點。圖5(a) 給出了改進A*算法實現(xiàn)流程示意圖。

2.3 多目標協(xié)同路徑規(guī)劃模型實現(xiàn)

采用DMCA算法對多目標協(xié)同路徑規(guī)劃函數(shù)f(G)進行求解，每個布谷鳥個體代表一種協(xié)同規(guī)劃方案，種群個體分別執(zhí)行突變、同類進化和異類進化操作，通過迭代更新，最終得到Pareto最優(yōu)解集R*，決策者按照偏好選取R*內(nèi)1個或多個解為最終的協(xié)同規(guī)劃方案，圖5(b)給出了多目標協(xié)同路徑規(guī)劃模型求解流程示意圖。

圖5 改進A*算法與多目標協(xié)同路徑規(guī)劃模型實現(xiàn)流程圖Figure 5 Implementation flow chart of improved A* algorithm and multi-objective collaborative path planning model

3 仿真試驗

3.1 實例仿真

設某企業(yè)原材料倉庫為200 m×200 m的方形區(qū)域，均勻劃分為400個網(wǎng)格，網(wǎng)格邊長為10 m。某客戶訂單需11種原材料，原材料配方比例、機器人數(shù)量、機器人滿載量、原材料所在貨位等信息見表1。機器人從點位(100,200)出發(fā)，協(xié)同完成原材料揀取任務，采用DMCA算法對協(xié)同路徑規(guī)劃模型進行求解，DMCA算法參數(shù)設置：算法種群規(guī)模Q=300、算法最大迭代次數(shù)Tmax=400、λ=2、τ=2、ω1=0.25、ω2=0.4、ω3=0.35。圖6給出了一個揀取周期Pareto最優(yōu)解集(?=11)。

表1 原材料倉儲信息Table 1 Storage information of raw materials

從圖6可以看出，DMCA算法得到的Pareto最優(yōu)解集分布相對均勻，能夠為決策者提供較好的備選規(guī)劃方案。

圖6 DMCA算法Pareto最優(yōu)解集Figure 6 Pareto optimal solution set of DMCA algorithm

3.2 決策路徑規(guī)劃結(jié)果分析

采用TOPSIS評價法[18]和模糊決策方法[19]從Pareto最優(yōu)解集中選取路徑規(guī)劃方案1，表2給出了規(guī)劃方案1、極端解1(移動距離最短)、極端解2(揀取重量最大)、極端解3(距離重量乘積最小)4種決策路徑規(guī)劃方案結(jié)果，圖7給出了極端解2下的機器人路徑規(guī)劃圖，表3 給出了不同規(guī)劃方案下采用改進A*算法和A*算法的節(jié)點間移動距離、算法運算時間對比結(jié)果。

從表2可以看出，DMCA算法給出了移動距離最短、揀取原材料重量最大和距離重量乘積最小3種極端解方案和1種根據(jù)評價法得到的規(guī)劃方案，每種方案代表了不同決策偏好，極端解1方案側(cè)重于降低總移動距離，總移動距離最小可以縮短到1 200m；極端解2方案側(cè)重提高材料重量，最大揀取重量可以達到550kg；極端解3方案側(cè)重降低移動能耗，距離重量乘積最小可以達到68 684m·kg；方案1中的3種評價指標更加均衡，揀取重量達到了400kg、總移動距離為1 310m、距離重量乘積為108 290m·kg。

表2 不同方案路徑規(guī)劃結(jié)果Table 2 Route planning results of different planning schemes

從圖7可以看出，對于極端解2方案，3個機器人移動路徑相對平滑，路徑規(guī)劃結(jié)果較為合理。

圖7 極端解2下的機器人路徑規(guī)劃圖Figure 7 Robot path planning diagram under extreme solution 2

從表3可以看出，對于4種路徑規(guī)劃方案，在移動距離上，采用改進A*算法得到的路徑移動距離要小于采用A*算法得到的路徑移動距離，例如，對于“機器人1”，改進A*算法下移動距離為480，660，370，360m，而A*算法下對應移動距離則為510，680，400，380m；在算法運算時間上，由于改進A*算法引入了擴展節(jié)點判定參數(shù)，縮小了搜索范圍，很大程度地降低了算法運算復雜度，使得改進A*算法運算時間明顯小于A*算法。

表3 不同規(guī)劃方案下采用改進A*算法和A*算法的節(jié)點間路徑規(guī)劃對比Table 3 Comparison of inter node path planning using improved A* algorithm and A* algorithm under different planning schemes

3.3 對比試驗

為進一步對比分析DMCA算法性能，分別采用文獻[20]提出的多目標優(yōu)化算法和文獻[21]提出的改進多目標粒子群算法進行對比試驗，圖8給出了揀取重量與能耗(移動距離重量乘積)曲線圖，圖9給出了移動距離與能耗(移動距離重量乘積)曲線圖，表4給出了極端解情況下最小總移動距離Ltime,min、最大揀取重量mtime,min、最小距離重量乘積Etime,min和算法運算時間t對比結(jié)果。

從圖8可以看出，在同等揀取原材料重量下，DMCA算法得到的距離重量乘積要小于其他兩種算法，表明當揀取原材料揀取重量相同時，DMCA算法規(guī)劃路徑的能耗更低。從圖9可以看出，同等移動距離下，DMCA算法得到的距離重量乘積同樣優(yōu)于其他兩種算法，表明DMCA算法規(guī)劃路徑能夠以更低的能耗移動更長的距離。從表4可以看出，DMCA算法得到的移動距離、能耗、揀取重量優(yōu)于其他兩種算法，總移動距離縮短了約6.3%，總能耗降低了約7.5%，揀取總重量提高了約12.9%，運行時間縮短了約33.5%。綜上仿真試驗結(jié)果表明，通過設計離散多目標布谷鳥算法編碼方式和更新進化方式，提升了算法多目標問題優(yōu)化能力；采用DMCA算法對協(xié)同路徑規(guī)劃模型進行求解，得到的路徑規(guī)劃方案有效平衡了總移動距離、總能耗和揀取原材料總重量的關(guān)系，能夠更好地為企業(yè)提供決策依據(jù)。

圖8 揀取重量與距離重量乘積對比圖Figure 8 Comparison of picking weight and distance weight product

圖9 移動距離與距離重量乘積對比圖Figure 9 Comparison of moving distance and distance weight product

表4 不同算法結(jié)果對比Table 4 Comparison results of different schemes

4 結(jié)論

對按食品加工配方比例揀取多貨位原材料問題進行研究，提出了基于離散多目標布谷鳥算法的食品揀取機器人協(xié)同路徑規(guī)劃方法，建立協(xié)同路徑規(guī)劃模型，通過引入改進的多目標離散多目標布谷鳥算法和改進A*算法對模型進行求解，得到的Pareto最優(yōu)解分布更加均勻，并且在同等揀取原材料重量、同等移動距離條件下，得到的路徑規(guī)劃方案能耗更低，更具決策優(yōu)勢，具有一定的應用推廣價值。下一步，將重點研究在線動態(tài)協(xié)同路徑規(guī)劃方法。