[發(fā)明專利]用于國家公園及自然保護地的無人機巡護路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202211112515.1
• 申請日: 2022-09-14
• 公開（公告）號: CN115185303B
• 公開（公告）日: 2023-03-24
• 發(fā)明（設(shè)計）人: 郭強輝;殷虹嬌;張鵬;王永峰;宋尚源;高琳
• 申請（專利權(quán)）人: 南開大學(xué);北京新智感科技有限公司
• 主分類號: G05D1/10
• 分類號: G05D1/10
• 代理公司: 天津創(chuàng)智睿誠知識產(chǎn)權(quán)代理有限公司 12251
• 代理人: 王海濱

1.一種用于國家公園及自然保護地的無人機巡護路徑規(guī)劃方法，其特征在于，包括以下步驟：

步驟1：輸入三維地形數(shù)據(jù)，生成一個有界的三維區(qū)域，在該區(qū)域上方空中設(shè)置路徑點V＝{v₁，v₂，...，v_n}，要求無人機遍歷所有路徑點后完成視覺覆蓋任務(wù)；

步驟2：以無人機飛行路徑為優(yōu)化目標，添加無人機遍歷路徑點、無人機電量限制、無人機自助充電線路規(guī)劃的約束條件，建立無人機路徑規(guī)劃模型；步驟2包括以下步驟：

步驟2.1：定義無人機的飛行路徑?jīng)Q策變量x_ij；

x_ij＝1,表示無人機從路徑點i飛到路徑點j；

x_ij＝0,表示無人機不會從路徑點i飛到路徑點j；

定義目標函數(shù)：

其中d_ij表示路徑點i與路徑點j之間的直線距離；

飛行路徑?jīng)Q策變量要確保能夠形成一條完整的、可行的一次遍歷路徑，具體約束如下：

步驟2.2：針對無人機的自助充電功能，調(diào)整帶自動機場的無人機自助充電線路規(guī)劃；

以飛行路徑衡量無人機能量消耗，將無人機的最大續(xù)航記為R，定義能量損失變量E_ij，自動機場集合B＝{b₁，b₂，...，b_m}；

無人機的剩余續(xù)航距離不超過最大續(xù)航R的非負數(shù)，公式表示如下：

x_ki是無人機從路徑點k飛到路徑點i的決策變量，E_ki是無人機從路徑點k飛至路徑點i所需能量損耗；

無人機離開自動機場時，電量滿載，公式表示如下：

更新目標函數(shù)：

步驟3：在步驟2建立的無人機路徑規(guī)劃模型下，利用分枝定界算法并結(jié)合線性松弛和貪心算法進行求解，得到無人機的遍歷路徑。

2.根據(jù)權(quán)利要求1所述的用于國家公園及自然保護地的無人機巡護路徑規(guī)劃方法，其特征在于：步驟3包括以下步驟：

步驟3.1：記MIP為需要求解的無人機路徑規(guī)劃問題，best_sol為當前最優(yōu)解，用于在求解過程中不斷更新搜索到的最優(yōu)解，初值取MIP中的任一可行解；記Lb為當前解空間下界，用于記錄求解過程中搜索到的當前最優(yōu)解對應(yīng)的目標函數(shù)值；

步驟3.2：分枝

設(shè)S為MIP的解空間，對飛行路徑?jīng)Q策變量x_ij進行枚舉，將解空間S劃分為兩個互不相交的子解空間S₀和S₁，其中，S₀中所有可行解的x_ij取值為0；S₁中所有可行解的x_ij取值為1；劃分出的子解空間稱為分枝節(jié)點；

步驟3.3：定界

使用貪心算法在子解空間中搜索可行解，若可行解的目標函數(shù)值小于best_sol的目標函數(shù)值，則更新best_sol；采用線性松弛方法計算可行解目標函數(shù)值下界，將未固定取值的飛行路徑?jīng)Q策變量的取值范圍由{0,1}轉(zhuǎn)變?yōu)閇0,1]，擴大子解空間中未固定值的飛行路徑?jīng)Q策變量的取值范圍，松弛后的子解空間使用CPLEX求解器進行計算；

步驟3.4：剪枝

根據(jù)求解情況篩選出合適的分枝節(jié)點，刪除的分枝節(jié)點中不存在比已知可行解best_sol更優(yōu)的，或者下界大于已知的解空間下界；

步驟3.5：根據(jù)剪枝后剩余的分枝節(jié)點，更新當前解空間下界Lb和best_sol，然后迭代進行分枝、定界和剪枝的操作，直至完成對解空間的樹搜索。

3.根據(jù)權(quán)利要求2所述的用于國家公園及自然保護地的無人機巡護路徑規(guī)劃方法，其特征在于：在步驟3.3中，使用貪心算法在子解空間中搜索可行解時，首先使用多種不同類型的貪心算法計算出多個局部最優(yōu)解，然后取并集，在并集中定義飛行路徑?jīng)Q策變量。