基于與或圖的啟發(fā)式復雜決策任務求解方法

摘 要：現(xiàn)代戰(zhàn)爭的快速性，要求計算機輔助決策系統(tǒng)能夠支持指揮員快速形成有效決策計劃，以實現(xiàn)戰(zhàn)場指揮中任務逐級規(guī)劃、執(zhí)行的高效性。圖搜索法是智能決策系統(tǒng)中問題規(guī)劃的重要方法，可有效支持決策支持系統(tǒng)（DSS）完成有效任務分解。本文提出一種基于與或圖的啟發(fā)式?jīng)Q策求解方法，并通過擴展與、或連接符支持任務分解，所定義構造算子保障與或解圖的可執(zhí)行性，可有效支持復雜決策任務求解和執(zhí)行，并通過一個火力打擊決策任務案例驗證本方法的有效性。

關鍵詞：任務分解；復雜決策；與或圖；啟發(fā)式；可執(zhí)行任務流

中圖分類號：TP311.5 文獻標識碼：A

1 引言（Introduction）

現(xiàn)代作戰(zhàn)的高速度、快節(jié)奏，需要實現(xiàn)快速的決策。傳統(tǒng)的機械化地方作戰(zhàn)通常是任務式指揮法，逐級賦予任務計劃。通常在一個火力打擊決策中，需要明確具體打擊目標、區(qū)分打擊任務、確定打擊順序、打擊效果評估等，是一個“偵、策、打、評”的不斷反復的過程，尤其要求總指揮部具有更快的組織計劃反應能力和決策能力。決策時間越短，越能有效占領戰(zhàn)場優(yōu)勢，而借助計算機的智能決策輔助，可快速形成有效的決策計劃，使己方的決策周期始終快于敵方的決策周期，掌握戰(zhàn)場的主動權[1]。

決策支持系統(tǒng)（DSS）是基于計算機的交互式系統(tǒng)，用以幫助決策者使用數(shù)據(jù)和模型去解決結構化較差的問題。決策科學和決策支持科學發(fā)展至今，研究者和實踐家們在各自的領域提出了大量的決策模型[2]。根據(jù)不同的應用領域和任務性質(zhì)，利用Decision Support System（DSS）進行復雜決策任務。目前有關任務分解方法的主要研究包括[3]：文獻[4]借助項目工作分解結構技術，從任務靜、動態(tài)結構兩方面描述作戰(zhàn)任務的分解概念，并舉例建立了任務的分解結構和流程結構；文獻[5]在文獻[6—8]的研究基礎上，提出一種按照基于活動約束的任務粒度設計方法，以得到最佳的任務分解模型，文中的粒度是靜態(tài)的，即最優(yōu)設計；另外還有利用過程網(wǎng)[9]和時序邏輯公式[10]等有關任務分解及描述分解所得子任務之間關系的方法。這些研究從不同角度和層面給出子任務分解和描述方法，但多數(shù)方法僅從宏觀理論上給出了相關定義和說明，較難直接應用于實際計算機輔助手段中，而基于自動組合的直接搜索法可有效解決此類問題。直接搜索法是根據(jù)具體應用的需求將任務求解問題表示為特定問題狀態(tài)空間，相當于是實現(xiàn)了一個特定用途的規(guī)劃器，然后選擇適合的搜索算法直接搜索目標狀態(tài)，在搜索過程中生成模型組裝方案[3]。目前，采用直接搜索法進行自動組合的方法有很多種，如文獻[11—13]將其應用于服務自動組合中，該方法被認為是目前最為有效的自動組合方法之一。如文獻[14]中所述，在傳統(tǒng)的人工智能中，與或圖搜索是處理空間搜索問題的一個重要的工具，且具有形式化表示簡單、實施容易的特點。因此，本文提出一種基于與或圖[15]的復雜決策任務求解方法，此方法將決策任務分解為更小的子任務、原子任務，并通過與、或等構造算子支持決策模型有效組裝，并使用啟發(fā)式算法搜索以找到最優(yōu)、無矛盾解圖，設計執(zhí)行構造子等支持解圖到執(zhí)行工作流的轉換，以及基于啟發(fā)式函數(shù)的與或圖搜索支持有效的任務分解以及優(yōu)化選擇。

本文以下內(nèi)容首先講述任務決策原則，以支持有效啟發(fā)式任務分解；其次，給出相應的執(zhí)行構造子定義，以支持與或圖任務到可執(zhí)行工作流的轉換；然后給出基于與或圖的啟發(fā)式?jīng)Q策任務分解方法，并給出決策任務分集算法執(zhí)行步驟；最后通過一個案例進行證明。

2 火力打擊的決策原則（Decision principle of fire

against）

任務的定義具有兩層含義：首先任務的本質(zhì)是工作，即一組實際的行動，任務的實施者執(zhí)行這些行動以完成任務；其次任務必須有特定目標，沒有目標的行為不能稱為任務。任務規(guī)劃過程是通過任務分解和解決威脅（或沖突）來進行的?；镜囊?guī)劃步驟是遞歸地將任務網(wǎng)絡中的復合任務分解成越來越?。戳６仍絹碓郊殻┑淖尤蝿?，并在分解過程中進行檢查和解決，直到出現(xiàn)那些可以直接執(zhí)行規(guī)劃動作就能完成的原子任務為止[16]。

火力分配是在軍事指揮中常見的決策任務之一，指用彈炮結合系統(tǒng)抗擊多個敵方目標時，合理進行火力分配以有效打擊目標，消除敵方威脅。目標分配原則使火力單元對目標的毀傷效能達到最大（或者某種目標效果，如干擾），并且已方人員和裝備發(fā)揮諸火力單元的整體協(xié)調(diào)優(yōu)勢，尋求對敵方最大的打擊效果并最大限度地降低已方部隊消耗。在此原則下，目標的最優(yōu)分配應該考慮以下幾點：（1）武器單位特點，包括武器系統(tǒng)類別（如防空導彈）、型號、數(shù)量、位置、對各種目標的毀傷效能以及彈藥用量等。（2）目標特點，主要有目標的類型、數(shù)量、運動特征、價值、威脅程度、易損性以及目標的集合特性等。（3）最優(yōu)準則，對目標的毀傷程度要大、所用的武器單元數(shù)目和彈藥的消耗要小等[17]。

3 基于與或圖的啟發(fā)式任務決策（Heuristic task

decision based on And/Or graph）

任務規(guī)劃可以很方便地使用一個與或圖結構來表示，主要包含兩類節(jié)點類型：（1）與節(jié)點，將單個問題變?yōu)槎鄠€子問題組成的結合，這是所有當所有子問題都有解時，則該父輩節(jié)點有解。（2）或節(jié)點，幾個方法同時適用于同一問題，從而產(chǎn)生不同的后繼問題節(jié)點，此時當其中任意子問題節(jié)點有解時，其父輩節(jié)點問題可解。

任務規(guī)劃問題可規(guī)約描述為一個與或圖的分解過程，原始任務目標對應于起始節(jié)點（根節(jié)點），任務分解方案所對應的節(jié)點成為葉節(jié)點（已存在的可解子任務集）。在與或圖上執(zhí)行搜索過程，相當于完成任務由復雜任務逐級細化到子任務、原子任務的過程。值得注意的是，此過程的目標在于表示起始節(jié)點是有解的，即搜索的過程是尋找一個解圖。

在搜索解圖的過程中，需要進行節(jié)點耗散值的計算。設節(jié)點連接符的耗散值規(guī)定為：k-連接符的耗散值=k，則解圖的耗散值記為k（n，N），則可以遞歸計算如下[18]：

a：若n是N的一個元素，則k（n，N）=0；

b：若n有一個外向連接符指向后繼節(jié)點（n1，n2，...，nk），并設該連接符的耗散值為Cn，則：

K（n，N）=Cn+k（n1，N1）+......+k（ni，Ni）

具有最小耗散值的解圖為最佳解圖。本文討論使用評價函數(shù)支持與或圖的啟發(fā)式搜索，實現(xiàn)復雜決策任務的有效解獲取。

搜索過程中需要標記能解節(jié)點（SOLVED），為此需要給出如下定義[18]：

（1）能解節(jié)點（SOLVED）

a：終結點是能解節(jié)點。

b：若非終結點，有“或”子節(jié)點時，當且僅當其子節(jié)點中至少一個能解，該非終結點才能解。

c：若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解，該非終結點才能解。

（2）不能解節(jié)點（UNSOLVED）

a：沒有后裔的非終結點是不能解節(jié)點。

b：若非終結點有“或”子節(jié)點時，當且僅當所有子節(jié)點均不能解時，該非終結點才不能解。

c：若非終結點有“與”子節(jié)點時，當至少有一子節(jié)點不能解時，該非終結點才不能解。

4 使用與或圖的決策任務分解（Task decomposition

by And/Or graph）

規(guī)劃過程是通過任務分解和解決威脅（或沖突）來進行的。本章將擴展與或圖連接符類型以支持所形成任務分解圖的可執(zhí)行性，并解釋如何采用基于與或圖的啟發(fā)式函數(shù)進行高效的任務規(guī)劃。

4.1 執(zhí)行構造子

經(jīng)典與或圖中僅包含與、或節(jié)點兩種類型，對于與或圖的可執(zhí)行力描述不足。因此，本文參照當前規(guī)劃組合的執(zhí)行集合：Sequence，Unordered，Choice，Switch，If-Then，Split and Split+Join[19]，擴展定義了四種類型的可執(zhí)行節(jié)點：AND節(jié)點，OR節(jié)點，SEQUENCE-AND節(jié)點，SWITCH-OR節(jié)點。其中，AND節(jié)點和OR節(jié)點的定義與前面與或圖中的定義一樣。SEQUENCE-AND節(jié)點是AND節(jié)點的一種，使用 表示。SWITCH-OR節(jié)點是OR節(jié)點的一種，使用 表示。每一個執(zhí)行節(jié)點代表一種執(zhí)行步驟，其具體的含義如下[20]：

（1）AND節(jié)點表示Split執(zhí)行，即從左到右順序執(zhí)行。邊表示滿足所需的輸入集是其它任務輸出集的子集。

（2）SEQUENCE-AND節(jié)點表示Split+Join執(zhí)行。

（3）OR節(jié)點表示Choice執(zhí)行。OR節(jié)點的子節(jié)點從左到右是同等的[21]。

（4）SWITCH-OR節(jié)點表示Switch執(zhí)行，表示只能選擇一個子節(jié)點。

（5）路徑表示自下而上序列Sequence執(zhí)行。

（6）不同的路徑默認表示無序，除非遇到SEQUENCE-AND節(jié)點。

（7）圖的邊表示If-Then條件執(zhí)行，即所需的輸入集是其它任務的輸出集的子集。當輸出為空時為空（NULL）時，執(zhí)行器將停止。

執(zhí)行節(jié)點與對應的執(zhí)行集合組合的執(zhí)行結構如圖1所示。

圖1 執(zhí)行結構

Fig.1 Execute structure

4.2 基于與或圖的啟發(fā)式任務規(guī)劃

定義由原子任務和組合任務構成的狀態(tài)空間，包括開始狀態(tài)、目標狀態(tài)和推理規(guī)則（組合操作）。決策任務分解圖搜索過程如下[20]：

開始狀態(tài)：

a.一系列具有不同狀態(tài)空間的決策任務作為本地可用節(jié)點。

b.一個單一的START節(jié)點，包含任務的輸出，代表用戶需求。

c.一系列有限TERMINAL節(jié)點，包含任務的輸入，代表目前可用的用戶輸入。

結果：一個優(yōu)化的組合任務圖作為解。

任務分解：

決策任務分解算法執(zhí)行以下步驟，完成啟發(fā)式搜索與轉換為可執(zhí)行工作流：

（1）本文給出的任務分解算法如下：

a.自上而下的擴展操作以尋找潛在解圖，此過程可包括基于有向邊的可連接性和相似性進行權重評價，直到任務的輸入是一個存在TERMINAL節(jié)點的子集。如果權重值低于某特定值或節(jié)點是NONTERMINAL節(jié)點，則此節(jié)點應不被擴展。

b.自下而上的成本（路徑權重）修改操作，從而更新節(jié)點的權重值，以找到具有低成本的最優(yōu)解圖。

（2）轉換可執(zhí)行工作流：一個搜索狀態(tài)代表了一系列可執(zhí)行步驟，此步驟從TERMINAL節(jié)點開始到START節(jié)點并滿足決策模型組裝要求。從解圖轉換到可執(zhí)行工作流的執(zhí)行主要依據(jù)上節(jié)給出的構造子的執(zhí)行定義。

啟發(fā)式任務規(guī)劃利用所處理問題的啟發(fā)信息引導規(guī)劃，因此需給出相應的評價函數(shù)。利用啟發(fā)信息定義一個評價函數(shù)f對待擴展的節(jié)點計算，可表述為f（n）=g（n）+h（n），表示即考慮起始節(jié)點到節(jié)點n的消耗，也考慮從節(jié)點n到達目標的消耗，利用此評價函數(shù)可完成節(jié)點優(yōu)先擴展的選擇。啟發(fā)式函數(shù)的啟發(fā)能力越強，規(guī)劃效果越好，規(guī)劃效率也越高。在火力決策等任務規(guī)劃過程中，啟發(fā)式函數(shù)可通過第一章中考慮的目標分配影響因素進行評價，如武器系統(tǒng)數(shù)量、目標易損程度、目標的毀傷程度和彈藥消耗等，以決定擴展節(jié)點的消耗值。

參照啟發(fā)式函數(shù)給出的消耗值，基于本文給出的啟發(fā)式搜索算法進行任務規(guī)劃的步驟截圖，圖2給出一個具體的例子。A表示了當前任務分解的START節(jié)點，它可由（B與E）組合任務，或F、或H三個子任務完成?？山馊蝿占癁楫斍翱捎萌蝿?，包括D1、D2、G2、H等以一些列原子任務。通過對三個子任務的計算，發(fā)現(xiàn)第一個子任務的耗散值最小，因此優(yōu)先擴展B節(jié)點至C、D1、D2子節(jié)點，并同步依據(jù)子節(jié)點的耗散值反向修改父節(jié)點的耗散值，以判定下一步擴展指針的方向。最終將形成由（D1，D2，E，G1，G2）組成的TERMINAL節(jié)點。此過程反復進行，通過不斷的自上到下的評價函數(shù)計算以及自下到上的消耗值計算，判定優(yōu)先擴展節(jié)點，以進一步執(zhí)行節(jié)點搜索分解。在分解過程中，參照解節(jié)點（SOLVED）和不解節(jié)點（UNSOLVED）的定義進行節(jié)點標記，當某節(jié)點被標記為不能解節(jié)點時，則將其從與或圖中刪除。

圖2 啟發(fā)式任務決策

Fig.2 A heuristic task decision

5 火力打擊決策任務分解（Task decomposition of

fire fighting）

我們以一個戰(zhàn)術級聯(lián)合火力打擊的情景作為例子。具體情景表現(xiàn)為：一個連執(zhí)行戰(zhàn)備任務時發(fā)現(xiàn)不明入侵物體并快速啟動火力打擊任務決策規(guī)劃程序，要求在明確具體打擊目標的基礎上，進行區(qū)分打擊任務、確定打擊順序、打擊效果評估等過程規(guī)劃。由于連級任務規(guī)劃需要將任務具體下發(fā)到營級打擊任務，因此必須滿足：首先，明確目標類型，獲取目標軌跡信息；其次，將任務分解到具體營級任務；然后，由于營級火力打擊任務由各武器系統(tǒng)（近、遠程）聯(lián)合執(zhí)行打擊任務，因此需要將其分解到具體武器系統(tǒng)打擊子任務，如近程防御系統(tǒng)準備；而后，武器系統(tǒng)打擊任務將由具體的計算彈道條件等原子任務組成；最后，通過調(diào)用彈藥消耗量等進行綜合評價。同時，還存在用戶交互需求，如指揮員依據(jù)戰(zhàn)斗經(jīng)驗進行武器系統(tǒng)選擇。本節(jié)將通過以上聯(lián)合火力打擊任務為例對任務分解的自動構建和可執(zhí)行任務工作流轉換進行實驗，如圖3所示。

開始狀態(tài)：

（1）連級火力打擊所需輸出，即武器系統(tǒng)打擊結果，成功或失敗。

（2）連級火力打擊的已知輸入，即某不明飛行物體位置信息。

（3）一個USER PREFERENCE任務節(jié)點，輸入為武器列表，輸出為一個武器系統(tǒng)編號。

搜索結果：一個解圖，如圖3所示。

圖3 連級聯(lián)合火力打擊任務工作流

Fig.3 The task workflow of company joint

firepower strike

規(guī)劃執(zhí)行：

（1）首先，規(guī)劃器發(fā)現(xiàn)為不存在可直接使用的連火力打擊的任務，因此進行任務分解。

（2）規(guī)劃器擴展START節(jié)點到一營武器系統(tǒng)打擊節(jié)點和二營武器系統(tǒng)打擊節(jié)點，并標記START節(jié)點為OR節(jié)點。

（3）規(guī)劃器擴展一營武器系統(tǒng)打擊節(jié)點到遠程打擊系統(tǒng)A和近程打擊系統(tǒng)A節(jié)點，并標記一營武器系統(tǒng)打擊節(jié)點為Sequence-And節(jié)點，其中近程打擊系統(tǒng)啟動條件為遠程打擊系統(tǒng)的執(zhí)行結果。

（4）規(guī)劃器擴展二營武器系統(tǒng)打擊節(jié)點到近程打擊系統(tǒng)B節(jié)點，由于近程打擊系統(tǒng)啟動條件為遠程打擊系統(tǒng)的執(zhí)行結果，因此修改START節(jié)點為Sequence-And節(jié)點。

（5）規(guī)劃器擴展所有系統(tǒng)節(jié)點到初始條件，即輸入飛行物位置。

聯(lián)合火力打擊任務是一個滿足決策任務要求的任務集的工作流。執(zhí)行程序由具體的輸入值激活。執(zhí)行步驟如下：遠程打擊系統(tǒng)A得到打擊目標-不明飛行物位置并輸出打擊結果。同時近程打擊系統(tǒng)A獲得飛行物位置并以SEQUENCE-AND節(jié)點模式等待遠程打擊系統(tǒng)A執(zhí)行結果的喚醒，并返回結果到一營武器系統(tǒng)打擊任務節(jié)點。同時，執(zhí)行器收集各任務的輸出，包括遠程打擊結果并激活了近程打擊系統(tǒng)B節(jié)點。最終給出相應的打擊結果，執(zhí)行完畢。

6 結論（Conclusion）

與或圖搜索技術可以用于處理復雜決策任務分解問題，它支持將任務分解成較小的與、或子任務直到所有的任務是

可解的，對應任務由下一層子任務或原子任務組成。執(zhí)行此操作過程的空間搜索得到一個使初始狀態(tài)滿足的解圖，并根據(jù)其生成一個可執(zhí)行線性工作流。本文給出一個決策任務求解方法，解決了決策方案自動產(chǎn)生問題，可有效降低決策計劃制定時間，但有關多個決策方案綜合比較、決策者個人偏好、影響、決策經(jīng)驗等對于整個決策過程也有很大的影響，需要進一步加強研究。此外，有關將決策任務與領域本體結合，以實現(xiàn)更智能的決策推理過程等體系，有待進一步研究。

參考文獻（References）

[1] 李策.陸軍合同作戰(zhàn)指揮決策過程建模[J].計算機仿真，2009， 24（7）：163-169.

[2] 吳昕晟，蕭毅鴻.基于方案本體的決策模型組裝[J].計算機與 現(xiàn)代化，2009，12：249-253.

[3] 蕭毅鴻.基于本體的復雜決策任務表示方法與求解技術研究 [D].南京大學，2007.

[4] 曹裕華，馮書興，徐雪峰.作戰(zhàn)任務分解的概念表示方法研究 [J].計算機仿真，2007，24（8）：1-4.

[5] 龐輝，方宗德.網(wǎng)絡化協(xié)作任務分解策略和粒度設計[J].計算 機集成制造系統(tǒng)，2008，14（3）：425-430.

[6] VANDE，SALOMONM.Production plaxining and inventory control with remanufacturing and disposal[J].European Journal of Operational Research，1997，102（2）：264-278.

[7] 鄧家提.產(chǎn)品設計的基本理論與技術[J].中國機械工程，2000， 11（1/2）：139-143.

[8] CHENSJ，LINL.Decoma position of inter dependent task group for eon current engineering[J].Computer & Industrial engineering.2003， 44（3）：435-459.

[9] 劉秀羅.建模相關技術及其在指揮控制建模中的應用研究 [D].國防科技大學，2001.

[10] 曹裕華.面向實體的作戰(zhàn)建模方法[D].軍事科學院，200

[11] Lecue F，Leger A.A Formal Model for Semantic Web Service Composition[C].In：Proceedings of the 5th International Semantic Web Conference.Springer，LNCS 4273，2006：385-398.

[12] 鄧水光，等.基于回溯樹的web服務自動組合[J].軟件學報， 2007，18（8）：189-1910.

[13] 溫嘉佳，陳俊亮，彭泳.基于目標距離評估的啟發(fā)式WebServiees 組合算法[J].軟件學報，2007，18（l）：85-93.

[14] Xining Li，Wei Fan.An object-oriented And/Or graph inference engine Electrical and Computer Engineering. Canadian Conference on 14-17 Sept.1993.

[15] Ching-Fang Liaw，etc.Multiobjective Heuristic Search in AND/OR Grapes. Proceeding of IEEE transactions on systems，man，and cybernetics，vol.25， November 1995.

[16] 蕭毅鴻，周獻中，張鐵.擴展層級任務網(wǎng)絡規(guī)劃的變粒度作戰(zhàn) 任務分解策略[J].火力與指揮控制，2011，7（4）：119-122.

[17] 王小藝，等.防空武器多目標優(yōu)化分配建模與決策[J].兵工學 報，2007，28（2）：228-231.

[18] 林堯瑞，馬少平.人工智能導論[M].北京：清華大學出版社， 2002：158-160.

[19] Evren Sirin，ect. HTN planning for web service composition using SHOP2 [J].Journal of Web Semantics， 2004， 1（4）：377-396.

[20] 賈慧彤.面向偏差問題的語義Web服務 [D].北京工業(yè)大學計 算機系，2009.

[21] Milanovic N，Malek M.Architectural support for automatic service composition[C].In：Proceeding of the IEEE International Conference.On Service computing （SCC 2005）.

Orlando：IEEE，2005，133-140.

作者簡介：

賈慧彤（1982-），女，碩士，工程師.研究領域：人工智能，

決策分析.