谷月 張德育 晉峰高

摘 ?要：隨著全球科技技術(shù)的不斷發(fā)展，人類對未知的不斷探索和對科技的需求不斷增加，移動機器人也在科技的浪潮中應(yīng)運而生，并且一直處在人工智能科技的前沿。移動機器人的應(yīng)用與人們的生活聯(lián)系越來越緊密，其最重要的研究方向是對路徑搜索算法的研究，比如某些尋路游戲機器人、資源探索機器人、自動尋路機器人、搜索營救機器人等。該文對機器人路徑搜索算法的研究，在A*算法的基礎(chǔ)上做了改進，整體提高了搜索的效率。

關(guān)鍵詞：人工智能;移動機器人;路徑搜索;A*算法

中圖分類號：TP242 ? ? ?文獻標識碼：A 文章編號：2096-4706（2020）13-0030-03

Abstract：With the continuous development of global science and technology，humans continuous exploration of the unknown and the increasing demand for science and technology in the process，the development of intelligent robot also arises at the historic moment in the tide of science and technology，has been in the forefront of artificial intelligence technology. The application of mobile robot is more and more closely related to people's life. The most important research direction of intelligent robots is the study of path search algorithms，such as some pathfinding game robots，resource exploration robots，automatic pathfinding robots，search and rescue robots，etc. The research on the robot path search algorithm is improved on the basis of the A* algorithm，which improves the search efficiency as a whole.

Keywords：artificial intelligence;mobile robot;path search;A* algorithm

0 ?引 ?言

近年來，人工智能技術(shù)不斷發(fā)展，其在移動機器人的應(yīng)用越來越廣泛，移動機器人在實際生活中應(yīng)用最多、最重要的是路徑搜索問題。在未知環(huán)境中，通過移動機器人進行路徑搜索的研究還不是太完備，搜索算法的效率還有待提升。移動機器人的路徑搜索問題主要是從搜索時間、搜索效率、搜索能耗等方面進行研究的，機器人的路徑搜索所解決的問題是在復(fù)雜環(huán)境中自主搜索出一條可行的較優(yōu)路徑。目前廣泛使用的搜索算法是啟發(fā)式搜索算法中的A*算法，在簡單環(huán)境下，A*算法可以較高效地搜索出最優(yōu)路徑。但是在復(fù)雜環(huán)境下，移動機器人使用A*算法進行路徑搜索卻變得不那么容易，搜索的效率還有待提高，因為復(fù)雜環(huán)境下障礙物的分布多且形狀復(fù)雜，機器人需要在避障的同時搜索路徑，因此對路徑搜索算法的效率會有影響，一些常用的路徑搜索算法在復(fù)雜環(huán)境下的搜索效率也會受到很大的影響。

因此本文基于校內(nèi)對移動機器人路徑搜索項目的研究，以A*算法為研究重點，進行改進，對移動機器人路徑搜索的整個過程進行研究。并提出改進的想法，闡述改進的過程。

1 ?復(fù)雜環(huán)境中環(huán)境模型的建立

環(huán)境模型的建立是路徑搜索算法研究過程中非常重要的一步，環(huán)境模型的建立有視圖法、拓撲法和柵格法。柵格法是由一個個大小相等的正方形小格組成，構(gòu)成一個連通圖，可用坐標表示各個柵格，障礙物在柵格中用黑色表示。路徑搜索算法搜索路徑的過程就是設(shè)置一個初始節(jié)點和一個目標節(jié)點，通過搜索算法生成從初始節(jié)點到目標節(jié)點的最優(yōu)路徑。

機器人的環(huán)境模型是對其現(xiàn)實環(huán)境的仿照，為了更準確地描述機器人所處的環(huán)境，采用正方形柵格表示法來建立環(huán)境模型。按照真實的地圖環(huán)境和機器人的大小比例，建立大小合適的正方形柵格地圖用于算法的研究，在這里我們將被控物體看成是點狀物體，它的移動環(huán)境是二維平面，黑色格塊對應(yīng)柵格地圖中的障礙物，白色格塊是可以通行的自由格塊;將每一個正方形柵格與坐標相對應(yīng)，坐標可用P（x，y）表示，每個柵格都有對應(yīng)的屬性。

當柵格的屬性為0時，柵格為自由柵格，可以通行;當柵格的屬性為1時，柵格為障礙物柵格，不可以通行;當柵格的屬性為2時，柵格表示路徑搜索的初始位置;當柵格的屬性為3時，柵格表示路徑搜索的目標位置。

柵格大小的選取影響著整個移動機器人路徑搜索算法的效率，柵格如果選取得過大，相應(yīng)的計算量會變少，但得到的路徑長度可能會變大;另一方面，柵格選取得過小，雖然搜索路徑的效率會提高，但是搜索時間會變長，搜索過程緩慢。所以柵格大小的選取根據(jù)所處的環(huán)境來決定，柵格長度選取為l=（r+R）+λ;其中，r是障礙物的半徑大小，R是機器人的半徑大小，λ是設(shè)定的安全距離。由以上條件可知，移動機器人在復(fù)雜環(huán)境下路徑搜索算法的研究可轉(zhuǎn)化為通過在已得到的環(huán)境模型中的無障礙物的區(qū)域搜索，最終得到的一個連續(xù)路徑。

2 ?A*搜索算法的改進

啟發(fā)式算法是路徑搜索算法中最常用的搜索算法，A*算法也屬于其中，啟發(fā)式搜索算法就是根據(jù)對柵格地圖中每一個柵格的相鄰柵格位置進行搜索比較，從相鄰柵格中找到距離目標點最近的柵格，再從這個柵格進行搜索比較，直到搜索到目標節(jié)點為止。然而在啟發(fā)式搜索中，對于柵格位置的評估是十分重要的，根據(jù)選取最佳搜索節(jié)點的策略不同，采用不同的估價函數(shù)有著不同的效果，其中A*搜索算法中的估價函數(shù)表示為：

傳統(tǒng)A*算法能夠有效地對目標進行全局路徑搜索，但是在較為復(fù)雜的環(huán)境中，A*算法優(yōu)化后得到的路徑冗余點較多、運動路線折線多、轉(zhuǎn)折次數(shù)多、轉(zhuǎn)折角度大，這些缺陷嚴重影響路徑搜索的效果，直接影響算法的執(zhí)行效率。為此，本文提出對傳統(tǒng)A*算法改進的想法，并對考察節(jié)點數(shù)、花費時間、路徑開銷和是否最優(yōu)四個方面進行優(yōu)化改進。在標準A*算法的基礎(chǔ)上增加父節(jié)點，防止走到死路，減少冗余點。該A*算法改進成跳點搜索的方法進行優(yōu)化，這種方法能夠減少搜索的節(jié)點和轉(zhuǎn)折次數(shù)。

本文對A*改進并進行路徑搜索的流程圖如圖1所示。

2.1 ?A*搜索算法流程

傳統(tǒng)A*搜索算法的搜索步驟如下：

（1）把起始節(jié)點看作是點A進行搜索，建立一個開啟列表，將點A加入此列表。開啟列表存儲待搜索的節(jié)點。

（2）在節(jié)點A的可搜索方向進行搜索，搜索所有可到達目標節(jié)點的相鄰節(jié)點，將這些節(jié)點存儲到開啟列表中。

（3）節(jié)點A已經(jīng)搜索完畢，就從開啟列表中將其刪除，將節(jié)點A加入閉合列表。

（4）按照公式F=G+H計算A點所有周圍點的H值，選取開啟列表中H值最低的節(jié)點B，將此節(jié)點作為A之后搜尋到的節(jié)點，并加入閉合列表中。

（5）繼續(xù)從B節(jié)點開始搜索所有相鄰節(jié)點，除去閉合列表中的節(jié)點。

（6）如果存在B的相鄰節(jié)點不在開啟列表中，則將它們加入，如果節(jié)點B的相鄰節(jié)點都已經(jīng)在開啟列表中，并且存在G值低于B點G值的點，那么放棄B節(jié)點作為A的下一個節(jié)點。然后按照F值最低原則選擇開啟列表里其他節(jié)點作為A點的下一個節(jié)點。

（7）重復(fù)這個過程，直到目標節(jié)點被添加進關(guān)閉列表。

2.2 ?A*回溯算法

傳統(tǒng)的A*算法是通過將搜索路徑過程中的信息存儲起來，然后再從最后一個節(jié)點信息向第一個信息節(jié)點逆向提取，提取出的節(jié)點可形成一條路徑，即為搜索到的路徑。但是在多障礙物的環(huán)境下會出現(xiàn)死胡同現(xiàn)象，搜索過程中無法找到下一個最優(yōu)節(jié)點，搜索過程一直等待，無法進行下去，形成死路，無法搜索到最優(yōu)路徑。算法的搜索效率變低，因此改進的A*回溯算法是在原來的基礎(chǔ)上增加了父節(jié)點，避免走彎路，而且在較為復(fù)雜的環(huán)境中也能更好地進行路徑搜索。從而達到提取最優(yōu)路徑的效果。

本文通過增加父指針對搜索步驟進行改進，如果當前搜索到的下一個節(jié)點比當前節(jié)點更優(yōu)時，就刪除當前節(jié)點，將當前節(jié)點加入閉合列表。然后父指針就指向該節(jié)點。搜索的過程不會改變。最終會通過閉合列表和父節(jié)點列表，根據(jù)父指針開始逆向搜索到開始節(jié)點，忽略冗余點，得到路徑。

在搜索節(jié)點的數(shù)目上、搜索時間上，增加父節(jié)點的A*回溯算法比標準A*算法有明顯的優(yōu)勢，A*回溯算法有效地避免了死路，有效節(jié)省了路徑開銷。

2.3 ?A*跳點搜索

在路徑優(yōu)化過程中，為了進一步減少搜索的節(jié)點和冗余點，在A*算法搜索過的路徑節(jié)點中，選取跳點作為新的節(jié)點，將式（1）中的估價函數(shù)作為初始值進行比較，根據(jù)代價函數(shù)的大小比較和不穿過障礙物為評價標準。如果選取的跳點的代價函數(shù)小于初始值并且沒有穿過障礙物，則選取這個跳點為新的路徑節(jié)點，將這些新的路徑節(jié)點連接起來就組成了新的路徑，僅包含開始節(jié)點、中間轉(zhuǎn)折點和目標節(jié)點。

3 ?實驗結(jié)果與分析

經(jīng)過改進后的A*算法與標準A*算法的路徑搜索仿真如圖所示，圖2為傳統(tǒng)的A*算法路徑仿真圖，圖3為改進后的A*算法路徑仿真圖。

由仿真圖的對比中可以看出改進算法后搜索的路徑冗余點減少、運動路線折線減少、轉(zhuǎn)折次數(shù)變少、轉(zhuǎn)折角度更平滑。

4 ?結(jié) ?論

本文在A*算法的基礎(chǔ)上對移動機器人的路徑搜索進行研究，引入了父節(jié)點，對一些搜尋到死路節(jié)點時的情況進行了優(yōu)化;而且通過A*回溯算法可以刪除多余的冗余點，縮短路徑搜索的時間。再進一步通過跳點搜索的原理，將A*回溯算法搜索的路徑進行優(yōu)化，進一步減少擴展節(jié)點，將整個搜索的路徑長度縮短、減少轉(zhuǎn)折次數(shù)、縮小轉(zhuǎn)折角度、平滑搜索到的路徑，在一定情況下可以提高路徑搜索的效率，優(yōu)化路徑搜索的結(jié)果。

參考文獻：

[1] 柯星.動態(tài)環(huán)境下多移動機器人路徑規(guī)劃研究 [D].成都：電子科技大學(xué)，2013.

[2] 鄔再新，李艷宏，劉濤.多移動機器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望 [J].機械，2008（1）：1-3+16.

[3] 王洪斌，郝策，張平，等.基于A*算法和人工勢場法的移動機器人路徑規(guī)劃 [J].中國機械工程，2019，30（20）：2489-2496.

[4] 王殿君.基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃 [J].清華大學(xué)學(xué)報（自然科學(xué)版），2012，52（8）：1085-1089.

[5] 紀海賓，師彩云.基于Origin的移動機器人測距傳感器參數(shù)標定 [J].現(xiàn)代信息科技，2020，4（9）：40-42+45.

作者簡介：谷月（1996—），女，漢族，河北任丘人，碩士，研究方向：系統(tǒng)監(jiān)控與網(wǎng)絡(luò)管理技術(shù)。