基于節(jié)點(diǎn)優(yōu)化的改進(jìn)全局路徑規(guī)劃A＊算法

衛(wèi) 彥，晉 芳，董凱鋒，宋俊磊，莫文琴，惠亞娟

（1.中國地質(zhì)大學(xué)（武漢）自動化學(xué)院，武漢 430074；2.復(fù)雜系統(tǒng)先進(jìn)控制與智能自動化湖北省重點(diǎn)實驗室，武漢 430074；3.地球探測智能化技術(shù)教育部工程研究中心，武漢 430074）

0 引言

隨著機(jī)器人技術(shù)的發(fā)展，機(jī)器人的功能從最開始的只能在固定位置做重復(fù)循環(huán)工作發(fā)展到如今可以根據(jù)指令在室內(nèi)室外進(jìn)行移動作業(yè)，并且能夠解決突發(fā)問題，移動機(jī)器人的能夠?qū)崿F(xiàn)的功能越來越豐富，移動機(jī)器人應(yīng)用的領(lǐng)域越來越多，在很多行業(yè)已經(jīng)使用移動機(jī)器人來代替人工作業(yè)。除了簡單的搬運(yùn)、運(yùn)輸工作，移動機(jī)器人還可以代替人類去做一些危險的工作，例如高空作業(yè)、危險探測、野外勘探等。隨著新冠疫情的爆發(fā)，人們再一次認(rèn)識了移動機(jī)器人的重要性。疫情期間的很多物資運(yùn)輸采用移動機(jī)器人就可以減少感染風(fēng)險。

比起以前單純靠人力和物力進(jìn)行的工作，移動機(jī)器人的工作效率和工作準(zhǔn)確率都更高，因此在在全球的經(jīng)濟(jì)貿(mào)易交流越來越頻繁的時代，很多傳統(tǒng)的依靠人工的方法逐漸被淘汰，掌握機(jī)器人的核心技術(shù)就相當(dāng)于抓住了經(jīng)濟(jì)的命脈。室內(nèi)移動機(jī)器人是我們在生活中能夠經(jīng)常接觸到的移動機(jī)器人。目前一些超市、餐廳已經(jīng)大規(guī)模投入使用移動機(jī)器人完成送餐工作；掃地機(jī)器人也是目前很多人會購買的家用室內(nèi)機(jī)器人。在2022北京冬奧會期間，投入使用了很多室內(nèi)移動機(jī)器人。例如食堂采用了送餐機(jī)器人給運(yùn)動員和工作人員們送餐；提供給媒體居住的酒店里應(yīng)用了室內(nèi)移動機(jī)器人消毒技術(shù)；各大場館還有防疫用的巡控移動機(jī)器人。

室內(nèi)移動機(jī)器人要完成任務(wù)，要解決的重要問題之一就是怎么去目標(biāo)地點(diǎn)，也就是路徑規(guī)劃問題。路徑規(guī)劃是移動機(jī)器人工作的重要保障之一，是移動機(jī)器人完成導(dǎo)航和其他任務(wù)的前提［4］。路徑規(guī)劃是指按照一定的標(biāo)準(zhǔn)，根據(jù)起點(diǎn)和終點(diǎn)規(guī)劃出一條規(guī)避障礙物的路徑。路徑規(guī)劃的主要內(nèi)容為：預(yù)設(shè)地圖環(huán)境模型，輸入起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，路徑規(guī)劃的輸出則是基于已設(shè)定的地圖模型得到的連接起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，并且不與地圖模型中的障礙物產(chǎn)生碰撞的最優(yōu)有效的序列點(diǎn)，最終把序列點(diǎn)連接將變成機(jī)器人在實際環(huán)境中的運(yùn)動軌跡。路徑規(guī)劃算法分為全局路徑規(guī)劃算法和局部路徑規(guī)劃算法，常用的全局路徑規(guī)劃算法有A＊算法、蟻群算法、遺傳算法和粒子群算法，常用的局部路徑規(guī)劃算法有人工勢場法、速度障礙法和動態(tài)窗口算法等［1］。

在路徑規(guī)劃算法中，A＊算法作為一種啟發(fā)式算法，有著廣泛的應(yīng)用領(lǐng)域［3］。但是A＊算法存在著路徑不平滑、拐點(diǎn)多、路徑非優(yōu)等問題［2］。針對這些不足，學(xué)者們研究出了很多改進(jìn)型A＊算法：文獻(xiàn)［3］通過改進(jìn)評價函數(shù)的計算方式和權(quán)重比例，減少生成路徑中的拐點(diǎn)，使生成的路徑更平滑。文獻(xiàn)［4］在改進(jìn)啟發(fā)函數(shù)的基礎(chǔ)上對生成的路徑做五次多項式平滑處理，減少了A＊算法的搜索時間，縮短了路徑長度。文獻(xiàn)［5］通過將3×3的搜索鄰域擴(kuò)展成7×7，減小了路徑轉(zhuǎn)折角度。文獻(xiàn)［6］在障礙物膨脹處理的基礎(chǔ)上使用射線法簡化冗余點(diǎn)，減少了50%以上的路徑轉(zhuǎn)折點(diǎn)。文獻(xiàn)［7］和文獻(xiàn)［1］通過對A＊算法生成的路徑進(jìn)行節(jié)點(diǎn)優(yōu)化，除去冗余點(diǎn)，縮短了路徑長度。上述方法都減少了A＊算法生成路徑的轉(zhuǎn)折點(diǎn)，減短了路徑長度，但是上述文獻(xiàn)中去除冗余點(diǎn)的方法在某些情況例如貼近障礙物的路徑比較多的情況下的路徑優(yōu)化效果不夠明顯。對此，本文在擴(kuò)大搜索鄰域基礎(chǔ)上引入一種隨機(jī)數(shù)去除冗余點(diǎn)的方法，使得路徑長度更短，訪問的節(jié)點(diǎn)個數(shù)更少，運(yùn)行時長更短，從而使得在貼近障礙物的路徑比較多的情況下的路徑優(yōu)化效果更好。

1 A＊算法原理

A＊算法是啟發(fā)式算法中常用的一種算法，通常在柵格地圖中進(jìn)行路徑規(guī)劃，對于當(dāng)前節(jié)點(diǎn)周圍的點(diǎn)使用評價函數(shù)對其進(jìn)行評估，選擇評價函數(shù)最小的點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，搜索到終點(diǎn)就停止搜索，最后將所有選擇的點(diǎn)在柵格地圖上連接起來，從而得到一條規(guī)避障礙物的完整路徑。A＊算法路徑規(guī)劃可以分為以下兩個部分進(jìn)行：環(huán)境建模和路徑規(guī)劃。

1.1 環(huán)境建模

A＊算法在路徑規(guī)劃前需要做環(huán)境建模，既生成有障礙物信息的柵格地圖，如圖1所示，白色區(qū)域為可通行區(qū)域，黑色區(qū)域為障礙物區(qū)域。柵格地圖通常以矩陣或者圖片的方式保存。對于圖片格式的柵格地圖，通常讀取圖片的像素獲得一個像素值矩陣即可使用。

圖1 柵格地圖

完成環(huán)境建模后，需定義算法在該柵格地圖中的搜索方式。常用A＊算法中，移動機(jī)器人通常在柵格地圖上采用3×3鄰域搜索，有8個運(yùn)動方向，即東、南、西、北、東南、東北、西南、西北，如圖2所示。將以當(dāng)前節(jié)點(diǎn)為中心的3×3鄰域中的節(jié)點(diǎn)作為備選節(jié)點(diǎn)，經(jīng)過比較后選擇擴(kuò)展的節(jié)點(diǎn)。因此在這種3×3鄰域搜索中，路徑是由很多段長度為1或者1.4個單位長度的路徑組成的。

圖2 移動機(jī)器人的8個運(yùn)動方向

1.2 A＊算法路徑規(guī)劃

接著在建立好的柵格地圖上實現(xiàn)路徑規(guī)劃。A＊算法路徑規(guī)劃有兩個列表，OPEN 列表和CLOSE 列表。A＊算法路徑規(guī)劃的基本思想是，從起點(diǎn)開始，將周圍3×3鄰域中的八個擴(kuò)展點(diǎn)加入到OPEN 列表，選擇OPEN 列表中評價函數(shù)最小的點(diǎn)作為下一個節(jié)點(diǎn)，并將選擇的節(jié)點(diǎn)記錄到CLOSE 列表，直到搜索到終點(diǎn)為止。A＊算法的評價函數(shù)為：

其中：f（n）是當(dāng)前點(diǎn)的評價函數(shù)，g（n）是起點(diǎn)到當(dāng)前點(diǎn)的實際代價即實際路徑長度，h（n）是當(dāng)前點(diǎn)到終點(diǎn)的最小估計代價，通常采用當(dāng)前點(diǎn)和終點(diǎn)的歐氏距離表示，即：

其中：（x＿n，y＿n）是當(dāng)前節(jié)點(diǎn)的坐標(biāo)，（x＿t，y＿t）是終點(diǎn)的坐標(biāo)。

A＊算法的路徑規(guī)劃實現(xiàn)流程如圖3 所示，具體步驟如下：

圖3 A＊算法路徑規(guī)劃實現(xiàn)流程

1）創(chuàng)建一個OPEN 列表和一個CLOSE 列表，將起點(diǎn)加入到OPEN 列表。

2）將除了CLOSE 列表中的節(jié)點(diǎn)和障礙物以外當(dāng)前節(jié)點(diǎn)的3×3搜索鄰域中的節(jié)點(diǎn)加入到OPEN 列表。

3）對OPEN 列表中的節(jié)點(diǎn)進(jìn)行評估，選出評估函數(shù)值f最小的節(jié)點(diǎn)n作為擴(kuò)展節(jié)點(diǎn)。

4）將已訪問的節(jié)點(diǎn)n放入CLOSE 列表，并判定n是否是終點(diǎn)，如果n不是終點(diǎn)，就回到第二步，如果n是終點(diǎn)，就結(jié)束此次路徑規(guī)劃。

2 改進(jìn)A＊算法

A＊算法路徑列表中存在冗余點(diǎn)，生成的路徑不是最優(yōu)路徑，且轉(zhuǎn)折點(diǎn)較多，轉(zhuǎn)折角度較大，路徑不夠平滑，這些問題會導(dǎo)致A＊算法在應(yīng)用在移動機(jī)器人運(yùn)動控制時，存在多余拐彎，加大控制難度的問題。為了優(yōu)化此問題，本文提出一種在搜索鄰域擴(kuò)大到5×5的基礎(chǔ)上隨機(jī)數(shù)選擇節(jié)點(diǎn)去除冗余點(diǎn)的改進(jìn)A＊算法。

2.1 冗余點(diǎn)去除方法

目前常用的去除冗余點(diǎn)方法有兩種：方法A 和方法B。方法A［15］就是先遍歷一遍路徑列表，找到其中的拐點(diǎn)，將起點(diǎn)、拐點(diǎn)和終點(diǎn)放在一個列表中，從起點(diǎn)開始，依次連接起點(diǎn)和各個拐點(diǎn)，若第n個拐點(diǎn)與起點(diǎn)的連線不經(jīng)過障礙物且第n＋1個拐點(diǎn)與起點(diǎn)的連線經(jīng)過障礙物，去除列表中起點(diǎn)與第n個拐點(diǎn)之間的拐點(diǎn)。再依次驗證列表中其他拐點(diǎn)之間的連線，最后提取剩余拐點(diǎn)，按照順序連接，生成路徑。如圖5 所示，針對［S，1，2，3，4，5，6，T］的路徑列表，生成一個只包含起點(diǎn)、拐點(diǎn)和終點(diǎn)的列表［S，1，2，3，5，T］，以起點(diǎn)為例，依次連接起點(diǎn)S和點(diǎn)3、點(diǎn)5、終點(diǎn)T，起點(diǎn)和點(diǎn)3的連線不經(jīng)過障礙物且起點(diǎn)S和點(diǎn)5的連線經(jīng)過障礙物，去除掉點(diǎn)1、點(diǎn)2。在去除全部冗余點(diǎn)之后，列表為［S，3，5，T］，最后按順序依次連接列表中拐點(diǎn)，生成如圖藍(lán)色路徑，路徑長度為7.16個單位長度。

方法B［4］與方法A 的原理類似。在路徑列表中從起點(diǎn)開始，依次連接起點(diǎn)和列表中的節(jié)點(diǎn)，若第n個節(jié)點(diǎn)與起點(diǎn)的連線不經(jīng)過障礙物且第n＋1個節(jié)點(diǎn)與起點(diǎn)的連線經(jīng)過障礙物，去除列表中起點(diǎn)與第n個節(jié)點(diǎn)之間的節(jié)點(diǎn)。再依次驗證列表中其他節(jié)點(diǎn)之間的連線，最后提取剩余節(jié)點(diǎn)，按照順序連接，生成路徑。如圖5所示，針對［S，1，2，3，4，5，6，T］的路徑列表。在去除全部冗余點(diǎn)之后，列表為［S，3，5，T］，最后按照順序依次連接列表中拐點(diǎn)，生成如圖紅色路徑。

方法A、B 去除冗余點(diǎn)的原理如圖4 所示。圖中l(wèi)en（path＿list）代表節(jié)點(diǎn)列表的長度。兩種方法判定冗余點(diǎn)的方法是一樣的，只不過方法A 在去除冗余點(diǎn)之前，多了一步尋找拐點(diǎn)的操作，接著在拐點(diǎn)列表中去除冗余點(diǎn)。

圖4 方法A 和B的工作原理流程圖

方法A、B在某一段路徑上的優(yōu)化結(jié)果如圖5所示。圖中由于非拐點(diǎn)的節(jié)點(diǎn)較少，方法A 和方法B優(yōu)化出來的路徑是一樣的。在稍復(fù)雜一些的環(huán)境中，方法A 在路徑長度的優(yōu)化效果上會比方法B 的差，但是方法B 的運(yùn)算次數(shù)會比方法A 多。

圖5 A＊算法和方法A、B去除冗余點(diǎn)效果對比

以上兩種去除冗余點(diǎn)的方式都有一定的局限性。方法A 會忽略掉非拐點(diǎn)，非拐點(diǎn)之間的連線也有不穿越過障礙物的可能。忽略掉非拐點(diǎn)會導(dǎo)致去除掉冗余點(diǎn)之后還是存在著路徑非最優(yōu)解的問題。而方法B運(yùn)算的次數(shù)太多，圖6中的路徑列使用方法A 只用運(yùn)算7次，而方法B 需要運(yùn)算13次，程序運(yùn)行時間更長。因此需要對去除冗余點(diǎn)的方法進(jìn)行優(yōu)化，找到一種結(jié)合兩者優(yōu)點(diǎn)的節(jié)點(diǎn)優(yōu)化的方法。

圖6 5×5搜索鄰域

2.2 擴(kuò)大搜索鄰域

A＊算法采用3×3鄰域擴(kuò)展節(jié)點(diǎn)的方法，一共有8個擴(kuò)展方向，轉(zhuǎn)折的角度不夠靈活，產(chǎn)生一些無效的轉(zhuǎn)彎路徑，導(dǎo)致生成的路徑并且不是最優(yōu)路徑。

針對這個問題，本文將3×3的鄰域擴(kuò)展成5×5的鄰域，即16個擴(kuò)展方向，如圖6所示。

以圖7的5×5地圖為例，圖中黑色圓點(diǎn)為當(dāng)前節(jié)點(diǎn)，紅色節(jié)點(diǎn)為目標(biāo)點(diǎn)。在使用3×3鄰域搜索時，由于搜索方向過于局限，導(dǎo)致從當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的路徑為向東北一個單元格再向北一個單元格，如圖中黑色實線所示，有一次轉(zhuǎn)折，在轉(zhuǎn)折處需要轉(zhuǎn)北偏東45°才能到達(dá)目標(biāo)點(diǎn)，路徑長度為2.4個單位長度。但是在使用5×5鄰域搜索時，只需要朝著北偏東26.57°運(yùn)動2.2個單位長度就可以直接到達(dá)目標(biāo)點(diǎn)，如圖中虛線所示，有效減少了轉(zhuǎn)折次數(shù)，轉(zhuǎn)折角度相比于3×3鄰域搜索也有所減小，更便于移動機(jī)器人運(yùn)動。

圖7 5×5搜索鄰域優(yōu)化效果

但是擴(kuò)大搜索鄰域并不能完全解決A＊算法路徑列表中有冗余點(diǎn)的問題，如圖8所示，5×5鄰域搜索出來的路徑需要先朝正北運(yùn)動1個單位長度，再朝北偏東26.57°運(yùn)動2.2個單位長度到達(dá)目標(biāo)點(diǎn)，而7×7鄰域搜索出來的路徑只需要朝北偏東18.44°運(yùn)動3.16個單位長度就能到達(dá)目標(biāo)點(diǎn)。5×5鄰域搜索出來的路徑會比7×7鄰域搜索出來的路徑長，且多一個轉(zhuǎn)折點(diǎn)。但是一味地擴(kuò)大搜索鄰域，并不適用于所有地圖，而且優(yōu)化效果有限，可以看到搜索鄰域越大，與原先生成的路徑組成的三角形的頂角越大，這樣優(yōu)化的路徑是比原先的路徑短不了太多。一味地擴(kuò)大搜索鄰域還可能會加大程序的計算量，使程序運(yùn)行時間變長。因此需要在適度擴(kuò)大搜索鄰域的基礎(chǔ)上去除冗余點(diǎn)。

圖8 7×7搜索鄰域優(yōu)化效果

2.3 冗余點(diǎn)去除方法改進(jìn)

目前廣泛使用去除冗余點(diǎn)的方法A、B有一個共同的缺點(diǎn)：過早地去除掉某些點(diǎn)會導(dǎo)致優(yōu)化效果不好。如圖9所示，圖9中路徑長度為6.06個單位長度，比圖5中的三條路徑都要短。但是在方法A 中，點(diǎn)2在起點(diǎn)和點(diǎn)3的連線不經(jīng)過障礙物的情況下被刪除，而點(diǎn)4和點(diǎn)6則早早地因為不是拐點(diǎn)被刪除掉了；在方法B 中點(diǎn)2在起點(diǎn)和點(diǎn)3的連線不經(jīng)過障礙物的情況下被刪除，點(diǎn)4和點(diǎn)6分別是因為點(diǎn)3和點(diǎn)5、點(diǎn)5和終點(diǎn)T 的連線不經(jīng)過障礙物被刪除。圖5中的路徑適合每兩個節(jié)點(diǎn)之間進(jìn)行連線驗證，這樣確實可以得出圖9中的路徑，但是局限性太大，并不是所有路徑都適合兩個兩個地驗證，因為在復(fù)雜一些的環(huán)境中，A＊算法規(guī)劃出來的路徑和其最優(yōu)解對比，最優(yōu)解在某一小段上的路徑的節(jié)點(diǎn)優(yōu)化的數(shù)字并不是固定的，在第一段中連接了第i個節(jié)點(diǎn)和第i＋a個節(jié)點(diǎn)，去除了這兩個點(diǎn)中間的節(jié)點(diǎn)；在第二段中連接了第n個節(jié)點(diǎn)和第n＋b個節(jié)點(diǎn)，去除了這兩個點(diǎn)中間的節(jié)點(diǎn)。因此，固定每幾個點(diǎn)之間連線驗證，是有非常大的局限性的。

圖9 優(yōu)于方法A 和方法B處理結(jié)果的路徑

為了解決這個問題，本文在將搜索鄰域擴(kuò)大至5×5的基礎(chǔ)上提出一種引入隨機(jī)數(shù)的去除節(jié)點(diǎn)列表冗余點(diǎn)方法。將搜索鄰域擴(kuò)大至5×5之后，有效減少了路徑列表中的節(jié)點(diǎn)，在5×5鄰域搜索出來的路徑列表中做節(jié)點(diǎn)優(yōu)化會減少很多運(yùn)算次數(shù)，有效優(yōu)化程序運(yùn)行時間。該方法的流程如圖10所示。具體步驟如下：

圖10 本文優(yōu)化算法去除路徑列表冗余點(diǎn)流程圖

1）依據(jù)地圖的大小，設(shè)定一個隨機(jī)數(shù)的取值范圍（a，b），設(shè)置一個循環(huán)次數(shù)r。

2）針對路徑列表，隨機(jī)?。╝，b）范圍內(nèi)的數(shù)字c，驗證和的連線是否經(jīng)過障礙物，若不經(jīng)過障礙物，則刪除列表中和之間的點(diǎn)。

3）按照順序依次檢測列表中的點(diǎn)，重復(fù)2），直到檢測到，整理剩下的點(diǎn)，依次連接列表中的點(diǎn)，生成路徑，計算路徑長度。

4）循環(huán)步驟2）和步驟3）r次，最后選擇路徑長度最短的一條路徑輸出。

在面對轉(zhuǎn)折點(diǎn)較多的路徑時，本文的算法中隨機(jī)數(shù)這一步可以保留方法A、B中被提前刪除掉的點(diǎn)，找出更優(yōu)的路徑。

3 仿真驗證

為了驗證本文改進(jìn)A＊算法的有效性和優(yōu)化效果，本文在不同環(huán)境建模的柵格地圖上進(jìn)行了仿真實驗，仿真軟件平臺為Python3.9，硬件平臺為Intel（R）Core（TM）i5-9500CPU＠3.00GHz，RAM 16GB。

首先，創(chuàng)建一個30×30的柵格地圖，障礙物占該地圖的30.6%，其中每個柵格代表一個單位（1m）。設(shè)置待規(guī)劃路徑起點(diǎn)坐標(biāo)為（5，17），終點(diǎn)坐標(biāo)為（27，2）。使用3×3搜索鄰域A＊算法在此地圖上進(jìn)行路徑規(guī)劃，得到的路徑如圖11所示?？梢钥闯鯝＊算法拐點(diǎn)較多，有8個拐點(diǎn)，存在明顯的冗余點(diǎn)。

圖11 A＊算法運(yùn)算結(jié)果

其次，使用常用的去除冗余點(diǎn)的方法A 和方法B 去除冗余點(diǎn)，結(jié)果如圖12（a）、（b）所示。方法A 生成的路徑拐點(diǎn)數(shù)減少到5個，方法B生成的路徑拐點(diǎn)數(shù)減少到4個?？梢钥闯鍪褂脙煞N方法后，路徑拐點(diǎn)較常用方法減少、長度有所縮短，但是仍然有優(yōu)化的空間，比較數(shù)據(jù)結(jié)果見表1。

表1 30×30地圖中算法運(yùn)行結(jié)果對比

圖12 方法A 和方法B處理后的路徑

然后在此地圖上使用將搜索鄰域擴(kuò)大至5×5的A＊算法進(jìn)行路徑規(guī)劃，結(jié)果如圖13（a）所示。路徑長度比A＊算法生成的路徑長度短，但轉(zhuǎn)折點(diǎn)比方法A 和B 生成的路徑多。接著使用本文提出的隨機(jī)去除冗余點(diǎn)法對圖13（a）所示路徑進(jìn)行優(yōu)化，在隨機(jī)數(shù)取值范圍為（2，8）、循環(huán)次數(shù)為10的情況下，運(yùn)行結(jié)果如圖13（b）所示。

圖13 5×5搜索鄰域A＊算法與隨機(jī)去除冗余點(diǎn)法處理后的路徑

整理上述A＊算法、方法A、方法B、5×5 搜索鄰域A＊算法與隨機(jī)去除冗余點(diǎn)運(yùn)行結(jié)果，對比如表1所示。表1中運(yùn)行時間、運(yùn)行長度均為運(yùn)行了10次的平均數(shù)?？梢钥吹奖疚奶岢龅碾S機(jī)去除冗余點(diǎn)法運(yùn)算出的訪問節(jié)點(diǎn)個數(shù)、運(yùn)行時長和路徑長度均優(yōu)于另外3種算法，證明隨機(jī)去除冗余點(diǎn)法在減少了A＊算法生成的路徑節(jié)點(diǎn)數(shù)和長度，減短了運(yùn)行時長。

為了驗證本文算法在不同方向路徑上的優(yōu)化效果，接著在此地圖中，選擇不同方向的幾組起點(diǎn)和終點(diǎn)進(jìn)行驗證，結(jié)果如表2、表3和表4所示。

表2 多組起點(diǎn)終點(diǎn)的路徑長度對比

表3 多組起點(diǎn)終點(diǎn)的運(yùn)行時長對比

表4 多組起點(diǎn)終點(diǎn)的訪問節(jié)點(diǎn)個數(shù)對比

可以看出，在此30×30柵格地圖中，面對不同方向的路徑，本文的算法在路徑長度、運(yùn)行時長和訪問節(jié)點(diǎn)個數(shù)上均優(yōu)于其他算法。結(jié)合上述4個表的數(shù)據(jù)，本文算法運(yùn)行結(jié)果對比A＊算法，路徑長度平均減少了4.46%，運(yùn)行時長平均減短了24.83%，訪問節(jié)點(diǎn)數(shù)平均減少了39.93%。

4 結(jié)束語

針對A＊算法拐點(diǎn)和冗余點(diǎn)較多的問題，本文在搜索鄰域擴(kuò)大至5×5的基礎(chǔ)上提出了一種引入隨機(jī)數(shù)去除節(jié)點(diǎn)列表冗余點(diǎn)的改進(jìn)A＊算法。通過仿真驗證并與其他算法對比，證明了本文算法有效改進(jìn)了A＊算法拐點(diǎn)和冗余點(diǎn)較多的問題，縮短了路徑長度、減少了訪問節(jié)點(diǎn)的個數(shù)并有效減少了運(yùn)行時間。但是該方法還存在一定的不足，如運(yùn)行的結(jié)果與隨機(jī)數(shù)取值范圍、循環(huán)次數(shù)有很大的關(guān)聯(lián)，不同的地圖適合的隨機(jī)數(shù)取值范圍和循環(huán)次數(shù)不同等。隨后將進(jìn)一步研究影響最優(yōu)隨機(jī)數(shù)取值范圍和循環(huán)次數(shù)的因素，找到適用于所有地圖的隨機(jī)數(shù)取值范圍和循環(huán)次數(shù)推導(dǎo)公式，使得該方法適用于更多地圖。