基于時空A*算法的多AGV無沖突路徑規(guī)劃①

郭 超,陳香玲,郭 鵬,王 強,汪世杰

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

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

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

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

1 引言

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

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

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

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

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

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

2.1 地圖選擇

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

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

圖1 柵格地圖法示意圖

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

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

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

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

圖2 四鄰域搜索方式

式(2)中,D表示相鄰兩個節(jié)點的移動距離;xi和yi分別表示節(jié)點i的橫縱坐標;xj和yj分別表示終點j的橫縱坐標.

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

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

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

3.1 沖突類型

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

圖3 兩種沖突類型

3.2 時空A*算法

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

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

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

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

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

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

圖6 時空A*算法流程

3.3 基于沖突搜索

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

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

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

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

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

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

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

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

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

4 多AGV無沖突路徑規(guī)劃仿真實驗

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

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

圖7 柵格地圖

4.1 相向沖突仿真實驗

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

圖8 雙AGV 相向行駛路線圖

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

圖9 雙AGV 相向行駛?cè)S時空圖

4.2 節(jié)點沖突仿真實驗

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

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

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

圖11 雙AGV 垂直方向行駛?cè)S時空圖

4.3 多種沖突并存的仿真實驗

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

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

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

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

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

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

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

圖14 多AGV 三維時空圖

算法的上層檢測到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＞后,施加對應(yīng)的5 個約束＜A1,(10,10),7＞、＜A7,(10,16),7＞、＜A4,(7,14),11＞、算法的下層根據(jù)AGV1、AGV4、AGV6 和AGV7 新添加的約束為它們重新規(guī)劃了路徑,因此這4 個AGV 的路徑有所變化.由此可以看出,當(dāng)多種沖突并存且AGV 數(shù)量較多時,基于沖突搜索算法也可以有效解決.

5 結(jié)論

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