久久一区二区免费播放,国产在线欧美日韩一区二区,国产综合色在线视频,精品伊人久久久香线蕉,精品视频麻豆网站,玖玖国产,国内精品久久久久影,在线观看精品视频一区二区三区,午夜久久影院,国产精品一区久久

基于自適應a星算法的飛行器最優(yōu)路徑確定方法
【專利摘要】本發(fā)明公開一種基于自適應A星算法的飛行器最優(yōu)路徑確定方法，主要解決現(xiàn)有技術劃分路徑長度過長、障礙物對飛行器的威脅值過大以及航路點數(shù)過多的問題。其實現(xiàn)步驟為：（1）在地圖中設置飛行器的起始點SP和終止點EP；（2）生成障礙物區(qū)域；（3）將障礙物區(qū)域進行網(wǎng)格劃分，得到網(wǎng)格地圖；（4）在網(wǎng)格地圖中，設飛行器的起始點SP所在的網(wǎng)格為SG、終止點EP所在的網(wǎng)格為EG；（5）根據(jù)飛行器的起始點所在網(wǎng)格SG和終止點所在網(wǎng)格EG，進行路徑規(guī)劃。本發(fā)明具有路徑長度短、威脅值低、航路點數(shù)少的優(yōu)點，可用于飛行器最優(yōu)路徑的確定。
【專利說明】基于自適應A星算法的飛行器最優(yōu)路徑確定方法
【技術領域】
[0001]本發(fā)明屬于空間數(shù)據(jù)處理【技術領域】，特別涉及飛行器的路徑規(guī)劃，該方法可用于開展智能導航、無人駕駛等領域的路徑規(guī)劃。
【背景技術】
[0002]飛行器是依靠地形信息和敵情信息來進行路徑規(guī)劃，即在一定約束條件下，飛行器從起始點到終止點，搜尋能優(yōu)先滿足特定目的最優(yōu)的飛行路徑，其中飛行路徑用一系列航路點表示。
[0003]隨著軍事技術、實際戰(zhàn)爭需求的不斷發(fā)展，飛行器的路徑規(guī)劃建模從單一的系統(tǒng)發(fā)展到復雜多變的系統(tǒng)。飛行器的路徑規(guī)劃問題呈現(xiàn)出實時性、多維性、不確定性和非線性等復雜特征。建立在傳統(tǒng)系統(tǒng)下的模型，仍習慣于從障礙物地形信息已知且不會改變的角度出發(fā)，以靜態(tài)、理想化為主的方式來研究飛行器路徑規(guī)劃的建模問題，忽視了從實際的角度來看待整個飛行過程。目前大多數(shù)路徑規(guī)劃方法對于復雜的貼近真實環(huán)境的障礙物地形場景效果較差。這是因為傳統(tǒng)算法采用的是簡單的靜態(tài)的規(guī)劃方法，即在實際飛行器在飛行之前根據(jù)障礙物地形場景來進行路徑規(guī)劃，在飛行過程中路徑不可改變以及障礙物符合特定規(guī)律，這與真實場景的差距較大。顯然這種規(guī)劃方法將障礙物地形場景進行了理想化的處理，而實際上飛行場景的地形信息是無規(guī)律無規(guī)則的。
[0004]目前主要有三類技術解決路徑規(guī)劃問題:1.傳統(tǒng)算法，如柵格法，Voronoi圖法；
2.智能優(yōu)化算法，如遺傳算法；3.其他算法，如動態(tài)規(guī)劃算法。
[0005]傳統(tǒng)算法是根據(jù)經(jīng)典的數(shù)學方程式進行計算，較一般地理想的障礙物地圖用此類算法計算出的路徑在全局上較優(yōu)，但對障礙物的要求較為理想化，針對實際地形地圖的規(guī)劃效果很大程度受到算法本身和障礙物理想化程度的影響。智能優(yōu)化算法，如遺傳算法是在1975年由John Holland提出，是一類借鑒生物界的進化規(guī)律，即利用適者生存、優(yōu)勝劣汰遺傳機制演化而來的隨機化搜索方法，其主要特點是直接對結構對象進行操作，不存在求導和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則。在魯棒性上較傳統(tǒng)算法有了明顯的提高，對障礙物理想化的依賴程度減低，但智能優(yōu)化算法的計算時間普遍過長，無法適應動態(tài)的，可變的更接近真實情景的地圖進行路徑規(guī)劃。對于其他算法，如動態(tài)規(guī)劃算法，由于算法自身限制，在局部路徑上可以達到最優(yōu)以及適應動態(tài)地圖，但在全局規(guī)劃上無法保證，可能會出現(xiàn)路徑結果不穩(wěn)定和計算不出總體路徑的情況。

【發(fā)明內(nèi)容】

[0006]本發(fā)明的目的在于針對已有技術的不足，提出一種基于自適應A星算法的飛行器最優(yōu)路徑確定方法，以提高對多種不同地圖規(guī)劃出的路徑的正確度，同時提高對同一幅地圖進行多次路徑規(guī)劃的路線的穩(wěn)定性，增強對不同地圖路徑規(guī)劃的魯棒性。[0007]本發(fā)明的技術思路是:將所需的各類數(shù)據(jù)進行預處理，獲得起止點和障礙物區(qū)域坐標，由起止點坐標差值比例，計算縱坐標方向網(wǎng)格尺寸大小，通過傳統(tǒng)A星算法得出其路徑規(guī)劃的路徑，并把搜索方向發(fā)生改變時的第一個航路點作為新的起始點，重新定義網(wǎng)格尺寸大小，用A星算法進行搜索，當滿足終止點條件時，路徑規(guī)劃結束，輸出所有的有效航路點。其具體步驟包括如下:
[0008](1)在地圖中設置飛行器的起始點SP和終止點EP ；
[0009](2)生成障礙物區(qū)域:
[0010]2a)根據(jù)飛行器的起始點SP和終止點EP的位置，建立直角坐標系；
[0011]2b)設Pi，qi*別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對Pi點分別做垂直于直角坐標系X軸和Y軸的直線，對Qi點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區(qū)域Ti，其中i為障礙物的個數(shù)；
[0012](3)將障礙物區(qū)域進行網(wǎng)格劃分，得到網(wǎng)格地圖；
[0013](4)在網(wǎng)格地圖中，設飛行器的起始點SP所在的網(wǎng)格為SG、終止點EP所在的網(wǎng)格為EG ；
[0014](5)根據(jù)飛行器的起始點所在網(wǎng)格SG和終止點所在網(wǎng)格EG，進行路徑規(guī)劃:
[0015]5a)令飛行器的起始點SP所在的網(wǎng)格SG為父節(jié)點Dj;設總計劃移動距離為:Ej+1=Lb+Ep其中Lb為父節(jié)點&到與其相鄰的每個網(wǎng)格b所需要走的路徑長度，即父節(jié)點Dj到與其相鄰的每個網(wǎng)格b中心連線的長度，b為相鄰網(wǎng)格的標號，1 < b ( 8,Ej為從起始點所在網(wǎng)格SG到達父節(jié)點h所移動的距離，j為父節(jié)點h的標號；設定父節(jié)點h在起始點所在網(wǎng)格SG時初值為:j = 0, L = 0, Ej = 0 ；
[0016]5b)分別計算第一個相鄰網(wǎng)格通過水平一垂直平移和垂直一水平平移這兩條路徑到達終止點所在網(wǎng)格EG的預估算耗費:Hn = R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經(jīng)過的網(wǎng)格數(shù)，k為平移過程中所經(jīng)過的網(wǎng)格標號，η為路徑標號，η為整數(shù)，1≤η≤2，m為地圖放大系數(shù)，1≤m≤20 ;
[0017]5c)對與父節(jié)點相鄰的每一個網(wǎng)格重復步驟(5b)，得到各自的預估算耗費的最小值HMb ;
[0018]5d)計算與父節(jié)點0」相鄰的每個網(wǎng)格b到終止點所在的網(wǎng)格EG的總估計值F(b):
[0019]F (b) = G (b) +HMb ；
[0020]其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費:G(b)=
Ej+i ;
[0021]5e)將總估計值F(b)中的最小值所對應的網(wǎng)格x作為新的父節(jié)點Dj+1，總計劃移動距離為:Ej+1 = LX+Ej，其中Lx為父節(jié)點0」到與其相鄰的網(wǎng)格X中心連線的長度，則當前的計劃移動路徑為父節(jié)點&與新的父節(jié)點1+1所在的網(wǎng)格中心的連線；
[0022]5f)判斷新的父節(jié)點^與父節(jié)點&的搜索方向是否相同，如果搜索方向相同，則返回步驟(5b)繼續(xù)進行搜索；否則，執(zhí)行步驟(5g)；
[0023]5g)將步驟(5f )中的新的父節(jié)點^作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規(guī)劃，此時，網(wǎng)格地圖中飛行器的起始點SP所在的網(wǎng)格SG到達終止點EP所在的網(wǎng)格EG的路徑，即為網(wǎng)格地圖中所有父節(jié)點Dt與Dt+1所在的網(wǎng)格中心連線組成的線段，其中0 < t < j，否則，返回步驟(3)。[0024]本發(fā)明與現(xiàn)有的技術相比具有以下優(yōu)點:
[0025]第一，本發(fā)明所采用自適應A星算法，相比傳統(tǒng)的A星算法，對飛行器進行路徑規(guī)劃所得出的路徑在長度上有所縮短，航路點數(shù)減少，提高了規(guī)劃出的路徑的正確度。
[0026]第二，本發(fā)明與傳統(tǒng)算法相比，飛行器在飛行過程中能夠根據(jù)周圍環(huán)境的變化，對當前地圖進行實時更新，縮短了路徑長度，并在此過程中降低了障礙物對飛行器的威脅值；
[0027]第三，本發(fā)明相比其他算法，由于不對障礙物地形地圖進行任何理想化處理，克服了對于不同障礙物地形地圖所規(guī)劃出的路徑的魯棒性不足的缺點。
【專利附圖】

【附圖說明】
[0028]圖1為本發(fā)明的實現(xiàn)流程圖；
[0029]圖2為本發(fā)明利用自適應A星算法進行路徑規(guī)劃的子流程圖；
[0030]圖3為本發(fā)明實驗的障礙物地形地圖；
[0031 ] 圖4為本發(fā)明方法規(guī)劃出的路徑結果圖；
[0032]圖5為傳統(tǒng)A星算法規(guī)劃出的路徑結果圖。
【具體實施方式】
[0033]下面結合附圖對本發(fā)明的步驟作進一步的詳細描述。
[0034]參照圖1，本發(fā)明的實現(xiàn)步驟如下:
[0035]步驟1.設置飛行器的起始點和終止點位置，即在地圖中對飛行器的起始點SP和終止點EP進行標記。
[0036]步驟2.生成障礙物區(qū)域。
[0037]2a)根據(jù)飛行器的起始點SP和終止點EP的位置，建立直角坐標系；
[0038]2b)設Pi，qi*別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對Pi點分別做垂直于直角坐標系X軸和Y軸的直線，對Qi點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區(qū)域Ti，其中i為障礙物的個數(shù)；
[0039]步驟3.將障礙物區(qū)域進行網(wǎng)格劃分，得到網(wǎng)格地圖。
[0040]3a)設定每個網(wǎng)格X方向邊長為2，依據(jù)起始點SP和終止點EP的坐標差值比例，計算網(wǎng)格Y方向的邊長I:
[0041]Yi=2*yep~ysp ;
Xep -ΧΨ
[0042]其中(xsp, ysp)為起始點SP的坐標，(xep, yep)為終止點EP的坐標；
[0043]3b)依據(jù)每個網(wǎng)格的大小，將障礙物區(qū)域劃分成含有100X 100個網(wǎng)格；
[0044]3c)在障礙物區(qū)域的所有網(wǎng)格中，將障礙物所覆蓋到的網(wǎng)格值均設為1，其他網(wǎng)格值設為0，得到網(wǎng)格地圖。
[0045]步驟4.在網(wǎng)格地圖中，設飛行器的起始點SP所在的網(wǎng)格為SG、終止點EP所在的網(wǎng)格為EG。
[0046]步驟5.根據(jù)飛行器的起始點所在網(wǎng)格SG和終止點所在網(wǎng)格EG，進行路徑規(guī)劃。[0047]參照圖2，本步驟的具體步驟是:
[0048]5a)令飛行器的起始點SP所在的網(wǎng)格SG為父節(jié)點Dj;設總計劃移動距離為:Ej+1=Lb+Ep其中Lb為父節(jié)點&到與其相鄰的每個網(wǎng)格b所需要走的路徑長度，即父節(jié)點Dj到與其相鄰的每個網(wǎng)格b中心連線的長度，b為相鄰網(wǎng)格的標號，1 < b ( 8,Ej為從起始點所在網(wǎng)格SG到達父節(jié)點h所移動的距離，j為父節(jié)點h的標號；設定父節(jié)點h在起始點所在網(wǎng)格SG時初值為:j = 0, L = 0, Ej = 0 ；
[0049]5b)分別計算第一個相鄰網(wǎng)格通過水平一垂直平移和垂直一水平平移這兩條路徑到達終止點所在網(wǎng)格EG的預估算耗費:Hn = R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經(jīng)過的網(wǎng)格數(shù)，k為平移過程中所經(jīng)過的網(wǎng)格標號，η為路徑標號，η為整數(shù)，1≤η≤2，m為地圖放大系數(shù)，1≤m≤20 ;
[0050]5c)對與父節(jié)點h相鄰的每一個網(wǎng)格重復步驟(5b)，得到各自的預估算耗費的最小值HMb ;
[0051]5d)計算與父節(jié)點0」相鄰的每個網(wǎng)格b到終止點所在的網(wǎng)格EG的總估計值F(b):
[0052]F (b) = G (b) +HMb ；
[0053]其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費:G(b)=
Ej+i ;
[0054]5e)將總估計值F(b)中的最小值所對應的網(wǎng)格x作為新的父節(jié)點Dj+1，總計劃移動距離為:Ej+1 = LX+Ej，其中Lx為父節(jié)點0」到與其相鄰的網(wǎng)格X中心連線的長度，則當前的計劃移動路徑為父節(jié)點&與新的父節(jié)點1+1所在的網(wǎng)格中心的連線；
[0055]5f)判斷新的父節(jié)點^與父節(jié)點&的搜索方向是否相同，如果搜索方向相同，則返回步驟(5b)繼續(xù)進行搜索；否則，執(zhí)行步驟(5g)；
[0056]5g)將步驟(5f )中的新的父節(jié)點^作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規(guī)劃，此時，網(wǎng)格地圖中飛行器的起始點SP所在的網(wǎng)格SG到達終止點EP所在的網(wǎng)格EG的路徑，即為網(wǎng)格地圖中所有父節(jié)點Dt與Dt+1所在的網(wǎng)格中心連線組成的線段，其中0 < t < j，否則，返回步驟(3)。
[0057]本發(fā)明的效果通過以下仿真進一步說明。
[0058]一、仿真條件
[0059]硬件平臺為:IntelCore2Duo CPU E6550i2.33GHZ.2GB RAM
[0060]軟件平臺為:VC++6.0
[0061]實驗所使用的障礙物地形圖如圖3所示，其中圖3 (a)中的方形區(qū)域為障礙物區(qū)域，左上角的圓環(huán)為飛行器的起始點SP，右下角的圓環(huán)為飛行器的終止點EP，其他區(qū)域為無障礙物區(qū)域。圖3 (b)中的兩個方形區(qū)域均為障礙物區(qū)域，左上角的圓環(huán)為飛行器的起始點SP，右下角的圓環(huán)為飛行器的終止點EP，其他區(qū)域為無障礙物區(qū)域。圖3 (c)中的兩個圓形區(qū)域均為障礙物區(qū)域，左上角的圓環(huán)為飛行器的起始點SP，右下角的圓環(huán)為飛行器的終止點EP，其他區(qū)域為無障礙物區(qū)域。圖3 (d)中的圓形和方形區(qū)域均為障礙物區(qū)域，左上角的圓環(huán)為飛行器的起始點SP，右下角的圓環(huán)為飛行器的終止點EP，其他區(qū)域為無障礙物區(qū)域。
[0062]二、仿真內(nèi)容
[0063]仿真一，用本發(fā)明方法分別對圖3 (a)~3 (d)進行路徑規(guī)劃，得到路徑規(guī)劃結果如圖4，其中圖4 (a)中從起始點SP至終止點EP的實線是對圖3 (a)進行規(guī)劃得到的路徑，圖4 (b)中從起始點SP至終止點EP的實線是對圖3 (b)進行規(guī)劃得到的路徑，圖4(c)中從起始點SP至終止點EP的實線是對圖3 (c)進行規(guī)劃得到的路徑，圖4 (d)中從起始點SP至終止點EP的實線是對圖3 (d)進行規(guī)劃得到的路徑。
[0064]仿真二，用傳統(tǒng)A星算法分別對圖3 (a)~3 (d)進行路徑規(guī)劃，得到的路徑規(guī)劃結果如圖5，其中圖5 (a)中從起始點SP至終止點EP的實線是對圖3 (a)進行規(guī)劃得到的路徑，圖5 (b)中從起始點SP至終止點EP的實線是對圖3 (b)進行規(guī)劃得到的路徑，圖5(c)中從起始點SP至終止點EP的實線是對圖3 (c)進行規(guī)劃得到的路徑，圖5 (d)中從起始點SP至終止點EP的實線是對圖3 (d)進行規(guī)劃得到的路徑。
[0065]三、結果分析
[0066]分別將圖4和圖5中規(guī)劃出的路徑長度、障礙物對飛行器的威脅值以及航路點數(shù)進行整理，得到的結果如表1，其中威脅值是障礙物區(qū)域?qū)︼w行器的威脅程度，根據(jù)雷達方程D = Ι/d4計算得出，其中d為飛行器距離障礙物的最短直線距離。
[0067]表1
【權利要求】
1.一種基于自適應A星算法的飛行器最優(yōu)路徑確定方法，包括如下步驟:(1)在地圖中設置飛行器的起始點SP和終止點EP；(2)生成障礙物區(qū)域:2a)根據(jù)飛行器的起始點SP和終止點EP的位置，建立直角坐標系；2b)設Pi，％分別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對Pi點分別做垂直于直角坐標系X軸和Y軸的直線，對Qi點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區(qū)域Ti，其中i為障礙物的個數(shù)；(3)將障礙物區(qū)域進行網(wǎng)格劃分，得到網(wǎng)格地圖；(4)在網(wǎng)格地圖中，設飛行器的起始點SP所在的網(wǎng)格為SG、終止點EP所在的網(wǎng)格為EG ；(5)根據(jù)飛行器的起始點所在網(wǎng)格SG和終止點所在網(wǎng)格EG，進行路徑規(guī)劃:5a)令飛行器的起始點SP所在的網(wǎng)格SG為父節(jié)點Dj;設總計劃移動距離為:Ej+1 =Lb+Ep其中Lb為父節(jié)點&到與其相鄰的每個網(wǎng)格b所需要走的路徑長度，即父節(jié)點&到與其相鄰的每個網(wǎng)格b中心連線的長度，b為相鄰網(wǎng)格的標號，1 ≤ b≤ 8,Ej為從起始點所在網(wǎng)格SG到達父節(jié)點h所移動的距離，j為父節(jié)點h的標號；設定父節(jié)點h在起始點所在網(wǎng)格SG時初值為:j = 0，L = 0，E」=0 ;5b)分別計算第一個相鄰網(wǎng)格通過水平一垂直平移和垂直一水平平移這兩條路徑到達終止點所在網(wǎng)格EG的預估算耗費:Hn = R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經(jīng)過的網(wǎng)格數(shù)，k為平移過程中所經(jīng)過的網(wǎng)格標號，η為路徑標號，n為整數(shù)，1≤n≤2，m為地圖放大系數(shù)，1≤m≤20 ;5c)對與父節(jié)點相鄰的每一個網(wǎng)格重復步驟(5b)，得到各自的預估算耗費的最小值HMb ;5d)計算與父節(jié)點Dj相鄰的每個網(wǎng)格b到終止點所在的網(wǎng)格EG的總估計值F(b):F(b) = G (b) +HMb ；其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費:G(b) = EJ+1 ；5e)將總估計值F(b)中的最小值所對應的網(wǎng)格X作為新的父節(jié)點1+1，總計劃移動距離為:Ej+1 = Lx+Ej，其中。為父節(jié)點Dj到與其相鄰的網(wǎng)格X中心連線的長度，則當前的計劃移動路徑為父節(jié)點&與新的父節(jié)點1+1所在的網(wǎng)格中心的連線；5f)判斷新的父節(jié)點^與父節(jié)點&的搜索方向是否相同，如果搜索方向相同，則返回步驟(5b)繼續(xù)進行搜索；否則，執(zhí)行步驟(5g)；5g)將步驟(5f)中的新的父節(jié)點h+1作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規(guī)劃，此時，網(wǎng)格地圖中飛行器的起始點SP所在的網(wǎng)格SG到達終止點EP所在的網(wǎng)格EG的路徑，即為網(wǎng)格地圖中所有父節(jié)點Dt與Dt+1所在的網(wǎng)格中心連線組成的線段，其中0 ≤t ≤j，否則，返回步驟(3)。
2.根據(jù)權利要求1所述的基于自適應A星算法的飛行器最優(yōu)路徑確定方法，其中步驟(3)所述的將障礙物區(qū)域進行網(wǎng)格劃分，得到網(wǎng)格地圖，按如下步驟進行:3a)設定網(wǎng)格X方向邊長為2，依據(jù)起始點SP和終止點EP的坐標差值比例，計算網(wǎng)格Y方向的邊長Y::
【文檔編號】G01C21/20GK103697895SQ201410010003
【公開日】2014年4月2日 申請日期:2014年1月9日 優(yōu)先權日:2014年1月9日
【發(fā)明者】于昕, 焦李成, 朱振強, 馬晶晶, 馬文萍, 劉軍強, 李陽陽 申請人:西安電子科技大學