胡蔚旻，靳文舟

華南理工大學(xué) 土木與交通學(xué)院，廣州 510461

1 引言

隨著科技的發(fā)展，機(jī)器人逐漸替代人工搬運(yùn)，自動(dòng)導(dǎo)引車（Automated Guided Vehicle，AGV）因其具有任務(wù)執(zhí)行、精確定位、環(huán)保高效、智能運(yùn)作等特點(diǎn)被廣泛使用，尤其在貨物運(yùn)輸領(lǐng)域[1]，被公認(rèn)為是實(shí)現(xiàn)物流運(yùn)輸?shù)淖罴阎x[2]。AGV 系統(tǒng)可通過控制平臺實(shí)現(xiàn)對各AGV運(yùn)行狀況、地理定位、任務(wù)派遣的監(jiān)控與更改，具有投資小、占地少、搭建周期短、安全、便捷等特點(diǎn)[3]，若將其合理地運(yùn)用于車間物流運(yùn)輸，通過科學(xué)地改進(jìn)線路算法與系統(tǒng)協(xié)調(diào)策略，能夠有效地減少人力需求，極大提高生產(chǎn)工作效率，降低生產(chǎn)損耗與成本。

秦珅等[4]利用雙向同步A*算法實(shí)現(xiàn)路徑起終點(diǎn)同步搜索，以提高路徑規(guī)劃效率。李強(qiáng)等[5]通過引入象限概念，篩選、剔除無效拓展備選點(diǎn)，實(shí)現(xiàn)搜索效率的提高，但是由于約束條件限制，只搜索與目標(biāo)點(diǎn)同象限位置的拓展點(diǎn)，導(dǎo)致該方法的普適性大幅降低。王子意[6]通過區(qū)分AGV直行、轉(zhuǎn)彎速度將路徑轉(zhuǎn)彎列入A*算法估計(jì)函數(shù)，利用實(shí)例證明在一定環(huán)境下單AGV 線路可減少超60%轉(zhuǎn)向次數(shù)。

上述方法大多針對單AGV 情況，由于運(yùn)輸路網(wǎng)為多臺AGV共用，運(yùn)行期間將存在線路間的時(shí)空沖突，需制定相應(yīng)的協(xié)調(diào)策略避免車輛間碰撞、死鎖等沖突現(xiàn)象的發(fā)生。常見算法有 A*算法[7]、遺傳算法[8]、Dijkstra 算法[6]、人工勢場法[9-11]等。Draganjac 等[12]通過對低優(yōu)先級的車輛采用等待或者移除的策略解決路徑?jīng)_突。Banaszak等[13]提出資源共享和流量排序的協(xié)調(diào)策略，以解決動(dòng)態(tài)環(huán)境中的沖突、死鎖等現(xiàn)象。袁洋等[14]通過引入負(fù)載量優(yōu)化A*算法，實(shí)現(xiàn)路網(wǎng)的負(fù)載均衡，有效降低AGV發(fā)生沖突的概率，提高系統(tǒng)工作效率。賀麗娜[15]通過將時(shí)間窗原理引入Dijkstra 算法實(shí)現(xiàn)多AGV 無碰撞路線規(guī)劃，結(jié)合實(shí)例證明了引入時(shí)間窗的有效性。許倫輝等[16]以下達(dá)任務(wù)的時(shí)間先后順序降序設(shè)置優(yōu)先級，并以優(yōu)先級從低至高依次對沖突路徑進(jìn)行協(xié)調(diào)，此方案能夠有效消除路網(wǎng)中所有沖突，但僅以下達(dá)任務(wù)時(shí)間作為線路協(xié)調(diào)順序標(biāo)準(zhǔn)，易導(dǎo)致系統(tǒng)完成所有任務(wù)的所需總時(shí)長大幅增加。

基于此，本文依據(jù)路網(wǎng)及車輛行駛特性，構(gòu)建笛卡爾坐標(biāo)系環(huán)境；通過提出一種以3軸-2象限為篩選約束的改進(jìn)A*算法，在保證普適性的前提下通過約束條件剔除無效搜索點(diǎn)，達(dá)到提高搜索效率的目的，并引入轉(zhuǎn)向數(shù)指標(biāo)優(yōu)化路徑平滑度；以改進(jìn)算法為基礎(chǔ)，結(jié)合所建環(huán)境，對車輛沖突類型、判別進(jìn)行量化分類，借鑒時(shí)間窗原理，以系統(tǒng)總工作時(shí)長最短為原則制定相應(yīng)的協(xié)調(diào)策略，尋求系統(tǒng)運(yùn)行效率最佳。

2 構(gòu)建坐標(biāo)系地圖模型

柵格法由Howden 提出[17]，利用單位柵格對地圖進(jìn)行劃分，結(jié)合灰度值區(qū)分自由、障礙柵格，柵格的大小對精度具有決定性作用，縮小柵格能夠提高精度，但會(huì)導(dǎo)致地圖的信息量呈幾何式增長[18]，從而降低路徑規(guī)劃效率?；跂鸥穹ㄋ枷?，結(jié)合AGV運(yùn)行線路的正交性、定位精準(zhǔn)性，構(gòu)建改進(jìn)笛卡爾坐標(biāo)系地圖模型作為規(guī)劃環(huán)境，即以笛卡爾坐標(biāo)系第一象限作為電子地圖，利用二維坐標(biāo)完成AGV 運(yùn)行的精確定位，此地圖模型還能滿足線路的正交性、路徑長度便捷計(jì)算等要求。

3 改進(jìn)A*算法

3.1 提高搜索效率

傳統(tǒng)A*算法是以當(dāng)前所在點(diǎn)為中心，對其各方向上限定范圍內(nèi)的點(diǎn)作為拓展備選點(diǎn)進(jìn)行遍歷，本質(zhì)與八碼數(shù)問題相同。目前AGV 運(yùn)行路徑多為正交線路，基于坐標(biāo)系地圖，若以八碼數(shù)遍歷原則進(jìn)行路徑規(guī)劃，則會(huì)導(dǎo)致對角線上的4 個(gè)無效點(diǎn)（圖1）仍然會(huì)進(jìn)行先運(yùn)算、再剔除的無效運(yùn)算過程，從而降低規(guī)劃效率。

圖1 傳統(tǒng)A*算法拓展備選點(diǎn)示意圖

李強(qiáng)等[5]通過引入象限概念篩選拓展備選點(diǎn)，但由于只選取與目標(biāo)同象限的周邊點(diǎn)，導(dǎo)致其適用范圍有所限制。鑒于此，本文提出正負(fù)象限概念，構(gòu)建3 軸-2 象限搜索法實(shí)現(xiàn)拓展備選點(diǎn)的篩選，即以當(dāng)前點(diǎn)為次坐標(biāo)軸原點(diǎn)建立x′y′正交坐標(biāo)系，4個(gè)半軸上單位長度定點(diǎn)為搜尋備選集（圖2），依據(jù)式（1）～（3）確定目標(biāo)點(diǎn)與當(dāng)前點(diǎn)的正負(fù)象限關(guān)系，剔除無效搜索軸，完成備選點(diǎn)篩選。

圖2 雙坐標(biāo)系

其中，(xs,ys)表示起點(diǎn)S坐標(biāo)，(xe,ye)表示目標(biāo)點(diǎn)E坐標(biāo)，Cx、Cy為常數(shù)。

3.2 優(yōu)化路徑平滑度

AGV 運(yùn)行時(shí)因轉(zhuǎn)向產(chǎn)生的延誤將降低工作效率，過于頻繁地轉(zhuǎn)向還會(huì)加速機(jī)器的損耗，縮短使用壽命。為了提高使用效率，減小與實(shí)際運(yùn)行的誤差，將路徑轉(zhuǎn)向數(shù)引入算法估價(jià)函數(shù)，通過減少轉(zhuǎn)向數(shù)，獲取平滑路徑，提升運(yùn)行效率。改進(jìn)后A*算法的估計(jì)函數(shù)如下：

其中，f(m)是擴(kuò)展節(jié)點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)，g(m)表示擴(kuò)展節(jié)點(diǎn)M至起點(diǎn)的實(shí)際代價(jià)，g(x)為擴(kuò)展節(jié)點(diǎn)到起點(diǎn)的已知成本[19]，σ表示轉(zhuǎn)向數(shù)轉(zhuǎn)換為成本代價(jià)的換算系數(shù)，為第k輛AGV 擴(kuò)展節(jié)點(diǎn)M的坐標(biāo)。由于行駛路徑的正交性，可選用曼哈頓距離作為啟發(fā)函數(shù)h(m) 的估計(jì)代價(jià)，如式（10）。表示第k輛AGV目標(biāo)點(diǎn)E的坐標(biāo)。改進(jìn)后A*算法流程如圖3。

4 多AGV協(xié)調(diào)

為進(jìn)一步提高工作效率，建立基于時(shí)間窗法的路徑協(xié)調(diào)模型，消除各路徑間潛在沖突，實(shí)現(xiàn)多AGV的路網(wǎng)時(shí)空共用，以提高系統(tǒng)運(yùn)行效率。本文基于此思想，細(xì)化空間沖突類型劃分，明確類型量化判別，通過多協(xié)調(diào)方式比對擇優(yōu)，實(shí)現(xiàn)系統(tǒng)工作效率最優(yōu)。

4.1 沖突分類、判別

AGV沖突可劃分為空間沖突、空間無沖突、時(shí)間無沖突三類。

空間沖突可細(xì)分為節(jié)點(diǎn)沖突（圖4（a））和路段沖突，其中路段沖突分為對向沖突（圖4（b））和同向沖突（圖4（c））。

空間無沖突表示不同AGV規(guī)劃線路在空間上不存在重疊現(xiàn)象，即可獨(dú)立運(yùn)行、互不影響、無須協(xié)調(diào)。

時(shí)間無沖突表示不同AGV 路徑可能存在空間重疊，但時(shí)間不重疊，此類沖突中不同AGV雖然共用同一路段，但在時(shí)間維度為錯(cuò)位重疊，因此互不產(chǎn)生影響，仍可獨(dú)立運(yùn)行，無須協(xié)調(diào)。

圖3 改進(jìn)A*算法流程圖

圖4 AGV沖突

沖突判別方式如下：

其中，T為任務(wù)執(zhí)行時(shí)刻集，tN表示第N輛AGV在tN時(shí)刻開始執(zhí)行任務(wù)，AGVN為第N輛AGV的路徑集，Nn表示第N輛AGV在n時(shí)刻的節(jié)點(diǎn)坐標(biāo)位置。

4.2 協(xié)調(diào)策略

對于節(jié)點(diǎn)沖突采用二者依次等待讓行策略，路段沖突則細(xì)分為兩類進(jìn)行討論：

若到達(dá)沖突起點(diǎn)的AGV存在時(shí)間錯(cuò)位，但因錯(cuò)位不足而產(chǎn)生沖突，采用先到先通行，后到等待讓行的策略。

若存在沖突的AGV 同時(shí)到達(dá)沖突路段起點(diǎn)，采用二者依次等待讓行、重新規(guī)劃路徑以最小工作總時(shí)長為指標(biāo)的多協(xié)調(diào)方案比對擇優(yōu)策略。此方法與目前多數(shù)以優(yōu)先度為指標(biāo)，單一重新規(guī)劃低優(yōu)先度的車輛路徑的協(xié)調(diào)策略相比，排除了主觀因素對制定優(yōu)先度的影響。

出于安全考慮，存在沖突的AGV 間需等優(yōu)先使用路段的AGV 完全通過后方可繼續(xù)使用，等待時(shí)間計(jì)算如下：

其中，lroadr表示路段r的長度，lAGVn表示第n輛AGV的長度，vAGVn為第n輛AGV的行駛速度。

5 評價(jià)指標(biāo)

5.1 算法評價(jià)

5.1.1 路徑總長L

AGV 運(yùn)行效率大多采用路徑總長度作為評價(jià)指標(biāo)，由于車輛轉(zhuǎn)向產(chǎn)生時(shí)間延誤，一些學(xué)者還將工作時(shí)長作為輔助評價(jià)指標(biāo)。本文引入轉(zhuǎn)向數(shù)對A*算法的估價(jià)函數(shù)進(jìn)行優(yōu)化，車輛在路徑選擇時(shí)已考慮轉(zhuǎn)向造成的延誤，無須另外增設(shè)時(shí)間評價(jià)指標(biāo)，因此選用各AGV規(guī)劃路徑總長度作為規(guī)劃方法優(yōu)劣的評價(jià)指標(biāo)。

5.1.2 備選點(diǎn)數(shù)P

對于相同的路網(wǎng)環(huán)境、任務(wù)起終點(diǎn)，同一評價(jià)體系下采用不同規(guī)劃方法存在獲取相同且最優(yōu)的規(guī)劃路徑的現(xiàn)象，因此選用方法的運(yùn)行效率成為系統(tǒng)工作效率的決定因素。路徑規(guī)劃時(shí)需對當(dāng)前點(diǎn)進(jìn)行多向拓展確定備選點(diǎn)并擇優(yōu)確定拓展點(diǎn)，拓展備選點(diǎn)的總數(shù)量可反映規(guī)劃方法的工作效率，因此選取完成系統(tǒng)規(guī)劃任務(wù)所需的拓展備選點(diǎn)總數(shù)作為系統(tǒng)運(yùn)行效率的評價(jià)指標(biāo)。

5.1.3 路徑轉(zhuǎn)向數(shù)TN

具有不同轉(zhuǎn)彎數(shù)的規(guī)劃路徑即使線路長度一致，所需的實(shí)際運(yùn)行時(shí)長也會(huì)存在差異，轉(zhuǎn)彎數(shù)過多則會(huì)導(dǎo)致與預(yù)測值相差懸殊，從而降低規(guī)劃精度。為提高規(guī)劃可行性、可靠性，縮小與實(shí)際差值，將路徑轉(zhuǎn)彎數(shù)列入評價(jià)指標(biāo)體系。

5.2 協(xié)調(diào)策略評價(jià)

由于一個(gè)系統(tǒng)中存在AGV 間的沖突協(xié)調(diào)、轉(zhuǎn)向時(shí)間延誤等，僅通過系統(tǒng)路徑總長度無法達(dá)到對效率的有效評價(jià)，而整個(gè)系統(tǒng)完成任務(wù)所需的總時(shí)間則能較好地反映工作效率。

6 實(shí)例分析

構(gòu)建圖5所示具有障礙物的30 m×30 m坐標(biāo)系地圖模型作為規(guī)劃環(huán)境（×表示障礙物，下同），以X=1 為任務(wù)起點(diǎn)線，X=30 為任務(wù)目標(biāo)點(diǎn)線。隨機(jī)產(chǎn)生5個(gè)搬運(yùn)任務(wù)，每個(gè)任務(wù)由一臺AGV 獨(dú)自完成，每臺AGV 車身長度lAGVn為1 m，行駛速度vAGVn為0.5 m/s，每個(gè)轉(zhuǎn)向延誤時(shí)長3 s。各搬運(yùn)任務(wù)信息及運(yùn)行結(jié)果如表1和表2。

圖5 規(guī)劃環(huán)境

表1 任務(wù)信息

表2 運(yùn)行結(jié)果

依據(jù)表2 可知，采用歐幾里德距離、曼哈頓距離作為啟發(fā)函數(shù)均可獲得相同且最短的規(guī)劃路徑；無論啟發(fā)函數(shù)是歐氏距離，還是曼氏距離，采用傳統(tǒng)4 軸搜索法的遍歷點(diǎn)數(shù)均少于3軸-2象限搜索法；以相同搜索法為前提，曼氏距離作為啟發(fā)函數(shù)的搜索點(diǎn)均少于歐式距離，證明了3 軸-2 象限搜索法、曼哈頓距離啟發(fā)函數(shù)的合理性、有效性。因此采用3 軸-2 象限搜索法，以曼氏距離為估價(jià)函數(shù)的A*算法作為AGV路徑規(guī)劃原則。

為進(jìn)一步提高規(guī)劃精度，縮小與實(shí)際運(yùn)行的誤差，將行駛轉(zhuǎn)向數(shù)1-cos引入成本函數(shù)參數(shù)集進(jìn)行路徑規(guī)劃，結(jié)果如表3所示。

表3 規(guī)劃路徑詳情

由于拓展節(jié)點(diǎn)時(shí)考慮了轉(zhuǎn)向所產(chǎn)生的附加成本，在獲取相同最短路徑長度的前提下，上述A*算法更偏向于擇取產(chǎn)生轉(zhuǎn)向數(shù)較少的節(jié)點(diǎn)進(jìn)行拓展。依據(jù)表中數(shù)據(jù)可知，基于上述A*算法并考慮轉(zhuǎn)向數(shù)的改進(jìn)A*算法能顯著縮減行駛路徑的轉(zhuǎn)向次數(shù)，降低因轉(zhuǎn)向產(chǎn)生的附加延誤，從而縮小與實(shí)際運(yùn)行間的誤差。其中任務(wù)3由于已為最短路徑下最少轉(zhuǎn)向方案，增設(shè)轉(zhuǎn)向數(shù)參數(shù)后的規(guī)劃方案仍為最短路徑的最少轉(zhuǎn)向路徑。采用改進(jìn)A*算法對上述搬運(yùn)任務(wù)進(jìn)行路徑規(guī)劃，結(jié)果如圖6所示。

由圖6 可知，系統(tǒng)工作總時(shí)長為 123 s（AGV-2 所對應(yīng)的任務(wù)2），存在空間沖突的路段如表4所示。

表4 沖突路段詳情信息

圖6 （a）規(guī)劃線路結(jié)果

圖6 （b）規(guī)劃線路（X 軸）-時(shí)間圖

圖6 （c）規(guī)劃線路（Y 軸）-時(shí)間圖

路段C4C5起始端點(diǎn)為任務(wù)4 的起點(diǎn)，因此選用AGV-5等待讓行的協(xié)調(diào)策略，等待時(shí)長為2 s；由于時(shí)間延長的傳遞性，AGV-5 到達(dá)路段E的時(shí)間延長至26 s，較AGV-3推遲2 s到達(dá)，則繼續(xù)選取AGV-5等待讓行的協(xié)調(diào)策略，等待時(shí)長為2 s；AGV-2和AGV-4均在58 s到達(dá)路段A 起始端點(diǎn)，則分別對兩臺AGV 進(jìn)行路線重規(guī)（圖7、圖8，為便于觀察，圖中僅顯示AVG-2/4線路）、等待讓行，進(jìn)而擇優(yōu)選取協(xié)調(diào)方案。

（1）AGV-2路線重規(guī)

AGV-4仍按原規(guī)劃線路行駛，AGV-2則將路段A視為障礙物后進(jìn)行路徑重新規(guī)劃，如圖7，重規(guī)后的路徑長度增加2 m，轉(zhuǎn)向數(shù)增加2個(gè)，但避免了因沖突而產(chǎn)生的等待延誤，AGV-2、AGV-4工作總時(shí)長分別為133 s、116 s，系統(tǒng)工作總時(shí)長為133 s（AGV-2所對應(yīng)的任務(wù)2）。

圖7 （a）AGV-2重規(guī)線路圖

圖7 （b）AGV-2重規(guī)線路（X 軸）-時(shí)間圖

圖7 （c）AGV-2重規(guī)線路（Y 軸）-時(shí)間圖

（2）AGV-4路線重規(guī)

AGV-2仍按原規(guī)劃線路行駛，AGV-4則將路段A視為障礙物后進(jìn)行路徑重新規(guī)劃，如圖8，重規(guī)前后的路徑長度不變，轉(zhuǎn)向數(shù)略有增加，AGV-2、AGV-4工作總時(shí)長分別為123 s、122 s，系統(tǒng)工作總時(shí)長為123 s（AGV-2所對應(yīng)的任務(wù)2）。

（3）AGV-2等待讓行

AGV-2在沖突路段A 起始端點(diǎn)處等待AGV-4完全通過后方可通行，等待時(shí)長為4 s，則AGV-2、AGV-4 工作總時(shí)長分別為127 s、116 s，系統(tǒng)工作總時(shí)長為127 s（AGV-2所對應(yīng)的任務(wù)2）。

圖8 （a）AGV-4重規(guī)線路圖

圖8 （b）AGV-4重規(guī)線路（X 軸）-時(shí)間圖

圖8 （c）AGV-4重規(guī)線路（Y 軸）-時(shí)間圖

（4）AGV-4等待讓行

AGV-4在沖突路段A 起始端點(diǎn)處等待AGV-2完全通過后方可通行，等待時(shí)長為4 s，則AGV-2、AGV-4 工作總時(shí)長分別為123 s、120 s，系統(tǒng)工作總時(shí)長為123 s（AGV-2所對應(yīng)的任務(wù)2）。

通過方案比對可知，4 種沖突協(xié)調(diào)方案中對AGV-2采取等待讓行、路線重規(guī)均會(huì)導(dǎo)致系統(tǒng)工作總時(shí)長的增加，分別為4 s、10 s；對AGV-4 采取等待讓行、路線重規(guī)不改變系統(tǒng)工作總時(shí)長且二者所需的時(shí)間總長一致，即均為123 s。前者利用時(shí)間錯(cuò)位避免沖突，但仍存在較長的空間沖突，一旦處于時(shí)間維度前期的車輛在重疊路段上出現(xiàn)故障，將會(huì)影響后期使用該路段的所有車輛。若假設(shè)車輛發(fā)生故障的概率呈隨機(jī)分布，則存在空間沖突的路段長度與發(fā)生上述情況的概率為正相關(guān)，因此針對本系統(tǒng)任務(wù)，擇優(yōu)選擇AGV-4路線重規(guī)的協(xié)調(diào)策略。若借鑒先到先服務(wù)的原則，依據(jù)下達(dá)任務(wù)的時(shí)間先后順序，僅對后者AGV采取等待讓行或線路重規(guī)策略，將增加系統(tǒng)運(yùn)輸總時(shí)，降低工作效率。

7 結(jié)束語

本文通過結(jié)合AGV 路徑特征建立坐標(biāo)系環(huán)境，并引入3 軸-2 象限概念及轉(zhuǎn)向數(shù)實(shí)現(xiàn)對傳統(tǒng)A*算法的改進(jìn)，以系統(tǒng)總時(shí)最小為目標(biāo)，借鑒時(shí)間窗原理制定多AGV沖突判別、協(xié)調(diào)策略。通過實(shí)例證實(shí)，改進(jìn)的方法不僅大幅減少拓展備選點(diǎn)數(shù)和轉(zhuǎn)向數(shù)，提高路徑規(guī)劃效率，還能保證協(xié)調(diào)結(jié)果達(dá)到系統(tǒng)最佳，避免因追尋某一任務(wù)最短用時(shí)而陷入系統(tǒng)局部最優(yōu)的現(xiàn)象。

本文算法在速度、規(guī)劃效果上均有所優(yōu)化，但在動(dòng)態(tài)魯棒性上尚未改進(jìn)，針對車輛故障等突發(fā)情況，整體路網(wǎng)如何進(jìn)行動(dòng)態(tài)實(shí)時(shí)調(diào)整可后續(xù)深入研究。