文章編號： 1006-9798（2024）03-0013-07； DOI： 10.13306/j.1006-9798.2024.03.003

摘要： 針對傳統(tǒng)A*算法在自動引導(dǎo)車（Automated Guided Vehicle，AGV）尋路時存在搜索路徑規(guī)劃時間長、搜索效率低和不考慮AGV運行體積等問題，提出以動態(tài)加權(quán)方式改進啟發(fā)式估計函數(shù)中啟發(fā)因子，根據(jù)路徑實際情況選擇加權(quán)值，篩選搜索鄰域時節(jié)點，剔除必然使路徑代價值升高的方向，以增加障礙物影響半徑的方式，避免AGV導(dǎo)航過程中發(fā)生碰撞。仿真結(jié)果表明，相比于原始A*算法，改進后的A*算法路徑節(jié)點搜索數(shù)量減少82%，時間減少81%，提高了路徑規(guī)劃效率，且考慮AGV運行的安全半徑，保證了AGV運行的安全性，避免在實際導(dǎo)航時發(fā)生碰撞。

關(guān)鍵詞： A*算法； 啟發(fā)因子； 自動引導(dǎo)車； 路徑規(guī)劃

中圖分類號： TP242.2文獻標(biāo)識碼： A

路徑規(guī)劃是AGV的核心技術(shù)之一，在特定環(huán)境中尋找最優(yōu)路徑或多條路徑，確保AGV穩(wěn)定高效地運輸貨物[1-2]。目前AGV路徑規(guī)劃算法主要包括動態(tài)窗口法（Dynamic Window Approach， DWA）、迪杰斯特拉算法（Dijkstra）及A* 算法等[3]。A*算法因其高效性而被廣泛應(yīng)用，但也存在拐點冗雜、搜索效率低[4-6]等問題。對此，諸多學(xué)者進行優(yōu)化改進。蔡梓豐等[7]通過實時閾值法和懲罰因子法，減少了不必要的搜索空間和冗余路徑，顯著提高了搜索和路徑規(guī)劃速度。加權(quán)曼哈頓距離引入轉(zhuǎn)彎修正參數(shù)作為啟發(fā)函數(shù)可優(yōu)化管理遍歷節(jié)點數(shù)，顯著降低轉(zhuǎn)彎頻率，提升路徑尋找效率和路徑流暢性[8]。采用三領(lǐng)域與八領(lǐng)域混合搜索策略，有效縮短搜索時間、減少路徑拐點數(shù)量[9]。吳曉嵐等[10]提出了一種基于安全距離的Floyd刪除算法，去除冗余路徑點以減少路徑長度。然而，上述研究大多集中在改善A*算法的搜索效率和路徑質(zhì)量，而對在動態(tài)環(huán)境下保證AGV運行體積安全性的考慮相對較少。為解決傳統(tǒng)A*算法搜索路徑計算量大和不考慮AGV運行體積的問題，本文提出一種改進A*算法，通過優(yōu)化A*算法中啟發(fā)式估計函數(shù)，采用動態(tài)加權(quán)方式改進其啟發(fā)因子，根據(jù)路徑實際情況設(shè)置加權(quán)值。同時，改進鄰域關(guān)鍵節(jié)點的搜索方式，依據(jù)AGV起點和目標(biāo)點的位置，對搜索方向進行篩選，為保證AGV路徑規(guī)劃的安全性，根據(jù)障礙物大小、AGV尺寸，設(shè)置障礙物安全半徑。仿真實驗驗證了改進A*算法的路徑規(guī)劃效率及AGV運行的安全可靠性。

1傳統(tǒng)A*算法

A*算法是一種啟發(fā)式搜索算法[11]，是路徑規(guī)劃中的代表性算法，核心在于使用了啟發(fā)式估計函數(shù)。啟發(fā)式估計函數(shù)又稱啟發(fā)函數(shù)，通過估計起始節(jié)點經(jīng)過節(jié)點n到達目標(biāo)節(jié)點的代價值指導(dǎo)節(jié)點搜索方向。啟發(fā)式估計函數(shù)公式為

f（n）=g（n）+h（n）（1）

其中，f（n）為實際代價值與代價估計值的總和；g（n）為起始節(jié)點到節(jié)點n到的實際代價值；h（n）是啟發(fā)因子，用估計節(jié)點n到目標(biāo)節(jié)點的代價估計值。

常見啟發(fā)因子計算方式有切比雪夫距離、曼哈頓距離和歐幾里得距離3種[12]。

1）切比雪夫距離表示當(dāng)前和目標(biāo)兩節(jié)點之間坐標(biāo)距離之差的最大值，即

h（n）=max（xn－x0，yn－y0）（2）

2）曼哈頓距離表示當(dāng)前節(jié)點與目標(biāo)節(jié)點在橫軸和縱軸上的距離之和，即

h（n）=xn－x0+yn－y0（3）

3）歐幾里得距離表示當(dāng)前節(jié)點與目標(biāo)節(jié)點的直線距離，即

h（n）=（xn－x0）2+（yn－y0）2（4）

A*算法節(jié)點選擇示意圖如圖1所示，A*算法原理[13]是創(chuàng)建OPEN_LIST和CLOSE_LIST 2張表：將起始節(jié)點添加至CLOSE_LIST表中，將起始節(jié)點周圍8個節(jié)點添加至OPEN_LIST表，計算每個節(jié)點的代價值f，將代價值最小的節(jié)點，即圖中黃色節(jié)點，從OPEN_LIST表中移動到CLOSE_LIST表，并將代價值最小的節(jié)點作為新的起始節(jié)點，直到到達目標(biāo)節(jié)點為止。

2基于改進A*算法的路徑規(guī)劃

傳統(tǒng)A*算法原理簡單，能夠準(zhǔn)確搜索到地圖中最優(yōu)路徑，比較依賴啟發(fā)函數(shù)，合適的啟發(fā)函數(shù)有利于提高路徑規(guī)劃的性能，但傳統(tǒng)A*算法未考慮空間約束，AGV導(dǎo)航風(fēng)險系數(shù)增加，從而導(dǎo)致AGV受損。因此本文基于傳統(tǒng)A*算法存在的問題進行改進。

2.1改進A*算法的啟發(fā)函數(shù)

啟發(fā)函數(shù)中預(yù)估代價值和實際代價值的大小會影響A*算法的路徑搜索的效率和精度。當(dāng)預(yù)估代價值小于實際代價值時，A*算法的節(jié)點搜索范圍更廣，搜索節(jié)點數(shù)量更多，能夠保證生成最優(yōu)路徑，但搜索時間較長。反之，則搜索范圍變小，搜索節(jié)點數(shù)量減少，路徑規(guī)劃時間短，但不能保證最優(yōu)路徑的生成[14]。為了權(quán)衡兩者之間的關(guān)系，更加合理地實現(xiàn)路徑規(guī)劃算法，引入優(yōu)化后的啟發(fā)因子h（n），提出一種優(yōu)化的啟發(fā)因子距離公式。

本文優(yōu)化距離以動態(tài)加權(quán)方式獲取啟發(fā)因子，根據(jù)路徑實際情況選擇加權(quán)值

h（n）=ω1×（xn－x0+yn－y0），xn－x0+yn－y0>λ，ω1≥1ω2×（xn－x0+yn－y0），xn－x0+yn－y0≤λ，0<ω2<1（5）

其中，x0和y0表示當(dāng)前節(jié)點坐標(biāo)；xn和yn表示目標(biāo)節(jié)點坐標(biāo)；λ表示閾值常數(shù)；ω1和ω2為權(quán)重。

規(guī)劃路徑時，既要考慮搜索速度又要考慮最優(yōu)路徑，此時需要使用式（5）動態(tài)加權(quán)的啟發(fā)因子。以原本的啟發(fā)因子h（n）為判斷依據(jù)，當(dāng)其高于閾值λ時，權(quán)重增大，算法搜索速度更快；當(dāng)?shù)陀陂撝郸藭r，權(quán)值降低，優(yōu)先考慮最優(yōu)路徑。閾值根據(jù)計算機運算性能、地圖尺寸等因素動態(tài)選擇，權(quán)重值也根據(jù)設(shè)定地圖的大小、復(fù)雜程度進行調(diào)節(jié)。

設(shè)置優(yōu)化距離參數(shù)λ=18，ω1=3，ω2=0.8，在同一地圖中，4種啟發(fā)因子對比結(jié)果如圖2所示，其中黑色線條為障礙物或邊界，綠色圓點為開始位置，藍色“x”符號為搜索節(jié)點，紅色線條為路徑規(guī)劃結(jié)果，即最優(yōu)路徑。

由圖2可以看出，使用4種啟發(fā)因子規(guī)劃的路徑都能避過障礙物到達指定節(jié)點，與其他距離計算方法相比，本文優(yōu)化距離搜索節(jié)點明顯減少。與切比雪夫距離和歐幾里得距離相比，本文優(yōu)化距離的搜索路徑轉(zhuǎn)角更少，更符合實際情況。各啟發(fā)因子路徑搜索詳細信息見表1。

由表1可以看出，使用本文優(yōu)化距離的啟發(fā)因子，搜索節(jié)點僅336個，路徑規(guī)劃時間為281.1 ms。仿真結(jié)果表明，本文采用的啟發(fā)因子在保證路徑準(zhǔn)確的前提下，減少了路徑搜索的時間消耗，顯著提高了路徑規(guī)劃的效率。

2.2篩選搜索鄰域關(guān)鍵節(jié)點

處于當(dāng)前節(jié)點的AGV在地圖上運動時，搜索相鄰的8個節(jié)點，然后取其一作為目標(biāo)節(jié)點進行運動[15]，當(dāng)前節(jié)點運動圖如圖3所示。雖然從當(dāng)前位置有8個方向可選擇，但在有些地圖中，部分方向不可能成為最優(yōu)路徑的一部分。起始位置及目標(biāo)位置示意圖如圖4，圖中綠色圓圈為起始位置，藍色叉號為目標(biāo)位置，處于當(dāng)前節(jié)點的AGV，不需要搜索圖3中相鄰節(jié)點1、4、6，因為這3個節(jié)點一定會使代價值增大，因此可以對搜索鄰域進行優(yōu)化。

本文根據(jù)當(dāng)前節(jié)點和終點的位置信息，采用參數(shù)化的方式選擇可搜索方向，分類結(jié)果見表2。iCQB7ikPCT9yJ9Ow8lgtSlFu1hU/P7avagC/5W0v8/M=表中α為當(dāng)前點與目標(biāo)點的連線夾角，當(dāng)前節(jié)點到相鄰節(jié)點2的移動方向為0°。這種方法會舍棄8個方向中的3個方向，因為這3個方向的選點會使路徑代價值升高，舍棄后可降低計算量，提高路徑搜索的效率。

利用本文優(yōu)化距離的啟發(fā)因子，鄰域搜索方法優(yōu)化前后對路徑搜索的節(jié)點如圖5所示。相比于優(yōu)化前，優(yōu)化后的方法節(jié)點搜索數(shù)量明顯減少，搜索節(jié)點數(shù)量為265，減少了21.1%，時間為192.1 ms，減少了31.7%。因此，優(yōu)化后的鄰域搜索算法提前避開代價值高的方向，減少節(jié)點搜索數(shù)量，提高路徑搜索效率。

2.3設(shè)置障礙物影響半徑

A*算法是以AGV中心坐標(biāo)為基準(zhǔn)進行路徑規(guī)劃，但在實際運行中需要考慮AGV的輪廓尺寸，本文

以AGV半徑來增加障礙物影響半徑，設(shè)定障礙物可影響范圍公式為

R′o≥Ro+RAGV+d0（6）

其中，R′o為障礙物可影響半徑；Ro為障礙物中心到邊緣的半徑；RAGV為AGV最大半徑；d0為安全半徑常數(shù)。

障礙物影響半徑示意圖如圖6所示，虛線為搜索路徑，Ro為障礙物實際半徑，R′o為障礙物最小影響半徑，RAGV為AGV最大半徑，A、B、C表示AGV行駛路徑上的節(jié)點。

A*算法以AGV中心為起始坐標(biāo)進行路徑規(guī)劃，為了防止AGV和障礙物之間發(fā)生碰撞，基于相對距離原理，設(shè)置AGV運行半徑，其實就是增加障礙物影響半徑，因此將AGV最大半徑加到障礙物實際半徑上，保障AGV運行的安全，避免發(fā)生碰撞。

3路徑規(guī)劃實驗

3.1仿真實驗

3.1.1實驗設(shè)計

為了驗證改進A*算法在AGV全局路徑規(guī)劃中的有效性，使用A*算法、文獻[8]算法、啟發(fā)函數(shù)算法和改進算法分別在尺寸為20×20和50×50的柵格地圖上進行仿真實驗。在地圖中按照復(fù)雜環(huán)境特征要求，設(shè)置了不同大小、形狀及密集程度的障礙物，假設(shè)AGV運行的安全距離為1個柵格。

3.1.2實驗結(jié)果與分析

仿真圖中黑色柵格為障礙物，白色柵格為可通行區(qū)域，黃色柵格為起始節(jié)點，綠色柵格為目標(biāo)節(jié)點，灰色柵格為搜索完的CLOSE_LIST列表，紅色柵格為待搜索的OPEN_LIST列表，棕色柵格為增加的障礙物影響半徑。整體仿真結(jié)果如圖7所示。

A*算法、文獻[8]算法、啟發(fā)函數(shù)算法和改進算法路徑搜索節(jié)點數(shù)量、路徑規(guī)劃時間及路徑長度見表3。

仿真結(jié)果表明，在20×20的柵格地圖中，使用改進A*算法進行路徑規(guī)劃時，搜索節(jié)點僅為28個，路徑規(guī)劃時間為20 ms，相比于A*算法，搜索節(jié)點減少129個，時間減少81 ms，相比于文獻[8]算法，搜索節(jié)點減少30個，時間減少21 ms。在50×50的柵格地圖中，改進A*算法路徑規(guī)劃搜索節(jié)點僅為132個，路徑規(guī)劃時間為73 ms，相比于A*算法，搜索節(jié)點減少1 020個，時間減少606 ms，相比于文獻[8]算法，搜索節(jié)點減少32個，時間減少14 ms。但改進A*算法規(guī)劃路徑長度增加，主要因為改進后增加了障礙物半徑，導(dǎo)致AGV路程增加。綜上所述，A*算法和改進A*算法均能在不同尺寸柵格地圖下實現(xiàn)路徑規(guī)劃，改進A*算法搜索節(jié)點和時間明顯減少，提高了路徑規(guī)劃效率，且考慮AGV運行的安全距離，避免在實際導(dǎo)航時發(fā)生碰撞。

3.2真實環(huán)境AGV導(dǎo)航實驗

3.2.1實驗設(shè)計

環(huán)境地圖圖像尺寸為440×550，采用46×58的柵格分割圖像，每一格圖像大小為9.6×4950828d64d2218b5d0d99bfb79d06849.5，實際運行環(huán)境大小為4.6 m×5.8 m，分割后每一個柵格表示真實環(huán)境大小為0.1 m×0.1 m。AGV在真實環(huán)境和柵格地圖中位置如圖8所示。

車間的工位發(fā)出調(diào)度AGV的需求，工位通過局域網(wǎng)和TCP傳輸協(xié)議將坐標(biāo)位置信息傳給上位機，上位機獲取目標(biāo)點在柵格地圖中的位置（xb，yb），獲取AGV在柵格地圖中的坐標(biāo)（36，52），再將其作為路徑規(guī)劃產(chǎn)生的第一個節(jié)點，目標(biāo)點（xb，yb）為路徑規(guī)劃產(chǎn)生的最后一個節(jié)點。

3.2.2實驗結(jié)果與分析

車間物流AGV在負載情況下，AGV尺寸會相應(yīng)變換，分別針對AGV在空載和負載情況設(shè)置障礙物影響半徑，并使用改進A*算法規(guī)劃路徑。AGV空、負載尺寸及障礙物影響半徑見表4，其中，原障礙物影響半徑為R0，設(shè)置安全半徑常數(shù)d0=5 cm。

改進A*算法對空載AGV和負載AGV路徑規(guī)劃結(jié)果如圖9所示。

路徑規(guī)劃仿真實驗結(jié)果見表5，表中記錄了使用改進A*算法，AGV在空載和負載情況下，路徑規(guī)劃搜索節(jié)點、規(guī)劃時間、最優(yōu)路徑長度和AGV是否發(fā)生碰撞。

實驗結(jié)果表明，基于改進A*算法的路徑規(guī)劃，空載和負載AGV均能實現(xiàn)路徑的最優(yōu)解，雖然不同狀態(tài)下AGV路徑導(dǎo)航的地圖和起始點相同，但由于AGV負載時會導(dǎo)致AGV運行半徑增加，增加的半徑映射到障礙物上會加大障礙物影響半徑，從而減少可運行區(qū)域，所以節(jié)點搜索數(shù)量、路徑規(guī)劃時間和最優(yōu)路徑長度都不同。綜上，AGV在空載和負載情況下，改進A*算法均能規(guī)劃出最優(yōu)路徑，且避免AGV與障礙物發(fā)生碰撞，實驗結(jié)果符合路徑規(guī)劃的要求。

4結(jié)束語

本文針對AGV在真實地圖下的導(dǎo)航，提出一種改進的A*算法，優(yōu)化A*算法中啟發(fā)式估計函數(shù)，采用動態(tài)加權(quán)方式改進啟發(fā)因子，根據(jù)路徑實際情況設(shè)置加權(quán)值。同時，改進鄰域關(guān)鍵節(jié)點的搜索方式，依據(jù)AGV起點和目標(biāo)點的位置，對搜索方向進行篩選，為保證AGV路徑規(guī)劃的安全性，根據(jù)障礙物大小、AGV尺寸，設(shè)置障礙物安全半徑。經(jīng)實驗驗證，相比于原始A*算法，改進A*算法節(jié)點搜索數(shù)量和時間明顯減少，且保證了AGV運行的安全性，有效解決了傳統(tǒng)A*算法搜索節(jié)點多、路徑規(guī)劃時間長和不考慮AGV運行體積的問題。但改進算法中的加權(quán)值需要根據(jù)地圖大小和復(fù)雜程度動態(tài)調(diào)整，實際應(yīng)用中可能存在一定困難，未來將進一步探索如何自適應(yīng)確定加權(quán)值，提升算法的實用性和靈活性。

參考文獻：

［1］WANG Z， HU X， Li X， et al．Overview of global path planning algorithms for Mobile Robots[J]．Computer Science， 2021， 48（10）： 19-29．

［2］李曉旭， 馬興錄， 王先鵬． 移動機器人路徑規(guī)劃算法綜述[J]． 計算機測量與控制， 2022， 30（7）： 9-19．

［3］ZHAO X， YE H， JIA W， et al． Survey on AGV path planning and obstacle avoidance algorithms[J]． Journal of Chinese Computer Systems， 2024， 45（3）： 529-541．

［4］陳駿， 沈琦琦． 自動導(dǎo)引車路徑規(guī)劃算法的研究綜述[J]． 自動化與儀器儀表， 2023（9）： 8-15．

［5］陳曉冬， 王福威． 基于改進A～*算法的AGV路徑規(guī)劃[J]． 計算機系統(tǒng)應(yīng)用， 2023， 32（3）： 180-185．

［6］張涌， 成海飛， 趙奉奎． 基于自適應(yīng)A～*算法的自動駕駛車輛路徑規(guī)劃方法研究[J]． 重慶交通大學(xué)學(xué)報（自然科學(xué)版）， 2024， 43（2）： 115-121， 130．

［7］蔡梓豐， 張延生， 梁先樟， 等． 基于改進A～*算法的路徑規(guī)劃研究[J]． 現(xiàn)代信息科技， 2024， 8（10）： 51-55， 59．

［8］劉亞寧， 張東升． 基于改進A～*算法的AGV路徑規(guī)劃研究[J]． 信息與電腦（理論版）， 2023， 35（23）： 62-65．

［9］余震， 王棟， 王明天， 等． 基于改進A～*算法的AGV全局路徑規(guī)劃[J]． 武漢科技大學(xué)學(xué)報， 2024， 47（3）： 234-240．

［10］WU X L， ZHANG Q Y， BAI Z F， et al． A selfadaptive safe A* algorithm for AGV in largescale storage environment[J]． Intelligent Service Robotics， 2024， 17（2）： 221-235．

［11］王向宇． 基于改進A～*算法和動態(tài)窗口法的室內(nèi)移動機器人路徑規(guī)劃研究[D]． 贛州： 江西理工大學(xué)， 2023．

［12］楊聿壬， 郭江宇， 董曉峰， 等． 基于改進A～*算法的安全路徑規(guī)劃[J]． 電腦知識與技術(shù)， 2024， 20（9）： 1-4， 11．

［13］宣仁虎． 基于改進A*算法和人工勢場法智能小車路徑規(guī)劃研究[D]． 西安： 西安電子科技大學(xué)， 2020．

［14］武善平， 黃炎焱， 陳天德． 改進A～*算法的水面艦艇靜態(tài)航路規(guī)劃[J]． 計算機工程與應(yīng)用， 2022， 58（23）： 307-315．

［15］趙曉， 王錚， 黃程侃， 等． 基于改進A*算法的移動機器人路徑規(guī)劃[J]． 機器人， 2018， 40（6）： 903-910．

Research on AGV Path Planning Based on Improved A* Algorithm

ZHANG Yameng， WANG Jun， FU Chaoxing

（College of Mechanical and Electrical Engineering， Qingdao University， Qingdao 266071， China）

Abstract：

Aiming at the problems of long search path planning time，low search efficiency and lack of consideration of AGV running volume in the traditional A* algorithm in Automated Guided Vehicle pathfinding，the heuristic factor in the heuristic estimation function is improved by dynamic weighting method，and the weighting value is selected according to the actual path situation．It filters and searches the neighborhood time points，eliminates the direction that is certain to inevitably increase the path generation value，and increase the influence radius of obstacles to avoid collision during AGV navigation．Simulation results show that compared with the original A* algorithm，the number of nodes searching is reduced by 82% and the search time is reduced by 81%，which improves the path planning efficiency．Moreover，the improved A* algorithm considers the safety radius of AGV operation and ensures the safety of AGV operation．Avoid collisions during actual navigation．

Keywords：

A* algorithm； heuristic factor； automated guided vehicle； path planning

收稿日期： 2024-06-10； 修回日期： 2024-07-19

基金項目： 山東省自然科學(xué)基金資助項目（ZR2020QE183）

第一作者： 張亞萌（2001-），男，碩士研究生，主要研究方向為人工智能。

通信作者： 符朝興（1967-），男，博士，副教授，主要研究方向為人工智能和機械振動。Email： cx_f@163.com