移動機器人全局路徑規劃算法的研究

黃 靜，陳漢偉

(浙江理工大學信息學院，浙江杭州 310018)

0 引言

目前，移移動機器人普遍存在行動機械、決策遲鈍的問題，無法真正實現模擬自然環境中生物體的行為模式。因此，如何使這些移動機器人擁有較為真實的行為能力成為一個研究熱點。全局路徑規劃是移動機器人要解決的重要問題之一[1]，作用是移動機器人在已知錯綜復雜的地形的狀況下，找到一條到目標位置較優的路徑，不僅能夠有效避開障礙，而且時間開銷較短。由于特殊地形、障礙、多角色實時移動等因素，使路徑規劃變得十分復雜。優秀的路徑規劃方法不僅可以讓移動機器人的行為讓用戶看起來更加智能，而且能夠節約大量的運算時間。

如圖1所示，盡管兩條路徑的長度相同，圖1(b)模型顯然更符合現實中智能體的移動規律。

(a)路徑一

(b)路徑二圖1無障礙普通路徑規劃示意圖

文中針對移動機器人智能化中的路徑規劃問題，著重研究了盲目式搜索算法、A*算法和遺傳算法，使用A*算法在Unity平臺上實現移動機器人的路徑規劃模塊，旨在提高路徑搜索的效率，提升移動機器人的真實感。

1 路徑規劃算法的研究與分析

1.1 盲目式搜索算法

深度優先搜索算法(Deep First Search, DFS)和廣度優先搜索算法(Breadth First Search, BFS)是兩種常見的搜索算法[2]。

DFS沿著樹的深度遍歷地圖中的節點，盡可能深地搜索分支節點。當一個節點i的所有子節點都已被探尋過，搜索將回溯到發現節點i的那條邊的起始節點。如果并沒有搜索到目標節點，則選擇其中一個作為源節點并重復以上過程，整個進程反復進行直到發現目標節點為止。深度優先算法找到的路徑通常不是最短或最有效的路徑，在場景地形復雜、障礙物繁多的情況下，搜索到的路線常常偏離目標方向，具有一定的盲目性，搜索的過程也缺乏移動機器人應有的智能性。圖2為深度優先搜索的示意圖。

BFS則是從起始節點開始，先訪問起始節點的所有子節點，再訪問子節點的所有子節點，直到搜索到目標節點為止。這種搜索方式可以搜索到最短的路徑，但是算法本身消耗的時間根本無法滿足移動機器人決策模塊對實時性的要求。圖3為廣度優先搜索的示意圖。

使用C/C++實現DFS和BFS搜索算法，解決一個20×20的矩陣中的路徑搜索問題，起始點為點[3,3]，搜索目標點為點DFS和BFS都是盲目式搜索算法，算法進行搜索的時候，不會對節點進行評估，且跳轉到最優結點進行下一步的搜索。當搜索狀態最為糟糕的時候，算法很可能需要搜索整個地圖空間才能得出所需的路徑。顯然，這類盲目型搜索算法只能適用于解決規模不大的搜索問題。

圖2 DFS示意圖

圖3 BFS示意圖

[17,17]，結果如圖4和圖5所示。實驗結果證明，DFS的搜索路徑十分地盲目，完全不符合智能體的決策行為，而BFS能夠更為有效地搜索到最短路徑，路徑較真實，但時間消耗較大。

圖4 DFS路徑搜索的實現

圖5 BFS路徑搜索的實現

1.2 A*算法

不同于DFS和BFS等傳統的盲目式搜索算法，啟發式搜索算法在從一個節點向下一個節點搜索時，會引入一個啟發函數，這個啟發函數為每一個子節點進行評估，選擇子節點中評估值最低的節點作為路徑的節點。優秀的啟發函數可以迅速地搜索到路徑規劃問題中的最優路徑。A*算法是啟發式搜索中比較有效的方法[3]，常用于解決最優路徑問題及其他一些策略性問題。

在路徑規劃過程中，A*算法會引入一些具有啟發意義的信息，這些信息能夠引導算法發現有效的路徑。算法通常使用一個啟發函數表示這些信息，在搜索的過程中使用啟發函數對路徑規劃中的搜索位置進行評估，選取評估值最低的節點作為路徑節點，并從這個節點再次進行進一步搜索，直到目標節點被搜索到，完成整個搜索過程。A*算法避免了路徑規劃問題中常常產生的大量無效搜索路徑，相對于盲目式搜索，提高了算法本身的搜索效率。

A*算法中最重要的就是算法的啟發函數：

f(n)=g(n)+h(n)

(1)

式中：f(n)是路徑中每個可能搜索節點的評估值，由兩部分組成：g(n)表示從起始節點到當前節點的評估值；h(n)表示當前節點到目標節點的評估值，h(n)的優劣會直接影響算法的性能，也決定了算法是否能夠被定義為A*算法。

如果要將啟發式搜索算法定義為A*算法，需要保證路徑規劃問題中存在著從起始節點到目標節點的最優路徑，而且路徑中所有節點的評估值都大于零。此外，h(n)需要盡量地接近路徑規劃問題的實際評估值h*(n)。

路徑規劃問題存在解、節點評估值大于零，這些條件都比較容易滿足，但是如果要滿足h(n)接近實際評估值就需要進行有效的設計。A*算法中的h(n)和h*(n)相差不能過大[4-5]，過小的h(n)會使整個算法的區分能力減弱，從而使算法的效率降低。優秀的h(n)應該盡量逼近h*(n)，但是始終小于h*(n)[6-7]。這種設計不僅可以增加啟發信息，還能減少搜索過程中需要探索的節點數，從而有效提高算法的搜索速度。

和盲目式搜索算法相比，A*算法搜索時探索的節點要少很多，而且路徑的效果較好，如圖6所示。

圖6 A*搜索算法的實現

1.3 遺傳算法

遺傳算法是一種模擬自然選擇和遺傳機制的隨機搜索算法[8-9]。遺傳算法模擬生物遺傳過程中發生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從種群中選取較優的個體，利用遺傳算子進行選擇、交叉和變異，對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足預置收斂指標為止。

基本過程如下：

(1)初始化。確定種群規模N、交叉概率Pc、變異概率Pm和置終止進化準則；隨機生成個體數量為N的種群作為初始種群Population(t)；種群代數t=0。

(2)個體評價。計算或估價Population(t)中各個體的適應度。

(3)種群進化。

①選擇親代染色體。從Population(t)中運用選擇算子選擇出M/2對染色體(M≥N)。

②交叉。對所選擇的M/2對染色體，根據Pc的概率執行交叉形成M個臨時個體。

③變異。M個臨時個體都有Pm的幾率發生變異，形成M個候選個體。

④選擇子代染色體。從上述所形成的M個候選個體中根據適應度選擇出N個個體組成新一代種群Population(t+1)。

(4)終止檢驗。如果已經滿足終止的條件，則輸出Population(t+1)中具有最大適應度的個體作為最優解，終止計算；否則置t=t+1并轉至步驟(3)。

在智能體的路徑規劃中，文中將四個搜索動作編碼為二進制碼，如表1所示。

表1 遺傳算法二進制編碼

由表1中編碼組成的二進制序列，如00100111，就是遺傳算法在解決路徑規劃時的一個染色體。若要評估這條染色體的適應度，則從起始點開始，根據染色體中的編碼進行搜索。若其中的一個編碼使本次搜索遇到了障礙，則忽略該編碼，使用下一個編碼繼續搜索，直到歷遍所有編碼或者抵達目標位置。適應度fitness由這次搜索的最終位置距離目標位置的距離d給出：

(2)

圖7、圖8為使用遺傳算法進行路徑搜索的實驗結果。從圖中易知，遺傳算法能夠有效地搜索到目標位置，且規劃的路徑較符合自然環境中智慧生物的決策行為。然而，隨著地圖面積的增大，遺傳算法在解決此類問題時就需要增長染色體的長度，增加種群的規模，因此算法的計算量往往變得十分龐大，這顯然無法滿足移動機器人的高實時性需求[10]。當虛擬場景的地圖較大，起始位置和目標位置相聚較遠時，遺傳算法并不是最合適的路徑規劃算法。

圖7 進化4次后的路徑

圖8 進化11次后的路徑

1.4 算法總體分析

盲目式的搜索算法不僅運算時間長，而且搜索得到的路徑真實性差；遺傳算法得到的路徑較符合現實中智能體的路徑選擇方式，但運算量大，耗時長，無法滿足實時性要求；啟發式的搜索算法能夠有效利用路徑中的啟發信息，搜索得到的路徑真實，運算效率較好。A*算法能夠有效解決傳統虛擬環境路徑搜索算法造成的避障不及時，原地徘徊等移動機器人反應不靈活等問題，而且效率較好。

2 A*路徑規劃的應用及其優化

本文利用Unity平臺[11-12]虛擬移動機器人路徑規劃模塊，針對移動機器人行動遲鈍，行動時模型重疊等問題，選取最適用于移動機器人路徑規劃的A*算法設計移動機器人的路徑規劃模塊，并且使用貪婪平滑算法進行優化，旨在使虛擬移動機器人能夠靈活避開障礙。

A*算法需要維持兩張列表：存放未評估節點的Open表和存放已評估節點的Closed表，具體實現方式如下：

(1)把起始節點添加到Open表。

(2)考察Open表

①如果Open表中的元素為空，則表示搜索失??；尋找Open表中f(n)值最低的節點作為當前的搜索節點，并把它移入Closed表中。

②如果當前點為終點，則路徑規劃成功，轉驟(4)。

(3) 對相鄰的上下左右4個方向的每個節點進行如下操作。

①如果該節點不可訪問，或者已經存在于Closed表中，忽略該節點。

②如果該節點不在Open表中，把它添加進去，并記錄它的f(n)、g(n)和h(n)值。

③如果該節點已經在Open表中，用f(n)值作為參考檢查新的路徑是否更好，即有更低的f(n)值，并且重新計算該點的f(n)值。

④ 如果所有方向都已搜索完畢，則轉向驟(2)；否則，轉向步驟(3)。

(4) 保存路徑，根據Closed表中的節點信息，進行逆向提取，便能夠得到一條從起始節點到目標節點的路徑。

場景中的小型圓柱體需要需找一條從A點到達B點，并且能繞過障礙物的有效路徑。場景設計如圖9所示，路徑搜索的實驗結果如圖10所示。實驗結果表明，A*算法能夠有效地避開路徑中的障礙物抵達目標，而且能夠滿足決策模塊對實時性要求。

圖9 實驗場景設計

(a) 障礙一

(b) 障礙二圖10 在不同障礙場景中的路徑搜索結果

然而，從實驗結果也容易發現，A*算法搜索產生的路徑存在一些多余路徑，這是由于算法的啟發函數并不一直最佳。因此，需要對A*算法得到的路徑進行優化。在規劃路徑的過程中，如果相鄰的兩條直線路徑之間沒有障礙物，就使用一條路徑代替這兩條路徑。

文中采用貪婪平滑算法改進A*算法[13-14]規劃生成的路徑。將A*生成的路徑按下列步驟進行平滑：

(1)將路徑中的第一點作為貪婪平滑算法的起點；

(2)如果路徑中從起點開始后續沒有連續的3個點，則轉到步驟(4)；否則每次從路徑當前起點開始連續取3個點，分別為記為a，b，c，如果ac直線路徑上沒有障礙并且ac長度小于ab長度加上bc長度，則在路徑中刪除b點，保持起點不變，重新執行步驟(2)；否則執行步驟(3)；

(3)將起點的下一點作為新的計算起點，轉到步驟(2)執行；

(4)路徑剩余的點就是平滑后的新路徑。

算法優化前后的效果如圖11和圖12所示。

圖11 普通A*算法的路徑圖

圖12 優化后的A*算法的路徑

通過貪婪平滑算法改進的A*算法，能夠使移動機器人的行動路徑更加接近真實智慧生命體的路徑選擇方式，并且依然居然較好的算法執行效率。

3 結論

文中基于Unity3D平臺，針對移動機器人智能化中的全局路徑規劃問題，研究了盲目式搜索算法、遺傳算法和A*算法的優劣：遺傳算法雖然夠有效地搜索到目標位置，但并不適合地圖場景較大的情況；使用A*算法實現移動機器人的路徑規劃模塊，相比傳統的盲目搜索算法，能夠有效尋找當前位置到目標位置成本最小的路徑，然而實驗結果表明，A*算法的啟發函數并不總是最佳的，路徑搜索過程中會產生一些拐角或者其他形式的多余路徑，需要進行路徑優化。文中利用貪婪平滑算法對A*算法進行優化，算法效率較好，移動機器人的智能性較強。

參考文獻：

[1] 王麗. 移動機器人路徑規劃方法研究：[學位論文]. 西安: 西北工業大學, 2007.

[2] 曲道奎,杜振軍,徐殿國,等. 移動機器人路徑規劃方法研究. 機器人, 2008(2): 97-101.

[3] 史輝, 曹聞, 朱述龍，等. A*算法的改進及其在路徑規劃中的應用. 測繪與空間地理信息, 2009(6): 208-211.

[4] 陳剛, 付少鋒, 周利華. A*算法在游戲地圖尋徑中的幾種改進策略研究. 科學技術與工程, 2007(15): 3731-3736.

[5] 邱磊. 基于A～*算法的游戲地圖尋路實現及性能比較. 陜西科技大學學報(自然科學版), 2011(6): 89-93.

[6] 王紅衛, 馬勇, 謝勇，等. 基于平滑A*算法的移動機器人路徑規劃. 同濟大學學報(自然科學版), 2010, (11): 1647-1650.

[7] 劉浩, 鮑遠律. A*算法在矢量地圖最優路徑搜索中的應用. 計算機仿真, 2008(4): 253-257.

[8] 陳華華,杜歆,顧偉康. 基于遺傳算法的靜態環境全局路徑規劃. 浙江大學學報(理學版), 2005(1): 49-53.

[9] 馬永杰, 云文霞. 遺傳算法研究進展. 計算機應用研究, 2012(4): 1201-1206.

[10] 唐文艷. 結構優化中的遺傳算法研究和應用：[學位論文].大連：大連理工大學, 2002.

[11] 陳俊鋒. 基于Unity3D的跨平臺手機網絡游戲的研究與實現：[學位論文]. 廣州：中山大學, 2013.

[12] 鄭磊. 基于三維網頁技術的Unity3D教學管理系統的設計與實現：[學位論文]. 上海：上海交通大學, 2013.

[13] ZHANG Z Y，ZHAO Z P. A multiple mobile robots path planning algorithm based on a-star and dijkstra algorithm．International Journal of Smart Home, 2014, 8(3)：75-86.

[14] LI J，SUN X X. Route planning's method for unmanned aerial vehicles based on improved a-star algorithm. Acta Armamentarii, 2008, 29(7), 788-792