智能倉庫中基于兩層架構的群機器人路徑規(guī)劃*

薛頌東 張 宇 趙 靜 潘理虎

（1.太原科技大學 太原 030024）

（2.廣東機電職業(yè)技術學院 廣州 510515）

1 引言

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

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

2 問題描述

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

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

圖1 智能倉庫模型

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

圖2 任務流程

3 建模

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

圖3 碰撞類型

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

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

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

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

4 路徑規(guī)劃算法

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

4.1 改進遺傳算法

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

4.1.1 種群初始化

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

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

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

4.1.2 適應度函數(shù)設計

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

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

4.1.3 遺傳算法

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

1）選擇操作

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

2）交叉操作

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

3）變異操作

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

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

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

4.2.1 改進A*算法

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

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

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

式中，s.x和s.y分別表示當前柵格s的x軸坐標和y軸坐標，goal.x和goal.y分別表示目標柵格goal的x軸坐標和y軸坐標。

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

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

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

4.2.2 預約表設計

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

表1 預約表

5 算法流程

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

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

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

6 仿真

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結語

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