[發明專利]一種用于航線規劃的最優路徑生成方法

有效

• 申請號: 201810030677.8
• 申請日: 2018-01-12
• 公開（公告）號: CN108225333B
• 公開（公告）日: 2020-03-24
• 發明（設計）人: 黃琦龍;卜卿;付強;劉唐興;茆超;張艷偉;黃山良
• 申請（專利權）人: 中國電子科技集團公司第二十八研究所
• 主分類號: G01C21/20
• 分類號: G01C21/20
• 代理公司: 江蘇圣典律師事務所 32237
• 代理人: 胡建華;于瀚文

本發明公開了一種用于航線規劃的最優路徑生成方法，本發明是在僅輸入部分轉彎信息下，通過對航線進行分割和回溯處理，利用二叉樹搜索和剪枝方法啟發式的遍歷所有可行航線，并提取當前輸入信息下所能得到的最優航線，從而解決傳統航線規劃方法計算量大、耗時長的問題。本發明提出的方法能夠根據實際系統環境和性能要求，調整搜索過程中的參數，從而保證本方法搜索到最優路徑的耗時滿足系統快速生成航線方案的實際需求。

技術領域

本發明涉及航線規劃技術領域，尤其涉及一種用于航線規劃的最優路徑生成方法。

背景技術

目前，航天航空技術正在不斷快速發展，航線規劃和繪制作為航天航空技術中的重要組成部分，也影響著軍民航管理系統的運行效率。特別的，對于無人機飛行航線管理系統，在規劃、繪制無人飛行器航線時，為了繪制方便，通常由操作人員在地圖上繪出單點航線。對于每個航線點，其屬性可以有三種類型，分別是轉彎開始點、轉彎圓心點和轉彎結束點。對于不同位置的航線點，由于該航線點執行任務不同，相應點的屬性也不同，例如無人機執行偵察任務時，通常選擇轉彎圓心點作為航線點，而在執行攻擊投彈任務時，通常選擇轉彎開始點作為航線點。另外，操作人員在繪出航線點時，多數也不對轉彎方向做要求，因此在完成單點航線繪制時，需要根據航線點類型對航線進行計算，選擇合理的轉彎方向以獲得最優航線。

基于航線單點的航線規劃問題主要面臨如下幾個難點。首先，由于輸入的轉彎單點信息不完整，例如一些轉彎單點無轉彎方向信息，飛行器的飛行航線有多種可能。對于每一個轉彎過程，其轉彎方向有2種可能，因而所有可能飛行航線數與轉彎點數成指數增長關系。因此，如何在指數增長的解空間中搜索到最優飛行航線是航線規劃的一個主要難點。其次，飛行航線管理系統通常對最優航線的計算時間有要求。由于可行的飛行航線數目過于龐大，通過遍歷搜索最優飛行航線的常規方法會由于計算異常耗時的原因而不可行。因此，如何在龐大的解空間中快速的搜索到最優飛行航線也是一個主要難點。最后，當每個轉彎過程的飛行航向已知時，如果輸入的轉彎單點中無轉彎結束點，則每個轉彎單點可以通過利用前面相鄰點的轉彎三點信息(轉彎開始點、圓心點、結束點)和后面相鄰點的位置唯一確定當前轉彎過程的全部信息。但是當輸入的轉彎單點中存在轉彎結束點時，該轉彎結束點對應的轉彎過程信息可能無法按照上述方法求出(例如若干個轉彎結束點相鄰的情況)。因此，如何有效的處理轉彎結束點情況也是航線規劃的一個難點。

近年來，航線規劃作為飛行航線管理系統的核心功能，得到了很多關注。常見的航線規劃方法有動態規劃方法[陳長林,孫邁,宋順達.基于Voronoi圖的突防航線動態規劃.指揮控制與仿真,2009,31(5):27-29]、粒子群方法[吳逸,李強,代科學,王國師.基于粒子群算法的預警機航線規劃.空軍雷達學院學報,2010,24(6):410-413]、A*方法[周榮坤,黃麗芳.一種航線規劃算法應用.火力與指揮控制,2010,35(6):176-182]等。對于基于航線單點的航跡規劃問題，已有傳統方法沒有針對航線單點這種輸入信息進行航線規劃，并且忽略了飛行器的轉彎過程。另外，已有傳統方法通常是利用一些基于迭代的優化方法進行啟發式搜索，這類方法面臨迭代耗時、收斂速度慢的問題，因而不能滿足飛行航線管理系統的實際應用需求。

發明內容

為了解決無人機飛行管理系統中的航線規劃問題，本發明提供了一種基于二叉樹分割搜索和剪枝的最優航線規劃方法。

現有的航線規劃方法需要利用基于迭代的優化方法進行求解，面臨計算耗時的困難。為了提高航線規劃的計算效率，本發明要利用啟發式信息，限制遍歷搜索的可行解空間，保證搜索方向維持在最優航線解的方向，從而實現航線規劃方案的快速生成。

所采用的技術方案是：基于二叉樹分割搜索和剪枝的最優航線規劃方法，包括如下步驟：

步驟1，假設操作人員共繪出了N個航線單點。獲取轉彎點數據集合(P₁,P₂,...,P_N)，P_i表示第i個轉彎點，i取值為1～N，N為轉彎點總數；