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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文優(yōu)化距離以動(dòng)態(tài)加權(quán)方式獲取啟發(fā)因子，根據(jù)路徑實(shí)際情況選擇加權(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é)點(diǎn)坐標(biāo)；xn和yn表示目標(biāo)節(jié)點(diǎn)坐標(biāo)；λ表示閾值常數(shù)；ω1和ω2為權(quán)重。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3路徑規(guī)劃實(shí)驗(yàn)

3.1仿真實(shí)驗(yàn)

3.1.1實(shí)驗(yàn)設(shè)計(jì)

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

3.1.2實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

3.2.1實(shí)驗(yàn)設(shè)計(jì)

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

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

3.2.2實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

4結(jié)束語

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

參考文獻(xià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］李曉旭， 馬興錄， 王先鵬． 移動(dòng)機(jī)器人路徑規(guī)劃算法綜述[J]． 計(jì)算機(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òng)導(dǎo)引車路徑規(guī)劃算法的研究綜述[J]． 自動(dòng)化與儀器儀表， 2023（9）： 8-15．

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

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

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

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

［9］余震， 王棟， 王明天， 等． 基于改進(jìn)A～*算法的AGV全局路徑規(guī)劃[J]． 武漢科技大學(xué)學(xué)報(bào)， 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］王向宇． 基于改進(jìn)A～*算法和動(dòng)態(tài)窗口法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃研究[D]． 贛州： 江西理工大學(xué)， 2023．

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

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

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

［15］趙曉， 王錚， 黃程侃， 等． 基于改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J]． 機(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

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

第一作者： 張亞萌（2001-），男，碩士研究生，主要研究方向?yàn)槿斯ぶ悄堋?/p>

通信作者： 符朝興（1967-），男，博士，副教授，主要研究方向?yàn)槿斯ぶ悄芎蜋C(jī)械振動(dòng)。Email： cx_f@163.com