[發明專利]一種無人機路徑規劃方法

在審

• 申請號: 201410012975.6
• 申請日: 2014-01-13
• 公開（公告）號: CN103697896A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 焦李成;馬文萍;居陽;馬晶晶;王爽;侯彪;李陽陽
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 天津市三利專利商標代理有限公司 12107
• 代理人: 閆俊芬

技術領域

本發明屬于無人機技術領域，尤其涉及一種無人機路徑規劃方法。

背景技術

隨著信息化技術的發展，無人機（UAV）將逐漸的在軍事領域和民用領域中取得更加廣泛的應用。無人機應用中的關鍵技術之一是路徑規劃。路徑規劃（Path?Planning）的目的是在給定區間上，找出一條連接起點和終點的，代價最小的路徑。

路徑規劃是一個NP-Complete問題，截至目前，仍未有固定的最優算法。主流的路徑規劃算法有：Dijkstra、A*、進化算法（Genetic?Algorithm）、人工勢場法（Artificial?Potential?Field）等。但這些算法的計算復雜度較高，其計算量隨著地圖的增大呈指數上升。

在2001年，Cem?Hocaoglu和Arthur?C.Sanderson在《Planning?Multiple?Paths?with?Evolutionary?Speciation》中提出了一種計算復雜度與地圖大小無關的路徑規劃HOCAOGLU算法，HOCAOGLU算法計算復雜度只與地圖的障礙物數量相關，地圖越復雜，路徑需要的節點就越多，HOCAOGLU算法的搜索空間就越大，從而導致算法計算代價的提升，而若是對于一種極端情況——無障礙物的地圖，HOCAOGLU算法的計算復雜度為常量，HOCAOGLU算法避免了大多數路徑規劃算法在大地圖上運算量過大的問題。

HOCAOGLU算法盡管上述多種優點，但依然存在固有的缺陷。HOCAOGLU算法并未給出確立節點的具體方法，而是采用進化算法進行搜索；同時，HOCAOGLU算法為了減小進化算法的搜索空間，僅在兩點連線的中點上作垂線，這降低了路徑的多樣性，經常會導致算法搜索不到可行路徑。

發明內容

本發明的目的是提供一種無人機路徑規劃方法，以解決現有技術中利用HOCAOGLU算法計算路徑時，存在的無法具體確定節點以及降低路徑多樣性進而經常無法搜到可行路徑的問題。

為實現本發明的目的，本發明提供了一種無人機路徑規劃方法，所述方法包括如下步驟：

第一步，初始化任務地圖，標注起點Start(x_start,y_start)、終點Goal(x_goal,y_goal)和障礙物的坐標，計算出所述無人機的最小安全轉向半徑R；

第二步，設定起點為節點Node[0]和終點為節點Node[-1]，查找其它節點坐標，以結構體建立二叉樹，所述結構體包括變量：節點在原屬線上的位置double?Position、節點坐標int?X,Y、障礙物高度double?Height、左子節點node*Child_Left、

右子節點node*Child_Right、左父節點node*Father_Left、右父節點node*Father_Right，

其中所述查找其它節點坐標，包括如下步驟：

（1）對于任意Node[i]，i=-1、0、1…i，令其與Node[i-1]之間進行連線，所述連線為所述原屬線；

（2）判斷所述Node[i]與所述Node[i-1]之間的連線距離，

若小于6R并且連線被所述障礙物遮擋，可判定為進入了死角，返回上一層并重新選取Node[i]節點；

若大于6R并且連線被障礙物遮擋，設點K(x_k,y_k)在連線(Node[i-1],Node[i])上，令K(x_k,y_k)從Node[i-1]沿該連線步進移動至Node[i]，形成數組K[Len]；對于K[Len]上每個處于障礙物區域中的點K[i]，向連線兩側作垂線H[i]，記錄其距離障礙物邊緣的距離，若該點障礙物延續到地圖M[Width][Height]邊緣則該側均不予記錄；