[發明專利]一種基于樹分解的智能搜捕方法

在審

• 申請號: 201611047818.4
• 申請日: 2016-11-25
• 公開（公告）號: CN106779169A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 米士超;白永強;魯剛;杜嘉薇;郭榮華
• 申請（專利權）人: 中國人民解放軍63880部隊
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N5/00
• 代理公司: 北京中海智圣知識產權代理有限公司11282
• 代理人: 胡靜

1.一種基于樹分解的智能搜捕方法，其特征在于，包括以下步驟：

(1)獲取目標環境，根據搜捕者的感知能力將監測環境轉換為拓撲圖；

(2)環境拓撲圖的樹分解；

(3)求解拓撲圖樹寬；

(4)求解基于樹分解的搜捕算法；

(5)求解搜捕者數量最小上界。

2.根據權利要求1所述的一種基于樹分解的智能搜捕方法，其特征在于，所述步驟(1)中，獲取目標環境，根據搜捕者的感知能力和移動速度將環境離散化為有限圖，根據智能體的感知能力將環境離散化為單元，使得每個搜捕者能夠監測環境離散化后的每一個單元，若入侵者進入此單元，搜捕者能夠及時對其進行捕獲，用頂點代替單元，相鄰的單元之間插入一條邊，目標環境離散化為圖G＝(V,E)表示，其中圖G為無向連通，V表示頂點集，|V|表示頂點的個數，E表示邊集。

3.根據權利要求1所述的一種基于樹分解的智能搜捕方法，其特征在于，所述步驟(2)中，在圖G＝(V,E)中選取路徑L，且L中包含頂點集V中的兩個端點，對圖G按如下方式進行樹分解：

圖G＝(V,E)的一個樹分解為(T_L,X)，X＝{X_i|i∈I}，其中I是V的一個子集族，T_L是指以I為頂點集的樹，T_L中的節點是X的子集，路徑L為圖G中端點v₁到v_K的連接路徑，路徑L中包含K個節點v₁,v₂,...,v_K，并且滿足：

(31)∪X_i＝V；

(32)對于任意的i∈L，X_i至少包含一個v_i，1≤i≤K；

(33)對于任意一條邊(u,v)∈E，存在一個i∈L使得

(34)對于樹的節點X_i，X_j以及X_k，如果樹節點X_k是樹節點X_i到X_j路徑上的一個樹節點，則圖G中存在一個節點屬于X_i∩X_j，且有

分解后的每一個樹的子節點X_i,j包含路徑L上的至少一個圖的節點i，j表示圖G中的任一頂點，J是V的一個子集族。

4.根據權利要求1所述的一種基于樹分解的智能搜捕方法，其特征在于，所述步驟(3)中，依據步驟(2)對圖G求得的樹分解(T_L,X)，求取樹的寬度為