改進平滑A*算法的多AGV路徑規(guī)劃

胡蔚旻，靳文舟

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

1 引言

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

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

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

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

2 構建坐標系地圖模型

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

3 改進A*算法

3.1 提高搜索效率

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

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

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

圖2 雙坐標系

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

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

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

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

4 多AGV協(xié)調

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

4.1 沖突分類、判別

AGV沖突可劃分為空間沖突、空間無沖突、時間無沖突三類。

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

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

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

圖3 改進A*算法流程圖

圖4 AGV沖突

沖突判別方式如下：

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

4.2 協(xié)調策略

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

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

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

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

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

5 評價指標

5.1 算法評價

5.1.1 路徑總長L

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

5.1.2 備選點數(shù)P

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

5.1.3 路徑轉向數(shù)TN

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

5.2 協(xié)調策略評價

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

6 實例分析

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

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

表1 任務信息

表2 運行結果

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

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

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

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

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

表4 沖突路段詳情信息

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

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

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

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

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

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

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

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

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

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

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

（3）AGV-2等待讓行

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

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

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

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

（4）AGV-4等待讓行

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

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

7 結束語

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

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