薛頌東 張 宇 趙 靜 潘理虎

（1.太原科技大學(xué) 太原 030024）

（2.廣東機(jī)電職業(yè)技術(shù)學(xué)院 廣州 510515）

1 引言

在由群機(jī)器人執(zhí)行揀貨任務(wù)的智能倉庫中，路徑規(guī)劃關(guān)系揀貨任務(wù)執(zhí)行效率。其控制方法分為集中式和分布式，集中式控制通過中央控制系統(tǒng)處理機(jī)器人之間的協(xié)調(diào)，發(fā)現(xiàn)全局最優(yōu)路徑，但隨著群機(jī)器人系統(tǒng)規(guī)模擴(kuò)大將導(dǎo)致計算復(fù)雜度增加，擴(kuò)展性不好，僅適合小規(guī)模倉庫情形。分布式控制則基于機(jī)器人的實(shí)時信息進(jìn)行路徑規(guī)劃，能較好適應(yīng)機(jī)器人數(shù)量增長和環(huán)境變化。不過，在有限感知和局部交互機(jī)制下，機(jī)器人的最優(yōu)路徑非全局。常用的分布式路徑規(guī)劃算法，主要有D*算法、A*算法、蟻群算法等［1］。其中，D*算法屬于動態(tài)路徑規(guī)劃算法，A*算法和蟻群算法屬于啟發(fā)式算法。Wang C和Wang L［2］針對自動導(dǎo)引車AGV 的路徑規(guī)劃提出了一種改進(jìn)A*算法，用其去除邊緣，解決K 最短路徑問題；提出的另一種基于A*算法的沖突路徑規(guī)劃方法，能有效搜索最短路徑并避免碰撞。高小杰［3］為Kiva系統(tǒng)設(shè)計了機(jī)器人動態(tài)避障規(guī)則，提出了帶優(yōu)先級列表的改進(jìn)A*算法。針對遺傳算法局部搜索能力較差問題，孫波等［4］提出了一種改進(jìn)的自適應(yīng)遺傳算法。劉昂等［5］融合改進(jìn)蟻群算法和鴿群算法，以改善蟻群算法收斂速度慢的問題。Digani 等［6］提出分層地圖的思想，第一層為拓?fù)浣Y(jié)構(gòu)地圖，機(jī)器人用D*算法進(jìn)行動態(tài)路徑規(guī)劃，第二層采用A*算法進(jìn)行運(yùn)動控制，一定程度上實(shí)現(xiàn)動態(tài)路徑規(guī)劃并避免交通堵塞，但系統(tǒng)運(yùn)行效率不高。泰應(yīng)鵬等［7］在基礎(chǔ)A*算法中引入時間窗，以增加實(shí)時避障功能，但算法實(shí)現(xiàn)復(fù)雜，對系統(tǒng)時序要求嚴(yán)格。裴以建等［8］在遺傳算法中增加插入算子、刪除算子，使優(yōu)化后的無障礙路徑質(zhì)量明顯提高。

群機(jī)器人路徑規(guī)劃，可轉(zhuǎn)化為多維旅行商問題（MTSP），與旅行商問題相比，疊加不能形成MTSP的全局最優(yōu)解，需要解決群機(jī)器人之間的避碰［9］。大多數(shù)路徑規(guī)劃算法并不能適應(yīng)群機(jī)器人協(xié)同完成大規(guī)模的任務(wù)，未能做到任務(wù)目標(biāo)與整體路徑規(guī)劃結(jié)合。在遺傳算法中融入K-means聚類，確保排序后相鄰任務(wù)之間的距離之和最小，減少成員機(jī)器人在完成遠(yuǎn)距離任務(wù)時的路徑浪費(fèi)，從而減少群機(jī)器人的總行駛路程，提高群機(jī)器人的路徑規(guī)劃效率。故提出基于K-means 聚類算法、遺傳算法和A*算法集成的求解群機(jī)器人多目標(biāo)路徑規(guī)劃問題。具體地，采用集中控制與分布控制相結(jié)合的多層控制：用融合K-means聚類改進(jìn)的遺傳算法優(yōu)化任務(wù)目標(biāo)的遍歷順序，通過集中控制獲得倉庫全局信息，構(gòu)造預(yù)約表，為機(jī)器人提供交通信息；在此基礎(chǔ)上，用改進(jìn)A*算法規(guī)劃相鄰目標(biāo)點(diǎn)之間的最優(yōu)路徑；局部沖突消除和底層安全保護(hù)則基于交通規(guī)則和預(yù)約表實(shí)現(xiàn)。

2 問題描述

智能倉庫中配置的群機(jī)器人R=｛R1，…，Rm｝由m個成員機(jī)器人組成，要求其將訂單物品從貨架上搬運(yùn)至揀貨臺，由工人負(fù)責(zé)打包。中央控制系統(tǒng)首先按機(jī)器人個數(shù)將所有任務(wù)分成m組訂單任務(wù)T=｛T1，…Tm｝。訂單任務(wù)Tj（j∈1，…，m）分配給機(jī)器人Ri（i∈1，…，m）后，Ri將依次搬運(yùn)Tj中的t個貨物Ti=｛Ti1，…，Tit｝至揀貨臺。執(zhí)行任務(wù)時，機(jī)器人Ri以揀選平臺為起始點(diǎn)，以Ti1為目標(biāo)點(diǎn)進(jìn)行路徑規(guī)劃。取貨Ti1后，以Ti1為起始點(diǎn)，Ti2為目標(biāo)點(diǎn)進(jìn)行路徑規(guī)劃。以此類推，直到提貨Tit，以Tit為起點(diǎn)，以揀貨臺為目標(biāo)點(diǎn)，將所有目標(biāo)貨物移回揀貨臺［10］。

圖1［11］為某智能倉庫的結(jié)構(gòu)化示例，此倉庫模型可以充分利用地圖空間，在模型中設(shè)計相關(guān)規(guī)則可以提高路徑規(guī)劃的效率。其中，22 個揀貨臺在左側(cè)均勻分布，35 個標(biāo)識為深灰色的貨架按2 行5列分布，可將環(huán)境建模為22×33 大小的二維柵格地圖。機(jī)器人的初始位置在揀貨臺附近隨機(jī)分布，機(jī)器人可在貨架之間、貨架與揀貨臺之間的通道中同時穿梭運(yùn)動。要求機(jī)器人無碰撞地從初始位置移動至目標(biāo)貨架的位置，將貨架上的物品搬運(yùn)至揀貨臺，完成一次揀貨任務(wù)。

圖1 智能倉庫模型

訂單分配和信息共享采用集中控制方式，機(jī)器人之間的協(xié)同路徑規(guī)劃采用分布式控制方式。首先，將訂單信息中的所有任務(wù)利用改進(jìn)遺傳算法進(jìn)行排序，得到最優(yōu)揀貨序列，然后發(fā)送到揀貨臺，揀貨臺查看所有機(jī)器人狀態(tài)，為“空閑”機(jī)器人分配訂單任務(wù)。各機(jī)器人得到一組順序任務(wù)，確定目標(biāo)貨架位置后，進(jìn)行路徑規(guī)劃，直到一筆訂單中的所有物品都被收集起來，機(jī)器人搬運(yùn)所“屬”揀貨臺要求的貨物返回該揀貨臺，由揀貨臺上的工人完成打包。同時，機(jī)器人狀態(tài)從“工作”變?yōu)椤翱臻e”，等待新的訂單任務(wù)。群機(jī)器人執(zhí)行的貨物揀選流程見圖2。

圖2 任務(wù)流程

3 建模

假設(shè)機(jī)器人Ri為執(zhí)行揀貨任務(wù)走過路徑Pi，Pi表示機(jī)器人Ri完成一次揀貨任務(wù)的一個順序集合，在機(jī)器人路徑規(guī)劃過程中，貨架占用的網(wǎng)格被設(shè)置為不可達(dá)，以避免機(jī)器人與貨架之間發(fā)生碰撞。這樣，可能導(dǎo)致堵塞甚至死鎖的機(jī)器人之間的碰撞有四種典型情形，見圖3。若機(jī)器人之間發(fā)生情形b所示碰撞，則可按優(yōu)先權(quán)高低順序通過。但其他三種情形下，僅靠避讓操作可能造成死鎖。為此，設(shè)計了交通規(guī)則，規(guī)定貨架之間的道路為單行道，相鄰兩條通道方向相反，機(jī)器人運(yùn)行時，只能按規(guī)定的通道方向單行，且只能選擇“上”“下”“左”“右”或“原地等待”其中之一的運(yùn)動狀態(tài)。

圖3 碰撞類型

考慮m個機(jī)器人無碰撞完成所有任務(wù)時所走總路程最短和總時間最短，將群機(jī)器人路徑規(guī)劃建模為約束條件下的優(yōu)化問題，見式（1）：

這里，Si表示機(jī)器人Ri完成所規(guī)劃任務(wù)的路徑長度，用機(jī)器人Ri完成所有任務(wù)的步數(shù)表示。

將局部路徑?jīng)_突建模為柵格坐標(biāo)下的優(yōu)化問題，C1（Pi）表示機(jī)器人是否與貨架相撞，C2（Pi，Pj）表示倆個機(jī)器人之間是否相撞，用式（2）和式（3）表示：

這里，Ri（x，y）和Ui（x，y）分別為機(jī)器人和貨架占據(jù)的柵格坐標(biāo)，Pi∩Pj≠?表示機(jī)器人Ri和Rj規(guī)劃的路徑在時空上有交集，即機(jī)器人Ri和Rj在某時刻同時出現(xiàn)在某個柵格中，即二者發(fā)生相撞［12］。

4 路徑規(guī)劃算法

在機(jī)器人進(jìn)行路徑規(guī)劃之前，首先對系統(tǒng)中的訂單進(jìn)行分配，將確定的目標(biāo)作為路徑終點(diǎn)。建立群機(jī)器人的任務(wù)規(guī)劃模型，使用融合K-means聚類的改進(jìn)遺傳算法對任務(wù)目標(biāo)進(jìn)行排序整理后，確定目標(biāo)節(jié)點(diǎn)的最優(yōu)遍歷序列，得到最優(yōu)揀選任務(wù)順序。再用改進(jìn)A*算法規(guī)劃各機(jī)器人的多任務(wù)目標(biāo)路徑矩陣。然后用預(yù)約表化解局部動態(tài)沖突，得到最優(yōu)路徑。

4.1 改進(jìn)遺傳算法

路徑規(guī)劃需要的信息，主要是目標(biāo)任務(wù)位置。目標(biāo)任務(wù)規(guī)劃的目的是使機(jī)器人在根據(jù)訂單任務(wù)進(jìn)行路徑規(guī)劃和提貨時避免繞道，使總距離最小化。首先對種群進(jìn)行編碼，然后用K-means聚類算法把種群按機(jī)器人數(shù)進(jìn)行聚類，用遺傳算法中的選擇、交叉和變異操作，重復(fù)迭代后得到最優(yōu)或次優(yōu)遍歷序列，即得到最優(yōu)揀選任務(wù)順序。

4.1.1 種群初始化

種群編碼方法采用實(shí)數(shù)編碼。對于一組有n個目標(biāo)的任務(wù)，將其編碼為從2到n+1的實(shí)數(shù)，并將相應(yīng)的揀貨臺位置編碼為實(shí)數(shù)1。從實(shí)數(shù)1到n+1，隨機(jī)生成k個個體的種群，個體基因數(shù)為n+1。由于機(jī)器人在接到訂單任務(wù)后將以揀選臺為出發(fā)點(diǎn)，提取貨物后還要返回揀選臺，因此將種群中每個個體的第一個基因設(shè)置為揀貨臺位置1。同時，設(shè)置遺傳算法的迭代次數(shù)、交叉概率和變異概率。

將n個目標(biāo)按機(jī)器人數(shù)量分成m組，規(guī)定每組任務(wù)由一個機(jī)器人完成。通過K-means 聚類把n個目標(biāo)點(diǎn)按距離關(guān)系分成m組，建立式（4）、（5）所示的規(guī)劃模型，優(yōu)化目標(biāo)為分在同一組內(nèi)的任意兩點(diǎn)間的行走距離之和最小。

其中，i=1，…，n，j=1，…，m。

4.1.2 適應(yīng)度函數(shù)設(shè)計

假設(shè)機(jī)器人Ri有t個揀貨目標(biāo)任務(wù)，將揀貨目標(biāo)隨機(jī)排列，得到機(jī)器人Ri的揀貨順序為Ti=｛Ti1，…，Tit｝，其中任意兩個分揀節(jié)點(diǎn)Tix，Tiy之間的路徑為C（Tix，Tiy）。用改進(jìn)A*算法計算各任務(wù)目標(biāo)點(diǎn)之間的距離長度為Ci（Tx，Ty），得到遺傳算法中適應(yīng)度函數(shù)Z，見式（6）。

這里，m表示機(jī)器人個數(shù)，L表示群機(jī)器人中最慢的一個機(jī)器人完成其全部任務(wù)走過的路徑長度。

4.1.3 遺傳算法

遺傳算法主要有三個關(guān)鍵操作，分別是選擇操作、交叉操作和變異操作。選擇操作可以留下優(yōu)勢的個體，交叉操作通過交換兩個個體的基因序列產(chǎn)生新個體，變異操作則通過使個體基因的某個序列突變產(chǎn)生新個體。通過這三種操作，選擇出優(yōu)勢的群體基因。

1）選擇操作

采用輪盤賭的方法進(jìn)行選擇操作，選擇的概率根據(jù)個體的適應(yīng)度函數(shù)值大小來決定，適應(yīng)度值越大，選擇該個體的概率就越大；適應(yīng)度值越小，選擇該個體的概率就越小。如某個體適應(yīng)度為fi，種群大小為N，則該個體被選擇的概率可用式（7）求得：

2）交叉操作

采用單點(diǎn)交叉法，對第1）步選擇操作篩選出來的個體進(jìn)行隨機(jī)配對，設(shè)置交叉概率，配對的依據(jù)即按照交叉概率。交叉操作是將配對的組合其中一個個體的某一個基因和組合中另一個個體的某個基因互換。由于基因序列中第1 個位置代表揀貨臺，揀貨臺的位置始終是不變的，所以交叉時設(shè)置基因序列1的位置不變。

3）變異操作

設(shè)置變異概率，在交叉操作后的個體中依據(jù)變異概率進(jìn)行個體的選擇，變異操作就是將某個個體的某個基因變異為其他的基因。因為要保證任務(wù)對應(yīng)的編碼數(shù)字不能重復(fù)出現(xiàn)，所以采用對隨機(jī)選擇的個體中的某兩個基因進(jìn)行交換操作。

4.2 節(jié)點(diǎn)間路徑規(guī)劃

機(jī)器人將按照目標(biāo)規(guī)劃一條高效且無碰撞的揀貨路線，基本想法是使用A*算法來計算任意兩個目標(biāo)點(diǎn)間的路徑長度，在目標(biāo)點(diǎn)間建立一條路線，按照任務(wù)目標(biāo)點(diǎn)的遍歷次序，對其進(jìn)行規(guī)劃，找出一條為成員機(jī)器人創(chuàng)建的全局路徑，并且這條路徑要保證機(jī)器人之間沒有路徑?jīng)_突。解決沖突的方式是用預(yù)約表法消解，保證所有成員機(jī)器人的所有路徑序列之間沒有沖突。

4.2.1 改進(jìn)A*算法

A*算法是一種在路徑規(guī)劃中常用的啟發(fā)式搜索算法，可以用來求解兩點(diǎn)間的最短路徑。算法過程如下：算法從起始節(jié)點(diǎn)開始利用估算代價函數(shù)依次向外估算相鄰節(jié)點(diǎn)的路徑代價，根據(jù)估算路徑代價對臨近節(jié)點(diǎn)進(jìn)行排序，然后選擇最優(yōu)的臨近節(jié)點(diǎn)進(jìn)行下一步的搜索直至目標(biāo)點(diǎn)。應(yīng)用到柵格地圖中，機(jī)器人將從開始柵格出發(fā)，每次選擇下一步將要移動的柵格時，都會計算出相鄰柵格的估算代價；然后移動至估算代價最小的柵格。機(jī)器人重復(fù)上述步驟，直到移動至目標(biāo)柵格［13］。估算代價函數(shù)用式（8）計算：

這里，g（s）表示機(jī)器人從起始柵格移動到當(dāng)前柵格s的真實(shí)代價；h（s）表示機(jī)器人從當(dāng)前柵格s移動到目標(biāo)柵格的啟發(fā)估算代價。

一般地，路徑規(guī)劃中的代價指距離代價，本文用曼哈頓距離作為估算函數(shù)的代價。曼哈頓距離如式（9）所示。

式中，s.x和s.y分別表示當(dāng)前柵格s的x軸坐標(biāo)和y軸坐標(biāo)，goal.x和goal.y分別表示目標(biāo)柵格goal的x軸坐標(biāo)和y軸坐標(biāo)。

當(dāng)機(jī)器人在真實(shí)的倉庫中行走時，它將在轉(zhuǎn)彎時需要更長的時間，因此機(jī)器人在路徑長度相同但彎道數(shù)不同的路徑上行走時，彎道越少，所需的時間就越少。故修改估算函數(shù)估算的代價為時間代價，得到時間代價估算函數(shù)g'（s）和h'（s），用式（10）和式（11）計算。

考慮轉(zhuǎn)彎代價時間，改進(jìn)后的A*算法的估算代價函數(shù)用式（12）計算。

式中，tturn代表轉(zhuǎn)彎額外花銷的時間，q代表轉(zhuǎn)彎個數(shù)。

4.2.2 預(yù)約表設(shè)計

針對圖3 所示的b 類碰撞，通過預(yù)約表來避免。預(yù)約表中記錄各柵格的狀態(tài)，如果柵格被占用，則機(jī)器人ID 會寫入預(yù)約表的相應(yīng)位置，如表1所示。該系統(tǒng)可以根據(jù)預(yù)約表的查詢，提前得到相應(yīng)時間點(diǎn)上的網(wǎng)格的狀態(tài)。如果柵格中沒有任何機(jī)器人的ID，表示在相應(yīng)的時間內(nèi)沒有任何機(jī)器人占據(jù)此網(wǎng)格，那么機(jī)器人可以進(jìn)入該柵格；如果柵格中有某個機(jī)器人的ID，表示在相應(yīng)的時間有其他的機(jī)器人占據(jù)了這個網(wǎng)格，那么這個網(wǎng)格就被看作是一個障礙物，機(jī)器人不可進(jìn)入該柵格。預(yù)約表是實(shí)時變化的，機(jī)器人每走一個步長，系統(tǒng)就會根據(jù)當(dāng)前倉庫中機(jī)器人占用柵格的情況更新預(yù)約表［15］。

表1 預(yù)約表

5 算法流程

集成K-means聚類算法、改進(jìn)的遺傳算法和改進(jìn)的A*算法，得到偽碼描述的本文算法［14］，見算法1。首先利用K-means聚類算法將所有任務(wù)目標(biāo)按機(jī)器人個數(shù)進(jìn)行分組，按分組給種群編碼；然后，依照改進(jìn)A*算法計算各任務(wù)目標(biāo)之間的路徑長度，并轉(zhuǎn)化為遺傳算法中的適應(yīng)度函數(shù)，經(jīng)過遺傳算法中的選擇操作、交叉操作和變異操作，然后迭代若干代，得到的個體即為最優(yōu)個體，也急速最優(yōu)的任務(wù)序列。任務(wù)規(guī)劃完成后，根據(jù)改進(jìn)A*算法在倉庫中進(jìn)行路徑規(guī)劃，群機(jī)器人按照路徑規(guī)劃好的路線依次執(zhí)行任務(wù)，利用交通規(guī)則和預(yù)約表避免群機(jī)器人之間發(fā)生碰撞，群機(jī)器人完成所有揀貨任務(wù)后，得到所消耗的總時間和所有機(jī)器人走過的總路程。

路徑規(guī)劃算法流程見圖4。

圖4 路徑規(guī)劃算法流程圖

6 仿真

為驗證本文方法的有效性，采用圖1 所示的倉庫地圖模型，將本文算法（算法1）與基于傳統(tǒng)遺傳算法的路徑規(guī)劃方法（算法2）、基于交通規(guī)則和預(yù)約表的A*算法（算法3）、基于交通規(guī)則和預(yù)約表的改進(jìn)A*算法（算法4）進(jìn)行比較。仿真實(shí)驗在Matlab 2020a環(huán)境中進(jìn)行。實(shí)驗設(shè)計如下：

1）比較相同規(guī)模群機(jī)器人執(zhí)行不同規(guī)模任務(wù)情形，設(shè)機(jī)器人數(shù)10，任務(wù)數(shù)依次為50，100，150，200，250，300，比較機(jī)器人完成所有任務(wù)的總消耗時間和總行走路程。

2）比較相同任務(wù)數(shù)由不同規(guī)模群機(jī)器人執(zhí)行情形，設(shè)任務(wù)數(shù)300，機(jī)器人數(shù)分別為10，20，30，40，50，比較機(jī)器人完成所有任務(wù)的總消耗時間和總行走路程。

因為所用算法是一種啟發(fā)式算法，所以在相同的參數(shù)下，實(shí)驗的結(jié)果并不完全一致。所以，每組實(shí)驗算法都獨(dú)立地運(yùn)行了50 次并取平均數(shù)作為實(shí)驗結(jié)果。

圖5 為4 種路徑規(guī)劃算法下10 個機(jī)器人完成不同數(shù)量任務(wù)需要的總時間。機(jī)器人數(shù)量維持不變時，運(yùn)行的總時間隨任務(wù)數(shù)增加而增加。相較于其他路徑規(guī)劃算法，算法1 能有效減少系統(tǒng)運(yùn)行的總時間，這是因為算法1 中融入聚類算法，把距離近的任務(wù)聚集成一類，彌補(bǔ)了其他算法任務(wù)分配的不足，隨著任務(wù)數(shù)的增加，聚類算法的效果也就越明顯。

圖5 群機(jī)器人完成不同數(shù)量任務(wù)所花費(fèi)的總時間

圖6 為在4 種路徑規(guī)劃算法下10 個機(jī)器人完成不同數(shù)量任務(wù)所行走的總路程。由圖可知，在機(jī)器人數(shù)量一定時，任務(wù)數(shù)量越多，機(jī)器人完成任務(wù)所走總路程也越多。從實(shí)驗結(jié)果可以看出，相較于算法3 和算法4，算法2 在路徑規(guī)劃前先采用遺傳算法進(jìn)行分配任務(wù)，可以在一定程度上減少系統(tǒng)運(yùn)行的總路程。算法1 在遺傳算法中融入聚類算法后，可以減少機(jī)器人在做遠(yuǎn)距離任務(wù)時的路徑浪費(fèi)，有效縮短機(jī)器人行走的總路程。

圖6 群機(jī)器人完成不同數(shù)量任務(wù)所行走的總路程

圖7 為在4種路徑規(guī)劃算法下不同數(shù)量機(jī)器人完成300 個任務(wù)所需要的總時間。由圖可知，在任務(wù)數(shù)量不變的情況下，隨著機(jī)器人的數(shù)量增加，機(jī)器人完成任務(wù)所需總時間在不斷減少。相較于其他算法，算法1 仍然有效地縮短了機(jī)器人完成所有任務(wù)所需要的時間。隨著機(jī)器人的數(shù)量增多，總時間下降的趨勢逐漸變緩，這是因為機(jī)器人數(shù)量越多，群機(jī)器人在做任務(wù)過程中產(chǎn)生的路徑?jīng)_突就越多，導(dǎo)致群機(jī)器人需要一部分的時間來解決沖突，造成總時間趨勢下降緩慢的現(xiàn)象。

圖7 不同數(shù)量機(jī)器人完成任務(wù)所花費(fèi)的總時間

圖8 顯示了不同數(shù)量機(jī)器人在4種路徑規(guī)劃算法下完成分配任務(wù)所行走的總路程。群機(jī)器人完成任務(wù)行走的總路程隨著群機(jī)器人數(shù)量的變化而不定的變化。使用本文提出的算法1 后，仍然比其他算法行走更少的路程。可以看出，在群機(jī)器人數(shù)量由10 增加到20 的階段，群機(jī)器人執(zhí)行任務(wù)的總路程隨著機(jī)器人數(shù)量的增多而快速減少。但是當(dāng)群機(jī)器人數(shù)量超過20 時，群機(jī)器人總行走路程會緩慢上升。這是由于隨著群機(jī)器人規(guī)模增大，路徑?jīng)_突可能性隨之增大，機(jī)器人為了避開路徑?jīng)_突而選擇繞路，導(dǎo)致犧牲一部分路徑代價。

圖8 不同數(shù)量機(jī)器人完成任務(wù)所行走的總路程

綜上所述，采用20個機(jī)器人來執(zhí)行300個任務(wù)將減少群機(jī)器人執(zhí)行任務(wù)的總時間，同時也能避免過多機(jī)器人產(chǎn)生路徑?jīng)_突造成總路程的增加，提高智能倉庫系統(tǒng)效率，節(jié)約智能倉庫資源。

統(tǒng)計4種算法在最大規(guī)模組合條件下（即50個機(jī)器人完成300 個任務(wù)）總耗時的最優(yōu)值、平均值和方差，見表2。從統(tǒng)計結(jié)果可以看出，本文算法（算法1）的總耗時最優(yōu)值和平均值均低于其他算法；而方差數(shù)據(jù)顯示，算法1和算法2的穩(wěn)定性不如算法3 和算法4，這是為優(yōu)化目標(biāo)順序犧牲了算法穩(wěn)定性。另外，本文算法的穩(wěn)定性高于傳統(tǒng)遺傳算法，算法有效性和穩(wěn)定性具有優(yōu)勢。

表2 算法有效性和穩(wěn)定性數(shù)據(jù)分析表

7 結(jié)語

針對智能倉庫群機(jī)器人路徑規(guī)劃問題，提出一種基于兩層架構(gòu)的群機(jī)器人路徑規(guī)劃方法。在遺傳算法中融合聚類算法，為機(jī)器人分配任務(wù)；在智能倉庫中制定交通規(guī)則并設(shè)計預(yù)約表，避免機(jī)器人碰撞。集成多任務(wù)目標(biāo)規(guī)劃和機(jī)器人路徑規(guī)劃算法后，通過仿真實(shí)驗驗證了算法的可行性和高效性。但是對于一個完整的智能倉庫來說，也可以從貨物的排列，貨物的分配等方面進(jìn)行分析，從多個角度來提升智能倉庫的運(yùn)作效率。本文僅針對每組任務(wù)的貨物排列順序進(jìn)行了規(guī)劃，同時假設(shè)每組訂單任務(wù)數(shù)相同，沒有考慮到動態(tài)分配的情況。因此，未來將考慮允許系統(tǒng)根據(jù)貨物情況隨機(jī)分配每組任務(wù)訂單的數(shù)目，結(jié)合機(jī)器人的任務(wù)分配，研究智能倉庫中的群機(jī)器人路徑規(guī)劃問題。