搜索研究論文-基于cpn模型的coa狀態(tài)空間搜索算法

《搜索研究論文-基于cpn模型的coa狀態(tài)空間搜索算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1、搜索研究論文-基于CPN模型的COA狀態(tài)空間搜索算法基于CPN模型的COA狀態(tài)空間搜索算法在信息化條件下，隨著軍事行動(dòng)越來(lái)越復(fù)雜，速度越來(lái)越快，軍事行動(dòng)正在從一種嚴(yán)格縱向的組織結(jié)構(gòu)向一種更加集成、更加模塊化、定制能力更強(qiáng)的結(jié)構(gòu)轉(zhuǎn)變。由于戰(zhàn)場(chǎng)情況的不確定性，以及作戰(zhàn)行動(dòng)的高對(duì)抗性，指揮員對(duì)參謀人員作戰(zhàn)計(jì)劃擬制、調(diào)整和修改的時(shí)效性提出了更高的要求，而傳統(tǒng)的人工作業(yè)方式無(wú)法滿足快速擬制作戰(zhàn)計(jì)劃的要求，需要采用信息化手段提高計(jì)劃擬制和調(diào)整的效率［1］。行動(dòng)方案是執(zhí)行使命任務(wù)的行動(dòng)過(guò)程或者任務(wù)流程，是在作戰(zhàn)目的(Op

2、erationObjective)和首長(zhǎng)意圖的指導(dǎo)下，使一定的戰(zhàn)爭(zhēng)實(shí)體在一定的時(shí)間，一定的地點(diǎn)，執(zhí)行一定的行動(dòng)，并產(chǎn)生一定的相互作用效果，按規(guī)則判斷實(shí)體狀態(tài)和行動(dòng)效果是否觸發(fā)條件或以時(shí)間驅(qū)動(dòng)，選擇下一行動(dòng)，最終確定整個(gè)可能的行動(dòng)序列［2］。所以COA的開(kāi)發(fā)與分析是作戰(zhàn)計(jì)劃制定關(guān)鍵步驟。COA開(kāi)發(fā)過(guò)程作戰(zhàn)單位從上級(jí)指揮部門(mén)受領(lǐng)作戰(zhàn)任務(wù)之后，軍事計(jì)劃人員分析作戰(zhàn)資源和能力指標(biāo)、評(píng)估當(dāng)前的敵我雙方的作戰(zhàn)態(tài)勢(shì)、作戰(zhàn)限制條件以及事實(shí)與假設(shè)，其中事實(shí)與假設(shè)決定了首長(zhǎng)的關(guān)鍵情報(bào)需求。然后，軍事計(jì)劃人員確定理想的作戰(zhàn)最終狀

3、態(tài)，并把整個(gè)作戰(zhàn)過(guò)程分解成若干個(gè)決定點(diǎn)，針對(duì)每個(gè)作戰(zhàn)決定點(diǎn)開(kāi)發(fā)具體的作戰(zhàn)任務(wù)。最后，因?yàn)檫@些大量的作戰(zhàn)任務(wù)之間存在復(fù)雜的因果關(guān)系，必須針對(duì)這些作戰(zhàn)任務(wù)進(jìn)行排序以及對(duì)作戰(zhàn)資源進(jìn)行分配，進(jìn)行COA開(kāi)發(fā)。如圖1所示。著色Petri網(wǎng)著色Petri網(wǎng)是一種典型的高級(jí)Petri網(wǎng)，當(dāng)我們?cè)趯?duì)較復(fù)雜的系統(tǒng)進(jìn)行建模時(shí)，常會(huì)出現(xiàn)庫(kù)所節(jié)點(diǎn)和變遷節(jié)點(diǎn)過(guò)多的情況，導(dǎo)致Petri網(wǎng)的建模和分析的復(fù)雜性大大增加。著色Petri網(wǎng)就是用來(lái)簡(jiǎn)化Petri網(wǎng)模型結(jié)構(gòu)的。它通過(guò)把系統(tǒng)中具有同類(lèi)行為特性的庫(kù)所節(jié)點(diǎn)歸并到一個(gè)庫(kù)所節(jié)點(diǎn)中，并通過(guò)令

4、牌的不同顏色來(lái)進(jìn)行區(qū)分，這樣就可以簡(jiǎn)化Petri網(wǎng)的結(jié)構(gòu)。著色Petri網(wǎng)中，還可以引入層次的概念，通過(guò)層次來(lái)把整個(gè)系統(tǒng)的模型組織起來(lái)，因此，建模和使用起來(lái)更方便和清楚［3］。CPN建模語(yǔ)言可以對(duì)那些可被視為并行系統(tǒng)的系統(tǒng)進(jìn)行建模，在這些系統(tǒng)里，同步化與資源分配是關(guān)鍵要素。系統(tǒng)的CPN模型既面向行動(dòng)，也面向狀態(tài)，因?yàn)樗梢圆东@該系統(tǒng)的當(dāng)前狀態(tài)以及在特定狀態(tài)下可能發(fā)生的事件。CPN還包括一個(gè)時(shí)間概念，該概念使得有可能對(duì)系統(tǒng)里的事件所需要的時(shí)間進(jìn)行描述。COA具有的大量的作戰(zhàn)任務(wù)，給定的作戰(zhàn)資源、同步化約束及任

5、務(wù)間的復(fù)雜關(guān)系使得COA的開(kāi)發(fā)十分復(fù)雜，而CPN的上述特性決定了其適用于對(duì)COA的建模與開(kāi)發(fā)［4］。在第一階段的基礎(chǔ)上執(zhí)行寬度優(yōu)先搜索。寬度優(yōu)先搜索也用到了三個(gè)結(jié)構(gòu)：Visited保存己訪問(wèn)狀態(tài)的軌跡；LOP用來(lái)關(guān)聯(lián)狀態(tài)和從初始狀態(tài)到達(dá)該狀態(tài)所有的可能路徑，這些路徑用LOPs表示；Queue存儲(chǔ)寬度優(yōu)先搜索遍歷隊(duì)列。調(diào)用此算法時(shí)，初始狀態(tài)插入到該隊(duì)列中，算法通過(guò)選擇隊(duì)列中的狀態(tài)s來(lái)獲得狀態(tài)s的lops。但是，隨著作戰(zhàn)任務(wù)數(shù)量的增加，模型執(zhí)行的可選方式也在增加，導(dǎo)致模型的狀態(tài)空間成指數(shù)級(jí)增長(zhǎng)，例如：在時(shí)刻t有

6、n個(gè)具備開(kāi)始條件的作戰(zhàn)任務(wù)，那么就有2n個(gè)作戰(zhàn)任務(wù)執(zhí)行方式，這將帶來(lái)模型的狀態(tài)空間爆炸問(wèn)題。該文目的是對(duì)兩階段算法進(jìn)行改進(jìn)，采用反向路徑搜索算法替代寬度優(yōu)先搜索算法緩解COA開(kāi)發(fā)的模型狀態(tài)空間爆炸問(wèn)題。改進(jìn)的兩階段算法兩階段算法中的深度優(yōu)先搜索算法能快速產(chǎn)生部分完整的及不完整的LOPs。雖然作戰(zhàn)任務(wù)之間存在復(fù)雜的約束關(guān)系，通常情況下，作戰(zhàn)任務(wù)清單中包括一個(gè)確定的最終任務(wù)，這個(gè)任務(wù)的執(zhí)行將到達(dá)理想的最終狀態(tài)，例如：兩棲登陸作戰(zhàn)計(jì)劃，其中兩棲登陸這個(gè)任務(wù)可以看作是作戰(zhàn)任務(wù)清單中的最終作戰(zhàn)任務(wù)，在一定程度上，其他

7、的所有作戰(zhàn)任務(wù)都是為這個(gè)最終的作戰(zhàn)任務(wù)的執(zhí)行提供開(kāi)始條件的。當(dāng)作戰(zhàn)計(jì)劃參謀人員開(kāi)發(fā)的作戰(zhàn)任務(wù)清單中不存在作戰(zhàn)任務(wù)冗余時(shí)，一個(gè)COA的CPN模型狀態(tài)空間最多只有一個(gè)理想的最終狀態(tài)。由于作戰(zhàn)任務(wù)之間緊密的約束關(guān)系，即使存在作戰(zhàn)任務(wù)冗余，理想的最終狀態(tài)的個(gè)數(shù)相比于可達(dá)狀態(tài)集也是占很小的比例。對(duì)于COA開(kāi)發(fā)問(wèn)題，作戰(zhàn)計(jì)劃參謀人員需要的是完整的LOPs,因此可以考慮在兩階段算法中，用反向路徑搜索算法取代寬度優(yōu)先搜索算法，即從理想的最終狀態(tài)節(jié)點(diǎn)由下往上搜索，由子節(jié)點(diǎn)找到父節(jié)點(diǎn)，最后到達(dá)模型的初始狀態(tài)。反向路徑搜索算法同

8、寬度優(yōu)先搜索算法相似，采用三個(gè)數(shù)據(jù)結(jié)構(gòu)。Visited保存已訪問(wèn)狀態(tài)的軌跡，LOP用來(lái)關(guān)聯(lián)狀態(tài)和該狀態(tài)到達(dá)理想的最終狀態(tài)的所有可能路徑，這些路徑用lops來(lái)表示，Queue存儲(chǔ)寬度優(yōu)先搜索遍歷隊(duì)列算法通過(guò)選擇隊(duì)列中的狀態(tài)s來(lái)獲得狀態(tài)s的lops。與寬度優(yōu)先搜索不同的是當(dāng)調(diào)用此算法時(shí)，將理想的最終狀態(tài)插入到該隊(duì)列中。