基于改進(jìn)A*算法的多機(jī)器人動態(tài)路徑規(guī)劃①

董朝瑞 郭 欣 李 寧 邵謝寧

(河北工業(yè)大學(xué)人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300130)

0 引 言

近年來，隨著電商行業(yè)的迅猛發(fā)展，物流配送作為電商行業(yè)的核心要素之一越來越受到人們的關(guān)注。由于電子商務(wù)的物流配送工作具有品種多、批次多的特點(diǎn)，傳統(tǒng)工作模式下工人大多數(shù)的時間都浪費(fèi)在了取貨上[1]。因此人們對智能倉儲系統(tǒng)的需求越來越迫切，隨著以亞馬遜Kiva Systems為代表的智能倉儲系統(tǒng)興起，高效的多移動機(jī)器人智能倉儲系統(tǒng)成為研究熱點(diǎn)之一[2]。將多移動機(jī)器人應(yīng)用在智能倉儲系統(tǒng)中代替人來進(jìn)行搬運(yùn)工作可以有效降低倉儲系統(tǒng)運(yùn)維成本，提高運(yùn)作效率。在多移動機(jī)器人智能倉儲系統(tǒng)的研究中，多機(jī)器人路徑規(guī)劃和碰撞預(yù)防是實現(xiàn)多移動機(jī)器人智能倉儲系統(tǒng)的關(guān)鍵。

對于多機(jī)器人路徑規(guī)劃，傳統(tǒng)的方法是將Dijkstra算法和時間窗原理結(jié)合起來進(jìn)行多機(jī)器人路徑規(guī)劃[3-5]。但是，隨著節(jié)點(diǎn)數(shù)量的不斷增加，Dijkstra算法的效率將顯著降低，因此Dijkstra算法僅適用于小型系統(tǒng)。目前在智能倉庫的環(huán)境下研究多機(jī)器人系統(tǒng)主要采用以A*算法[6，7]、蟻群算法[8，9]、D*算法[10]為基礎(chǔ)的路徑規(guī)劃。其中蟻群算法和D*算法可以避開環(huán)境中未知障礙，屬于動態(tài)路徑規(guī)劃算法，但是這2種算法無法得到全局最優(yōu)的路徑。A*算法作為一種啟發(fā)式搜索算法，具有簡單高效的特點(diǎn)，能夠得到全局最優(yōu)路徑，是目前最流行的機(jī)器人路徑規(guī)劃算法。由于智能倉儲系統(tǒng)中多機(jī)器人同時工作的特點(diǎn)，機(jī)器人工作環(huán)境變化迅速，應(yīng)用傳統(tǒng)的A*算法進(jìn)行路徑規(guī)劃可能會導(dǎo)致交通堵塞問題，甚至產(chǎn)生死鎖現(xiàn)象，導(dǎo)致系統(tǒng)崩潰。

為了解決上述問題，本文提出了基于預(yù)約表和交通擁堵地圖的多機(jī)器人路徑規(guī)劃方法。通過使用預(yù)約表和基于機(jī)器人優(yōu)先級的交通規(guī)則，解決多機(jī)器人間的碰撞沖突問題；通過基于交通擁堵地圖的改進(jìn)A*算法，在路徑規(guī)劃過程中考慮到交通擁堵狀況帶來的路徑代價，使機(jī)器人運(yùn)行時盡可能避開擁塞程度高的區(qū)域，以減小系統(tǒng)擁塞程度進(jìn)而縮短系統(tǒng)運(yùn)行時間；根據(jù)交通狀況動態(tài)地更改路徑代價，在機(jī)器人行進(jìn)道路前方出現(xiàn)擁堵時，重新進(jìn)行路徑規(guī)劃，實現(xiàn)了倉儲環(huán)境下機(jī)器人的實時路徑規(guī)劃。

1 倉儲環(huán)境模型

本文采用柵格建模法構(gòu)建地圖模型，如圖1所示，在物流配送中心倉儲貨架的布局是整齊對稱的，同時貨架間的道路也是垂直交叉的。多個移動機(jī)器人同時在此倉儲空間中運(yùn)動，貨架之間的通道為單排車道，黑色柵格表示貨架。本文對機(jī)器人在配送中心的應(yīng)用場景進(jìn)行如下簡化。

(1)機(jī)器人在任意一條道路只能單向行駛；

(2)機(jī)器人在正常行駛過程中速度可變，機(jī)器人直行通過一個柵格的路徑代價為1，在機(jī)器人轉(zhuǎn)彎過程會消耗更多的時間，在柵格完成90 °轉(zhuǎn)向需要額外轉(zhuǎn)向代價為1；

(3)地圖中的每個柵格均可容納1臺機(jī)器人，并且每一柵格同一時刻只允許通過1臺機(jī)器人；

(4)為防止機(jī)器人間的意外碰撞，規(guī)定機(jī)器人間的最小安全距離，該距離根據(jù)機(jī)器人的長度和運(yùn)行速度確定。

圖1 智能倉庫模型

在多機(jī)器人系統(tǒng)中，需要確定不同機(jī)器人的優(yōu)先級以確保系統(tǒng)安全穩(wěn)定運(yùn)行。根據(jù)智能倉儲多機(jī)器人系統(tǒng)的工作流程，可以將機(jī)器人單個任務(wù)的揀選工作分為以下步驟：

(1)機(jī)器人從當(dāng)前所在位置前往目標(biāo)貨架；

(2)機(jī)器人將貨架從當(dāng)前位置搬運(yùn)至揀選站臺；

(3)機(jī)器人在揀選臺等待工人從貨架上揀選貨物；

(4)機(jī)器人將揀選完成的貨物送回存儲位置存放。

機(jī)器人在不同的工作狀態(tài)下的優(yōu)先級定義如表1所示。

當(dāng)2臺機(jī)器人工作狀態(tài)不同時判斷機(jī)器人的優(yōu)先級，滿載的機(jī)器人的優(yōu)先級高于空載的機(jī)器人，去往揀選臺的載貨機(jī)器人的優(yōu)先級高于返回存儲位置的機(jī)器人；當(dāng)2臺機(jī)器人工作狀態(tài)相同時判斷機(jī)器人的優(yōu)先級，對機(jī)器人所載貨物進(jìn)行判斷，貨物優(yōu)先級高的機(jī)器人有更高的優(yōu)先級；對于2臺機(jī)器人都是空載的情況，編號更小的機(jī)器人有更高的優(yōu)先級。

表1 機(jī)器人優(yōu)先級

2 多機(jī)器人系統(tǒng)沖突預(yù)防策略

智能倉庫中，多個移動機(jī)器人在同一區(qū)域來回穿梭，在其運(yùn)動過程中難免會發(fā)生機(jī)器人之間的碰撞，如圖2所示。針對圖2(a)中的迎面碰撞造成死鎖的問題，本文采用單向圖法[11]對道路方向進(jìn)行約束，規(guī)定貨架間的道路為單行道，移動機(jī)器人在同一道路只能沿同一方向行駛。雖然單向圖在某些情況下會使機(jī)器人在路徑規(guī)劃時存在繞遠(yuǎn)路的情況，但是考慮到倉庫的復(fù)雜環(huán)境，使用單向圖約束可以明顯提高系統(tǒng)運(yùn)算效率以及多機(jī)器人系統(tǒng)的安全性和穩(wěn)定性。

圖2 幾種碰撞類型

采用單向圖的方式對智能倉儲系統(tǒng)的道路環(huán)境進(jìn)行定義后可以杜絕圖2中迎面碰撞的發(fā)生，然而多機(jī)器人系統(tǒng)仍然存在著圖2(b)、(c)中所示的碰撞情形。為了使其他機(jī)器人可以在碰撞發(fā)生前采取停車或繞行的方式避免沖突，在當(dāng)前機(jī)器人規(guī)劃好路徑之后，必須通過一定的方法表示該機(jī)器人占有柵格的情況。為此結(jié)合上一節(jié)的機(jī)器人的優(yōu)先級定義，通過使用預(yù)約柵格的方法對機(jī)器人的位置情況進(jìn)行表述，預(yù)防碰撞。

本文中所研究的多機(jī)器人系統(tǒng)中，機(jī)器人在行駛過程中需要保證中央控制模塊和各個機(jī)器人之間保持實時通訊。因此在為機(jī)器人申請預(yù)約位置的時候，機(jī)器人將行駛道路前方的一個柵格也加入了預(yù)約作為預(yù)約柵格。預(yù)約柵格的添加不僅可以為機(jī)器人的通訊留出足夠的反應(yīng)時間，同時可以為機(jī)器人的行駛提供一定的安全空間，保證機(jī)器人減速到停止過程中一直在所預(yù)約的柵格范圍內(nèi)。本文中，稱機(jī)器人當(dāng)前的位置為當(dāng)前柵格，預(yù)留的柵格為預(yù)約柵格。此外，如果機(jī)器人處于停止?fàn)顟B(tài)，則當(dāng)前柵格和預(yù)約柵格都為機(jī)器人當(dāng)前所在位置的柵格。

多機(jī)器人系統(tǒng)運(yùn)行過程中，由中央控制器統(tǒng)一協(xié)調(diào)處理機(jī)器人的預(yù)約柵格。如果有多個機(jī)器人同時申請一個柵格資源，則通過判斷沖突機(jī)器人的優(yōu)先級，各個機(jī)器人按照優(yōu)先級順序通過該柵格。在進(jìn)行預(yù)約柵格協(xié)調(diào)過程中，系統(tǒng)所依據(jù)的原則主要有以下2條：

(1)如果低優(yōu)先級機(jī)器人的預(yù)約柵格與高優(yōu)先級機(jī)器人的當(dāng)前柵格或預(yù)約柵格相同，則低優(yōu)先級的機(jī)器人停止移動，并將預(yù)約柵格的位置更改為當(dāng)前機(jī)器人所在位置，高優(yōu)先機(jī)器人正常行駛。

(2)如果高優(yōu)先級機(jī)器人的預(yù)約柵格與低優(yōu)先權(quán)機(jī)器人的當(dāng)前柵格相同，則高優(yōu)先級的機(jī)器人停止移動，并將預(yù)約柵格的位置更改為當(dāng)前機(jī)器人所在位置，低優(yōu)先機(jī)器人正常行駛。多機(jī)器人系統(tǒng)依據(jù)預(yù)約柵格進(jìn)行沖突預(yù)防的過程如圖3所示。

圖3(a)顯示了t時刻2臺機(jī)器人r1和r2的當(dāng)前位置和預(yù)約柵格的位置，圖中灰色框內(nèi)的柵格1為r1的預(yù)約柵格，柵格2為r2的預(yù)約柵格，機(jī)器人r2的優(yōu)先級大于r1的優(yōu)先級；圖3(b)顯示了t+1時刻2臺機(jī)器人移動之后的位置和預(yù)約柵格，圖中機(jī)器人r1與r2的預(yù)約柵格沖突；如圖3(c)所示，t+2時刻中央控制器讀取各臺機(jī)器人的預(yù)約柵格之后，對沖突柵格進(jìn)行調(diào)整。由于r2的優(yōu)先級高于r1，因此r2的預(yù)約柵格不變，r1的預(yù)約柵格調(diào)整為機(jī)器人當(dāng)前位置，同時機(jī)器人r1做停車處理，r2繼續(xù)前進(jìn)；t+3時刻機(jī)器人位置如圖3(d)所示，圖中2臺機(jī)器人的預(yù)約柵格不再有沖突，機(jī)器人r1和r2按規(guī)劃路徑正常行駛，沖突調(diào)節(jié)成功。

圖3 利用預(yù)約柵格躲避碰撞

3 智能倉儲系統(tǒng)多機(jī)器人動態(tài)路徑規(guī)劃算法

3.1 加入轉(zhuǎn)向代價的A*算法

A*算法的時間和空間復(fù)雜度較小，能夠在短時間內(nèi)得到最優(yōu)的路徑，并且適應(yīng)能力較強(qiáng)，其啟發(fā)函數(shù)可以根據(jù)實際環(huán)境的約束條件進(jìn)行調(diào)整，以滿足多機(jī)器人路徑規(guī)劃的需要[12]。A*算法的基本流程為機(jī)器人從起始柵格出發(fā)，根據(jù)路徑代價選擇下一步將要擴(kuò)展的柵格。其中路徑代價是指機(jī)器人從起始柵格出發(fā)，經(jīng)過將要擴(kuò)展的柵格，到達(dá)目標(biāo)柵格的最短估算值。機(jī)器人會選擇路徑代價最小的柵格進(jìn)行擴(kuò)展，直到擴(kuò)展到目標(biāo)柵格。其估價函數(shù)是尋找起點(diǎn)到終點(diǎn)最優(yōu)路徑的關(guān)鍵，估價函數(shù)的一般形式為

f(n)=g(n)+h′(n)

(1)

式中，f(n)代表從起始節(jié)點(diǎn)經(jīng)節(jié)點(diǎn)n到達(dá)目標(biāo)點(diǎn)的預(yù)估路徑代價，g(n)為機(jī)器人從起始節(jié)點(diǎn)移動到當(dāng)前節(jié)點(diǎn)n的真實路徑代價，h′(n)代表當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的估計距離。當(dāng)h′(n)≤h(n)(從當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的實際最優(yōu)距離)時，可以確保A*算法得到路徑為最優(yōu)路徑[13]。

根據(jù)倉儲環(huán)境中機(jī)器人的移動規(guī)則，在柵格化的倉庫模型中最優(yōu)路徑的搜索方向為上下左右4個方向，因此距離估計函數(shù)采用曼哈頓距離，其公式為

h′(n)=abs(n.x-goal.x)+abs(n.y-goal.y)

(2)

式中，n.x與n.y分別為當(dāng)前柵格的橫坐標(biāo)與縱坐標(biāo)，goal.x與goal.y分別為目標(biāo)柵格的橫坐標(biāo)與縱坐標(biāo)。

由于機(jī)器人在轉(zhuǎn)向上的時間耗費(fèi)和能量耗費(fèi)比直線行駛時要多，本文在計算路徑代價時中加入轉(zhuǎn)向代價，此時路徑代價函數(shù)為

f′(n)=g(n)+h′(n)+ε0

(3)

其中ε0表示轉(zhuǎn)向代價，其值為

(4)

圖4 轉(zhuǎn)向判斷

3.2 交通擁堵地圖

上文提到的改進(jìn)后的路徑規(guī)劃算法通過引入轉(zhuǎn)角代價和單向圖約束，在機(jī)器人路徑規(guī)劃時可以有效降低路徑的轉(zhuǎn)角次數(shù)，減小機(jī)器人發(fā)生碰撞的概率。但是，在多機(jī)器人環(huán)境中，工作區(qū)域通常包含多臺同時運(yùn)行的機(jī)器人，交通擁堵的情況會大幅度降低機(jī)器人搬運(yùn)貨物的效率。本文通過基于交通擁堵地圖的路徑規(guī)劃策略解決交通堵塞的問題，在路徑規(guī)劃時將環(huán)境的擁塞程度加入到考量中，使機(jī)器人運(yùn)行時盡可能避開擁塞程度高的區(qū)域，通過減小系統(tǒng)擁塞程度來縮短系統(tǒng)運(yùn)行時間，提高系統(tǒng)的運(yùn)作效率。顯然機(jī)器人在運(yùn)行過程中某一區(qū)域的擁堵程度與在其范圍內(nèi)的機(jī)器人數(shù)量和附近的可通行道路柵格數(shù)有關(guān)。一般區(qū)域內(nèi)的機(jī)器人數(shù)量越多，機(jī)器人在該區(qū)域發(fā)生擁堵的程度越大。因此考慮擁堵程度P用下式表示：

(5)

式中，Nr表示該柵格附近區(qū)域的機(jī)器人數(shù)量，即2個柵格范圍內(nèi)的機(jī)器人數(shù)量，C為該區(qū)域中的柵格總數(shù)，如圖5所示。

(6)

式中，K是擁堵程度向路徑代價轉(zhuǎn)化的常數(shù)參數(shù)，pi, j表示(i,j)柵格的擁堵程度。本文將K設(shè)置為機(jī)器人遇到堵塞時停車等待的額外時間所消耗的路徑代價，所以通過改進(jìn)的A*算法進(jìn)行擴(kuò)展節(jié)點(diǎn)n的f值計算時，式(3)中的實際路徑代價g(n)可以表示為

(7)

式中，g(m)為當(dāng)前f值最小柵格m到起點(diǎn)的實際路徑代價。

圖5 m柵格附近的機(jī)器人數(shù)量

3.3 多機(jī)器人動態(tài)路徑規(guī)劃

上述的算法可以很好地解決倉儲環(huán)境中機(jī)器人最優(yōu)路徑規(guī)劃問題，但是該算法還是存在一些問題。首先，A*算法在復(fù)雜環(huán)境下的搜索空間會增加，因此路徑規(guī)劃效率會相應(yīng)地降低。其次，A*算法作為一種全局路徑規(guī)劃方法，算法產(chǎn)生離線先驗路徑是根據(jù)靜態(tài)環(huán)境中生成的全局路徑，忽略了移動機(jī)器人運(yùn)行環(huán)境的變化。為了減小A*算法的搜索空間，減少搜索時的擴(kuò)展節(jié)點(diǎn)數(shù)目，可以對柵格地圖進(jìn)行抽象處理，將整個地圖劃分依據(jù)道路分為若干部分，并為其設(shè)置關(guān)鍵節(jié)點(diǎn)，利用改進(jìn)A*算法在各個道路中進(jìn)行路徑搜素，得到同一道路中各個關(guān)鍵點(diǎn)之間的路徑代價，得到抽象地圖。最后利用A*算法對關(guān)鍵節(jié)點(diǎn)進(jìn)行擴(kuò)展，得到從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。為了提高機(jī)器人系統(tǒng)對運(yùn)行環(huán)境變動的適應(yīng)，在路徑規(guī)劃過程中加入在線規(guī)劃階段，實時檢測機(jī)器人道路前方的路況信息，并對擁堵區(qū)域進(jìn)行躲避，減少因停車等待耗費(fèi)的時間。

3.3.1 離線階段的靜態(tài)路徑規(guī)劃

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

在應(yīng)用改進(jìn)A*算法在倉儲地圖環(huán)境中搜索路徑時，可以將地圖分為若干道路，一條完整的路徑可以表示為起點(diǎn)-道路1-道路2-…-道路n-目標(biāo)點(diǎn)。因此可以根據(jù)倉儲地圖環(huán)境將大地圖分為若干個道路，如圖6所示。圖中35×25的地圖被分成了24條道路，其中縱向道路15條(記為L1～L15)，橫向道路9條(記為H1～H9)。對于任意2條道路，在其交點(diǎn)定義一系列的關(guān)鍵點(diǎn)，用這些關(guān)鍵點(diǎn)來連接這2條道路。

圖6 倉儲地圖關(guān)鍵節(jié)點(diǎn)示意圖

(2)地圖抽象化

對于同一條道路內(nèi)的任意2個關(guān)鍵節(jié)點(diǎn)之間定義一個鍵來連接它們，鍵值為每個關(guān)鍵點(diǎn)之間的最優(yōu)距離。例如圖6中，道路L3共有8個連接道路的關(guān)鍵點(diǎn)，按從上到下的順序?qū)⑵錁?biāo)記為A～H。在建立抽象地圖的過程中，把任意2個關(guān)鍵點(diǎn)之間的路徑長度返回作為節(jié)點(diǎn)之間的路徑代價值，如表2所示。

表2 道路L3所有鍵的鍵值

(3)路徑搜索

路徑搜索的第一步是要把起始節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)g擴(kuò)展到道路中，如圖7(a)所示。選取與起點(diǎn)和目標(biāo)點(diǎn)最近的道路柵格,將其擴(kuò)展為道路關(guān)鍵點(diǎn),并計算該點(diǎn)到當(dāng)前道路其他各個關(guān)鍵點(diǎn)的路徑代價。這樣就將起始及節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)添加到了抽象地圖中，然后就可以通過改進(jìn)A*算法在抽象地圖上進(jìn)行路徑搜索，搜索過程如圖7(b)所示。圖中當(dāng)前節(jié)點(diǎn)為N1，N1的可擴(kuò)展節(jié)點(diǎn)為當(dāng)前道路前方的所有關(guān)鍵節(jié)點(diǎn)。對抽象地圖進(jìn)行路徑搜索可以提供一條從起始點(diǎn)所在道路關(guān)鍵節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)所在道路關(guān)鍵節(jié)點(diǎn)的抽象路徑，通過對抽象路徑細(xì)化可以獲得從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)的真實路徑。對于給定的起點(diǎn)s和目標(biāo)點(diǎn)g，路徑規(guī)劃結(jié)果如圖8所示。從圖中可以看出由于倉庫環(huán)境的拓?fù)浣Y(jié)構(gòu)的規(guī)律性，因此在細(xì)化路徑時，無需再進(jìn)行搜索，只需要將關(guān)鍵點(diǎn)之間的路徑柵格加入規(guī)劃好的路徑中。貨架區(qū)域中的道路關(guān)鍵節(jié)點(diǎn)較少，所以應(yīng)用改進(jìn)A*算法在抽象地圖進(jìn)行路徑搜索可以減少路徑搜索時擴(kuò)展節(jié)點(diǎn)的數(shù)量，提高路徑規(guī)劃的效率。

圖7 抽象地圖中的路徑搜索方式

圖8 細(xì)化后返回的路徑

3.3.2 在線階段的動態(tài)路徑規(guī)劃

基于交通擁堵控制的多機(jī)器人路徑規(guī)劃可以在機(jī)器人開始執(zhí)行任務(wù)之前規(guī)劃出一條理論上的時間最少路徑，但是由于該算法為對靜態(tài)環(huán)境進(jìn)行的路徑規(guī)劃，并且有任務(wù)不斷加入到系統(tǒng)，機(jī)器人之間的路徑可能出現(xiàn)干涉的情況。因此，為了提高機(jī)器人系統(tǒng)對運(yùn)行環(huán)境變動的適應(yīng)，本文提出動態(tài)路徑規(guī)劃算法，在路徑規(guī)劃過程中加入重新規(guī)劃階段，當(dāng)檢測到機(jī)器人因為交通擁堵而停車時，以當(dāng)前位置為起點(diǎn)重新進(jìn)行路徑規(guī)劃，對擁堵區(qū)域進(jìn)行躲避，減少因停車等待的時間。

多機(jī)器人系統(tǒng)動態(tài)路徑規(guī)劃算法采用分布式結(jié)構(gòu)。該系統(tǒng)中存在n+1個可以用作計算的模塊，包括1個中央控制模塊和n個機(jī)器人模塊。其中中央控制模塊可以從各個機(jī)器人處接受預(yù)約柵格信息，根據(jù)一定的原則協(xié)調(diào)各機(jī)器人間的沖突，以及根據(jù)機(jī)器人位置信息維護(hù)交通擁堵地圖。機(jī)器人模塊則可以從中央控制模塊處獲得沖突協(xié)調(diào)信息和地圖環(huán)境，并根據(jù)這些信息進(jìn)行自身的路徑規(guī)劃及運(yùn)動控制。由于各個機(jī)器人都執(zhí)行計算任務(wù)，避免了系統(tǒng)中所有的計算任務(wù)集中到一個模塊上，這樣的分布式路徑規(guī)劃方法可提高系統(tǒng)的運(yùn)行效率，避免計算資源的浪費(fèi)。

在倉儲地圖環(huán)境中，中央控制模塊根據(jù)各個機(jī)器人位置情況實時更新交通擁堵地圖，機(jī)器人在交通擁堵地圖中采用本文設(shè)計的改進(jìn)A*算法各自進(jìn)行路徑規(guī)劃，然后在機(jī)器人沿該路徑行駛過程中協(xié)調(diào)機(jī)器人之間的碰撞，并在檢測到機(jī)器人因路徑?jīng)_突停車等待時，根據(jù)最新的交通擁堵地圖重新進(jìn)行路徑規(guī)劃，選擇交通擁堵代價最小的路徑。多機(jī)器人動態(tài)路徑規(guī)劃算法流程如圖9所示。在線階段的動態(tài)路徑規(guī)劃的主要步驟如下：

圖9 多機(jī)器人動態(tài)路徑規(guī)劃流程圖

(1)中央控制模塊根據(jù)各機(jī)器人預(yù)約柵格實時更新?lián)矶碌貓D和道路各個關(guān)鍵點(diǎn)之間的鍵值；

(2)機(jī)器人模塊根據(jù)交通擁堵地圖進(jìn)行離線靜態(tài)路徑規(guī)劃；

(3)機(jī)器人根據(jù)規(guī)劃好的路徑信息生成預(yù)約柵格信息，并向中央控制模塊發(fā)送預(yù)約柵格信息；

(4)從中央控制模塊接收各機(jī)器人的預(yù)約柵格信息，并根據(jù)機(jī)器人的優(yōu)先級對機(jī)器人間的沖突進(jìn)行協(xié)調(diào)，并將協(xié)調(diào)后的結(jié)果返回各機(jī)器人模塊；

(5)如果協(xié)調(diào)結(jié)果為該機(jī)器人停止移動，則將該機(jī)器人的預(yù)約柵格設(shè)置為當(dāng)前柵格，返回步驟(2)；

(6)機(jī)器人移動到預(yù)約柵格位置，然后更新機(jī)器人的當(dāng)前柵格和預(yù)約柵格，轉(zhuǎn)到步驟(3)。

4 仿真實驗

為研究多移動機(jī)器人路徑規(guī)劃與任務(wù)分配算法的性能，本文使用智能倉儲多機(jī)器人仿真系統(tǒng)進(jìn)行了仿真實驗。為了便于仿真系統(tǒng)的實現(xiàn)，本實驗對仿真系統(tǒng)中多機(jī)器人的運(yùn)行環(huán)境進(jìn)行了簡化，在機(jī)器人進(jìn)行分揀過程時假設(shè)貨架上的貨物充足不存在缺貨情況，機(jī)器人的電量足夠完成所有任務(wù)。該仿真系統(tǒng)可以根據(jù)需要任意設(shè)置機(jī)器人數(shù)量等仿真環(huán)境，同時利用不同的路徑規(guī)劃算法模擬多移動機(jī)器人系統(tǒng)執(zhí)行分揀任務(wù)，輸出各種仿真數(shù)據(jù)。本仿真系統(tǒng)的界面設(shè)計如圖10所示。

仿真系統(tǒng)界面左側(cè)是多機(jī)器人系統(tǒng)運(yùn)行區(qū)域，用于顯示仿真系統(tǒng)中多移動機(jī)器人執(zhí)行任務(wù)的情況。倉儲地圖環(huán)境采用35×25規(guī)格的柵格地圖表示，整個地圖區(qū)域中共320個貨架，每8個貨架相背排列成1組，共40組貨架。仿真系統(tǒng)界面右側(cè)是控制區(qū)域，包括所有的操作按鈕及用來設(shè)置機(jī)器人各種參數(shù)的編輯框。

在上述的智能倉儲仿真環(huán)境中進(jìn)行仿真實驗，驗證多機(jī)器人動態(tài)路徑規(guī)劃方法的有效性。為保證實驗結(jié)果的客觀性，設(shè)定實驗方法如下：

(1)所有任務(wù)都由隨機(jī)算法生成。機(jī)器人順序排列在地圖環(huán)境的上方位置。

(2)設(shè)置任務(wù)數(shù)量為300，隨機(jī)生成10組任務(wù)。對比機(jī)器人數(shù)量分為10、20、30、40和50時執(zhí)行相同任務(wù)的情況。每種情況下分別采用本文的動態(tài)路徑規(guī)劃方法和傳統(tǒng)的A*算法完成隨機(jī)生成的10組任務(wù)，共100次實驗。

(3)按照就近分配的原則為每臺機(jī)器人分配任務(wù)，保證機(jī)器人的空閑時間最短。

圖10 仿真系統(tǒng)主界面

機(jī)器人遇到交通堵塞的情況如圖11所示，機(jī)器人r1在沿原規(guī)劃路徑行進(jìn)到當(dāng)前道路的關(guān)鍵節(jié)點(diǎn)時遇到了道路擁堵。圖12使用了不同的灰度值表示當(dāng)前交通擁堵地圖中的每個柵格的擁堵概率，柵格的顏色越深，該處的擁堵程度越高。圖13中，機(jī)器人r1根據(jù)當(dāng)前交通擁堵地圖以當(dāng)前點(diǎn)為起點(diǎn)重新進(jìn)行路徑規(guī)劃，選擇通過交通擁堵代價更小的路徑，減少完成任務(wù)所需的時間。

圖11 機(jī)器人遇到交通堵塞的情況

圖12 交通擁堵地圖表示阻塞情況

圖13 動態(tài)路徑規(guī)劃算法重新規(guī)劃路徑

圖14給出了不同數(shù)量配置的機(jī)器人在2種路徑規(guī)劃算法下完成300個任務(wù)所運(yùn)行總里程，所取數(shù)據(jù)為10次實驗的平均值。由于增加機(jī)器人數(shù)量可以為多機(jī)器人系統(tǒng)提供更高的靈活性，系統(tǒng)可以選取離貨架更近的機(jī)器人完成任務(wù)，所以隨著機(jī)器人數(shù)量的增加，多機(jī)器人系統(tǒng)完成所有任務(wù)的總里程逐漸減少。對于相同數(shù)量的機(jī)器人，使用動態(tài)路徑規(guī)劃方法進(jìn)行路徑規(guī)劃的機(jī)器人系統(tǒng)完成任務(wù)運(yùn)行的總里程比使用傳統(tǒng)的A*算法要長。隨著機(jī)器人數(shù)量的增加，系統(tǒng)的交通堵塞情況增加，使用動態(tài)路徑規(guī)劃方法進(jìn)行路徑規(guī)劃的機(jī)器人為了避開交通堵塞而選擇了繞路的方式減少等待時間，因而增加了里程數(shù)。

圖15給出了不同數(shù)量配置的機(jī)器人在2種路徑規(guī)劃算法下完成300個任務(wù)所運(yùn)行總時間，所取數(shù)據(jù)為10次實驗的平均值?？梢钥闯鲭S著機(jī)器人數(shù)量的增加，多機(jī)器人系統(tǒng)完成所有任務(wù)的總時間逐漸減少。

圖14 系統(tǒng)完成任務(wù)運(yùn)行總里程

圖15 系統(tǒng)完成任務(wù)運(yùn)行總時間

從表3可以直觀地看出，當(dāng)智能倉儲系統(tǒng)中的機(jī)器人數(shù)量大于等于30時，本文的動態(tài)路徑規(guī)劃方法相對普通的交通規(guī)則下的A*算法其完成任務(wù)總的運(yùn)行時間有明顯的減少。在倉儲環(huán)境下，本文的動態(tài)路徑規(guī)劃方法也不能完全地避免道路擁堵的發(fā)生，當(dāng)機(jī)器人數(shù)量增加到一定數(shù)目后，系統(tǒng)運(yùn)行效率明顯降低，繼續(xù)增加機(jī)器人的數(shù)量并不能明顯減少完成相同任務(wù)所用的總時間。因此為了提高智能倉儲系統(tǒng)運(yùn)行效率，根據(jù)倉儲系統(tǒng)大小合理調(diào)整機(jī)器人的數(shù)量十分必要。

表3 2種算法運(yùn)行總時間對比

5 結(jié) 論

為解決智能倉儲系統(tǒng)多機(jī)器人路徑規(guī)劃問題，提出了一種預(yù)約柵格和交通擁堵地圖下多機(jī)器人動態(tài)路徑規(guī)劃算法。通過對A*算法的改進(jìn)，實現(xiàn)了多機(jī)器人的動態(tài)協(xié)同路徑規(guī)劃，解決了機(jī)器人間的交通擁堵問題，提高了系統(tǒng)效率。實驗結(jié)果表明，相對于傳統(tǒng)的A*算法，使用動態(tài)路徑規(guī)劃方法進(jìn)行路徑規(guī)劃可以有效減少多機(jī)器人系統(tǒng)完成任務(wù)所需的時間，但是當(dāng)機(jī)器人達(dá)到一定數(shù)量后，由于系統(tǒng)的擁堵程度增加，完成任務(wù)所需總時間的減少變得緩慢，因此進(jìn)行多機(jī)器人系統(tǒng)規(guī)劃時需要根據(jù)倉庫大小合理配置機(jī)器人數(shù)量。在多機(jī)器人智能倉儲系統(tǒng)中，訂單任務(wù)分配方式也會影響系統(tǒng)工作效率。未來將研究智能倉儲系統(tǒng)中的訂單任務(wù)分配方式，并將其與多機(jī)器人的路徑規(guī)劃結(jié)合，進(jìn)一步提升智能倉儲系統(tǒng)工作效率。