辜 勇，段晶晶，袁源乙，蘇宇霞

（武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢 430063）

1 引言

智能倉庫中移動(dòng)機(jī)器人有助于促進(jìn)倉庫無人化操作及自動(dòng)化運(yùn)轉(zhuǎn)。隨著市場不斷擴(kuò)大，單個(gè)機(jī)器人難以滿足日益復(fù)雜、繁多的任務(wù)需求，多機(jī)器人協(xié)同作業(yè)系統(tǒng)[1]應(yīng)運(yùn)而生，其具有更強(qiáng)的魯棒性和環(huán)境適應(yīng)性。其中多機(jī)器人的路徑規(guī)劃[2]是實(shí)現(xiàn)當(dāng)前多機(jī)器人系統(tǒng)在智能倉儲(chǔ)中應(yīng)用的研究熱點(diǎn)。智能倉庫中多機(jī)器人路徑規(guī)劃是指，在倉庫復(fù)雜動(dòng)態(tài)環(huán)境下多倉儲(chǔ)機(jī)器人能夠無碰撞、快速地完成揀選任務(wù)。根據(jù)多機(jī)器人路徑規(guī)劃的特點(diǎn)，該問題可以轉(zhuǎn)化為多維旅行商問題（Multidimensional Traveling Salesman Problem,MTSP）[3]。相對于旅行商問題（Traveling Salesman Problem,TSP），多個(gè)TSP的單純疊加不能構(gòu)成MTSP的全局最優(yōu)解，還需要考慮多機(jī)器人相互之間的協(xié)調(diào)、避碰。因此本文提出一種基于遺傳算法和A*算法相結(jié)合的混合算法解決倉儲(chǔ)機(jī)器人多目標(biāo)路徑規(guī)劃問題。

多機(jī)器人路徑規(guī)劃屬于NP-hard問題，主要解決算法有：傳統(tǒng)算法[4]、智能優(yōu)化算法[5]和其它算法等。其中遺傳算法[6]是一種典型的智能算法，它通過模擬生物體遺傳變異得到優(yōu)勢種群的過程來解決問題，具有隨機(jī)并行搜索能力，能夠快速搜索尋找全局最優(yōu)解。Bajrami,等[7]針對封閉條件下的靜態(tài)和動(dòng)態(tài)障礙物環(huán)境，利用遺傳算法進(jìn)行路徑規(guī)劃取得較好效果。裴以建,等[8]在遺傳過程中增加插入算子、刪除算子，使得機(jī)器人得到優(yōu)化后的無障礙路徑。但大多數(shù)算法并不適應(yīng)多機(jī)器人協(xié)同系統(tǒng)，未從整體出發(fā)，將多機(jī)器人路徑?jīng)_突與整體路徑規(guī)劃進(jìn)行結(jié)合。

機(jī)器人行駛過程中，避免相互之間的局部動(dòng)態(tài)沖突是多機(jī)器人規(guī)劃的關(guān)鍵問題。可采用交通規(guī)則[9]規(guī)定倉庫行駛方向，從而降低沖突發(fā)生數(shù)目，但犧牲了倉庫通道的利用率，而且仍存在不可避免的沖突。也可采用速度調(diào)整法[10]，借助增大或降低機(jī)器人速率等策略來避開沖突，該方法對系統(tǒng)性能要求比較高。夏清松,等[11]通過對機(jī)器人進(jìn)行優(yōu)先級排序，化解不同類型路徑?jīng)_突。通過以上文獻(xiàn)分析可知，優(yōu)先級法雖然簡單易行、效率較高，但忽視了從減少路徑?jīng)_突數(shù)目的角度考慮問題。在實(shí)際路徑規(guī)劃中，A*算法[12]作為一種啟發(fā)式算法，通過啟發(fā)函數(shù)將搜索方向指向目標(biāo)點(diǎn)，該算法對環(huán)境信息敏感，能直接有效應(yīng)對動(dòng)態(tài)環(huán)境下路徑規(guī)劃問題，根據(jù)優(yōu)先級不同可迅速調(diào)整路徑。

本文從多機(jī)器人協(xié)調(diào)配合出發(fā)，利用A*算法規(guī)劃各機(jī)器人兩兩目標(biāo)點(diǎn)之間的最優(yōu)路徑，并結(jié)合不同機(jī)器人的優(yōu)先級得到全局路徑；然后引入改進(jìn)遺傳算法調(diào)整目標(biāo)節(jié)點(diǎn)遍歷序列和化解路徑?jīng)_突方式，以實(shí)現(xiàn)多機(jī)器人路徑規(guī)劃全局最優(yōu)。

2 環(huán)境建模

合理的倉庫環(huán)境建模方法有助于后續(xù)路徑規(guī)劃算法的設(shè)計(jì)。本文利用柵格建模法，提出一個(gè)高效、可重構(gòu)的自動(dòng)化倉庫模型，如圖1所示。倉庫由貨架、揀選臺、停放點(diǎn)和可行道路四部分組成，劃分成30×30的柵格。倉庫正中間擺放立體貨架用來容納倉儲(chǔ)貨物，是倉庫的主體部分；倉庫左側(cè)均勻分布4個(gè)分揀臺，機(jī)器人將貨物搬運(yùn)到這里進(jìn)行分揀；倉庫左下方為機(jī)器人停放點(diǎn)，為機(jī)器人充電或暫時(shí)停放空閑機(jī)器人。倉庫中空白柵格是行駛道路，每排貨架之間、每列貨架之間均為單車道。

智能倉庫的作業(yè)流程為：每個(gè)倉儲(chǔ)機(jī)器人都有n個(gè)揀選任務(wù)，分布在不同的貨架節(jié)點(diǎn)，各機(jī)器人需遍歷其目標(biāo)節(jié)點(diǎn)完成揀選任務(wù)。倉儲(chǔ)物流機(jī)器人在收到出貨指令后快速響應(yīng)，揀選所需貨物，然后包裝出庫。

圖1 倉庫地圖模型

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

在智能倉庫中，每個(gè)機(jī)器人根據(jù)目標(biāo)任務(wù)，需要規(guī)劃無碰撞、高效率的路徑進(jìn)行揀選作業(yè)?；舅悸肥怯肁*算法計(jì)算兩兩節(jié)點(diǎn)之間的路徑，按照目標(biāo)節(jié)點(diǎn)的遍歷順序，得到單個(gè)機(jī)器人的全局路徑規(guī)劃；然后檢查機(jī)器人路徑間是否存在沖突。若存在沖突，則利用優(yōu)先級法化解沖突，再繼續(xù)檢查是否存在新沖突，直到所有路徑之間無沖突產(chǎn)生。

3.1 A＊算法

本文采用A*算法進(jìn)行路徑尋優(yōu)。該算法設(shè)置open表和close表，搜索過程從初始節(jié)點(diǎn)出發(fā)，將其相鄰節(jié)點(diǎn)加入open表；通過估算相鄰節(jié)點(diǎn)的路徑代價(jià)f(n)，選擇f(n)最小的節(jié)點(diǎn)更新為當(dāng)前節(jié)點(diǎn)，加入close表；重復(fù)該過程，直到到達(dá)目標(biāo)節(jié)點(diǎn)。f(n)的計(jì)算公式是：

其中，g(n)指從初始節(jié)點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)n的代價(jià)，h(n)指從當(dāng)前節(jié)點(diǎn)n移動(dòng)到目標(biāo)節(jié)點(diǎn)所需的代價(jià)。兩者之和為f(n)，指經(jīng)過當(dāng)前節(jié)點(diǎn)n的總路徑代價(jià)。

3.2 沖突類型及化解

本文假設(shè)：（1）倉庫道路均為雙向單車道，僅允許單個(gè)機(jī)器人通過，可雙向行駛；（2）各機(jī)器人的行駛速度保持不變，避免相互之間發(fā)生追趕沖突；（3）機(jī)器人運(yùn)行過程中不會(huì)出現(xiàn)意外故障；（4）每單位時(shí)間可行駛單位柵格距離，即1個(gè)單位路徑長度；（5）每個(gè)機(jī)器人執(zhí)行多個(gè)目標(biāo)任務(wù)，且每個(gè)任務(wù)只能由單個(gè)機(jī)器人完成。

在實(shí)際過程中多個(gè)機(jī)器人同時(shí)運(yùn)行作業(yè)，其中兩個(gè)或多個(gè)機(jī)器人同時(shí)到達(dá)某位置，便會(huì)產(chǎn)生沖突。若沖突不能被及時(shí)化解消除，甚至?xí)斐陕窂剿梨i。路徑?jīng)_突可分為以下3種典型類別：（1）相向沖突：指兩機(jī)器人在同車道相向行駛，其行駛方向呈180°夾角，兩者在同一時(shí)刻到達(dá)某節(jié)點(diǎn)。若發(fā)生該沖突，任一機(jī)器人暫停都會(huì)造成路徑堵塞。必須將其中一個(gè)機(jī)器人重新規(guī)劃路徑行駛，才能消除沖突。（2）交叉沖突：指兩個(gè)機(jī)器人的行駛方向呈90°夾角，同一時(shí)刻到達(dá)交叉路口某節(jié)點(diǎn)?；庠摏_突可采用暫停策略，例如機(jī)器人Robot1在t時(shí)刻占用沖突節(jié)點(diǎn)，另一個(gè)機(jī)器人Robot2暫停等待；等到t+1時(shí)刻，Robot1已經(jīng)安全通過，Robot2再占用沖突節(jié)點(diǎn)。結(jié)果是兩個(gè)機(jī)器人的總行駛路徑不變，僅增加一個(gè)單位的總行駛時(shí)間。（3）復(fù)合沖突：指相向沖突和交叉沖突同一時(shí)刻在同一個(gè)節(jié)點(diǎn)發(fā)生。具體如圖2所示。

圖2 路徑?jīng)_突類型

3.3 優(yōu)先級

優(yōu)先級是根據(jù)一定的準(zhǔn)則或目標(biāo)，給發(fā)生路徑?jīng)_突的機(jī)器人指定先后順序，有序化解路徑?jīng)_突。優(yōu)先級高的機(jī)器人占據(jù)沖突位置，繼續(xù)按照原路徑行駛；優(yōu)先級低的機(jī)器人可以選擇暫停，等待其他機(jī)器人行駛過后，再繼續(xù)前進(jìn)；優(yōu)先級低的機(jī)器人也可重新規(guī)劃路徑，避免路徑?jīng)_突的發(fā)生。化解沖突過程中，優(yōu)先級的確定準(zhǔn)則對倉庫總運(yùn)行效率有著重要影響。

各機(jī)器人在全局路徑規(guī)劃過程中，忽略其他機(jī)器人動(dòng)態(tài)變化。因此不僅會(huì)與其他機(jī)器人產(chǎn)生沖突，而且應(yīng)對路徑?jīng)_突而調(diào)整路徑后，會(huì)造成新的沖突。例如，在時(shí)刻t時(shí)，Robot1、Robot2、Robot3的初始規(guī)劃路徑如圖3（a）所示，各機(jī)器人在倉庫內(nèi)同時(shí)向各自目標(biāo)行駛?？梢灶A(yù)見全局路徑規(guī)劃中，在t+2時(shí)Robot1與Robot2發(fā)生沖突，在t+5時(shí)Robot1與Robot3發(fā)生沖突。當(dāng)正常行駛到t+2時(shí)，需要確定Robot1和Robot2的優(yōu)先級priority，此時(shí)有兩種優(yōu)先級順序：（1）priority1>priority2，那么Robot1和Robot2按照圖3（b）順序通過路口。之后在t+5時(shí)，再消除Rrobot1和Robot3之間的路徑?jīng)_突，如圖3（c）所示。（2）priority1

依據(jù)上述分析，本文提出圍繞動(dòng)態(tài)路徑規(guī)劃中的路徑?jīng)_突數(shù)目，決定優(yōu)先級大小。將某機(jī)器人在全局路徑規(guī)劃中與其他機(jī)器人形成的沖突數(shù)目，命名為該機(jī)器人的基本沖突數(shù)目conflict_basic。另外，假定其他機(jī)器人的路徑均不變化，令該機(jī)器人作為次優(yōu)先級，造成的新沖突數(shù)目稱為conflict_add。因此，本文提出機(jī)器人的總沖突數(shù)目為all_conflict，由式（2）得到。該值越大，機(jī)器人的優(yōu)先級越低；相反，優(yōu)先級越高。

因此，解決路徑?jīng)_突問題，首先應(yīng)計(jì)算沖突中各機(jī)器人的總沖突數(shù)目，沖突數(shù)越小，優(yōu)先級越高；若兩者沖突次數(shù)相同，則隨機(jī)選擇某機(jī)器人作為高優(yōu)先級。

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

隨著目標(biāo)節(jié)點(diǎn)的增多，倉儲(chǔ)機(jī)器人的多目標(biāo)點(diǎn)路徑規(guī)劃的復(fù)雜度也顯著提升。本節(jié)利用遺傳算法調(diào)節(jié)目標(biāo)節(jié)點(diǎn)的遍歷序列，根據(jù)問題的具體特征對變量進(jìn)行編碼，然后采用選擇、交叉、變異等遺傳操作，重復(fù)迭代后得到最優(yōu)或次優(yōu)解。

圖3 消除沖突序列圖

4.1 多目標(biāo)任務(wù)規(guī)劃建模

假設(shè)robot(i)的揀貨任務(wù)有n個(gè)目標(biāo)任務(wù)，將揀選目標(biāo)隨機(jī)排列順序，得到分揀順序?yàn)門i1,Ti2,...,Tin，其中任意兩個(gè)分揀節(jié)點(diǎn)Tix,Tiy之間的路徑為Ci(Tx,Ty)。robot(i)有n!種方式遍歷所有目標(biāo)節(jié)點(diǎn)。

按照上文中A*算法計(jì)算各目標(biāo)節(jié)點(diǎn)之間的路徑，可以得到robot(i)的距離矩陣Di：

在各機(jī)器人遍歷目標(biāo)節(jié)點(diǎn)的基礎(chǔ)上，化解局部路徑?jīng)_突，才能得到可行的全局路徑長度，繼而轉(zhuǎn)化為遺傳算法中目標(biāo)函數(shù)Z，即：

式中，L表示多機(jī)器人消除局部路徑?jīng)_突后，完成全部目標(biāo)任務(wù)所需的路徑長度；v表示機(jī)器人勻速行駛速度。twait表示各機(jī)器人為解決路徑?jīng)_突所耗費(fèi)的總等待時(shí)間。

4.2 符號矩陣編碼法

常見編碼方式包括二進(jìn)制編碼法、矩陣編碼法、浮點(diǎn)編碼法、符號編碼法等。符號編碼法是指將個(gè)體染色體的基因值取為符號集，如{A1,A2,...,B1,B2,...}。矩陣編碼法是指用矩陣的形式表示染色體基因。

根據(jù)問題特性，結(jié)合符號編碼和矩陣編碼的優(yōu)點(diǎn)，創(chuàng)新編碼方式，提出符號矩陣編碼法。一方面，本問題中多目標(biāo)節(jié)點(diǎn)各不相同，具有唯一性，可采用符號代表目標(biāo)任務(wù)節(jié)點(diǎn)；另一方面，每個(gè)機(jī)器人的任務(wù)已分配完成，相互之間獨(dú)立，利用矩陣將多個(gè)機(jī)器人的目標(biāo)節(jié)點(diǎn)進(jìn)行組合排列。

將robot(i)的n個(gè)目標(biāo)節(jié)點(diǎn)隨機(jī)分布排列為其中共有m個(gè)robot，可以組成單個(gè)染色體，即：

式中，chrom(k)表示第k個(gè)染色體，是m×n維矩陣，每一行表示單個(gè)機(jī)器人的目標(biāo)任務(wù)節(jié)點(diǎn)。

4.3 遺傳操作

在遺傳過程中，“選擇”操作選擇優(yōu)勢個(gè)體、“交叉”操作交換個(gè)體的染色體基因、“變異”操作指個(gè)體染色體基因突變，產(chǎn)生新個(gè)體。這三種遺傳操作幫助優(yōu)勢群體基因存活下來。與此對應(yīng)的是選擇算子、交叉算子和變異算子。

（1）選擇操作。本文利用輪盤賭選擇法，根據(jù)各個(gè)個(gè)體的適應(yīng)度大小來決定該個(gè)體基因保留的可能性，適應(yīng)度越大，被選擇的概率就越大；反之亦然。某個(gè)體適應(yīng)度為fi，種群大小為NP，則它被選擇的概率為：

（2）交叉算子。常見交叉算子主要有：單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉等。由于本文中每個(gè)個(gè)體染色體包含多個(gè)目標(biāo)節(jié)點(diǎn)，每個(gè)robot的目標(biāo)節(jié)點(diǎn)為一行，行與行之間不相同。因此選擇多點(diǎn)交叉算子。即在個(gè)體染色體矩陣編碼中的每行都選擇交叉點(diǎn)，然后兩兩個(gè)體配對交叉。

（3）變異算子。本文采用實(shí)值變異方式，把相應(yīng)的基因用取值范圍內(nèi)的其他隨機(jī)基因代替。

4.4 算法流程圖

針對倉儲(chǔ)機(jī)器人群的多目標(biāo)點(diǎn)路徑規(guī)劃，融合改進(jìn)優(yōu)先級策略和遺傳算法，可以得到本文的算法流程。首先建立各個(gè)移動(dòng)機(jī)器人關(guān)于目標(biāo)節(jié)點(diǎn)的路徑信息表；然后依照改進(jìn)優(yōu)先級法計(jì)算總行駛時(shí)間，并轉(zhuǎn)化為遺傳算法中種群的個(gè)體適應(yīng)度；對種群進(jìn)行選擇、交叉、變異操作；經(jīng)過數(shù)次迭代，得到最優(yōu)個(gè)體，即為最優(yōu)路徑規(guī)劃結(jié)果。如圖4所示。

圖4 流程圖

5 模型仿真實(shí)驗(yàn)

為驗(yàn)證本文算法改進(jìn)的有效性，在圖1倉庫地圖模型的基礎(chǔ)上，將本文提出的基于遺傳算法的倉儲(chǔ)機(jī)器人多目標(biāo)路徑規(guī)劃方法（簡稱算法1）與基于常規(guī)優(yōu)先級法的路徑規(guī)劃算法[11]（簡稱算法2）以及交通規(guī)則下的路徑規(guī)劃算法[9]（簡稱算法3）進(jìn)行比較，證明基于遺傳算法的倉儲(chǔ)機(jī)器人多目標(biāo)路徑規(guī)劃算法能有效提高多倉儲(chǔ)機(jī)器人系統(tǒng)的運(yùn)行效率。其中算法2和算法3均為目前普遍使用的先規(guī)劃最短路徑，再進(jìn)行動(dòng)態(tài)路徑規(guī)劃的算法。

仿真實(shí)驗(yàn)基于相同數(shù)量的機(jī)器人，運(yùn)用不同規(guī)劃算法，執(zhí)行不同任務(wù)數(shù)量，比較算法的路徑規(guī)劃長度和行駛時(shí)間。機(jī)器人數(shù)量為5，目標(biāo)任務(wù)數(shù)量依次為15，20，25，30，35，40。其中算法1由于基于遺傳算法，每次運(yùn)行結(jié)果可能不盡相同。因此每個(gè)任務(wù)量都運(yùn)行100次后，選擇眾數(shù)作為算法1的實(shí)驗(yàn)結(jié)果。算法的路徑長度對比結(jié)果如圖5所示。

圖5 不同算法的路徑長度比較

首先比較不同算法規(guī)劃的路徑長度?？偟膩碚f，隨著任務(wù)量的增加，總路徑長度均呈上升趨勢。在任務(wù)量較少時(shí)，路徑之間的沖突較少，算法1和算法2的路徑長度幾乎沒有差別，算法3因交通限制致使繞路行駛，導(dǎo)致路徑較長。隨著任務(wù)量逐漸增加，算法1逐漸優(yōu)于算法2。這是由于路徑?jīng)_突數(shù)目的增加，算法1通過計(jì)算沖突數(shù)目和路徑長度，調(diào)整了目標(biāo)節(jié)點(diǎn)的序列，從而有效縮短了路徑長度。算法3隨任務(wù)量的增加，多機(jī)器人之間由于交通規(guī)則存在，路徑?jīng)_突對其影響不大，所以路徑長度增長緩慢，后期優(yōu)于算法2。

對3種算法的行駛時(shí)間進(jìn)行比較，具體如圖6所示?？傏厔莺蛨D5的路徑長度趨勢相似，呈上升態(tài)勢。由于算法1能有效減少路徑?jīng)_突數(shù)目，且路徑長度并沒有太大變化，從而節(jié)約了更多的時(shí)間，因此在總行駛時(shí)間方面的優(yōu)勢更加明顯。

圖6 不同算法的總行駛時(shí)間比較

6 結(jié)束語

本文針對智能倉庫多機(jī)器人協(xié)調(diào)分揀作業(yè)過程，提出一種基于遺傳算法的倉儲(chǔ)機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃方法。根據(jù)機(jī)器人間路徑?jīng)_突類型以及總沖突數(shù)目，調(diào)整優(yōu)先級排序化解沖突；然后將多目標(biāo)規(guī)劃與機(jī)器人路徑規(guī)劃進(jìn)行融合，運(yùn)用遺傳算法從全局出發(fā)，調(diào)整倉庫總體運(yùn)行效率。最后通過仿真實(shí)驗(yàn)，驗(yàn)證了該方法的可行性和高效性。.