[發明專利]一種多目標約束的低空無人機航路規劃設計方法

在審

• 申請號: 202010746683.0
• 申請日: 2020-07-29
• 公開（公告）號: CN111915932A
• 公開（公告）日: 2020-11-10
• 發明（設計）人: 曹先彬;杜文博;李思遠;張明遠
• 申請（專利權）人: 北京航空航天大學
• 主分類號: G08G5/00
• 分類號: G08G5/00
• 代理公司: 北京永創新實專利事務所 11121
• 代理人: 周長琪

1.一種多目標約束的低空無人機航路規劃設計方法，其特征在于：具體步驟為：

步驟1：確定航路網絡作用的區域；

步驟2：確定區域內有效空域；

步驟3：提取有效區空域內的城市輪廓；

步驟4：城市輪廓中構建節點；

步驟5：構建航路連邊，形成初始航路網絡；

步驟6：引入約束條件，確定多目標函數，優化無人機中心位置與連邊，構建滿足約束條件且多目標函數達到最優的航路網絡。

2.如權利要求1多目標約束的低空無人機航路規劃設計方法，其特征在于：步驟4中節點構建方法為：

A：確定無人機需求區域，并將區域拆分為離散需求點；

B：有限覆蓋法選取無人機中心位置作為節點。

3.如權利要求2多目標約束的低空無人機航路規劃設計方法，其特征在于：選取無人機中心位置，具體表述為最大化：

有

x_j∈{0,1},j∈J

y_i∈{0,1},i∈I，I為需求點的集合

d_i,j≤r

其中，x_j表示第j個候選被選中情況，被選中表示為1，未選中表示為0；y_i表示需求點i被覆蓋情況，被無人機中心覆蓋表示為1，未覆蓋表示為0；I表示需求點的集合；J表示候選無人機中心位置的集合；d_i,j表示需求點i到無人機中心j的距離(歐幾里得距離)；K表示選擇的無人機中心位置數量；r表示需求點與無人機中心位置之間的最大距離。

4.如權利要求1多目標約束的低空無人機航路規劃設計方法，其特征在于：步驟5中根據構建的節點，采用Kruskal算法相連，構成內部聯通的無人機航路網絡。

5.如權利要求4多目標約束的低空無人機航路規劃設計方法，其特征在于：具體方式為：

首先，初始最小有效無人機航路網絡邊數為0，每迭代一次就選擇一條最小代價邊，加入到最小有效無人機航路網絡的邊集合里；

隨后通過下述步驟構建連邊：

(1)將最小有效無人機航路網絡的邊集合里的所有邊按代價從小到大排序；

(2)將無人機航路網絡中的n個無人機中心看成獨立的n個有效無人機航路網絡組成的航路網絡集合；

(3)按權值從小到大選擇邊，所選的邊連接的兩個無人機中心ui,vi應屬于兩個不同的有效無人機航路網絡，該邊成為最小有效無人機航路網絡的一條邊，并將兩個無人機中心ui,vi所屬的兩個有效無人機航路網合并作為一個有效無人機航路網絡；

(4)重復步驟(3)，直到所有頂點都在一個有效無人機航路網內且整個網絡有n-1條邊為止，形成最小有效無人機航路網絡。

6.如權利要求1多目標約束的低空無人機航路規劃設計方法，其特征在于：步驟6的具體方法為：

以步驟4中選取的節點為圓心，在給定范圍內隨機移動，形成新的無人機中心，在完成所有無人機中心位置移動后，重復步驟5，重構航路連邊，形成新的航路網絡，并判斷該網絡是否滿足約束條件，如果滿足約束條件，則本次移動有效，如果不滿足約束條件，則返回本次移動前的航路網絡，并重新進行前述過程；上述每次無人機中心位置移動后，判斷多目標函數是否達到最優，若多目標函數達到最優，則航路網絡優化完畢，否則繼續移動無人機中心，直到多目標函數達到最優。