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

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

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

0 引言

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

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

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

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

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

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

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

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

圖2 單個(gè)移動(dòng)機(jī)器人分揀作業(yè)流程

單個(gè)移動(dòng)機(jī)器人的分揀流程如下：

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

步驟2：機(jī)器人在交通管理模塊的協(xié)調(diào)下沿由路徑規(guī)劃模塊規(guī)劃的最優(yōu)路徑運(yùn)行，待到達(dá)目的地后，轉(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；若無(wú)，則結(jié)束。

2 仿真模型

2.1 對(duì)象模型

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

(1)柵格點(diǎn)：柵格點(diǎn)為移動(dòng)機(jī)器人在作業(yè)區(qū)域中的臨時(shí)停靠點(diǎn)，為了便于控制和采集數(shù)據(jù)，采用Station對(duì)象表示柵格點(diǎn)。

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

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

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

圖3 仿真模型圖

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

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

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

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

步驟1：對(duì)給定柵格地圖(圖1)所示中的N個(gè)柵格點(diǎn)按順序編碼；

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

(1)

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

(2)

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

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

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

(3)路徑規(guī)劃

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

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

(3)

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

(4)

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

(5)

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

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

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

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

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

規(guī)則1：每個(gè)柵格點(diǎn)至多只允許分配給一臺(tái)移動(dòng)機(jī)器人以避免機(jī)器人間發(fā)生碰撞。

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

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

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

圖6 柵格點(diǎn)動(dòng)態(tài)分配方法流程

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

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

步驟3：等待所有移動(dòng)機(jī)器人通過已分配柵格點(diǎn)，并停留在臨時(shí)停靠柵格點(diǎn)后，返回步驟1，重新對(duì)所有移動(dòng)機(jī)器人進(jìn)行柵格點(diǎn)分配。

3 仿真分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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