官祥錦，陳 娟，張為民

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

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

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

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

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

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

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

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

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

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

曼哈頓距離的表示方式為

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

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

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

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

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

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

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

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

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

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

圖1 改進(jìn)A*算法流程圖Fig.1 Flow chart of improved A* algorithm

本文以實(shí)際的工業(yè)生產(chǎn)制造車間為背景，利用柵格法和拓?fù)鋱D法對(duì)工業(yè)生產(chǎn)制造車間的平面圖進(jìn)行電子地圖的構(gòu)建，圖2為實(shí)際工業(yè)生產(chǎn)制造車間平面圖，圓形數(shù)字標(biāo)識(shí)的點(diǎn)為AGV的運(yùn)輸站點(diǎn)，其他數(shù)字標(biāo)識(shí)的點(diǎn)為AGV路徑上的節(jié)點(diǎn)。圖3為與圖2相對(duì)應(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]。柵格地圖中的每個(gè)數(shù)字點(diǎn)代表著生產(chǎn)車間的一個(gè)站點(diǎn)，其中站點(diǎn)1和17是AGV的車庫(kù)和充電樁所在位置。由于使用柵格地圖規(guī)劃出的AGV路徑存在冗余的節(jié)點(diǎn)，因此本文對(duì)使用改進(jìn)A*算法在柵格地圖下得到的路徑做進(jìn)一步處理，刪除生成路徑上不必要的冗余節(jié)點(diǎn)，使最終規(guī)劃出的路徑需要保留的節(jié)點(diǎn)數(shù)更少。

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

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

表2 本文改進(jìn)A*算法相較其他3種算法遍歷節(jié)點(diǎn)數(shù)和平均搜索時(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

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

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

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

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

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

2.1 多AGV沖突類型

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

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

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

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

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

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

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

2.2 基于時(shí)間窗的沖突解決方案

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

圖7 時(shí)間窗模型Fig.7 Time window model

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖11 AGV原型Fig.11 AGV prototype

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

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

圖13 兩輛AGV路徑無(wú)沖突時(shí)間窗Fig.13 Two AGV conflict-free time window

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

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

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

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

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

圖17 兩輛AGV在節(jié)點(diǎn)（2，17）發(fā)生相向沖突時(shí)間窗（重規(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上進(jìn)行了試驗(yàn)驗(yàn)證。表3和4分別對(duì)應(yīng)圖12、14和16中，兩輛AGV沒有路徑?jīng)_突、發(fā)生相向沖突（避讓等待）和發(fā)生相向沖突（重規(guī)劃）時(shí)進(jìn)行路徑規(guī)劃消耗的時(shí)間，并在4種路徑規(guī)劃算法上進(jìn)行了驗(yàn)證和對(duì)比分析。

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

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

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

4 結(jié)論

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