[發明專利]基于文化蟻群搜索機制的多無人機航跡規劃方法

有效

• 申請號: 201710833308.8
• 申請日: 2017-09-15
• 公開（公告）號: CN107622327B
• 公開（公告）日: 2020-11-03
• 發明（設計）人: 高洪元;蘇雪;侯陽陽;刁鳴;張世鉑;蘇雨萌;王宇;池鵬飛;劉子奇
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/00;G05D1/02
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于文化蟻群搜索機制的多無人機航跡規劃方法，其特征是包括如下步驟：

步驟一：采用柵格法對規劃空間進行網格劃分

設規劃空間橫坐標范圍為[x_min,x_max]，其中x_min為橫坐標最小值，x_max為橫坐標最大值，規劃空間縱坐標范圍為[y_min,y_max]，其中y_min為縱坐標最小值，y_max為縱坐標最大值，設網格大小為N_grid，規劃空間中共有網格列數為：共有網格行數為共有節點數N＝h×q，按照從下到上，從左到右的順序對所有節點編號，若第i個節點p_i的坐標為(x_i,y_i)，其節點編號計算公式為：

步驟二：建立多無人機航跡規劃模型

設第u條無人機航跡的起點的坐標為(x_startu,y_startu)，其中1≤u≤U，U為無人機航跡數，終點的坐標為(x_endu,y_endu)，四種威脅的個數分別為k_R、k_M、k_A和k_C，其中第r個第一種威脅點坐標表示為第m個第二種威脅點坐標為第a個第三種威脅點表示為第c個第四種威脅點表示為第一種威脅半徑為d_R，第二種威脅半徑為d_M，第三種威脅半徑d_A,第四種威脅威脅半徑d_C；

第i個節點的p_i受到的威脅代價表示如下：其中1≤i≤N，N為節點數，ω_i是第i個節點p_i受到的威脅代價和，為第i個節點p_i受到第r個第一種威脅的威脅代價，其中為第i個節點p_i與第r個第一種威脅的距離；為第i個節點p_i受到第m個第二種威脅的威脅代價，為第i個節點p_i與第m個第二種威脅的距離；為第i個節點p_i受到第a個第三種威脅的威脅代價，為第i個節點p_i與第a個第三種威脅的距離；為第i個節點p_i受到第c個第四種威脅的威脅代價，為第i個節點p_i與第c個第四種威脅的距離，δ_R為第一種威脅的威脅代價和的權重，δ_R∈[0,1]；δ_M為第二種威脅的威脅代價和的權重，δ_M∈[0,1]；δ_A為第三種威脅威脅代價和的權重，δ_A∈[0,1]；δ_C為第四種威脅的威脅代價和的權重，δ_C∈[0,1]；

步驟三：初始化起點和終點

設第u條無人機航跡的起點的坐標為終點的坐標為1≤u≤U，初始時令u＝1；

步驟四：初始化蟻群

(1)初始化蟻群，

初始化第t代當前節點v到下一個節點e的信息素濃度τ₀為初始信息素濃度，其中1≤v≤N，1≤e≤N，t為迭代次數，得到N×N的矩陣初始化信息素增加強度Q，信息素重要程度α，啟發因子的重要程度β，引導因子的重要程度γ，信息素揮發系數ρ，初始時設t＝0，初始化第t代當前節點v到下一個節點e的信息素濃度得到N×N的矩陣

(2)計算啟發因子，

首先計算第i個節點p_i的受到的威脅代價ω_i，第i個節點p_i的啟發因子η_i等于該節點的威脅代價的倒數，即

(3)計算引導因子

計算第i個節點p_i與第u條無人機航跡的終點的距離第i個節點p_i與第u條無人機航跡的終點的引導因子λ_u,i為第i個節點p_i與第u條無人機航跡的終點的距離的d_u,i的倒數，即

步驟五：將第k只螞蟻分配到初始節點，1≤k≤K，令k＝1，執行以下步驟：

(1)初始化第t代第k只螞蟻的禁忌知識矩陣為其中N為共有節點數，初始第t代第k只螞蟻在第i個節點禁忌知識

(2)將起點歸到相應節點，

第t代第u條無人機航跡的起點的編號為第t代第u條無人機航跡的終點的編號為記第t代第k只螞蟻當前所在節點記為第t代第k只螞蟻相鄰的節點集合記為

(3)將第t代第k只螞蟻置于起點上，其中K為最大螞蟻只數，即令將起點加入第t代第k只螞蟻的禁忌知識，即令將第t代第k只螞蟻的起點的編號加入到第t代第k只螞蟻的路徑集中；

步驟六：螞蟻根據狀態轉移策略選擇下一節點

(1)尋找當前節點相鄰的節點，

根據柵格法，若當前節點不在規劃空間邊界時附近有8個節點，第t代第k只螞蟻相鄰的節點集合若當前節點在規劃空間邊界時排除不相鄰的點，根據第t代第k只螞蟻的禁忌知識更新第t代第k只螞蟻相鄰的節點集合得到第t代第k只螞蟻可訪問的節點集合對于第t代第k只螞蟻相鄰的節點集合第j個點若則刪除相鄰的節點集合第j個點得到第t代第k只螞蟻可訪問的節點集合

(2)判斷第t代第k只螞蟻可訪問節點集合是否為空，若為空則執行(5)，否則執行(3)；

(3)第t代第k只螞蟻可訪問節點集合中節點的個數為對于第t代第k只螞蟻可訪問的第n個節點，狀態轉移概率根據輪盤賭法選出第t代第k只螞蟻待訪問的第y個節點第t代第k只螞蟻待訪問的節點記為

(4)判斷第t代第k只螞蟻待訪問的節點是否為第t代第u條無人機航跡的終點，若為第t代第u條無人機航跡的終點即則將第t代第u條無人機航跡的終點的編號加入到第t代第k只螞蟻的路徑集然后執行(5)，否則令將第t代第k只螞蟻當前節點加入到第t代第k只螞蟻的路徑集中，更新第t代第k只螞蟻的禁忌知識，即令然后返回(1)；

(5)若k≠K則令k＝k+1并返回步驟五中的(1),否則執行步驟七；

步驟七：根據歷史知識對信息素全局更新

(1)選出第t代到達終點的螞蟻中經過的最短路徑作為歷史知識ROUT^t，計算第t代最短路徑的綜合代價其中δ_O為油耗代價和的權重，δ_O∈[0,1]，且δ_R+δ_M+δ_A+δ_C+δ_O＝1，L^t是第t代最短路徑長度，是第t代最短路徑對應的威脅代價和，為第t代最優路徑對應的油耗代價，的計算公式為其中C_O為單位航程的油耗量；

(2)利用歷史知識對信息素增量進行更新，利用歷史知識對信息素進行更新其中|·|為求取絕對值函數；

步驟八：如果沒有達到最大迭代數，則令t＝t+1，返回步驟五繼續迭代；否則迭代終止，執行步驟九；

步驟九：若u＝U則得到U條航跡，將相應路徑中的節點映射到坐標軸映射成U條多無人機多路徑航跡，畫出多無人機從起點和終點的多條多路徑航跡，否則令u＝u+1返回步驟三繼續執行。