基于改進A*算法的多AGV路徑規(guī)劃研究

官祥錦，陳 娟，張為民

（1. 北京化工大學(xué)，北京 100029；2. 中國航空制造技術(shù)研究院，北京 100024）

AGV在工業(yè)生產(chǎn)和物流領(lǐng)域扮演著越來越重要的作用，能夠有效地改善工業(yè)生產(chǎn)和生活的運輸系統(tǒng)結(jié)構(gòu)，將人力從繁瑣重復(fù)的體力勞動中解放出來，不僅大大地降低了生產(chǎn)成本，也提高了生產(chǎn)效率[1]。而多AGV的路徑規(guī)劃和無碰撞調(diào)度是AGV應(yīng)用面臨的兩大問題[2–3]，其在環(huán)境復(fù)雜的工業(yè)現(xiàn)場和生產(chǎn)車間尤為突出。根據(jù)是否已知全局路徑信息，可將AGV路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃。全局路徑規(guī)劃是指AGV在行駛前已經(jīng)掌握了全局的路徑信息，包括AGV的位置信息、所處環(huán)境的障礙物信息以及可行駛的路徑信息，然后根據(jù)掌握的全局信息規(guī)劃出一條從起點到終點的最優(yōu)路徑；局部路徑規(guī)劃是指AGV在行駛前對環(huán)境信息一無所知或知道部分環(huán)境信息，需要在行駛的過程中實時動態(tài)地了解自身的位置和環(huán)境信息，然后通過掌握的環(huán)境信息規(guī)劃出一條從起點到終點的最優(yōu)路徑。目前應(yīng)用于全局路徑規(guī)劃的算法主要有：柵格法（其中最具代表性的是A*算法[4]、D*算法和Dijkstra算法[5–7]）、快速搜索隨機樹法[8]（Rapidlyexploring random tree，RRT）、Voronoi圖法等。應(yīng)用于局部路徑規(guī)劃的算法主要有：人工勢場法[9]、動態(tài)窗口法（Dynamic window approach，DWA），以及一些智能算法（其中主要有模糊算法、遺傳算法[10]、神經(jīng)網(wǎng)絡(luò)、粒子群算法[11]、蟻群算法等）[12–15]。由于計算的復(fù)雜度以及現(xiàn)實生產(chǎn)環(huán)境的限制，且大多工業(yè)生產(chǎn)和物流環(huán)境是全局已知的，所以在實際的AGV路徑規(guī)劃中，局部路徑規(guī)劃算法和智能路徑規(guī)劃算法應(yīng)用的較少，大多還停留在仿真研究階段，并沒有應(yīng)用到實際的生產(chǎn)生活中。

A*算法由于其算法簡單，在中小型地圖中具有良好的搜索性能，是當(dāng)前AGV進行路徑規(guī)劃時應(yīng)用的最廣泛的算法。但傳統(tǒng)的A*算法存在需要搜索的節(jié)點數(shù)多、路徑轉(zhuǎn)角多、生成的路徑平滑度低等問題[16]，這些問題在多AGV同時進行路徑規(guī)劃時尤為突出，特別是當(dāng)多輛AGV存在路徑?jīng)_突或者已規(guī)劃好的路徑上出現(xiàn)障礙物，需要對其進行重規(guī)劃時，搜索的節(jié)點數(shù)將大大增加，降低了重規(guī)劃的效率。針對傳統(tǒng)A*算法存在的問題，Song等[17]做了很多研究，但大都是根據(jù)特定的應(yīng)用環(huán)境進行的改進與研究。余星寶等[18]采用傳統(tǒng)A*算法找出最短路徑上轉(zhuǎn)彎處的特征點，再利用四階貝塞爾曲線對轉(zhuǎn)彎處的特征點進行平滑處理，得到1條無碰撞、平滑度高、具有一定曲率，且相對距離更短的路徑，解決了傳統(tǒng)A*算法生成的路徑轉(zhuǎn)角多、平滑度低、易發(fā)生碰撞的問題。但該方法對于只能沿著已鋪設(shè)路徑引導(dǎo)線行走的AGV不實用。胡蔚旻等[19]以傳統(tǒng)A*算法為基礎(chǔ)，引入3軸–2象限、AGV路徑轉(zhuǎn)向數(shù)來刪除路徑上的無效備選點，從而使AGV的行駛路徑得到有效的平滑。但該算法在多輛AGV發(fā)生路徑?jīng)_突時，不能對其路徑進行動態(tài)調(diào)整，所以不適用于對多輛AGV進行路徑規(guī)劃的情況。劉生偉等[20]在傳統(tǒng)A*算法啟發(fā)函數(shù)的基礎(chǔ)上，引入了父節(jié)點的啟發(fā)函數(shù)值，對當(dāng)前節(jié)點和父節(jié)點啟發(fā)函數(shù)之和進行加權(quán)處理，并通過判斷轉(zhuǎn)折點的方式，刪除多余的冗余節(jié)點，使得規(guī)劃出的路徑更加平滑。該算法和傳統(tǒng)的A*算法及指數(shù)衰減加權(quán)改進A*算法相比，在搜索時間、路徑長度以及路徑包含的節(jié)點數(shù)上都有所減少。然而本文所使用的八鄰域搜索方式，對于已鋪設(shè)引導(dǎo)線的AGV來說并不實用。余文凱等[21]將環(huán)境信息和AGV位置信息融入到評價函數(shù)中，并使用障礙率和直通率給A*算法的評價函數(shù)進行加權(quán)處理。通過基于K-Means聚類算法對柵格地圖進行分區(qū)預(yù)處理后，再使用改進的A*算法搜索最短路徑。對搜索到的最短路徑，使用改進的Floyd算法對路徑進行雙向平滑度優(yōu)化處理，并添加防碰撞安全距離系數(shù)，有效地增加了路徑的平滑度和安全性。但該算法僅考慮單輛AGV的情況，并且對規(guī)劃出的路徑進行平滑處理的方式不適用于已鋪設(shè)路徑引導(dǎo)線線的AGV。卞永明等[22]根據(jù)AGV從起點到當(dāng)前點發(fā)生的轉(zhuǎn)彎次數(shù)，對A*算法的啟發(fā)函數(shù)進行獎勵和懲罰，可以顯著地降低轉(zhuǎn)彎次數(shù)，但該算法沒有考慮一條直線上的多余冗余節(jié)點。吳飛龍等[23]將AGV的位置信息和環(huán)境信息融入到了A*算法的啟發(fā)函數(shù)中，并使用環(huán)境的混亂程度和障礙率對啟發(fā)函數(shù)進行加權(quán)處理，刪除路徑中多余的轉(zhuǎn)折點和冗余節(jié)點，使AGV規(guī)劃出的路徑更加平滑。陸佳依等[24]采用分裂和篩選的方案對傳統(tǒng)A*算法進行優(yōu)化，通過在未搜索節(jié)點的啟發(fā)函數(shù)中增加轉(zhuǎn)彎權(quán)值，在路徑規(guī)劃過程中考慮轉(zhuǎn)彎帶來的消耗，縮短了路徑的總長度，減少了AGV的轉(zhuǎn)彎次數(shù)。該方法明顯提高了A*算法的復(fù)雜度，降低了搜索效率。

現(xiàn)有的AGV路徑規(guī)劃算法，考慮的情況大都比較理想化，沒有對AGV的行駛方向做約束，導(dǎo)致在使用A*算法對AGV行駛路徑進行規(guī)劃時，既可以四方位搜索，也可以八方位搜索，從而出現(xiàn)規(guī)劃的路徑只要存在空白區(qū)域就可隨便轉(zhuǎn)彎的情況。這對于重載AGV以及對生產(chǎn)安全要求極為嚴(yán)格的工業(yè)生產(chǎn)現(xiàn)場來說是不現(xiàn)實的，在對AGV進行路徑規(guī)劃的過程中，如果不對AGV的行駛方向做約束，直接按照規(guī)劃出的路徑行駛，將非常容易和障礙物發(fā)生碰撞，發(fā)生安全事故。并且當(dāng)涉及多輛AGV同時運行時，出于工業(yè)生產(chǎn)安全的考慮，對AGV的路徑規(guī)劃要求將變得更加嚴(yán)苛。此時，安全是路徑規(guī)劃優(yōu)先考慮的問題，所以在進行多AGV路徑規(guī)劃時，需盡量將多AGV發(fā)生沖突碰撞的概率降到最低，其次才是AGV路徑最優(yōu)的問題，這種情況下，單純地使用A*算法將不再滿足路徑規(guī)劃要求。當(dāng)涉及多輛AGV時，AGV在運行的過程中，彼此互為障礙物，并且障礙物在實時移動，此時的AGV路徑規(guī)劃問題將從1個靜態(tài)路徑規(guī)劃問題轉(zhuǎn)變?yōu)?個動態(tài)路徑規(guī)劃問題。邢普學(xué)等[25]通過增加AGV共享路徑的懲罰值對A*算法進行改進，結(jié)合改進的A*算法設(shè)置了碰撞解決規(guī)則，能夠解決AGV的碰撞問題，但是該規(guī)則在AGV發(fā)生路徑?jīng)_突時，只考慮對其進行重規(guī)劃，重歸化后的路徑可能會導(dǎo)致新的碰撞出現(xiàn)及多AGV死鎖的發(fā)生。泰應(yīng)鵬等[26]通過結(jié)合A*算法和時間窗模型，對多AGV進行了動態(tài)路徑規(guī)劃，通過提前計算AGV經(jīng)過每個節(jié)點的時間，對時間窗進行動態(tài)的排布和更新，并為多輛AGV動態(tài)地分配優(yōu)先級，實現(xiàn)了無沖突，無重復(fù)的系統(tǒng)調(diào)度。但是在實際中，準(zhǔn)確計算每輛AGV到達(dá)每個節(jié)點的時間是困難的，如果發(fā)生較大的時間計算偏差，將容易導(dǎo)致AGV發(fā)生碰撞問題。廉胤東等[27]將當(dāng)前節(jié)點到相鄰候選節(jié)點的期望運行時間加入到傳統(tǒng)A*算法的啟發(fā)函數(shù)中，對傳統(tǒng)A*算法進行了改進，在改進A*算法的基礎(chǔ)上，對AGV下一個運行位置進行預(yù)判，實現(xiàn)AGV的沖突避讓，提高了AGV路網(wǎng)資源的利用率。但該算法也存在計算量大，對AGV系統(tǒng)要求較高等問題。高新浩等[28]基于改進時間窗的兩階段動態(tài)路徑規(guī)劃算法，構(gòu)建環(huán)境拓?fù)涞貓D，使用A*算法實現(xiàn)AGV離線路徑規(guī)劃。通過動態(tài)環(huán)境拓?fù)涞貓D，使用BP神經(jīng)網(wǎng)絡(luò)實現(xiàn)AGV路徑的動態(tài)規(guī)劃，降低了多AGV在行駛過程中發(fā)生沖突和碰撞的可能性。但是該算法會隨著AGV的頻繁調(diào)度和重規(guī)劃，以及環(huán)境地圖的擴大而增加計算復(fù)雜度，降低AGV路徑搜索效率。

基于以上問題，本文以鋪設(shè)AGV導(dǎo)引線的工業(yè)生產(chǎn)現(xiàn)場為背景，提出了一種改進的A*算法，該算法使用切比雪夫距離對當(dāng)前節(jié)點的啟發(fā)函數(shù)進行加權(quán)處理，在相同的地圖環(huán)境下，相比于Dijkstra算法，傳統(tǒng)A*算法以及已有的使用切比雪夫距離對當(dāng)前節(jié)點和父節(jié)點的啟發(fā)函數(shù)進行加權(quán)的方法，其搜索節(jié)點數(shù)和搜索時間得到了有效的降低，顯著地提高了A*算法在進行重規(guī)劃時的搜索效率。在改進A*算法的基礎(chǔ)上，結(jié)合時間窗模型，通過對每輛AGV的行駛節(jié)點進行提前預(yù)判，動態(tài)調(diào)整AGV的優(yōu)先級，有效地解決了多AGV路徑規(guī)劃時的沖突問題，在AGV遇到其他車輛需要進行避讓或重規(guī)劃時，通過比較避讓預(yù)計增加的時間和重規(guī)劃預(yù)計增加的預(yù)估時間，并選擇預(yù)計增加時間少的方案解決多AGV路徑規(guī)劃時的死鎖以及路徑?jīng)_突問題。采用該算法既可以讓AGV得到了相對最優(yōu)路徑，也有效地解決了多AGV在運行過程中的時間、空間沖突問題。該算法增加的算法復(fù)雜度小，通過試驗證明，此方法在對多AGV進行路徑規(guī)劃時，搜索速度快、實時性較好。

1 改進A*算法

A*算法是從Dijsktra算法發(fā)展而來的，是一種啟發(fā)式搜索算法。它利用啟發(fā)信息來指導(dǎo)路徑的搜索，以實現(xiàn)減少搜索范圍和降低搜索問題的復(fù)雜度。同時，也是靜態(tài)路網(wǎng)中搜索最短路徑時最有效的直接搜索方法。在A*算法中，估計值（即啟發(fā)函數(shù)h（n）值）與實際距離值越接近，A*算法的搜索速度越快，搜索效率也就越高。由于A*算法在中小型地圖中搜索的高效性，在實際中得到了廣泛的應(yīng)用。但是傳統(tǒng)的A*算法由于其搜索路徑時需要遍歷的節(jié)點數(shù)多，且規(guī)劃出的路徑存在過多的冗余節(jié)點和轉(zhuǎn)折點，所以很多學(xué)者對傳統(tǒng)的A*算法進行了改進。傳統(tǒng)的A*算法為

式中，n為當(dāng)前節(jié)點；f（n）為從起始節(jié)點經(jīng)過當(dāng)前節(jié)點n到達(dá)目標(biāo)節(jié)點的最小代價估計；g（n）為起始節(jié)點到當(dāng)前節(jié)點的最小代價估計；h（n）為當(dāng)前節(jié)點n到目標(biāo)節(jié)點的最小代價估計，也稱為啟發(fā)函數(shù)。

啟發(fā)函數(shù)h（n）在A*算法中起著至關(guān)重要的作用。這里設(shè)當(dāng)前點到目標(biāo)點的實際代價為Q。當(dāng)h（n）=0時，A*算法將變成Dijkstra算法，Dijkstra算法能夠保證找到一條最短路徑；當(dāng)h（n）Q時，A*算法在尋找最佳路徑的過程中會擴展別的任何一個節(jié)點，這種情況下不能夠保證找到一條最短路徑。根據(jù)以上原則，為了能夠得到一條從起點到終點的最短路徑，要保證h（n）≤Q，并且h（n）越逼近Q值，其搜索速度會越快。這也是對A*算法進行改進的重要思路。

A*算法中h（n）常用曼哈頓距離、歐幾里德距離、歐幾里德距離的平方表示。歐幾里德距離的表示方式為

曼哈頓距離的表示方式為

切比雪夫距離的表示方式為

式（2）～（4）中，（xe，ye）為終點坐標(biāo)； （xn，yn）為當(dāng)前點n的坐標(biāo)。

由于傳統(tǒng)A*算法在搜索路徑時需要遍歷的節(jié)點數(shù)和生成路徑中的冗余節(jié)點較多，且在地圖較大時尤為突出，嚴(yán)重影響了A*算法的搜索效率。本文遵循啟發(fā)函數(shù)h（n）越逼近當(dāng)前點到目標(biāo)點的實際代價值Q，其搜索速度會越快的原則，對A*算法進行了改進。

從式（2）～（4）可得，對于?n和?e有

也即，ho≤hm。也即，hc≤hm。

也即，hc=|xe–xn|≤ho

從式（5）、（6）和（9）可以得到

由于本文所涉及的工業(yè)環(huán)境已經(jīng)鋪設(shè)了AGV路徑導(dǎo)引線，AGV不能沿著任意角度移動，只能沿著網(wǎng)格的方向移動。歐幾里德距離ho表示的是對角線距離，對于本文已鋪設(shè)引導(dǎo)線的AGV不適用。本文使用取值更接近實際代價Q的曼哈頓距離hm作為啟發(fā)函數(shù)，并使用切比雪夫距離hc對啟發(fā)函數(shù)hm進行加權(quán)，改進后的A*算法為

改進后的A*算法可以減少在路徑搜索時需要遍歷的節(jié)點數(shù)，提高搜索效率。

A*算法需要維護一個Open表和一個Close表，Open表中記錄了所有已經(jīng)遍歷過但是沒有被考察的節(jié)點；Close表中記錄了所有已經(jīng)考察過的節(jié)點，初始化時Open表中記錄了起始節(jié)點，Close表為空。執(zhí)行A*算法時，從起始節(jié)點開始，不斷地向外擴充，并維護和更新Open表和Close表，直到終點加入Close表為止。改進后的A*算法流程如圖1所示。

圖1 改進A*算法流程圖Fig.1 Flow chart of improved A* algorithm

本文以實際的工業(yè)生產(chǎn)制造車間為背景，利用柵格法和拓?fù)鋱D法對工業(yè)生產(chǎn)制造車間的平面圖進行電子地圖的構(gòu)建，圖2為實際工業(yè)生產(chǎn)制造車間平面圖，圓形數(shù)字標(biāo)識的點為AGV的運輸站點，其他數(shù)字標(biāo)識的點為AGV路徑上的節(jié)點。圖3為與圖2相對應(yīng)的使用柵格法構(gòu)建的電子地圖。

圖2 工業(yè)生產(chǎn)車間平面圖Fig.2 Floor plan of industrial production workshop

圖3中的柵格地圖大小為20×42，橫坐標(biāo)范圍[0，41]、縱坐標(biāo)范圍[0，19]。柵格地圖中的每個數(shù)字點代表著生產(chǎn)車間的一個站點，其中站點1和17是AGV的車庫和充電樁所在位置。由于使用柵格地圖規(guī)劃出的AGV路徑存在冗余的節(jié)點，因此本文對使用改進A*算法在柵格地圖下得到的路徑做進一步處理，刪除生成路徑上不必要的冗余節(jié)點，使最終規(guī)劃出的路徑需要保留的節(jié)點數(shù)更少。

為了驗證本文提出的改進A*算法的有效性，分別對Dijkstra算法、傳統(tǒng)A*算法、Tang等[16]提出的改進的A*算法和本文提出的改進的A*算法進行仿真試驗對比。以圖3的柵格地圖為試驗地圖，每次試驗分別以柵格地圖中的每個站點為起點或終點，經(jīng)排列組合每次共驗證378條路徑。共做10次試驗，最后取10次的平均值。試驗結(jié)果及其對比如表1和表2所示。

表1 4種路徑規(guī)劃算法遍歷節(jié)點數(shù)和平均搜索時間對比Table 1 Comparision of the number of traversed nodes and the average search time of four path planning algorithms

表2 本文改進A*算法相較其他3種算法遍歷節(jié)點數(shù)和平均搜索時間減少百分比Table 2 Compared with the other three algorithms, the improved A*algorithm in this paper reduces the number of nodes traversed and the average search time by a percentage %

圖3 工業(yè)生產(chǎn)車間柵格地圖Fig.3 Raster map of industrial production workshop

從試驗結(jié)果可以得出，與Dijkstra算法、傳統(tǒng)A*算法和Tang等[16]提出的改進的A*算法相比，本文提出的改進A*算法的平均搜索時間和平均遍歷節(jié)點數(shù)得到了顯著的減少，搜索效率得到了顯著的提高。與Dijkstra算法相比，平均搜索時間和平均遍歷節(jié)點數(shù)分別減少了74.95%和67.87%；與傳統(tǒng)A*算法相比，平均搜索時間和平均遍歷節(jié)點數(shù)分別減少了59.91%和20.81%；與Tang等[16]提出的改進的A*算法相比，平均搜索時間和平均遍歷節(jié)點數(shù)分別減少了17.57%和8.00%。使用改進的A*算法規(guī)劃從節(jié)點1（坐標(biāo)（2，1））到節(jié)點14（坐標(biāo)（22，11））的路徑如圖4所示。

圖4中x軸代表柵格點的橫坐標(biāo)；y軸代表柵格點的縱坐標(biāo)，其中曲線上的每個點代表規(guī)劃出的路徑需要經(jīng)過的每個節(jié)點。從圖4中可以看出，使用改進的A*算法規(guī)劃出的路徑需要保存的節(jié)點為32個，本文在規(guī)劃出的原始路徑基礎(chǔ)上做了進一步處理，刪除路徑中冗余的節(jié)點后，路徑需要保留的節(jié)點數(shù)僅剩5個，路徑也變得更加光滑。

圖4 使用改進A*算法規(guī)劃的從節(jié)點1到節(jié)點14的路徑Fig. 4 Using the improved A* algorithm to plan the path from node 1 to node 14

2 多AGV無碰撞規(guī)劃

工業(yè)生產(chǎn)車間常存在多個站點以及多個生產(chǎn)任務(wù)，需要多輛AGV同時進行無碰撞協(xié)調(diào)運行，所以需要對多輛AGV的行駛路徑進行合理規(guī)劃，在保證不發(fā)生碰撞的基礎(chǔ)上，使每輛AGV的行駛路徑最優(yōu)。由于多輛AGV在行駛的過程中互為障礙物，所以需要考慮多輛AGV在行駛過程中的動態(tài)規(guī)劃問題，保證每段路上在同一時間只能有1輛AGV通過。只有合理的規(guī)劃和協(xié)調(diào)好AGV行駛路徑的空間和時間資源利用問題，才能保證多輛AGV有條不紊地運行。

2.1 多AGV沖突類型

當(dāng)多輛AGV同時運行時，AGV之間主要存在路徑不沖突、路徑?jīng)_突但時間不沖突、相向沖突、節(jié)點沖突4種情況。

（1）路徑不沖突。當(dāng)多輛AGV之間規(guī)劃的路徑不存在重合節(jié)點和交叉節(jié)點，也即路徑不存在沖突時，每輛AGV可各自獨立運行，不需要考慮碰撞問題。

（2）路徑?jīng)_突時間不沖突。當(dāng)多輛AGV之間存在路徑?jīng)_突，但是時間不沖突時，因為在同一節(jié)點或同一路段上行駛的時間沒有交叉和重疊，每輛AGV可獨自運行，不需要考慮碰撞問題

（3）相向沖突。如圖5所示，當(dāng)兩輛AGV同一時間在同一條路段上相向行駛時，會產(chǎn)生相向沖突。此時需要采用相應(yīng)的碰撞預(yù)測方法和策略，解決多輛AGV同一時間在同一路段上的相向沖突問題。

圖5 AGV路徑發(fā)生相向沖突Fig.5 AGV conflicts in same direction

（4）節(jié)點沖突。如圖6所示，當(dāng)多輛AGV同一時間在交叉路口相遇時，會產(chǎn)生節(jié)點沖突問題，此時也需要采用相應(yīng)的碰撞預(yù)測方法和策略解決該問題。

圖6 AGV路徑發(fā)生節(jié)點沖突Fig.6 AGV conflicts in same node

2.2 基于時間窗的沖突解決方案

在AGV路徑規(guī)劃中，時間窗是指AGV從進入某路段到離開該路段所占用的時間段?？梢詫⒛陈范蔚臅r間窗劃分為空閑時間窗和占用時間窗。空閑時間窗為該路段空閑的時間段，在空閑時間窗內(nèi)任何一輛AGV都可在該路段上行駛；占用時間窗為當(dāng)前AGV在該路段行駛占用的時間段，在占用時間窗內(nèi)其他車輛不能駛?cè)朐撀范巍r間窗模型的示意圖如圖7所示。

圖7 時間窗模型Fig.7 Time window model

這里設(shè)AGV路徑上的每個節(jié)點都用相應(yīng)的坐標(biāo)（x，y）表示，（x1，y1）—（x2，y2）表示路徑上2個節(jié)點（x1，y2）和（x2，y2）之間的路段。圖8為兩輛AGV在路段（2，9）—（2，13）上發(fā)生相向沖突的情況。圖9為兩輛AGV在節(jié)點（2，13）發(fā)生節(jié)點沖突的情況。

圖8 兩輛AGV發(fā)生相向沖突時間窗Fig.8 Two AGVs conflict time window in the same direction

圖9 兩輛AGV發(fā)生節(jié)點沖突時間窗Fig.9 Two AGVs conflict time window in the same node

所有AGV在路段k上的時間窗模型可以表示為

式中，T（k）為所有AGV在路段k上的時間窗集合；i表示第i輛AGV；n表示AGV的數(shù)量。

根據(jù)式（12）可以得到所有AGV在所有路段上的時間窗集合，為

式中，Tm表示所有AGV在路段m上的時間窗集合；m表示AGV規(guī)劃出的路徑的路段數(shù)；n表示AGV的數(shù)量。式（13）中的每一列代表每一輛AGV在所有路段上的時間窗集合。

多輛AGV在路段k上發(fā)生相向沖突的時間窗模型為

式中，t′ik為第i輛AGV進入路段k時的時間；t″ik為第i輛AGV離開路段k時的時間；tqk為第q輛AGV在路段k上的時間窗。即當(dāng)兩輛AGV在同一路段k上的時間窗發(fā)生重疊時，AGV將發(fā)生相向沖突。

當(dāng)多輛AGV同時在某一節(jié)點的相鄰路段上行駛，并且同時到達(dá)該節(jié)點時，將發(fā)生節(jié)點沖突，節(jié)點沖突的時間窗模型為

式中，t″ik為第i輛AGV離開路段k時的時間；t″qp為第q輛AGV離開路段p時的時間。路段k和路段q有相同的節(jié)點，并且k，q∈[1，m]。即多輛AGV同時離開不同的路段，到達(dá)同一個節(jié)點時將發(fā)生節(jié)點沖突。

從圖8和9的相向沖突及節(jié)點沖突的時間窗中可以看出，將時間窗右移是解決多AGV路徑?jīng)_突的主要方法。本文在每輛AGV行駛過程中，提前對AGV路徑上的3個節(jié)點進行時間窗的更新和排布，當(dāng)檢測到時間窗有沖突時，根據(jù)生產(chǎn)任務(wù)需求以及當(dāng)前AGV離終點的遠(yuǎn)近程度動態(tài)調(diào)整相應(yīng)AGV的優(yōu)先級，讓優(yōu)先級低的AGV進行路徑重規(guī)劃或避讓，即讓其在沖突路段上的時間窗右移，從而避免AGV產(chǎn)生路徑上的沖突與碰撞。在重規(guī)劃或避讓策略的選擇上，可以通過式（16）進行選擇。

式中，Δtr表示AGV進行重規(guī)劃預(yù)計需要增加的行駛時間；Δte表示AGV進行避讓等待預(yù)計需要增加的行駛時間。

多AGV無碰撞規(guī)劃流程如圖10所示。

圖10中節(jié)點標(biāo)志g表示該節(jié)點既沒有AGV占用也不是AGV規(guī)劃路徑中的節(jié)點。節(jié)點標(biāo)志y表示該節(jié)點是AGV路徑規(guī)劃中需要經(jīng)過的節(jié)點，但是現(xiàn)在AGV還沒有經(jīng)過該節(jié)點。節(jié)點標(biāo)志r表示該節(jié)點是AGV路徑規(guī)劃中需要經(jīng)過的節(jié)點，并且當(dāng)前AGV離該節(jié)點的距離在3個節(jié)點以內(nèi)。

圖10 多AGV無碰撞規(guī)劃流程圖Fig.10 Flow chart of multi-AGV collision-free planning

3 試驗結(jié)果與分析

為了驗證本文提出的改進的A*算法以及多AGV無碰撞規(guī)劃策略的有效性，使用Visual Studio 2017+Qt5進行編程，將改進的算法及策略應(yīng)用到實際工業(yè)生產(chǎn)AGV上。AGV長2 m、寬90 cm、高60 cm、載重1500 kg，其中AGV自帶車載工控機用于AGV的控制，現(xiàn)場的AGV通道為單行道，即同一時間只允許有1輛AGV通過。出于工業(yè)現(xiàn)場安全考慮，AGV在運輸過程以0.5 m/s的速度勻速行駛。AGV原型圖如圖11所示。

圖11 AGV原型Fig.11 AGV prototype

在圖12中，AGV1從1號站點到17號站點；AGV2從8號站點到19號站點。圖13為相對應(yīng)的時間窗模型。使用改進的A*算法規(guī)劃出的路徑不存在重合和交叉的節(jié)點，所以兩輛AGV無需考慮路徑?jīng)_突問題，在圖13中對應(yīng)的時間窗上也不存在重疊情況。

圖12 兩輛AGV路徑無沖突Fig.12 No conflict between two AGVs

圖13 兩輛AGV路徑無沖突時間窗Fig.13 Two AGV conflict-free time window

在圖14中，AGV1從t1時刻開始，從17號站點到10號站點；AGV2從t4時刻開始，從8號站點到20號站點。圖15為相對應(yīng)的時間窗模型。使用本文提出的改進的A*算法規(guī)劃出的路徑存在重合和交叉的節(jié)點，從圖15時間窗模型中可以得出，AGV1和AGV2在路段（2，39）—（2，32）和（12，32）—（2，32）交叉位置將發(fā)生節(jié)點沖突，所以根據(jù)AGV的優(yōu)先級情況，AGV2將會在（2，37）節(jié)點選擇等待避讓，待AGV1經(jīng)過（2，32）節(jié)點后，AGV2再按照原規(guī)劃路徑行駛到20號站點。

圖14 兩輛AGV在節(jié)點（2，32）發(fā)生節(jié)點沖突Fig.14 Two AGVs have a node conflict at coordinates (2,32)

圖15 兩輛AGV在節(jié)點（2，32）發(fā)生節(jié)點沖突時間窗 （避讓等待）Fig.15 Time window when two AGVs have node conflict at coordinates (2,32) (Waiting)

在圖16中，AGV1從t1時刻開始，從1號站點到16號站點；AGV2從t1時刻開始，從9號站點到2號站點。圖17為相對應(yīng)的時間窗模型。使用本文提出的改進的A*算法規(guī)劃出的路徑存在重合和交叉的節(jié)點，規(guī)劃出的AGV1原始路徑為（1，2）→（2，2）→（2，32）→（12，32）→（12，39）→（13，39）。從圖17時間窗模型中可以得出，AGV1在節(jié)點（2，17）位置檢測到前向路徑上的節(jié)點被占用，根據(jù)AGV的無碰撞規(guī)劃策略，AGV1選擇以節(jié)點（2，17）為新節(jié)點，終點不變，重新進行路徑規(guī)劃，AGV1重規(guī)劃后的路徑為：（2，17）→（2，13）→（12，13）→（12，39）→（13，39）。AGV2的路徑保持不變，從而避免兩輛AGV發(fā)生路徑?jīng)_突碰撞。

圖16 兩輛AGV在節(jié)點（2，17）發(fā)生相向路徑?jīng)_突Fig.16 Two AGVs have a same direction conflict at coordinates (2,17)

圖17 兩輛AGV在節(jié)點（2，17）發(fā)生相向沖突時間窗（重規(guī)劃）Fig.17 Time window when two AGVs have a same direction conflict at coordinates (2,17)

本文以Visual Studio 2017+Qt5為開發(fā)環(huán)境，在圖11所示的AGV上進行了試驗驗證。表3和4分別對應(yīng)圖12、14和16中，兩輛AGV沒有路徑?jīng)_突、發(fā)生相向沖突（避讓等待）和發(fā)生相向沖突（重規(guī)劃）時進行路徑規(guī)劃消耗的時間，并在4種路徑規(guī)劃算法上進行了驗證和對比分析。

表3 AGV1路徑規(guī)劃消耗時間（不包括AGV運行時間）Table 3 AGV1 path planning consumption time(not including AGV driving time) s

從以上試驗可以看出，本文提出的改進A*算法與多AGV路徑規(guī)劃策略結(jié)合，在多AGV無路徑?jīng)_突，以及存在節(jié)點或路徑相向沖突時，能夠得到較好的無碰撞規(guī)劃結(jié)果，能夠有效地解決實際工業(yè)生產(chǎn)過程中多AGV同時行駛時的路徑?jīng)_突問題。當(dāng)某輛AGV出現(xiàn)故障，長時間占用某條路徑時，調(diào)度系統(tǒng)會檢測到故障并產(chǎn)生報警，通知工作人員進行處理，同時調(diào)度系統(tǒng)會將電子地圖中的該柵格點置為障礙物點，其他AGV進行路徑規(guī)劃時將不會再考慮該條路徑。從表3和4中可以看出，相較與Dijkstra算法、傳統(tǒng)A*算法和Tang等[16]提出的改進A*算法，使用本文改進的A*算法，無論是在兩輛AGV沒有路徑?jīng)_突或者發(fā)生路徑?jīng)_突時，都能夠很快地對每輛AGV進行路徑規(guī)劃，能夠較好地滿足實時性要求。

表4 AGV2路徑規(guī)劃消耗時間（不包括AGV運行時間）Table 4 AGV2 path planning consumption time(not including AGV driving time) s

4 結(jié)論

本文以實際工業(yè)生產(chǎn)現(xiàn)場為背景，研究了多AGV路徑規(guī)劃算法和無碰撞策略。通過使用切比雪夫距離對啟發(fā)函數(shù)進行加權(quán)，對傳統(tǒng)的A*算法進行了改進，同時，通過時間窗模型和動態(tài)調(diào)整AGV的優(yōu)先級，解決了多AGV的路徑?jīng)_突問題，具有較好應(yīng)用價值。試驗表明，本文提出的改進的A*算法顯著地降低了AGV在進行路徑規(guī)劃時的路徑搜索時間，提高了搜索效率，實時性也得到了進一步的提高。