一種基于網格地圖的雙A*算法的改進方法

袁川涵

【摘 要】隨著科技的發展和技術的提升，機器人在現代社會中的應用越發廣泛。在機器人路徑規劃問題中，傳統的Dijkstra和A*算法為帶來了在運算速度方面的諸多便利。但是Dijkstra和 A*算法也有著運行效率偏低，找到最優解的準確率不高，路徑距離計算不精確等諸多問題。本文提出了基于雙A*算法的直線和曲線替代的方法，對在傳統網格地圖上的路徑問題就行了綜合的分析與算法上的改進。在不提高算法計算復雜度的前提下，提升了機器人路徑規劃的空間距離的優化和系統處理的效率，同時節省了處理過程的內存占用。

【關鍵詞】路徑規劃;空間距離;雙A*算法

中圖分類號： TP18;TP242文獻標識碼： A 文章編號： 2095-2457（2019）29-0148-002

DOI：10.19694/j.cnki.issn2095-2457.2019.29.069

0 概述

隨著現代科技的發展，人類生活愈發依賴機器人的協作和輔助，機器人路徑規劃問題成為當前研究的重要方向。人力成本的節約和機器人自身的效率的高低成了判定機器人是否實用的重要指標。在機器人路徑規劃問題的眾多解決方法中，工程師們通常采取的是以Dijkstra算法為基礎的A*算法來解決機器人路徑問題，但是A*算法自身的局限性和單一性，導致在一些特殊情況中，A*算法求解出的最短路徑往往不是最優解，并且具有占用系統內存高，時間耗費大等缺點。故在本文中我們討論了針對A*算法進行了的優化，并提出了一種新的最短路徑方法，能夠在減少其響應時間的同時使路徑變得更平滑，該優化方法相對于傳統的A*算法在效率得到了顯著的提升。

1 背景知識/算法介紹

1.1 Dijkstra算法

Dijkstra（迪杰斯特拉算法）算法是由荷蘭計算機科學家提出來以貪婪算法為基礎的，解決從單點到其余各點的最短路徑的計算方法，其主要解決的是有向圖的最短路徑問題。Dijkstra算法的核心是某個頂點出發向外拓展遍歷相鄰所有頂點，找到最短解后再進行下一輪的遍歷，直至到達所以目標頂點。該算法雖然能得出最短路徑的最優解，但是它要計算所有點之間的路徑，導致運算效率偏低。Dijkstra算法的具體思路是，采用貪婪策略，建立一個數組Dis來保存起始點到各個頂點的最短距離，然后在建立一個集合T來保存已經找到最短路徑的各個頂點。首先，原點A的路徑權重被賦為0（Dis（a）=0）。若對于頂點s存在能直接到達的邊（a，m），則把Dis（a）設為W（a，m），同時把所有其他頂點的路徑長度設為無窮大。當程序開始時集合T只有頂點a。然后，從Dis數組選擇最小值，則該值就是源點a到該頂點的最短路徑，并且把該點加入到T中。再加入第一個頂點之后，需要判斷此頂點是否能夠到達其他頂點以及是否比從起點直接到其他頂點路徑更短，如果判斷有更優解，則保存更優解，再從Dis中找出最小值，重復上述動作，直到T中包含了圖的所有頂點。

1.2 A*算法

A*算法是建立在Dijkstra算法基礎上的一種啟發式搜索算法，根據一定的啟發函數，求解最優路徑。其啟發函數為

f（n）等于g（n）加h（n）（1）

其中：

f（n）為起始點與節點以及終點的代價函數，g（n）為起點到當前點的最短路徑的實際代價值，h（n）為當前點到終點的估計代價值。

在整個函數中起關鍵性作用是h（n），其決定了A*算法運算效率的高低。如果h（n）為0，那么只是g（n）在式中發揮作用，則A*算法就變為了Dijkstra算法，因此當h（n）變小，則運算量變大導致運行速率降低。若h（n）小于節點到終點的真實代價，那么此刻A*算法依舊能夠尋找最短路徑目的。若h（n）等于節點到終點的真實代價，則A*算法可以達到更快尋找路徑且不向外擴張以此得到效率最大化。若大于或遠遠大于節點到終點的代價，g（n）基本不發揮作用，則A*算法就會變成BFS（Best-First Search）算法。

A*算法相比于Dijkstra算法，能極大地提高搜索效率與檢索速度，并且極大地減少了搜索的區域。但是傳統的A*算法由于其搜索速度緩慢，內存占用大等缺點，故在自動尋路問題中，工程師一般采用雙A*算法來解決問題。

1.3 雙A*算法

由于A*算法的搜索方式屬于單向遞進搜索，即運行每一步都在選取最優解，當所有的最優解組合在一起則會形成最終的最優路徑。雙A*算法的基本思想是在起始點和終點出發，沿著正反兩個方向同時通過A*算法搜尋路線，當各自方向上拓展出相同的最優節點時停止搜索。其具體步驟如下：

（1）創建兩個open和兩個close表，open表存儲正反方向的拓展點信息，初始和終點也包含在內。

（2）找出各自open表內f（n）最小值select，并存進各自close表格內，并以此點為父節點拓展子節點，其子節點放入open表內。

（3）判斷兩個select點是否滿足終止條件，如不滿足則繼續進行（2）步驟，如滿足則停止程序并遍歷父節點存入result表作為最終路徑。

盡管A*算法對比Dijkstra等傳統算法的時候具有運算效率高，內存占用率低，運行速度快等優點。但是A*算法在面對復雜地形的問題時，特別是起點寬闊和終點被復雜的障礙物包裹的地圖，A*算法會自動尋找到離終點最接近的點，但是在尋路過程中因為障礙物無法穿透導致路徑圍繞障礙物一圈直至到達終點。在此情況中，雙A*算法則更加具有實用性。雙A*算法在繼承了A*算法所有的優點的同時，增加了準確性和尋路效率，減少了運算時間。

2 改進算法

在實際解決問題中，網格地圖會經常出現連續折線路徑和大量直角轉彎的情況。此情況中機器人路徑選擇缺乏靈活性，且會增加路徑的長度和煩瑣程度。因此本文在基于雙A*算法的基礎上，采用直線替代法和短邊曲線替代法，以及面對折線過渡直角轉彎的特殊情況下，兩種方法互相配合以達到最大程度節省路徑的目的。

直線替代：本文采用直線替代和短邊曲線的方式來進行雙A*算法的優化。直線替代法是在路徑中出現連續折線，同時檢測是否存在障礙物。則系統自動判定優化條件，在連續折線的情況下由連續折線的首端到連續折線的末端畫一條直線，以此來作為新的路徑。

短邊曲線：短邊曲線替代法是在路徑遇到直角轉彎這種情況，且兩邊長度a和b不同。則通過以短邊為半徑畫圓，其弧線作為路徑以便平滑地度過直角。

折線過渡直角轉彎：本文著重探討由折線到直角轉彎的過渡情況，這種情況通常以一條短邊連續向不同的方向轉彎兩次。因此會有不同的情況以及優化方案。詳細的解決方案在本文的實驗分析部分進行詳細闡述。

3 實驗分析

本文使用邊長為1的正方形網格地圖來進行測試分析。在連續折線的情況下，通常采用在起點和終點連接一條直線來節省路徑。以一個正方形為例，正常情況下機器人尋路程序采取折線法，改進后采取直線替代法由正方形的左上角畫一條直線到右下角。網格地圖每一邊的邊長為1，所以折線法的總路程為2。而直線替代法能夠有效地將路徑長度降低為1.141。相比原始方法降低了42.95%，且隨著折線數量的變長，能夠節省同樣比值的路徑，大大地提高小車的工作效率和運算速度。

在直角轉彎的情況下，通常尋路程序采取筆直的沿著兩條直角邊為路徑，改進后，以短直角邊為半徑的弧線作為小車的行駛路線。同樣以網格地圖為例，兩條直角邊長度為1，2。以1為半徑畫弧線，這一條弧線的長度為0.785，改進前的總長度為3，改進后為1.785。相比改進前，路徑節省了40.5%。

在直角邊長度為2和3時，通過計算得出弧線長度約為3.14，總長度為4.14，相比變長為1和2時，效率降低但仍有一定的節省路徑。

但在短邊長度大于3的時，此法不具有實用性。通過計算得出，在兩邊長度為3和4時，總路程為7。而使用短邊曲線替代法的時候，總路程為8.065。因此當短邊長度大于3的時候，我們采取直線替代法。通過計算得出直線替代法的總路程為5.24，相比原始路徑減少了25.1%的路徑。

圖1 示意圖

在連續折線轉直角邊的特殊情況下，小車的路徑問題通常需要考慮幾種不同的條件。我們以下圖為例，折線邊的長度為a，連接段的長度為b，直角段的長度為c。

（1）b大于6。

我們直接采取連接的方式，從連續線段的起點直至線段的終點。

（2）b小于或者等于6，a小于或者等于二分之一個b，b小于或者等于二分之一個b，我們采取短的那條邊的長度為半徑畫弧線。

（3）b小于6，a等于二分之一個b，b等于二分之一個b，我們采取直接畫弧線，半徑為任意一邊的長度。

（4）b小于6，a大于或者等于二分之一個b，b大于或者等于二分之一個b，我們采取以中間線段的1/2為半徑向兩邊畫弧線。

（5）b小于或者等于6，a小于或者等于二分之一個b，b大于或者等于二分之一個b或者a大于或者等于二分之一個b，b小于或者等于二分之一個b，我們采取讓短邊這一側用短邊長度為半徑畫弧線，而長邊則使用中間線段與短邊之差的長度為半徑畫弧線。

4 結論

本文主要研究了在經典網格地圖中的路徑問題，提出了基于雙A*算法的改進方法，在最短路徑算法中，使用直線和曲線進行替代，解決傳統路徑所導致的路徑距離過長的問題。通過對地圖上空間距離的計算和對多種情況的具體分心，給出了改進方法在路徑規劃上應用的具體方案，使算法能夠得到最優解，讓小車的路徑變得更加平滑和靈活。通過針對不同的路徑情況給出的不同規劃策略，使得在復雜的路徑問題能夠快速地找出最佳路徑。

本文實驗和算法都是基于傳統的A*算法及其擴展，后續將結合智能算法進一步在效率和性能上進行提升。