一種基于網(wǎng)格地圖的雙A*算法的改進(jìn)方法

袁川涵

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

【關(guān)鍵詞】路徑規(guī)劃;空間距離;雙A*算法

中圖分類號(hào)： TP18;TP242文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 2095-2457（2019）29-0148-002

DOI：10.19694/j.cnki.issn2095-2457.2019.29.069

0 概述

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

1 背景知識(shí)/算法介紹

1.1 Dijkstra算法

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

1.2 A*算法

A*算法是建立在Dijkstra算法基礎(chǔ)上的一種啟發(fā)式搜索算法，根據(jù)一定的啟發(fā)函數(shù)，求解最優(yōu)路徑。其啟發(fā)函數(shù)為

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

其中：

f（n）為起始點(diǎn)與節(jié)點(diǎn)以及終點(diǎn)的代價(jià)函數(shù)，g（n）為起點(diǎn)到當(dāng)前點(diǎn)的最短路徑的實(shí)際代價(jià)值，h（n）為當(dāng)前點(diǎn)到終點(diǎn)的估計(jì)代價(jià)值。

在整個(gè)函數(shù)中起關(guān)鍵性作用是h（n），其決定了A*算法運(yùn)算效率的高低。如果h（n）為0，那么只是g（n）在式中發(fā)揮作用，則A*算法就變?yōu)榱薉ijkstra算法，因此當(dāng)h（n）變小，則運(yùn)算量變大導(dǎo)致運(yùn)行速率降低。若h（n）小于節(jié)點(diǎn)到終點(diǎn)的真實(shí)代價(jià)，那么此刻A*算法依舊能夠?qū)ふ易疃搪窂侥康?。若h（n）等于節(jié)點(diǎn)到終點(diǎn)的真實(shí)代價(jià)，則A*算法可以達(dá)到更快尋找路徑且不向外擴(kuò)張以此得到效率最大化。若大于或遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)到終點(diǎn)的代價(jià)，g（n）基本不發(fā)揮作用，則A*算法就會(huì)變成BFS（Best-First Search）算法。

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

1.3 雙A*算法

由于A*算法的搜索方式屬于單向遞進(jìn)搜索，即運(yùn)行每一步都在選取最優(yōu)解，當(dāng)所有的最優(yōu)解組合在一起則會(huì)形成最終的最優(yōu)路徑。雙A*算法的基本思想是在起始點(diǎn)和終點(diǎn)出發(fā)，沿著正反兩個(gè)方向同時(shí)通過A*算法搜尋路線，當(dāng)各自方向上拓展出相同的最優(yōu)節(jié)點(diǎn)時(shí)停止搜索。其具體步驟如下：

（1）創(chuàng)建兩個(gè)open和兩個(gè)close表，open表存儲(chǔ)正反方向的拓展點(diǎn)信息，初始和終點(diǎn)也包含在內(nèi)。

（2）找出各自open表內(nèi)f（n）最小值select，并存進(jìn)各自close表格內(nèi)，并以此點(diǎn)為父節(jié)點(diǎn)拓展子節(jié)點(diǎn)，其子節(jié)點(diǎn)放入open表內(nèi)。

（3）判斷兩個(gè)select點(diǎn)是否滿足終止條件，如不滿足則繼續(xù)進(jìn)行（2）步驟，如滿足則停止程序并遍歷父節(jié)點(diǎn)存入result表作為最終路徑。

盡管A*算法對(duì)比Dijkstra等傳統(tǒng)算法的時(shí)候具有運(yùn)算效率高，內(nèi)存占用率低，運(yùn)行速度快等優(yōu)點(diǎn)。但是A*算法在面對(duì)復(fù)雜地形的問題時(shí)，特別是起點(diǎn)寬闊和終點(diǎn)被復(fù)雜的障礙物包裹的地圖，A*算法會(huì)自動(dòng)尋找到離終點(diǎn)最接近的點(diǎn)，但是在尋路過程中因?yàn)檎系K物無法穿透導(dǎo)致路徑圍繞障礙物一圈直至到達(dá)終點(diǎn)。在此情況中，雙A*算法則更加具有實(shí)用性。雙A*算法在繼承了A*算法所有的優(yōu)點(diǎn)的同時(shí)，增加了準(zhǔn)確性和尋路效率，減少了運(yùn)算時(shí)間。

2 改進(jìn)算法

在實(shí)際解決問題中，網(wǎng)格地圖會(huì)經(jīng)常出現(xiàn)連續(xù)折線路徑和大量直角轉(zhuǎn)彎的情況。此情況中機(jī)器人路徑選擇缺乏靈活性，且會(huì)增加路徑的長(zhǎng)度和煩瑣程度。因此本文在基于雙A*算法的基礎(chǔ)上，采用直線替代法和短邊曲線替代法，以及面對(duì)折線過渡直角轉(zhuǎn)彎的特殊情況下，兩種方法互相配合以達(dá)到最大程度節(jié)省路徑的目的。

直線替代：本文采用直線替代和短邊曲線的方式來進(jìn)行雙A*算法的優(yōu)化。直線替代法是在路徑中出現(xiàn)連續(xù)折線，同時(shí)檢測(cè)是否存在障礙物。則系統(tǒng)自動(dòng)判定優(yōu)化條件，在連續(xù)折線的情況下由連續(xù)折線的首端到連續(xù)折線的末端畫一條直線，以此來作為新的路徑。

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

折線過渡直角轉(zhuǎn)彎：本文著重探討由折線到直角轉(zhuǎn)彎的過渡情況，這種情況通常以一條短邊連續(xù)向不同的方向轉(zhuǎn)彎兩次。因此會(huì)有不同的情況以及優(yōu)化方案。詳細(xì)的解決方案在本文的實(shí)驗(yàn)分析部分進(jìn)行詳細(xì)闡述。

3 實(shí)驗(yàn)分析

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

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

在直角邊長(zhǎng)度為2和3時(shí)，通過計(jì)算得出弧線長(zhǎng)度約為3.14，總長(zhǎng)度為4.14，相比變長(zhǎng)為1和2時(shí)，效率降低但仍有一定的節(jié)省路徑。

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

圖1 示意圖

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

（1）b大于6。

我們直接采取連接的方式，從連續(xù)線段的起點(diǎn)直至線段的終點(diǎn)。

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

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

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

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

4 結(jié)論

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

本文實(shí)驗(yàn)和算法都是基于傳統(tǒng)的A*算法及其擴(kuò)展，后續(xù)將結(jié)合智能算法進(jìn)一步在效率和性能上進(jìn)行提升。