基于Plant Simulation的多機器人協(xié)作分揀系統(tǒng)仿真分析*

秦德金，周臨震，，肖海寧

(1. 江蘇大學(xué)機械工程學(xué)院，江蘇 鎮(zhèn)江 212013；2. 鹽城工學(xué)院機械工程學(xué)院，江蘇 鹽城 224051)

0 引言

隨著機器人技術(shù)的快速發(fā)展, 基于多移動機器人協(xié)作的自動化物料系統(tǒng)在自動化倉儲、港口運輸、制造車間等領(lǐng)域[1]的應(yīng)用愈加廣泛。移動機器人路徑規(guī)劃算法是多移動機器人協(xié)作系統(tǒng)運行的關(guān)鍵，其優(yōu)劣將直接影響移動機器人的效率和智能化水平[2]。目前，已有不少實現(xiàn)移動機器人路徑規(guī)劃的算法，如：遺傳算法[3]、蟻群算法[4]、Dijkstra算法[5]、A*算法[6]等。然而，這些算法多數(shù)是針對單個移動機器人的路徑規(guī)劃算法，一般以最小化移動機器人路徑總路程或行程時間為目標，若將該類方法直接用于多移動機器人時，不僅極易導(dǎo)致多移動機器人路徑分布的不均衡，進而增加局部交通擁堵風(fēng)險[7]。而且多數(shù)未考慮移動機器人間的碰撞及因路徑相向沖突引發(fā)的死鎖現(xiàn)象[8]，最終影響了多移動機器人協(xié)作系統(tǒng)的整體效率和智能化水平。

其次，隨著多機器人系統(tǒng)規(guī)模的日益增大，使得多移動機器人協(xié)作系統(tǒng)的分析難度與日俱增。傳統(tǒng)系統(tǒng)驗證方法一般基于數(shù)學(xué)抽象，通過對實體模型進行簡化，建立抽象的多機器人優(yōu)化數(shù)學(xué)模型[9-10]，但建立過程中的大量簡化，使得所建立的數(shù)學(xué)模型可能與實際系統(tǒng)相距較遠。因此，為了提高準確度，可以建立計算機仿真模型，通過仿真模型，方案設(shè)計人員可以在方案論證階段，對多移動機器人協(xié)作系統(tǒng)的運動過程進行仿真，分析在不同場景下各種算法的可行性，最大限度地節(jié)省人力、物力和時間[11]。

針對上述情況，本文首先以某應(yīng)用于快遞包裹分揀作業(yè)的多移動機器人協(xié)作系統(tǒng)為例，構(gòu)建了多機器人協(xié)作分揀系統(tǒng)仿真模型；然后，為了提高多機器人路徑分布的均衡性，對經(jīng)典Dijkstra算法進行改進, 提出了一種綜合考慮路程、轉(zhuǎn)彎次數(shù)和交通流量的多目標優(yōu)化Dijkstra算法；其次，為了綜合多機器人間的避碰與作業(yè)區(qū)共享需求，設(shè)計了一種基于柵格點動態(tài)分配的交通管理方法；最后，利用構(gòu)建的仿真模型對提出的多目標優(yōu)化Dijkstra算法和分揀系統(tǒng)效率進行了分析。

1 業(yè)務(wù)流程及仿真需求

以某應(yīng)用于快遞包裹分揀作業(yè)的多移動機器人協(xié)作系統(tǒng)為例，其布局如圖1所示。

1. 入庫傳送帶 2.分揀作業(yè)區(qū) 3.移動機器人 4.出庫傳送帶 5.?？繀^(qū)

具體包括：①入庫傳送帶：位于場地四周，用于將需要分揀的包裹送入分揀作業(yè)區(qū)；②分揀作業(yè)區(qū)域：分揀作業(yè)區(qū)采用柵格地圖[11]來描述，柵格地圖一般由一系列等距的導(dǎo)引標線組成，標線的交點稱為柵格點。移動機器人只能沿導(dǎo)引標線行駛，或在柵格點上臨時?？?；③移動機器人：從入庫傳送帶裝載待分揀的包裹，沿調(diào)度系統(tǒng)為其規(guī)劃的路徑行駛，將包裹送至指定出庫傳送帶；④出庫傳送帶：用于將完成分揀的包裹從作業(yè)區(qū)送至各指定區(qū)域，等待物流運輸車送至各地；⑤?？繀^(qū)：用于機器人停靠及充電。

單個移動機器人的分揀作業(yè)流程如圖2所示。

圖2 單個移動機器人分揀作業(yè)流程

單個移動機器人的分揀流程如下：

步驟1：系統(tǒng)開始運行后，機器人等待調(diào)度系統(tǒng)為其分配新的分揀任務(wù)，接收到新的分揀任務(wù)后，轉(zhuǎn)步驟2。

步驟2：機器人在交通管理模塊的協(xié)調(diào)下沿由路徑規(guī)劃模塊規(guī)劃的最優(yōu)路徑運行，待到達目的地后，轉(zhuǎn)步驟3。

步驟3：判斷任務(wù)類型，若是分揀任務(wù)，轉(zhuǎn)步驟4；若為充電任務(wù)，轉(zhuǎn)步驟5。

步驟4：根據(jù)分揀作業(yè)要求完成快遞包裹的裝卸操作，判斷電量是否不足，若電量不足則將?？繀^(qū)設(shè)為目的地，轉(zhuǎn)步驟2。若電量充足則轉(zhuǎn)步驟6。

步驟5：在?？繀^(qū)充電，充電結(jié)束轉(zhuǎn)步驟6。

步驟6：判斷系統(tǒng)中是否有未完成的分揀任務(wù)，若有，則轉(zhuǎn)步驟1；若無，則結(jié)束。

2 仿真模型

2.1 對象模型

在該系統(tǒng)中主要有柵格點、機器人行走路徑、移動機器人等對象。根據(jù)各對象的運行特性在Plant Simulation中選擇的仿真對象介紹如下：

(1)柵格點：柵格點為移動機器人在作業(yè)區(qū)域中的臨時?？奎c，為了便于控制和采集數(shù)據(jù)，采用Station對象表示柵格點。

(2)導(dǎo)引標線：軟件中可以表示導(dǎo)引標線的對象有雙向型和單向型Trcak兩種，由于移動機器人可以沿導(dǎo)引標線雙向行駛，因此本次建模采用雙向Track表示移動機器人的導(dǎo)引標線。

(3)移動機器人：選用Transporter對象表示系統(tǒng)中的移動機器人模型，Transporter是一個主動移動對象，它具備動力，能夠主動移動，并具備一定承載能力。

根據(jù)圖1所示的模型進行布局，最終構(gòu)建的仿真模型如圖3所示。

圖3 仿真模型圖

2.2 路徑規(guī)劃模塊的控制方法

分揀作業(yè)區(qū)由一系列柵格點和連接?xùn)鸥竦穆窂浇M成。Dijkstra算法是求解最短路徑問題的經(jīng)典算法[5]。但經(jīng)典Dijkstra算法以路程最短為目標，無法考慮交通流及轉(zhuǎn)彎等因素對運行時間的影響。針對這一現(xiàn)狀，本文對經(jīng)典Dijkstra算法進行改進，提出一種綜合考慮路程、轉(zhuǎn)彎及交通流量的多目標優(yōu)化路徑規(guī)劃算法，其控制流程如圖4所示，具體介紹如下：

圖4 路徑規(guī)劃模塊流程圖

(1)柵格地圖預(yù)處理

步驟1：對給定柵格地圖(圖1)所示中的N個柵格點按順序編碼；

步驟2：獲取鄰接矩陣A=[aij]N×N，其中aij表示柵格點i到柵格點j的最短距離，其取值如下：

(1)

步驟3：獲取柵格點方位矩陣D=[dij]N×N，其中dij表示柵格點i到柵格點j的方位角，其取值如下：

(2)

(2)數(shù)據(jù)統(tǒng)計

步驟1：統(tǒng)計每個柵格點交通流量，構(gòu)建流量矩陣F=[f(i)]1×N，其中N為圖中柵格點數(shù)。f(i)為第i個柵格點的交通流量，表示移動機器人已規(guī)劃路徑庫中經(jīng)過柵格點i的機器人數(shù)量。

步驟2：根據(jù)路徑庫中每臺移動機器人路徑標識各路徑允許的運行方向，標識方法如下：若路徑{i,j}已在路徑庫中，則設(shè)置1階鄰接矩陣中的元素aij=∞，保證新規(guī)劃的機器人路徑中不會出現(xiàn)路徑{j,i}，避免了倆機器人因路徑相向沖突引發(fā)的死鎖現(xiàn)象。

(3)路徑規(guī)劃

根據(jù)機器人的位置及目標柵格點，采用改進的Dijkstra算法規(guī)劃一條從機器人當(dāng)前位置至目標柵格點的最優(yōu)路徑，具體步驟如下：

步驟1：初始化VS、VD、最優(yōu)路徑矩陣p=[Psi]1×N，和權(quán)值矩陣T=[ti]1×N。集合VS中存放已搜索到與源點(機器人當(dāng)前位置s)最優(yōu)路徑的柵格點；集合VD中存放尚需搜索的柵格點；Psi表示源點s至柵格點i的最優(yōu)路徑；ti表示柵格點i的權(quán)值，計算方法如下：

(3)

步驟3：更新VD中每個柵格點的權(quán)值、最優(yōu)路徑和一階鄰接矩陣，更新方法如下，假定VD中的柵格點為n。其新的權(quán)值tn為：

(4)

其中，θ為轉(zhuǎn)向系數(shù)，計算方法如下：

(5)

其中，dmk為路徑ρsk最后兩個柵格點m與k間的方位角；w為轉(zhuǎn)向時間系數(shù)。

步驟4：搜索VD中擁有最小權(quán)值的柵格點，不妨設(shè)其為柵格點k，將k從VD移入VS，若柵格點k=d，則已搜索到最優(yōu)路徑，進入步驟5，否則，轉(zhuǎn)步驟3。

步驟5：輸出最優(yōu)路徑。

2.3 交通管理模塊的控制方法

可能引發(fā)機器人間碰撞的典型情況如圖5所示。如圖5a所示：兩臺機器人競爭同一柵格點，若將此柵格點同時分配給兩臺移動機器人，必然發(fā)生碰撞；如圖5b所示：一輛移動機器人即將進入已被其他機器人占用的柵格點，若允許其進入，必然發(fā)生碰撞。造成這兩種碰撞現(xiàn)象的根源在于系統(tǒng)將同一柵格點同時分配給了多臺移動機器人。因此，為了實現(xiàn)避碰，必須保證系統(tǒng)中任一柵格點在同一時刻至多只能分配給一臺移動機器人。其次，為了滿足多機器對作業(yè)區(qū)的共享需求，避免某機器人一次分配的柵格點過多，造成系統(tǒng)中大量機器人的長時間等待現(xiàn)象。本文設(shè)計了以下柵格點動態(tài)分配規(guī)則：

規(guī)則1：每個柵格點至多只允許分配給一臺移動機器人以避免機器人間發(fā)生碰撞。

規(guī)則2：每個機器人每輪至多只允許分配Nc個柵格點以滿足多機器人共享作業(yè)區(qū)的需求。

(a) 柵格點競爭沖突 (b)柵格點占據(jù)沖突圖5 引發(fā)機器人間碰撞的兩種典型情況示意圖

所提出的柵格點的動態(tài)分配交通管理方法流程如圖6所示，具體步驟如下：

圖6 柵格點動態(tài)分配方法流程

步驟1：標識所有柵格點及其狀態(tài)：記第i個移動機器人為Ri；NR表示移動移動機器人的總數(shù)；將系統(tǒng)已分配給Ri的柵格點中最靠近終點的柵格點作為Ri的臨時?？奎c，記為FinOcc(Ri)；記從FinOcc(Ri)開始沿著路徑前向第k個柵格點為NextRi(k)。完成以上信息標識后轉(zhuǎn)步驟2。

步驟2：采用本文設(shè)計的柵格點動態(tài)分配規(guī)則逐一為每輛移動機器人分配柵格點，為所有移動機器人分配過柵格點后轉(zhuǎn)步驟3。

步驟3：等待所有移動機器人通過已分配柵格點，并停留在臨時停靠柵格點后，返回步驟1，重新對所有移動機器人進行柵格點分配。

3 仿真分析

利用構(gòu)建的多移動機器人協(xié)作系統(tǒng)仿真模型進行以下仿真分析：①分析路徑規(guī)劃算法在不同優(yōu)化目標組合下的系統(tǒng)性能；②系統(tǒng)最大日分揀任務(wù)量分析；③根據(jù)以上分析結(jié)果，確定系統(tǒng)在給定日分揀任務(wù)量下的最佳移動機器人數(shù)量。

3.1 路徑規(guī)劃算法在不同優(yōu)化目標組合下的系統(tǒng)性能

以系統(tǒng)在各機器人數(shù)下所能實現(xiàn)的單位小時分揀任務(wù)量為評價指標，分析系統(tǒng)在三種優(yōu)化目標組合下的系統(tǒng)性能，三種優(yōu)化目標組合分別為：

(1)路程—僅以路程最短為優(yōu)化目標，該目標為經(jīng)典Dijkstra算法的優(yōu)化目標。

(2)路程+轉(zhuǎn)彎—考慮轉(zhuǎn)彎時間的行程時間最短。

(3)路程+轉(zhuǎn)彎+流量—本文所提出的改進的多目標優(yōu)化路徑規(guī)劃算法。

三種優(yōu)化目標組合在不同移動機器人數(shù)量下的性能表現(xiàn)如圖7所示。當(dāng)機器人數(shù)量少于10臺時，由于機器人密度較低，各機器人間出現(xiàn)路徑?jīng)_突的概率較小，因此三種優(yōu)化目標的單位小時完成任務(wù)數(shù)無明顯差異。隨著機器人數(shù)量的增多，各機器人間發(fā)生路徑?jīng)_突的概率顯著增加，若僅以最小化路程為目標，極易出現(xiàn)多移動機器人的路徑分布的不均衡，進而出現(xiàn)局部交通擁堵，如圖7所示，在該優(yōu)化目標下單位小時完成的任務(wù)數(shù)最少。而本文所提出的多目標優(yōu)化路徑規(guī)劃算法在任何數(shù)量的機器人下均能夠完成最多的分揀任務(wù)，尤其當(dāng)系統(tǒng)內(nèi)機器人數(shù)多于20臺時，其優(yōu)勢更為明顯。這表明本文所提出的多目標優(yōu)化路徑規(guī)劃算法能夠提升多機器人路徑分布的均衡性，從而提升系統(tǒng)分揀效率。

圖7 系統(tǒng)在各機器人數(shù)下所能實現(xiàn)的單位小時分揀任務(wù)數(shù)

3.2 系統(tǒng)最大日分揀任務(wù)量分析

因此，如圖7所示，雖然采用本文所提出的多目標優(yōu)化路徑規(guī)劃算法在機器人數(shù)量在40時，系統(tǒng)所能實現(xiàn)的分揀任務(wù)數(shù)最多，然而，由圖8可知此時單個機器人所能實現(xiàn)的每小時平均任務(wù)數(shù)為51個，少于機器人數(shù)為30時的69個。因此，綜合單個移動機器人的效率，系統(tǒng)最佳的機器人數(shù)量為30臺，此時系統(tǒng)能夠?qū)崿F(xiàn)的最大單位小時分揀任務(wù)數(shù)為2010個。以日工作8小時為例，采用本文所提出的多目標優(yōu)化路徑規(guī)劃算法能夠達到的最大日分揀任務(wù)量約為16 000個。

圖8 單個機器人所能實現(xiàn)的單位小時平均分揀任務(wù)數(shù)

3.3 給定日分揀任務(wù)量下最佳移動機器人數(shù)量分析

如圖8所示，隨著系統(tǒng)中機器人數(shù)量的提升，單個機器人所能實現(xiàn)的單位小時平均分揀任務(wù)數(shù)呈現(xiàn)下降趨勢，尤其當(dāng)系統(tǒng)中的移動機器人數(shù)量超過30時，下降明顯。這一現(xiàn)象表明，隨著機器人數(shù)量的提升，機器人間的路徑?jīng)_突概率上升，增加了交通擁堵風(fēng)險，最終降低了系統(tǒng)分揀效率，因此，系統(tǒng)中的機器人數(shù)量并非越多越好。反之，機器人配置數(shù)量不足又無法滿足系統(tǒng)的分揀能力要求。有必要根據(jù)系統(tǒng)日分揀任務(wù)數(shù)需求，確定最佳的移動機器人數(shù)量，利用構(gòu)建的仿真模型，系統(tǒng)在給定分揀任務(wù)需求下的完工時長如表1所示。

分揀系統(tǒng)維護人員可參照表1，根據(jù)日分揀任務(wù)數(shù)需求，選擇合適的機器人數(shù)量。以日分揀任務(wù)數(shù)12 000為例，當(dāng)投入系統(tǒng)中的機器人數(shù)量為20臺時，需運行8.54 h才能完成分揀任務(wù)，若為25臺，則需7.07 h。因此，以日工作8 h為例，投入的最佳機器人數(shù)量應(yīng)為21～25臺。

表1 給定日分揀任務(wù)量下的完工時長

4 結(jié)束語

本文以某應(yīng)用于快遞包裹分揀作業(yè)的多移動機器人協(xié)作系統(tǒng)為例，構(gòu)建了多機器人協(xié)作分揀系統(tǒng)仿真

模型；為了提高多機器人路徑分布的均衡性，對經(jīng)典Dijkstra算法進行改進，提出了一種綜合考慮路程、轉(zhuǎn)彎次數(shù)和沿途各柵格點交通流量的多目標優(yōu)化Dijkstra算法；并設(shè)計了一種基于柵格點動態(tài)分配的交通管理方法以兼顧多機器人間的避碰及作業(yè)區(qū)共享需求；最后利用構(gòu)建的模型對所提出的多目標優(yōu)化路徑規(guī)劃算法及系統(tǒng)性能進行了分析，分析結(jié)果表明：與經(jīng)典 Dijkstra算法相比，本文所提出的多目標優(yōu)化路徑規(guī)劃算法，能夠顯著提升多機器人路徑分布的均衡性，從而提升多機器人系統(tǒng)的分揀效率。另外，仿真結(jié)果表明隨著機器人數(shù)量的提升，機器人間的路徑?jīng)_突概率上升，增加了交通擁堵風(fēng)險，單個移動機器人單位小時平均分揀任務(wù)數(shù)呈現(xiàn)下降趨勢，因此，有必要根據(jù)系統(tǒng)日分揀任務(wù)數(shù)需求，動態(tài)調(diào)整最佳的移動機器人數(shù)量。