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

有效

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

本發明屬于無人機系統技術領域，具體涉及一種基于聚類和遺傳算法的多無人機協同任務規劃方法。該方法基于K?means聚類算法完成多個任務點的點簇劃分，將多無人機協同規劃能耗最優航跡問題簡化為多個單架無人機的旅行商問題，并對遺傳算法進行改進，基于改進后的遺傳算法提出一種UAV航點規劃優化算法進行航跡優化，使得無人機的能耗最優，以避免飛行過程中受到環境影響導致實際能耗值變大導致無法執行規劃航線的問題出現，提高飛行效率和能量利用率。

技術領域

本發明屬于無人機系統技術領域，具體涉及一種基于聚類和遺傳算法的多無人機協同任務規劃方法。

背景技術

近年來，全世界的經濟基礎實力得到很大程度的提升，科技也隨之逐漸發展、提高，無人機技術的研究也有了較大的飛躍，其應用非常廣泛。在很多復雜的場景之下，單個無人機根本無法達到人們的預期，于是提出了運用多架無人機協同實現快速高效的任務執行。

對比單無人機與多無人機協同發現：單架無人機操作簡單且易實現，而多架無人機執行任務時要完善它們之間的協同規劃，故而后者執行起來比較復雜，對服務器的處理速度有一定的要求。但是單架無人機只能按照順序依次完成所有任務，這樣會很耗時，很多情況下無法達到要求；而多架無人機能夠在同一時間解決多個任務。相較之下，多無人機很大地提升了任務執行速度，大多數情況下能夠應對任務實時性的要求。另外，無人機的運行需要能量支持，而一架無人機對能量的儲存能力是有限的，單無人機執行復雜任務時很可能出現能量耗盡需要返回基地補充能量的情況，而多架無人機只要選擇合適的任務管理方式完成任務分配和航跡規劃，便可以達到盡可能少的能量消耗，這對于環境保護、節約能源均有益。但是就目前而言，多架無人機之間的協同配合問題值得我們進一步的深度研究。因此，設計一種多無人機協同任務規劃方法至關重要。

發明內容

針對目前多架無人機協同配合存在的缺陷和問題，本發明提供一種基于聚類和遺傳算法的多無人機協同任務規劃方法，從而實現多無人機協同規劃能耗最優的航行軌跡，便于突發緊急任務時無人機能夠有一定的能源儲備。

本發明解決其技術問題所采用的方案是：一種基于聚類和遺傳算法的多無人機協同任務規劃方法，包括以下步驟：

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

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

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

步驟四、對遺傳算法的選擇、交叉變異以及進化環節進行改進，利用改進的遺傳算法對無人機的巡檢區域進行路徑規劃得到K架無人機協同的最優航跡；

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

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

上述的基于聚類和遺傳算法的多無人機協同任務規劃方法，步驟二中采用K-means聚類算法將n個任務點劃分為K個點簇，每一個點簇由一架UAV負責執行任務，包括以下步驟：

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

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