基于離散多目標布谷鳥算法的食品揀取機器人協同路徑規劃

劉 劍 胡祝兵 趙學超

(1. 河北石油職業技術大學，河北 承德 067000；2. 河北農業大學，河北 保定 071001)

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

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

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

1 多目標協同路徑規劃模型

(1)

1.1 周期揀取原材料總重量

(2)

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

(3)

1.2 周期總移動距離

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

(4)

式中：

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

(5)

1.3 周期總能耗

(6)

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

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

(7)

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

(8)

1.4 多目標協同路徑規劃模型建立

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

(9)

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

2 DMCA求解多目標協同路徑規劃模型

2.1 DMCA實現

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

(10)

式中：

Gi——第i個路徑規劃方案；

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

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

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

(11)

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

(12)

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

(13)

式中：

ω1、ω2、ω3——加權系數。

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

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

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

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

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

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

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

(14)

式中：

V——可擴展節點；

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

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

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

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

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

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

(16)

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

2.3 多目標協同路徑規劃模型實現

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

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

3 仿真試驗

3.1 實例仿真

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

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

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

圖6 DMCA算法Pareto最優解集Figure 6 Pareto optimal solution set of DMCA algorithm

3.2 決策路徑規劃結果分析

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

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

表2 不同方案路徑規劃結果Table 2 Route planning results of different planning schemes

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

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

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

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

3.3 對比試驗

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

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

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

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

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

4 結論

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