基于離散多目標(biāo)布谷鳥算法的食品揀取機(jī)器人協(xié)同路徑規(guī)劃

劉 劍 胡祝兵 趙學(xué)超

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

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

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

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

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

(1)

1.1 周期揀取原材料總重量

(2)

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

(3)

1.2 周期總移動距離

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

(4)

式中：

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

(8)

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

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

(9)

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

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

2.1 DMCA實(shí)現(xiàn)

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

(10)

式中：

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

由于Xi的編碼位是離散變化的，為此，設(shè)計(jì)突變、同類進(jìn)化、異類進(jìn)化3種離散編碼更新機(jī)制。

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

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

(11)

則認(rèn)為Xi支配Xj，用Xi?Xj描述。若個(gè)體Xi滿足：

(12)

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

(13)

式中：

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

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

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

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

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

2.2 改進(jìn)A*算法求解兩兩貨位間路徑

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

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

(14)

式中：

V——可擴(kuò)展節(jié)點(diǎn)；

h(V)——起始節(jié)點(diǎn)到V的實(shí)際代價(jià)；

g(V)——V到目標(biāo)點(diǎn)的估計(jì)代價(jià)。

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

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

(15)

式中：

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

d(Cstar,Ci)——點(diǎn)Cstar到點(diǎn)Ci的實(shí)際移動距離，m；

θ(Ci,j,D)——點(diǎn)Ci,j到目標(biāo)點(diǎn)的估計(jì)移動距離，m。

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

(16)

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

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

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

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

3 仿真試驗(yàn)

3.1 實(shí)例仿真

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

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

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

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

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

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

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

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

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

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

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

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

3.3 對比試驗(yàn)

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

從圖8可以看出，在同等揀取原材料重量下，DMCA算法得到的距離重量乘積要小于其他兩種算法，表明當(dāng)揀取原材料揀取重量相同時(shí)，DMCA算法規(guī)劃路徑的能耗更低。從圖9可以看出，同等移動距離下，DMCA算法得到的距離重量乘積同樣優(yōu)于其他兩種算法，表明DMCA算法規(guī)劃路徑能夠以更低的能耗移動更長的距離。從表4可以看出，DMCA算法得到的移動距離、能耗、揀取重量優(yōu)于其他兩種算法，總移動距離縮短了約6.3%，總能耗降低了約7.5%，揀取總重量提高了約12.9%，運(yùn)行時(shí)間縮短了約33.5%。綜上仿真試驗(yàn)結(jié)果表明，通過設(shè)計(jì)離散多目標(biāo)布谷鳥算法編碼方式和更新進(jìn)化方式，提升了算法多目標(biāo)問題優(yōu)化能力；采用DMCA算法對協(xié)同路徑規(guī)劃模型進(jìn)行求解，得到的路徑規(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é)論

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