[發明專利]一種基于聚類和遺傳算法的多無人機協同任務規劃方法

有效

• 申請號: 202011551845.1
• 申請日: 2020-12-24
• 公開（公告）號: CN112731967B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 王煜煒;薛晶晶;劉敏;付艷波;王元卓
• 申請（專利權）人: 中科院計算技術研究所大數據研究院
• 主分類號: G05D1/10
• 分類號: G05D1/10;G06K9/62;G06N3/12
• 代理公司: 鄭州明華專利代理事務所(普通合伙) 41162
• 代理人: 王明朗

1.一種基于聚類和遺傳算法的多無人機協同任務規劃方法，其特征在于：包括以下步驟：

步驟一、根據任務類型和巡檢區域獲取多個無人機協同任務的所有任務航點n，將所有任務航點共同組成任務航點集P＝{P₁,P₂,…,P_n}，計算任務航點集中所有任務航點的坐標；

步驟二、選取K架無人機負責執行該巡檢區域的巡檢任務，以距離為劃分依據使用K-means聚類算法對所有任務航點進行集中式分配；

步驟三、根據每架無人機負責的任務點的坐標計算出每架無人機執行任務的能量消耗，所述能量消耗包括飛行能耗、轉向能耗和數據傳輸能耗；

所述飛行能耗為：

式中：E_dj為UAV_j的飛行能耗；P為飛行功率；t為飛行時間；為飛行阻力；為飛行速度，表示UAV_j執行任務時的總直線飛行距離；

所述轉向能耗為：

式中：E_rj為UAV_j的轉向能耗、θ為轉向角；α為比例參數，||(x_i-x_i-1,y_i-y_i-1)||₂表示P_i-1、P_i兩點間的距離；

所述數據傳輸能耗為：

式中：E_tj為數據傳輸的能耗、ω為UAV_j需要傳輸的數據量、P_t為數據傳輸功率、C為數據傳輸的信道容量、L為數據傳輸路徑損耗、z為接收者的靈敏度、P₀＝10^z+δ為常數，δ為常數，λ為常數一般取20；(x₁,x₂)為任務點的坐標；

步驟四、利用改進的遺傳算法對無人機的巡檢區域進行路徑規劃得到K架無人機協同的最優航跡；

步驟五、K架無人機按照步驟四的最優航跡進行航行，并在將執行任務時收集的數據傳輸至本地服務器的同時實時傳送本機的能量剩余，若電池剩余百分比大于15％時，繼續按照航跡執行任務，若無人機電池剩余百分比小于15％，后端控制服務器發送相應信息要求無人機立刻中斷當前任務的執行，返回無人機基地補充能量。

2.根據權利要求1所述的基于聚類和遺傳算法的多無人機協同任務規劃方法，其特征在于：步驟一中還包括根據無人機裝載的傳感器或者攝像機的覆蓋范圍確定劃分的規格，采用網格分割法，將待測區域網格化處理，待測點為每個網格的中心，從而使能夠完全覆蓋巡檢區域。

3.根據權利要求1所述的基于聚類和遺傳算法的多無人機協同任務規劃方法，其特征在于：步驟二中采用K-means聚類算法將n個任務點劃分為K個點簇，每一個點簇由一架UAV負責執行任務，包括以下步驟：

(1)產生隨機坐標點作為聚類中心；

(2)分別計算各任務航點到K個聚類中心的距離，將任務航點依次劃分給距離最近的聚類中心所屬的點簇；

(3)采用均值法更新聚類中心得到新的中心坐標；

(4)根據新的中心坐標按照步驟(2)、(3)完成點簇劃分；

(5)判斷本次迭代得到的聚類中心的坐標是否滿足預先設定的聚類中心的坐標精確度，

若不滿足，則多次迭代重復(3)、(4)；

若滿足，則結束運行。

4.根據權利要求1所述的基于聚類和遺傳算法的多無人機協同任務規劃方法，其特征在于：步驟四中對單無人機進行航跡規劃，包括以下步驟：

(1)設定種群的個體數、算法的最大循環次數，隨機產生任務航點序列構成原始種群；

(2)計算個體適應度

(3)種群中適者生存淘汰部分個體，生存下來的所有個體作為父代按照計算出的概率交配重組產生下一代個體，之后再按照計算出的概率發生基因突變生成新個體，進而結合成新種群；

(4)重復(2)、(3)，直到完成循環，得到能耗最優的航跡規劃。

5.根據權利要求1所述的基于聚類和遺傳算法的多無人機協同任務規劃方法，其特征在于：步驟五中對于未完成巡檢的任務航點，派遣能量儲存足夠且距離較近的無人機繼續執行巡檢任務。