郭 超,陳香玲,郭 鵬,王 強(qiáng),汪世杰

1(宜賓職業(yè)技術(shù)學(xué)院 智能制造學(xué)院,宜賓 644003)

2(西南交通大學(xué) 機(jī)械工程學(xué)院,成都 610031)

3(軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室,成都 610031)

4(航空工業(yè)成都飛機(jī)工業(yè)(集團(tuán))有限責(zé)任公司,成都 610073)

1 引言

快遞業(yè)務(wù)量自2010年的不足24 億件,迅速攀升到2020年的833.6 億件.劇增的快遞業(yè)務(wù)量對(duì)配送效率提出了更高的要求,使得各大快遞企業(yè)不斷導(dǎo)入新的技術(shù)和手段.為了實(shí)現(xiàn)高效快捷的包裹配送,超過(guò)60%的物流配送中心裝備了分揀系統(tǒng)[1].采用自動(dòng)導(dǎo)引車(automated guided vehicle,AGV)分揀的系統(tǒng)具有高度無(wú)人化、自動(dòng)化、智能化等優(yōu)勢(shì),但多AGV 分揀作為高度復(fù)雜的集成系統(tǒng),需要合理的集群調(diào)度方案和路徑優(yōu)化策略方能保證所有AGV 得到高效利用,并在盡可能短的時(shí)間內(nèi)完成包裹的分揀.多個(gè)AGV 在分揀中心同時(shí)作業(yè)時(shí),需為每個(gè)AGV 合理規(guī)劃路徑,避免AGV 間發(fā)生沖突、死鎖等情況,保持整個(gè)分揀系統(tǒng)的正常運(yùn)行.

多AGV 路徑規(guī)劃旨在為每個(gè)AGV 規(guī)劃一條合適的路線,以便在AGV 運(yùn)行空間內(nèi)將物品從起點(diǎn)移動(dòng)到目的地.研究多AGV 路徑規(guī)劃問(wèn)題對(duì)于快遞包裹分揀效率的提升具有積極的理論和應(yīng)用意義.業(yè)界對(duì)于多AGV 路徑規(guī)劃的需求包括以下3 個(gè)方面:(1)隨著包裹數(shù)量和土地成本的急劇升高,倉(cāng)儲(chǔ)對(duì)于密集的多AGV 轉(zhuǎn)運(yùn)系統(tǒng)需求日益增強(qiáng),因而對(duì)于在此環(huán)境下保持多AGV 系統(tǒng)高效運(yùn)行的技術(shù)理論存在迫切需求;(2)隨著消費(fèi)產(chǎn)業(yè)愈發(fā)成熟,商品種類迅速增多,AGV面臨的任務(wù)特點(diǎn)和任務(wù)要求也越發(fā)復(fù)雜.除搬運(yùn)到指定位置外,還面臨平穩(wěn)、快速、大體積、超重搬運(yùn)等多種搬運(yùn)需求,使得多AGV 路徑規(guī)劃也面臨新的挑戰(zhàn);(3)隨著5G 高速通信和輕量化深度學(xué)習(xí)技術(shù)的出現(xiàn),AGV 系統(tǒng)的搭建存在更多新的技術(shù)選擇,以遠(yuǎn)程檢測(cè)和視覺(jué)導(dǎo)航為代表的新興AGV 技術(shù)使得多AGV路徑規(guī)劃面臨新的約束和場(chǎng)景.本文聚焦多AGV 路徑規(guī)劃在無(wú)碰撞要求下的算法改進(jìn),瞄準(zhǔn)上述所提的需求(1).

針對(duì)多AGV 路徑規(guī)劃,其制定的線路須確保各臺(tái)AGV 不會(huì)發(fā)生碰撞和死鎖等,且需要實(shí)現(xiàn)最短行駛時(shí)間、最短距離長(zhǎng)度或最少能量消耗等目標(biāo).選擇合適的路線對(duì)系統(tǒng)的性能有一定的影響,AGV 分揀單件包裹的時(shí)間越長(zhǎng),在給定時(shí)間周期內(nèi)可以處理的分揀任務(wù)就越少.因此,國(guó)內(nèi)外學(xué)者對(duì)多AGV 路徑規(guī)劃問(wèn)題進(jìn)行了大量的研究,主要的解決方法有精確算法、啟發(fā)式算法、人工智能和仿真模擬等[2].在精確算法方面,Langevin 等[3]采用動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)對(duì)兩臺(tái)AGV 調(diào)度與無(wú)沖突路徑規(guī)劃相結(jié)合的優(yōu)化問(wèn)題求解.Desaulniers等[4]提出了結(jié)合貪婪搜索、列生成和分支切割的精確算法,可以解決最多4 臺(tái)AGV 的情況.但該算法存在一定的局限性,其效率高度依賴于啟發(fā)式算法的性能,如果搜索啟發(fā)式方法不能找到可行解,則不能找到最優(yōu)解.與精確算法相比,啟發(fā)式方法的優(yōu)勢(shì)在于求解速度快,適合解決大規(guī)模問(wèn)題.對(duì)于AGV 路徑規(guī)劃,A*算法成為多數(shù)研究的首選方法,譬如改進(jìn)A*算法[5-7]、變步長(zhǎng)雙向A*算法[8]、時(shí)空沖突約束A*算法[9],并且在諸多場(chǎng)景中得到了應(yīng)用,包括智能泊車[10]、自動(dòng)駕駛[11]等.關(guān)于A*算法的更多應(yīng)用已由Foead 等進(jìn)行了總結(jié)[12].除此之外,遺傳算法[13]、人工蜂群算法[14]、迭代貪婪算法[15]、蟻群算法[16]等元啟發(fā)式算法也相繼被用于解決AGV 路徑規(guī)劃.隨著人工智能技術(shù)的日益成熟,部分學(xué)者也將人工智能算法用于解決多AGV 路徑規(guī)劃問(wèn)題,并取得了一定的效果[17].Srivastava 等[18]提出了基于智能體的框架來(lái)克服沖突和死鎖等問(wèn)題,該框架通過(guò)整合路徑生成、旅程時(shí)間計(jì)算、碰撞識(shí)別和死鎖識(shí)別等不同活動(dòng)來(lái)控制AGV 的運(yùn)行.劉輝等[19]提出了多智能體獨(dú)立強(qiáng)化學(xué)習(xí)算法,用于同時(shí)優(yōu)化多AGV 的任務(wù)調(diào)度和路徑規(guī)劃.仿真模擬法可以更加直觀地反應(yīng)每個(gè)AGV 的作業(yè)情況,Ashayeri 等[20]介紹了交互式微型計(jì)算機(jī)自動(dòng)物料搬運(yùn)系統(tǒng)的GPSS 仿真程序生成器.Um 等[21]提出了基于多AGV 的柔性制造系統(tǒng)仿真設(shè)計(jì)與分析方法.Kim 等[22]提出了面向?qū)ο蟮姆抡娼－h(huán)境-AgvTalk,為AGV 系統(tǒng)的仿真提供靈活的建模能力.

現(xiàn)有多AGV 路徑規(guī)劃研究大多是針對(duì)二維平面環(huán)境,盡管存在時(shí)間窗模型等考慮時(shí)效約束的研究,但是少有研究系統(tǒng)地從時(shí)空維度動(dòng)態(tài)地解決路徑規(guī)劃問(wèn)題.即將基于時(shí)間的搜索與基于空間的搜索結(jié)合起來(lái),以實(shí)現(xiàn)算法計(jì)算時(shí)間開(kāi)支最小與路徑規(guī)劃空間距離最短的均衡.

從這一角度出發(fā),本文首先根據(jù)物流分揀中心的場(chǎng)地特點(diǎn)選擇合適的地圖建模方法,然后將時(shí)間維度導(dǎo)入A*算法,將其改進(jìn)為時(shí)空A*算法,并將時(shí)空A*算法作為基于沖突搜索框架的下層規(guī)劃器,用于求解多AGV無(wú)沖突路徑規(guī)劃問(wèn)題.對(duì)上述兩種算法的融合,旨在優(yōu)勢(shì)互補(bǔ)為解決路徑規(guī)劃中的沖突問(wèn)題提供新的求解思路.最后,通過(guò)仿真實(shí)驗(yàn)驗(yàn)證所提算法在不同沖突情況下的求解效果.

2 地圖選擇與單AGV 路徑規(guī)劃

2.1 地圖選擇

生成AGV無(wú)沖突路徑方案首先需要構(gòu)建地圖模型.只有在AGV 工作環(huán)境已知的情況下才能利用有效的路徑規(guī)劃算法為AGV 找到合適的行駛路線,而環(huán)境信息的描述正是通過(guò)建立地圖模型實(shí)現(xiàn)的.環(huán)境信息描述的準(zhǔn)確性和復(fù)雜程度受到地圖建模方式的影響,進(jìn)而影響路徑規(guī)劃的決策效率和響應(yīng)速度,因此選擇合適的地圖建模方法是非常有必要的[23].

柵格地圖法是將已知的工作環(huán)境劃分為大小相同的固定柵格.如圖1所示,柵格按照顏色的不同分為黑白兩種,黑色柵格表示障礙物,白色柵格表示可通行區(qū)域.若障礙物位置變化,僅需調(diào)整柵格的占用情況.柵格法構(gòu)建地圖時(shí)需要確定柵格尺寸,柵格地圖的精度與柵格尺寸密切相關(guān),尺寸越小精度越高.若地圖精度過(guò)高,需要占用大量存儲(chǔ)空間且計(jì)算時(shí)間過(guò)長(zhǎng),但如果精度過(guò)低,又會(huì)影響AGV 移動(dòng)和定位的準(zhǔn)確性,因此選擇合適的柵格尺寸尤為重要.一般來(lái)說(shuō),以AGV 車體的大小為基準(zhǔn)設(shè)置柵格的尺寸,即可滿足地圖的精度需求.針對(duì)物流分揀中心布局規(guī)則、場(chǎng)地平坦、障礙物少等特征,柵格地圖法優(yōu)勢(shì)明顯,因此在后續(xù)的多AGV路徑規(guī)劃算法研究中采用柵格地圖法建立地圖模型.

圖1 柵格地圖法示意圖

2.2 單臺(tái)AGV 路徑規(guī)劃

當(dāng)分揀系統(tǒng)中僅有一臺(tái)AGV 工作時(shí),不存在路徑?jīng)_突問(wèn)題.本文單AGV 最優(yōu)路徑規(guī)劃問(wèn)題選用A*算法進(jìn)行搜索.A*算法利用評(píng)價(jià)函數(shù)在每次搜索時(shí)都對(duì)所有可擴(kuò)展點(diǎn)進(jìn)行評(píng)估,從而找到每次搜索的最佳擴(kuò)展點(diǎn),直至找到目標(biāo)節(jié)點(diǎn).使用評(píng)價(jià)函數(shù)的好處在于可以避免搜索過(guò)多無(wú)用的點(diǎn),算法的搜索效率得以提高.評(píng)價(jià)函數(shù)如下:

其中,f(i)表示從起點(diǎn)經(jīng)由節(jié)點(diǎn)i到達(dá)終點(diǎn)的路徑代價(jià)估計(jì)值;g(i)表示節(jié)點(diǎn)i距離起點(diǎn)的路徑代價(jià)實(shí)際值;h(i)表示節(jié)點(diǎn)i距離終點(diǎn)的路徑代價(jià)估計(jì)值.A*算法在每次搜索時(shí),選擇擁有最小f(i)值的節(jié)點(diǎn)作為下一次搜索的節(jié)點(diǎn).

分揀中心的AGV 通常是水平方向或豎直方向行走,不會(huì)出現(xiàn)斜著走的情況.因此設(shè)置A*算法的搜索方向?yàn)樗泥徲?即如圖2所示的節(jié)點(diǎn)擴(kuò)展方式.以四鄰域搜索方式擴(kuò)展節(jié)點(diǎn)時(shí),A*算法的啟發(fā)函數(shù)使用曼哈頓距離,其計(jì)算表達(dá)式如下:

圖2 四鄰域搜索方式

式(2)中,D表示相鄰兩個(gè)節(jié)點(diǎn)的移動(dòng)距離;xi和yi分別表示節(jié)點(diǎn)i的橫縱坐標(biāo);xj和yj分別表示終點(diǎn)j的橫縱坐標(biāo).

3 基于沖突搜索的多AGV 路徑規(guī)劃算法

在實(shí)際的分揀場(chǎng)景中通常多輛AGV 同時(shí)執(zhí)行分揀任務(wù),此時(shí),AGV 間可能會(huì)發(fā)生沖突.傳統(tǒng)的A*算法只能解決單AGV 路徑規(guī)劃問(wèn)題,而多AGV 路徑規(guī)劃問(wèn)題本質(zhì)上就是各AGV 相互協(xié)作,在保證不發(fā)生碰撞的前提下完成被分配的任務(wù),因此需要改進(jìn)傳統(tǒng)的A*算法使之能夠解決多AGV 路徑規(guī)劃問(wèn)題.

沖突搜索是由Sharon 等[24]提出的多Agent 路徑規(guī)劃(multi-agent pathfinding,MAPF)問(wèn)題求解框架.在本文中Agent 即AGV.該算法由上下兩層搜索結(jié)構(gòu)組成,在上層搜索中,使用二叉樹(shù)尋找多個(gè)AGV 間的沖突,如果存在沖突,則施加相應(yīng)的約束用于下層搜索;在下層搜索中,將MAPF 分解為多個(gè)單AGV,運(yùn)用單AGV 路徑規(guī)劃算法分別為每個(gè)AGV 規(guī)劃路徑.本文在下層搜索中使用的單AGV 路徑規(guī)劃算法為時(shí)空A*算法.

3.1 沖突類型

在多AGV 環(huán)境中,不同的運(yùn)行情況會(huì)引發(fā)不同的沖突類型.本文主要考慮如圖3所示的兩種沖突.當(dāng)兩輛AGV 在同一路段上相向行駛時(shí)會(huì)發(fā)生圖3(a)所示的相向沖突,當(dāng)兩輛AGV 位于十字路口處且行駛方向垂直時(shí)會(huì)發(fā)生圖3(b)所示的節(jié)點(diǎn)沖突.假設(shè)所有AGV的行駛速度始終保持勻速,不會(huì)發(fā)生趕超等情況.

圖3 兩種沖突類型

3.2 時(shí)空A*算法

當(dāng)環(huán)境中只有一輛AGV 時(shí),AGV 在靜態(tài)的環(huán)境中不會(huì)發(fā)生沖突,只需在二維空間地圖中進(jìn)行路徑規(guī)劃.一旦環(huán)境中有多輛AGV 時(shí),運(yùn)行中的AGV 會(huì)成為其它AGV 的動(dòng)態(tài)障礙物,為此須在時(shí)間和空間兩個(gè)維度上對(duì)車輛進(jìn)行有序地控制.為了解決物流分揀中心中的多AGV 路徑規(guī)劃,考慮在二維空間地圖中加入時(shí)間維度,進(jìn)而拓展為三維時(shí)空地圖.

A*算法在二維空間地圖搜索時(shí)只需要記錄拓展節(jié)點(diǎn)的位置信息,在引入時(shí)間維度后,不僅需要記錄位置信息,還需要記錄在每個(gè)位置的時(shí)間信息.對(duì)傳統(tǒng)的A*算法進(jìn)行改進(jìn),將改進(jìn)后的算法命名為時(shí)空A*算法.在時(shí)空A*算法中將時(shí)間編碼為圖中的狀態(tài),時(shí)間是線性推進(jìn)的,將圖簡(jiǎn)化為時(shí)空樹(shù).時(shí)空搜索樹(shù)是在普通的搜索樹(shù)中加入時(shí)間節(jié)點(diǎn),樹(shù)每搜索一層,時(shí)間也隨之增加一個(gè)單位.

以圖4所示的小規(guī)模地圖為例,當(dāng)點(diǎn)A 為AGV起點(diǎn)時(shí),時(shí)空A*算法搜索的時(shí)空樹(shù)如圖5所示.

圖4 小規(guī)模示例地圖

圖5 小規(guī)模示例地圖時(shí)空樹(shù)

樹(shù)中每個(gè)分支點(diǎn)的字母表示節(jié)點(diǎn)位置,數(shù)字表示到達(dá)該位置的時(shí)間點(diǎn),搜索的起始時(shí)間設(shè)置為0,到達(dá)下一鄰接點(diǎn)需要一個(gè)單位的時(shí)間.從圖4 可以看到,A 點(diǎn)的鄰接點(diǎn)只有B 點(diǎn),所以樹(shù)的下一層只有位置B 及對(duì)應(yīng)的時(shí)間點(diǎn)1;B 點(diǎn)的鄰接點(diǎn)為A 點(diǎn)和C 點(diǎn),因此樹(shù)的下一層包含位置A 和位置C 及對(duì)應(yīng)的時(shí)間2;由于本章采用四鄰域方向,因此C 點(diǎn)的鄰接點(diǎn)為B 點(diǎn)、D 點(diǎn)和F 點(diǎn),A 點(diǎn)的鄰接點(diǎn)為B 點(diǎn),所以樹(shù)的下一層包含位置B、位置D 和位置F,時(shí)間點(diǎn)為3;以此類推,直至找到目標(biāo)節(jié)點(diǎn).本文提出算法的核心在于生成樹(shù)的過(guò)程,找到目標(biāo)節(jié)點(diǎn)的方法與一般的廣度優(yōu)先搜索類似,搜索以及產(chǎn)生路徑流程如圖6.

圖6 時(shí)空A*算法流程

3.3 基于沖突搜索

基于沖突搜索的核心思想是算法上層搜索路徑間存在的沖突,然后生成對(duì)應(yīng)的約束,下層找到滿足這些約束的路徑,如果新生成的路徑仍然存在沖突,則通過(guò)添加新的約束來(lái)解決沖突.可能發(fā)生的沖突分為點(diǎn)沖突和邊沖突.點(diǎn)沖突用元組＜Ak,Aa,v,t＞表示,其中Ak和Aa分別表示第k輛和第a輛AGV,v表示位置點(diǎn),t表示時(shí)間,意為Ak和Aa會(huì)在t時(shí)刻同時(shí)占據(jù)v點(diǎn).當(dāng)檢測(cè)到點(diǎn)沖突時(shí)會(huì)分別為兩輛AGV 施加約束＜Ak,v,t＞和＜Aa,v,t＞.邊沖突用元組＜Ak,Aa,v1,v2,t＞表示,意為Ak和Aa會(huì)在t時(shí)刻到t+1 時(shí)刻之間交換位置,也即是說(shuō)Ak從v1點(diǎn)移動(dòng)到v2點(diǎn),Aa從v2點(diǎn)移動(dòng)到v1點(diǎn).當(dāng)檢測(cè)到邊沖突時(shí)會(huì)分別為兩個(gè)AGV 施加約束＜Ak,v1,v2,t＞和＜Aa,v2,v1,t＞.

搜索沖突和添加約束的過(guò)程在算法上層的約束樹(shù)(constraint tree,CT)中進(jìn)行.CT 是二叉樹(shù),樹(shù)中的任一節(jié)點(diǎn)i都包括以下3 條內(nèi)容:

(1)i.constraint:一組約束,由所有被施加的約束構(gòu)成,每個(gè)約束都屬于某一AGV.

(2)i.solution:一個(gè)解決方案,由多條路徑組成的集合,路徑數(shù)即為AGV 個(gè)數(shù).解決方案只有當(dāng)每條路徑滿足所有約束時(shí)才可行,這些路徑是在下層搜索中找到的.

(3)i.cost:當(dāng)前解決方案i.solution的總成本,即所有路徑的成本總和.

約束樹(shù)的根節(jié)點(diǎn)包含的約束集合為空,因?yàn)楦?jié)點(diǎn)的策略是為對(duì)每輛AGV 的路徑進(jìn)行無(wú)約束搜索,顯然根節(jié)點(diǎn)的解決方案中的每條路徑都是忽略其它AGV的存在而找到的.若節(jié)點(diǎn)i的i.solution有效,則該節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn).若節(jié)點(diǎn)i的i.solution無(wú)效,即i.solution中的路徑存在沖突,則需要從節(jié)點(diǎn)i分支出兩個(gè)子節(jié)點(diǎn),并對(duì)兩個(gè)子節(jié)點(diǎn)分別施加新的約束.分支出兩個(gè)子節(jié)點(diǎn)是為了檢查兩種可能性,其目的是為了保證最優(yōu)性.兩個(gè)子節(jié)點(diǎn)會(huì)根據(jù)新施加的約束生成各自的解決方案和路徑總成本,算法的上層對(duì)約束樹(shù)進(jìn)行最佳優(yōu)先搜索,根據(jù)路徑總成本的大小對(duì)節(jié)點(diǎn)進(jìn)行排序.若兩個(gè)子節(jié)點(diǎn)的解決方案均有效,則返回?fù)碛凶钚÷窂娇偝杀镜慕鉀Q方案.若兩個(gè)子節(jié)點(diǎn)的解決方案均無(wú)效,則對(duì)擁有最小路徑總成本的節(jié)點(diǎn)進(jìn)行下一步擴(kuò)展,直至找到有效的解決方案.需要注意的是,新擴(kuò)展的子節(jié)點(diǎn)不需要保存父節(jié)點(diǎn)的所有約束,只需要保存最新的約束,然后通過(guò)其父節(jié)點(diǎn)遍歷從當(dāng)前節(jié)點(diǎn)到根節(jié)點(diǎn)的其它約束.

算法1.基于沖突搜索的算法流程輸入:環(huán)境地圖,AGV 數(shù)量,每個(gè)AGV 的起點(diǎn)和終點(diǎn).初始化根節(jié)點(diǎn)r 的r.constraint 為空集合;調(diào)用下層搜索獲得r.solution 和r.cost;將根節(jié)點(diǎn)r 放入OPEN 表中;while OPEN 表不為空 do i←OPEN 表中擁有最小i.cost 的點(diǎn);if i.solution 無(wú)沖突 then返回i.solution;c←i.solution 中的第一個(gè)沖突＜Ak,Aa,v,t＞;for c 中的每個(gè)AGV Ax do P←創(chuàng)建一個(gè)新節(jié)點(diǎn);P.constraint←i.constraint+＜Ax,v,t＞;P.solution←i.solution;Ax 調(diào)用下層搜索更新P.solution;P.cost←計(jì)算P.solution 的路徑長(zhǎng)度;將P 點(diǎn)放入OPEN 表中;end for end while

在為約束樹(shù)的節(jié)點(diǎn)添加新的約束后,調(diào)用下層搜索.下層搜索使用單AGV 路徑規(guī)劃算法,旨在為每個(gè)AGV 規(guī)劃出當(dāng)前約束下成本最小的路徑.本文采用時(shí)空A*算法作為下層規(guī)劃器.當(dāng)上層搜索檢測(cè)到?jīng)_突并施加相應(yīng)的約束后,下層搜索只需要對(duì)與新添加的約束相關(guān)聯(lián)的AGV 重新規(guī)劃路徑,其它AGV 的路徑無(wú)需重新規(guī)劃,因?yàn)樗鼈儧](méi)有被施加新的約束.時(shí)空A*算法通過(guò)時(shí)空樹(shù)進(jìn)行搜索,一旦為所有需要重新規(guī)劃路徑的AGV 找到了滿足約束的路徑后,所有路徑會(huì)從時(shí)間和空間兩個(gè)維度上進(jìn)行相互驗(yàn)證,從而判斷當(dāng)前的解決方案是否有效.

雖然在下層搜索中每條路徑都是單獨(dú)規(guī)劃的,但是為了盡量避免與其它已有路徑發(fā)生沖突,還引入了沖突規(guī)避表(conflict avoidance table,CAT).該表保存了所有AGV 的路徑信息,通過(guò)該表可以獲取任意節(jié)點(diǎn)在任意時(shí)刻的AGV 數(shù)量,即CAT 值.時(shí)空A*算法在評(píng)價(jià)時(shí)空樹(shù)中某一節(jié)點(diǎn)的兩個(gè)鄰接點(diǎn)時(shí),如果兩個(gè)鄰接點(diǎn)的評(píng)價(jià)函數(shù)值f(i)相同,則選擇CAT 值小的點(diǎn).基于沖突搜索的算法框架偽代碼如算法1所示.

4 多AGV無(wú)沖突路徑規(guī)劃仿真實(shí)驗(yàn)

為驗(yàn)證基于沖突搜索的多AGV 路徑規(guī)劃算法的有效性,以規(guī)模為8 個(gè)分揀臺(tái)和35 個(gè)投放口的分揀中心為仿真實(shí)例,生成對(duì)應(yīng)的柵格地圖,進(jìn)行3 組不同AGV 數(shù)量和分揀任務(wù)的仿真實(shí)驗(yàn).所有的仿真實(shí)驗(yàn)在配置為AMD Ryzen 5-4600U with Radeon Graphics CPU @ 2.10 GHz,16 GB 的個(gè)人電腦上運(yùn)行,用Python語(yǔ)言實(shí)現(xiàn).

柵格化后的地圖環(huán)境如圖7所示,四周的黑色障礙物為墻壁,墻壁內(nèi)部為AGV 的行駛區(qū)域,被劃分為18 行27 列,共計(jì)486 個(gè)柵格.柵格的大小以AGV 自身的大小為基準(zhǔn),每個(gè)柵格大小相同且具有各自的位置坐標(biāo)(x,y),其中x表示柵格所在行數(shù),y表示柵格所在列數(shù).從當(dāng)前柵格到達(dá)下一柵格需要耗費(fèi)一個(gè)單位的時(shí)間.障礙物的大小不同其占據(jù)的柵格數(shù)也不同,其中充電區(qū)占據(jù)9 個(gè)柵格,每個(gè)投放口占據(jù)1 個(gè)柵格,每個(gè)分揀臺(tái)占據(jù)2 個(gè)柵格.

圖7 柵格地圖

4.1 相向沖突仿真實(shí)驗(yàn)

本節(jié)仿真實(shí)驗(yàn)用于驗(yàn)證算法解決相向沖突的有效性,該仿真實(shí)例中有2 輛AGV 同時(shí)分揀,行駛路線如圖8所示.AGV1 的起點(diǎn)為坐標(biāo)(10,3)的柵格,即紅色圓圈所在位置,終點(diǎn)為坐標(biāo)(10,14)的柵格,即紅色方框所在位置.AGV2 的起點(diǎn)為坐標(biāo)(10,25)的柵格,即綠色圓圈所在位置,終點(diǎn)為坐標(biāo)(10,11)的柵格,即綠色方框所在位置.紅色線段為AGV1 的行駛路線,綠色線段為AGV2 的行駛路線.從圖中可以看出AGV1 并沒(méi)有從柵格(10,13)直接到達(dá)終點(diǎn)柵格(10,14),而是從柵格(10,13)到柵格(11,13),然后經(jīng)過(guò)柵格(11,14)才到達(dá)柵格(10,14),這樣是為了避免在柵格(10,14)與AGV2 發(fā)生沖突.二者路線從空間上存在交叉,但是基于所提出的時(shí)空搜索框架,二者在時(shí)間上并不會(huì)同時(shí)訪問(wèn)到任何一點(diǎn),因此避免了潛在的碰撞沖突.

圖8 雙AGV 相向行駛路線圖

圖9 為AGV1 和AGV2 按照?qǐng)D8所示的起點(diǎn)和終點(diǎn)相向行駛時(shí)的三維時(shí)空?qǐng)D,時(shí)空?qǐng)D的x軸和y軸表示柵格的位置坐標(biāo),z軸表示時(shí)間t,兩條線段分別表示兩輛AGV 的行駛路徑.通過(guò)時(shí)空?qǐng)D可以清晰地看到AGV 在不同時(shí)間點(diǎn)所在的柵格位置.圖9(a)為未使用基于沖突搜索算法進(jìn)行規(guī)劃時(shí)的時(shí)空?qǐng)D,從圖中可以看出兩條線段在(10,14,11)有交叉,交叉點(diǎn)用小黑點(diǎn)表示,這表明當(dāng)t=11 時(shí),兩輛AGV 在柵格(10,14)處發(fā)生了沖突.圖9(b)為使用基于沖突搜索算法規(guī)劃后的時(shí)空?qǐng)D,從圖中可以看出兩條線段不存在交叉,AGV2 維持原有的路徑,而AGV1 的路徑發(fā)生了變化,當(dāng)t=11 時(shí),AGV1 未到達(dá)柵格(10,14),而是到達(dá)了柵格(11,13),因此兩輛AGV 未發(fā)生沖突.避免沖突的方式為算法的上層檢測(cè)到?jīng)_突＜A1,A2,(10,14),11＞,然后對(duì)AGV1 施加新的約束＜A1,(10,14),11＞,算法的下層根據(jù)AGV1 新施加的約束重新為其規(guī)劃路徑.由此可看出,基于沖突搜索的多AGV 路徑規(guī)劃算法可以有效解決時(shí)空角度的相向沖突.

圖9 雙AGV 相向行駛?cè)S時(shí)空?qǐng)D

4.2 節(jié)點(diǎn)沖突仿真實(shí)驗(yàn)

本節(jié)仿真實(shí)驗(yàn)使用兩輛沿著垂直方向行駛的AGV 驗(yàn)證算法解決節(jié)點(diǎn)沖突的有效性,使用基于沖突搜索算法規(guī)劃的兩輛AGV 的行駛路線如圖10所示.AGV1 的起點(diǎn)位置和終點(diǎn)位置分別為柵格(7,3)和柵格(7,14),分別用紅色圓圈和紅色方框表示.AGV2 的起點(diǎn)位置和終點(diǎn)位置分別為柵格(17,13)和柵格(4,14),分別用綠色圓圈和綠色方框表示.紅色線段表示AGV1 的行駛路線,綠色線段表示AGV2 的行駛路線.柵格(7,12)處的字母P 表示AGV1 到達(dá)該柵格后停留了一個(gè)單位時(shí)間才前往柵格(7,13),這樣可以避免兩輛AGV 在柵格(7,13)發(fā)生節(jié)點(diǎn)沖突.

圖10 雙AGV 垂直方向行駛路線圖

圖11 為AGV1 和AGV2 按照?qǐng)D10所示的起點(diǎn)和終點(diǎn)沿著垂直方向行駛時(shí)的三維時(shí)空?qǐng)D,圖11(a)為未使用基于沖突搜索算法進(jìn)行規(guī)劃時(shí)的時(shí)空?qǐng)D,從圖中可以看出兩條線段在(7,13,10)處有交叉,即當(dāng)t=10 時(shí),兩輛AGV 在柵格(7,13)處發(fā)生了碰撞.圖11(b)為使用基于沖突搜索算法規(guī)劃后的時(shí)空?qǐng)D,從圖中可以看出兩條線段無(wú)交叉,表示AGV2 的綠色線段未發(fā)生變化,而表示AGV1 的紅色線段在t=9 后有所改變.AGV1 的變化在于當(dāng)t=10 時(shí),AGV1 未到達(dá)柵格(7,13),而是繼續(xù)停留在柵格(7,12),等待AGV2 通過(guò)柵格(7,13)后才離開(kāi),因此兩輛AGV 未發(fā)生沖突.與相向沖突的解決方式同理,算法的上層檢測(cè)到?jīng)_突＜A1,A2,(7,13),10＞,然后給AGV1 添加新的約束＜A1,(7,13),10＞,為了滿足AGV1 的約束,算法下層為其重新規(guī)劃了滿足約束的路徑.由此可以看出,節(jié)點(diǎn)沖突在使用基于沖突搜索的多AGV 路徑規(guī)劃算法后也可以得到有效解決.

圖11 雙AGV 垂直方向行駛?cè)S時(shí)空?qǐng)D

4.3 多種沖突并存的仿真實(shí)驗(yàn)

本節(jié)仿真實(shí)驗(yàn)用于驗(yàn)證算法在多種沖突并存情形下的有效性,仿真實(shí)例中共有8 輛AGV 同時(shí)運(yùn)行,每輛AGV 的編號(hào)、起點(diǎn)柵格坐標(biāo)、終點(diǎn)柵格坐標(biāo)和被標(biāo)識(shí)的顏色如表1所示.

表1 各AGV 對(duì)應(yīng)信息表

圖12 和圖13 分別為使用基于沖突搜索算法前后8 輛AGV 的行駛路線圖.圖12 中每個(gè)AGV 都從給定的起點(diǎn)出發(fā)前往對(duì)應(yīng)的終點(diǎn),圖中不同的顏色對(duì)應(yīng)不同的AGV,圓形表示AGV 的起點(diǎn),方框表示AGV 的終點(diǎn),紅色六角星表示該處有沖突發(fā)生.

圖12所示的8 條行駛路線對(duì)應(yīng)的三維時(shí)空?qǐng)D如圖14(a)所示.圖14(a)中的8 條路徑在時(shí)空中存在5 個(gè)交叉點(diǎn),對(duì)應(yīng)了圖12 中的5 個(gè)紅色六角星,表示發(fā)生了5 次沖突.結(jié)合這兩張圖可以看出,當(dāng)t=7 時(shí),AGV1 和AGV2 在柵格(10,10)發(fā)生沖突,AGV7 和AGV8 在柵格(10,16)發(fā)生沖突;當(dāng)t=11 時(shí),AGV3 和AGV4 在柵格(10,16)發(fā)生沖突;當(dāng)t=15.5 時(shí),AGV6和AGV7 在柵格(4,18)和柵格(4,19)中間發(fā)生沖突;當(dāng)t=20 時(shí),AGV5 和AGV6 在柵格(4,14)發(fā)生沖突.

圖12 算法使用前的多AGV 路線圖

采用基于沖突搜索算法規(guī)劃的8 條路線如圖13所示,從圖中可以看出使用算法規(guī)劃后的路徑成功避免了上述的5 處沖突.圖13 中的8 條路徑對(duì)應(yīng)的三維時(shí)空?qǐng)D為圖14(b).從圖14(b)中也可以看出任意兩條路徑在時(shí)空中均無(wú)黑色交叉點(diǎn),說(shuō)明路徑間無(wú)沖突.結(jié)合兩張圖可以看出AGV2、AGV3、AGV5 和AGV8 的路徑?jīng)]有改動(dòng),而AGV1、AGV4、AGV6 和AGV7 的路徑為避免沖突發(fā)生了變化.

圖13 算法使用后的多AGV 路線圖

圖14 多AGV 三維時(shí)空?qǐng)D

算法的上層檢測(cè)到5 處沖突＜A1,A2,(10,10),7＞、＜A7,A8,(10,16),7＞、＜A3,A4,(7,14),11＞、＜A6,A7,[(4,19),(4,18)],15.5＞和＜A5,A6,(4,14),20＞后,施加對(duì)應(yīng)的5 個(gè)約束＜A1,(10,10),7＞、＜A7,(10,16),7＞、＜A4,(7,14),11＞、算法的下層根據(jù)AGV1、AGV4、AGV6 和AGV7 新添加的約束為它們重新規(guī)劃了路徑,因此這4 個(gè)AGV 的路徑有所變化.由此可以看出,當(dāng)多種沖突并存且AGV 數(shù)量較多時(shí),基于沖突搜索算法也可以有效解決.

5 結(jié)論

本文從物流分揀中心場(chǎng)地的特性出發(fā),選擇柵格地圖法作為多AGV 路徑規(guī)劃的地圖建模方法.采用四鄰域搜索方式實(shí)現(xiàn)了單AGV 路徑規(guī)劃.為解決多AGV無(wú)沖突路徑規(guī)劃問(wèn)題,提出在傳統(tǒng)A*算法中加入時(shí)間維度升級(jí)為時(shí)空A*算法,進(jìn)一步將其作為基于沖突搜索的多AGV 路徑規(guī)劃算法的下層規(guī)劃器.通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了所提出的基于沖突搜索的多AGV 路徑規(guī)劃算法能夠有效解決節(jié)點(diǎn)沖突、相向沖突和多種沖突并存的情況.下一步研究的重點(diǎn)將聚焦在利用時(shí)空A*算法進(jìn)行實(shí)際場(chǎng)景測(cè)試與系統(tǒng)開(kāi)發(fā)上面,同時(shí)也將與相關(guān)算法進(jìn)行性能對(duì)比分析.