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

在審

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

技術(shù)領(lǐng)域

本發(fā)明涉及一種基于樹分解的智能搜捕方法，屬于智能協(xié)同控制技術(shù)領(lǐng)域。

背景技術(shù)

圖搜索算法的研究是智能協(xié)同控制領(lǐng)域的一個重要分支，搜索算法的性能通過算法的復(fù)雜度、有效性來衡量。多智能體搜捕方法中最短路徑搜捕策略、最短時間搜捕策略、博弈搜捕策略等的方法主要側(cè)重于搜捕策略的最大效率，而忽視了所需搜捕者的數(shù)量以及搜捕的成功率，其算法的復(fù)雜度也較大。而本發(fā)明所定義的搜捕方法中的搜捕者數(shù)量既能保證搜捕的成功，又減少了搜捕的損耗。圖搜索算法的求解思想能用于應(yīng)急環(huán)境救援、室內(nèi)環(huán)境安防、戰(zhàn)場環(huán)境探測，因此基于樹分解的多智能體搜索方法既能為監(jiān)測環(huán)境的入侵搜索提供理論基石，也能為監(jiān)測環(huán)境安全防護(hù)提供解決方案。

監(jiān)測環(huán)境入侵搜索的理論基石圖搜索是解決監(jiān)測環(huán)境入侵搜索最常用的方法，根據(jù)多智能體的感知范圍、移動速度以及監(jiān)測環(huán)境的特點對監(jiān)測環(huán)境進(jìn)行拓?fù)淇坍嫞@取其拓?fù)浣Y(jié)構(gòu)，并利用圖論的方法對網(wǎng)絡(luò)進(jìn)行搜索，能夠最有效率的實現(xiàn)對整個環(huán)境的搜索，并以最快的速度定位入侵者。

監(jiān)測環(huán)境安全防護(hù)的解決方案在保證搜索成功的情況下，使用最少的多智能體對環(huán)境進(jìn)行安全防護(hù)，利用樹分解的方法，將圖中的環(huán)變?yōu)闃渲械墓?jié)點，防止了圖搜索過程中的重污染，保證了對整個環(huán)境的有效防護(hù)。

入侵者位置、速度不可知的情況下，基于搜捕策略的搜捕者數(shù)量的研究是非常有難度、有挑戰(zhàn)性的，當(dāng)前公開發(fā)表的文獻(xiàn)中，尚未看到相關(guān)研究成果。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種能夠克服上述技術(shù)問題的基于樹分解的智能搜捕方法，本發(fā)明提出了以最小搜捕者數(shù)量及追捕的有效性為優(yōu)化目標(biāo)的移動傳感網(wǎng)搜捕的技術(shù)方案，本發(fā)明基于樹分解的方法對環(huán)境進(jìn)行搜素，避免了搜索過程中入侵者的重復(fù)侵入，能提高搜索效率并減少了搜捕過程中的能量開銷。首先給出以下定義：

定義1搜捕者數(shù)量：指在某一環(huán)境中存在一種策略使得最少數(shù)量的搜捕者能夠成功圍捕入侵者，該最少數(shù)量即為搜捕者數(shù)量。

定義2上界：指某一環(huán)境中所需搜捕者數(shù)量的最大值。

本發(fā)明的基于樹分解的智能搜捕方法包括以下步驟：

步驟一，獲取目標(biāo)環(huán)境，根據(jù)搜捕者的感知能力將監(jiān)測環(huán)境轉(zhuǎn)換為拓?fù)鋱D；

獲取目標(biāo)環(huán)境，根據(jù)搜捕者的感知能力和移動速度將環(huán)境離散化為有限圖，根據(jù)智能體的感知能力將環(huán)境離散化為單元，使得每個搜捕者能夠監(jiān)測環(huán)境離散化后的每一個單元，若入侵者進(jìn)入此單元，搜捕者能夠及時對其進(jìn)行捕獲，用頂點代替單元，相鄰的單元之間插入一條邊，目標(biāo)環(huán)境離散化為圖G＝(V,E)表示，其中圖G為無向連通，V表示頂點集，|V|表示頂點的個數(shù)，E表示邊集。

步驟二，環(huán)境拓?fù)鋱D的樹分解；

在圖G＝(V,E)中選取路徑L，且L中包含頂點集V中的兩個端點，對圖G按如下方式進(jìn)行樹分解：

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

(1)∪X_i＝V；

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

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

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

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

步驟三，求解拓?fù)鋱D樹寬；

依據(jù)步驟二對圖G求得的樹分解(T_L,X)，求取樹的寬度為

步驟四，求解基于樹分解的搜捕算法；