基于改進A*算法的機器人路徑搜索的研究

谷月 張德育 晉峰高

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

關鍵詞：人工智能;移動機器人;路徑搜索;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 ?引 ?言

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

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

1 ?復雜環境中環境模型的建立

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

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

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

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

2 ?A*搜索算法的改進

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

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

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

2.1 ?A*搜索算法流程

傳統A*搜索算法的搜索步驟如下：

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

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

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

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

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

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

（7）重復這個過程，直到目標節點被添加進關閉列表。

2.2 ?A*回溯算法

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

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

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

2.3 ?A*跳點搜索

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

3 ?實驗結果與分析

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

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

4 ?結 ?論

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

參考文獻：

[1] 柯星.動態環境下多移動機器人路徑規劃研究 [D].成都：電子科技大學，2013.

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

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

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

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

作者簡介：谷月（1996—），女，漢族，河北任丘人，碩士，研究方向：系統監控與網絡管理技術。