基于自適應a星算法的飛行器最優路徑確定方法
【專利摘要】本發明公開一種基于自適應A星算法的飛行器最優路徑確定方法，主要解決現有技術劃分路徑長度過長、障礙物對飛行器的威脅值過大以及航路點數過多的問題。其實現步驟為：（1）在地圖中設置飛行器的起始點SP和終止點EP；（2）生成障礙物區域；（3）將障礙物區域進行網格劃分，得到網格地圖；（4）在網格地圖中，設飛行器的起始點SP所在的網格為SG、終止點EP所在的網格為EG；（5）根據飛行器的起始點所在網格SG和終止點所在網格EG，進行路徑規劃。本發明具有路徑長度短、威脅值低、航路點數少的優點，可用于飛行器最優路徑的確定。
【專利說明】基于自適應A星算法的飛行器最優路徑確定方法
【技術領域】
[0001]本發明屬于空間數據處理【技術領域】，特別涉及飛行器的路徑規劃，該方法可用于開展智能導航、無人駕駛等領域的路徑規劃。
【背景技術】
[0002]飛行器是依靠地形信息和敵情信息來進行路徑規劃，即在一定約束條件下，飛行器從起始點到終止點，搜尋能優先滿足特定目的最優的飛行路徑，其中飛行路徑用一系列航路點表示。
[0003]隨著軍事技術、實際戰爭需求的不斷發展，飛行器的路徑規劃建模從單一的系統發展到復雜多變的系統。飛行器的路徑規劃問題呈現出實時性、多維性、不確定性和非線性等復雜特征。建立在傳統系統下的模型，仍習慣于從障礙物地形信息已知且不會改變的角度出發，以靜態、理想化為主的方式來研究飛行器路徑規劃的建模問題，忽視了從實際的角度來看待整個飛行過程。目前大多數路徑規劃方法對于復雜的貼近真實環境的障礙物地形場景效果較差。這是因為傳統算法采用的是簡單的靜態的規劃方法，即在實際飛行器在飛行之前根據障礙物地形場景來進行路徑規劃，在飛行過程中路徑不可改變以及障礙物符合特定規律，這與真實場景的差距較大。顯然這種規劃方法將障礙物地形場景進行了理想化的處理，而實際上飛行場景的地形信息是無規律無規則的。
[0004]目前主要有三類技術解決路徑規劃問題:1.傳統算法，如柵格法，Voronoi圖法；
2.智能優化算法，如遺傳算法；3.其他算法，如動態規劃算法。
[0005]傳統算法是根據經典的數學方程式進行計算，較一般地理想的障礙物地圖用此類算法計算出的路徑在全局上較優，但對障礙物的要求較為理想化，針對實際地形地圖的規劃效果很大程度受到算法本身和障礙物理想化程度的影響。智能優化算法，如遺傳算法是在1975年由John Holland提出，是一類借鑒生物界的進化規律，即利用適者生存、優勝劣汰遺傳機制演化而來的隨機化搜索方法，其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。在魯棒性上較傳統算法有了明顯的提高，對障礙物理想化的依賴程度減低，但智能優化算法的計算時間普遍過長，無法適應動態的，可變的更接近真實情景的地圖進行路徑規劃。對于其他算法，如動態規劃算法，由于算法自身限制，在局部路徑上可以達到最優以及適應動態地圖，但在全局規劃上無法保證，可能會出現路徑結果不穩定和計算不出總體路徑的情況。
【發明內容】
[0006]本發明的目的在于針對已有技術的不足，提出一種基于自適應A星算法的飛行器最優路徑確定方法，以提高對多種不同地圖規劃出的路徑的正確度，同時提高對同一幅地圖進行多次路徑規劃的路線的穩定性，增強對不同地圖路徑規劃的魯棒性。[0007]本發明的技術思路是:將所需的各類數據進行預處理，獲得起止點和障礙物區域坐標，由起止點坐標差值比例，計算縱坐標方向網格尺寸大小，通過傳統A星算法得出其路徑規劃的路徑，并把搜索方向發生改變時的第一個航路點作為新的起始點，重新定義網格尺寸大小，用A星算法進行搜索，當滿足終止點條件時，路徑規劃結束，輸出所有的有效航路點。其具體步驟包括如下:
[0008](1)在地圖中設置飛行器的起始點SP和終止點EP ；
[0009](2)生成障礙物區域:
[0010]2a)根據飛行器的起始點SP和終止點EP的位置，建立直角坐標系；
[0011]2b)設Pi，qi*別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對Pi點分別做垂直于直角坐標系X軸和Y軸的直線，對Qi點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區域Ti，其中i為障礙物的個數；
[0012](3)將障礙物區域進行網格劃分，得到網格地圖；
[0013](4)在網格地圖中，設飛行器的起始點SP所在的網格為SG、終止點EP所在的網格為EG ；
[0014](5)根據飛行器的起始點所在網格SG和終止點所在網格EG，進行路徑規劃:
[0015]5a)令飛行器的起始點SP所在的網格SG為父節點Dj;設總計劃移動距離為:Ej+1=Lb+Ep其中Lb為父節點&到與其相鄰的每個網格b所需要走的路徑長度，即父節點Dj到與其相鄰的每個網格b中心連線的長度，b為相鄰網格的標號，1 < b ( 8,Ej為從起始點所在網格SG到達父節點h所移動的距離，j為父節點h的標號；設定父節點h在起始點所在網格SG時初值為:j = 0, L = 0, Ej = 0 ；
[0016]5b)分別計算第一個相鄰網格通過水平一垂直平移和垂直一水平平移這兩條路徑到達終止點所在網格EG的預估算耗費:Hn = R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經過的網格數，k為平移過程中所經過的網格標號，η為路徑標號，η為整數，1≤η≤2，m為地圖放大系數，1≤m≤20 ;
[0017]5c)對與父節點相鄰的每一個網格重復步驟(5b)，得到各自的預估算耗費的最小值HMb ;
[0018]5d)計算與父節點0」相鄰的每個網格b到終止點所在的網格EG的總估計值F(b):
[0019]F (b) = G (b) +HMb ；
[0020]其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費:G(b)=
Ej+i ;
[0021]5e)將總估計值F(b)中的最小值所對應的網格x作為新的父節點Dj+1，總計劃移動距離為:Ej+1 = LX+Ej，其中Lx為父節點0」到與其相鄰的網格X中心連線的長度，則當前的計劃移動路徑為父節點&與新的父節點1+1所在的網格中心的連線；
[0022]5f)判斷新的父節點^與父節點&的搜索方向是否相同，如果搜索方向相同，則返回步驟(5b)繼續進行搜索；否則，執行步驟(5g)；
[0023]5g)將步驟(5f )中的新的父節點^作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規劃，此時，網格地圖中飛行器的起始點SP所在的網格SG到達終止點EP所在的網格EG的路徑，即為網格地圖中所有父節點Dt與Dt+1所在的網格中心連線組成的線段，其中0 < t < j，否則，返回步驟(3)。[0024]本發明與現有的技術相比具有以下優點:
[0025]第一，本發明所采用自適應A星算法，相比傳統的A星算法，對飛行器進行路徑規劃所得出的路徑在長度上有所縮短，航路點數減少，提高了規劃出的路徑的正確度。
[0026]第二，本發明與傳統算法相比，飛行器在飛行過程中能夠根據周圍環境的變化，對當前地圖進行實時更新，縮短了路徑長度，并在此過程中降低了障礙物對飛行器的威脅值；
[0027]第三，本發明相比其他算法，由于不對障礙物地形地圖進行任何理想化處理，克服了對于不同障礙物地形地圖所規劃出的路徑的魯棒性不足的缺點。
【專利附圖】
【附圖說明】
[0028]圖1為本發明的實現流程圖；
[0029]圖2為本發明利用自適應A星算法進行路徑規劃的子流程圖；
[0030]圖3為本發明實驗的障礙物地形地圖；
[0031 ] 圖4為本發明方法規劃出的路徑結果圖；
[0032]圖5為傳統A星算法規劃出的路徑結果圖。
【具體實施方式】
[0033]下面結合附圖對本發明的步驟作進一步的詳細描述。
[0034]參照圖1，本發明的實現步驟如下:
[0035]步驟1.設置飛行器的起始點和終止點位置，即在地圖中對飛行器的起始點SP和終止點EP進行標記。
[0036]步驟2.生成障礙物區域。
[0037]2a)根據飛行器的起始點SP和終止點EP的位置，建立直角坐標系；
[0038]2b)設Pi，qi*別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對Pi點分別做垂直于直角坐標系X軸和Y軸的直線，對Qi點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區域Ti，其中i為障礙物的個數；
[0039]步驟3.將障礙物區域進行網格劃分，得到網格地圖。
[0040]3a)設定每個網格X方向邊長為2，依據起始點SP和終止點EP的坐標差值比例，計算網格Y方向的邊長I:
[0041]Yi=2*yep~ysp ;
Xep -ΧΨ
[0042]其中(xsp, ysp)為起始點SP的坐標，(xep, yep)為終止點EP的坐標；
[0043]3b)依據每個網格的大小，將障礙物區域劃分成含有100X 100個網格；
[0044]3c)在障礙物區域的所有網格中，將障礙物所覆蓋到的網格值均設為1，其他網格值設為0，得到網格地圖。
[0045]步驟4.在網格地圖中，設飛行器的起始點SP所在的網格為SG、終止點EP所在的網格為EG。
[0046]步驟5.根據飛行器的起始點所在網格SG和終止點所在網格EG，進行路徑規劃。[0047]參照圖2，本步驟的具體步驟是:
[0048]5a)令飛行器的起始點SP所在的網格SG為父節點Dj;設總計劃移動距離為:Ej+1=Lb+Ep其中Lb為父節點&到與其相鄰的每個網格b所需要走的路徑長度，即父節點Dj到與其相鄰的每個網格b中心連線的長度，b為相鄰網格的標號，1 < b ( 8,Ej為從起始點所在網格SG到達父節點h所移動的距離，j為父節點h的標號；設定父節點h在起始點所在網格SG時初值為:j = 0, L = 0, Ej = 0 ；
[0049]5b)分別計算第一個相鄰網格通過水平一垂直平移和垂直一水平平移這兩條路徑到達終止點所在網格EG的預估算耗費:Hn = R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經過的網格數，k為平移過程中所經過的網格標號，η為路徑標號，η為整數，1≤η≤2，m為地圖放大系數，1≤m≤20 ;
[0050]5c)對與父節點h相鄰的每一個網格重復步驟(5b)，得到各自的預估算耗費的最小值HMb ;
[0051]5d)計算與父節點0」相鄰的每個網格b到終止點所在的網格EG的總估計值F(b):
[0052]F (b) = G (b) +HMb ；
[0053]其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費:G(b)=
Ej+i ;
[0054]5e)將總估計值F(b)中的最小值所對應的網格x作為新的父節點Dj+1，總計劃移動距離為:Ej+1 = LX+Ej，其中Lx為父節點0」到與其相鄰的網格X中心連線的長度，則當前的計劃移動路徑為父節點&與新的父節點1+1所在的網格中心的連線；
[0055]5f)判斷新的父節點^與父節點&的搜索方向是否相同，如果搜索方向相同，則返回步驟(5b)繼續進行搜索；否則，執行步驟(5g)；
[0056]5g)將步驟(5f )中的新的父節點^作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規劃，此時，網格地圖中飛行器的起始點SP所在的網格SG到達終止點EP所在的網格EG的路徑，即為網格地圖中所有父節點Dt與Dt+1所在的網格中心連線組成的線段，其中0 < t < j，否則，返回步驟(3)。
[0057]本發明的效果通過以下仿真進一步說明。
[0058]一、仿真條件
[0059]硬件平臺為:IntelCore2Duo CPU E6550i2.33GHZ.2GB RAM
[0060]軟件平臺為:VC++6.0
[0061]實驗所使用的障礙物地形圖如圖3所示，其中圖3 (a)中的方形區域為障礙物區域，左上角的圓環為飛行器的起始點SP，右下角的圓環為飛行器的終止點EP，其他區域為無障礙物區域。圖3 (b)中的兩個方形區域均為障礙物區域，左上角的圓環為飛行器的起始點SP，右下角的圓環為飛行器的終止點EP，其他區域為無障礙物區域。圖3 (c)中的兩個圓形區域均為障礙物區域，左上角的圓環為飛行器的起始點SP，右下角的圓環為飛行器的終止點EP，其他區域為無障礙物區域。圖3 (d)中的圓形和方形區域均為障礙物區域，左上角的圓環為飛行器的起始點SP，右下角的圓環為飛行器的終止點EP，其他區域為無障礙物區域。
[0062]二、仿真內容
[0063]仿真一，用本發明方法分別對圖3 (a)~3 (d)進行路徑規劃，得到路徑規劃結果如圖4，其中圖4 (a)中從起始點SP至終止點EP的實線是對圖3 (a)進行規劃得到的路徑，圖4 (b)中從起始點SP至終止點EP的實線是對圖3 (b)進行規劃得到的路徑，圖4(c)中從起始點SP至終止點EP的實線是對圖3 (c)進行規劃得到的路徑，圖4 (d)中從起始點SP至終止點EP的實線是對圖3 (d)進行規劃得到的路徑。
[0064]仿真二，用傳統A星算法分別對圖3 (a)~3 (d)進行路徑規劃，得到的路徑規劃結果如圖5，其中圖5 (a)中從起始點SP至終止點EP的實線是對圖3 (a)進行規劃得到的路徑，圖5 (b)中從起始點SP至終止點EP的實線是對圖3 (b)進行規劃得到的路徑，圖5(c)中從起始點SP至終止點EP的實線是對圖3 (c)進行規劃得到的路徑，圖5 (d)中從起始點SP至終止點EP的實線是對圖3 (d)進行規劃得到的路徑。
[0065]三、結果分析
[0066]分別將圖4和圖5中規劃出的路徑長度、障礙物對飛行器的威脅值以及航路點數進行整理，得到的結果如表1，其中威脅值是障礙物區域對飛行器的威脅程度，根據雷達方程D = Ι/d4計算得出，其中d為飛行器距離障礙物的最短直線距離。
[0067]表1
【權利要求】
1.一種基于自適應A星算法的飛行器最優路徑確定方法，包括如下步驟:(1)在地圖中設置飛行器的起始點SP和終止點EP；(2)生成障礙物區域:2a)根據飛行器的起始點SP和終止點EP的位置，建立直角坐標系；2b)設Pi，％分別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對Pi點分別做垂直于直角坐標系X軸和Y軸的直線，對Qi點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區域Ti，其中i為障礙物的個數；(3)將障礙物區域進行網格劃分，得到網格地圖；(4)在網格地圖中，設飛行器的起始點SP所在的網格為SG、終止點EP所在的網格為EG ；(5)根據飛行器的起始點所在網格SG和終止點所在網格EG，進行路徑規劃:5a)令飛行器的起始點SP所在的網格SG為父節點Dj;設總計劃移動距離為:Ej+1 =Lb+Ep其中Lb為父節點&到與其相鄰的每個網格b所需要走的路徑長度，即父節點&到與其相鄰的每個網格b中心連線的長度，b為相鄰網格的標號，1 ≤ b≤ 8,Ej為從起始點所在網格SG到達父節點h所移動的距離，j為父節點h的標號；設定父節點h在起始點所在網格SG時初值為:j = 0，L = 0，E」=0 ;5b)分別計算第一個相鄰網格通過水平一垂直平移和垂直一水平平移這兩條路徑到達終止點所在網格EG的預估算耗費:Hn = R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經過的網格數，k為平移過程中所經過的網格標號，η為路徑標號，n為整數，1≤n≤2，m為地圖放大系數，1≤m≤20 ;5c)對與父節點相鄰的每一個網格重復步驟(5b)，得到各自的預估算耗費的最小值HMb ;5d)計算與父節點Dj相鄰的每個網格b到終止點所在的網格EG的總估計值F(b):F(b) = G (b) +HMb ；其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費:G(b) = EJ+1 ；5e)將總估計值F(b)中的最小值所對應的網格X作為新的父節點1+1，總計劃移動距離為:Ej+1 = Lx+Ej，其中。為父節點Dj到與其相鄰的網格X中心連線的長度，則當前的計劃移動路徑為父節點&與新的父節點1+1所在的網格中心的連線；5f)判斷新的父節點^與父節點&的搜索方向是否相同，如果搜索方向相同，則返回步驟(5b)繼續進行搜索；否則，執行步驟(5g)；5g)將步驟(5f)中的新的父節點h+1作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規劃，此時，網格地圖中飛行器的起始點SP所在的網格SG到達終止點EP所在的網格EG的路徑，即為網格地圖中所有父節點Dt與Dt+1所在的網格中心連線組成的線段，其中0 ≤t ≤j，否則，返回步驟(3)。
2.根據權利要求1所述的基于自適應A星算法的飛行器最優路徑確定方法，其中步驟(3)所述的將障礙物區域進行網格劃分，得到網格地圖，按如下步驟進行:3a)設定網格X方向邊長為2，依據起始點SP和終止點EP的坐標差值比例，計算網格Y方向的邊長Y::
【文檔編號】G01C21/20GK103697895SQ201410010003
【公開日】2014年4月2日 申請日期:2014年1月9日 優先權日:2014年1月9日
【發明者】于昕, 焦李成, 朱振強, 馬晶晶, 馬文萍, 劉軍強, 李陽陽 申請人:西安電子科技大學
專業數控銑床產品供應商
20年生產經驗，實力工廠，精工品質，質量有保障
