[發明專利]基于自適應A星算法的飛行器最優路徑確定方法

無效

• 申請號: 201410010003.3
• 申請日: 2014-01-09
• 公開（公告）號: CN103697895A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 于昕;焦李成;朱振強;馬晶晶;馬文萍;劉軍強;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

1.一種基于自適應A星算法的飛行器最優路徑確定方法，包括如下步驟：

（1）在地圖中設置飛行器的起始點SP和終止點EP；

（2）生成障礙物區域：

2a）根據飛行器的起始點SP和終止點EP的位置，建立直角坐標系；

2b)設p_i，q_i分別為飛行器需繞過的每一個障礙物的起點和終點的坐標，對p_i點分別做垂直于直角坐標系X軸和Y軸的直線，對q_i點分別做垂直于直角坐標系X軸和Y軸的直線，用這四條直線圍成的一個矩形，表示障礙物區域T_i，其中i為障礙物的個數；

（3）將障礙物區域進行網格劃分，得到網格地圖；

（4）在網格地圖中，設飛行器的起始點SP所在的網格為SG、終止點EP所在的網格為EG；

（5）根據飛行器的起始點所在網格SG和終止點所在網格EG，進行路徑規劃：

5a）令飛行器的起始點SP所在的網格SG為父節點D_j，設總計劃移動距離為：E_j+1＝L_b+E_j，其中L_b為父節點D_j到與其相鄰的每個網格b所需要走的路徑長度，即父節點D_j到與其相鄰的每個網格b中心連線的長度，b為相鄰網格的標號，1≤b≤8，E_j為從起始點所在網格SG到達父節點D_j所移動的距離，j為父節點D_j的標號；設定父節點D_j在起始點所在網格SG時初值為：j＝0，L＝0，E_j＝0；

5b）分別計算第一個相鄰網格通過水平—垂直平移和垂直—水平平移這兩條路徑到達終止點所在網格EG的預估算耗費：H_n＝R(k)*m，并將這兩個預估算耗費的最小值記為HM，其中R(k)為平移過程中所經過的網格數，k為平移過程中所經過的網格標號，n為路徑標號，n為整數，1≤n≤2，m為地圖放大系數，1≤m≤20；

5c）對與父節點D_j相鄰的每一個網格重復步驟（5b），得到各自的預估算耗費的最小值HM_b；

5d）計算與父節點D_j相鄰的每個網格b到終止點所在的網格EG的總估計值F(b)：

F(b)＝G(b)+HM_b；

其中G(b)為總移動耗費，其值與總計劃移動距離相等，即總移動耗費：G(b)＝E_j+1；

5e）將總估計值F(b)中的最小值所對應的網格x作為新的父節點D_j+1，總計劃移動距離為：E_j+1＝L_x+E_j，其中L_x為父節點D_j到與其相鄰的網格x中心連線的長度，則當前的計劃移動路徑為父節點D_j與新的父節點D_j+1所在的網格中心的連線；

5f）判斷新的父節點D_j+1與父節點D_j的搜索方向是否相同，如果搜索方向相同，則返回步驟（5b）繼續進行搜索；否則，執行步驟（5g）；

5g）將步驟（5f）中的新的父節點D_j+1作為新的起始點SP，并判斷該點與終止點EP的距離是否小于2，若距離小于2，則停止路徑規劃，此時，網格地圖中飛行器的起始點SP所在的網格SG到達終止點EP所在的網格EG的路徑，即為網格地圖中所有父節點D_t與D_t+1所在的網格中心連線組成的線段，其中0≤t≤j，否則，返回步驟（3）。

2.根據權利要求1所述的基于自適應A星算法的飛行器最優路徑確定方法，其中步驟（3）所述的將障礙物區域進行網格劃分，得到網格地圖，按如下步驟進行：

3a）設定網格X方向邊長為2，依據起始點SP和終止點EP的坐標差值比例，計算網格Y方向的邊長Y_l：

Yl=2*|yep-yspxep-xsp|;]]>

其中(x_sp,y_sp)為起始點SP的坐標，(x_ep,y_ep)為終止點EP的坐標；

3b）在障礙物區域中，將障礙物所覆蓋到的網格值均設為1，其他網格值均設為0，得到網格地圖。