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

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

關鍵詞：任務分解；復雜決策；與或圖；啟發式；可執行任務流

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

1 引言（Introduction）

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

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

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

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

against）

任務的定義具有兩層含義：首先任務的本質是工作，即一組實際的行動，任務的實施者執行這些行動以完成任務；其次任務必須有特定目標，沒有目標的行為不能稱為任務。任務規劃過程是通過任務分解和解決威脅（或沖突）來進行的。基本的規劃步驟是遞歸地將任務網絡中的復合任務分解成越來越小（即粒度越來越細）的子任務，并在分解過程中進行檢查和解決，直到出現那些可以直接執行規劃動作就能完成的原子任務為止[16]。

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

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

decision based on And/Or graph）

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

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

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

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

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

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

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

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

（1）能解節點（SOLVED）

a：終結點是能解節點。

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

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

（2）不能解節點（UNSOLVED）

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

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

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

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

by And/Or graph）

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

4.1 執行構造子

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

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

（2）SEQUENCE-AND節點表示Split+Join執行。

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

（4）SWITCH-OR節點表示Switch執行，表示只能選擇一個子節點。

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

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

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

執行節點與對應的執行集合組合的執行結構如圖1所示。

圖1 執行結構

Fig.1 Execute structure

4.2 基于與或圖的啟發式任務規劃

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

開始狀態：

a.一系列具有不同狀態空間的決策任務作為本地可用節點。

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

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

結果：一個優化的組合任務圖作為解。

任務分解：

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

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

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

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

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

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

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

圖2 啟發式任務決策

Fig.2 A heuristic task decision

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

fire fighting）

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

開始狀態：

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

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

（3）一個USER PREFERENCE任務節點，輸入為武器列表，輸出為一個武器系統編號。

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

圖3 連級聯合火力打擊任務工作流

Fig.3 The task workflow of company joint

firepower strike

規劃執行：

（1）首先，規劃器發現為不存在可直接使用的連火力打擊的任務，因此進行任務分解。

（2）規劃器擴展START節點到一營武器系統打擊節點和二營武器系統打擊節點，并標記START節點為OR節點。

（3）規劃器擴展一營武器系統打擊節點到遠程打擊系統A和近程打擊系統A節點，并標記一營武器系統打擊節點為Sequence-And節點，其中近程打擊系統啟動條件為遠程打擊系統的執行結果。

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

（5）規劃器擴展所有系統節點到初始條件，即輸入飛行物位置。

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

6 結論（Conclusion）

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

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

參考文獻（References）

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

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

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

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

[5] 龐輝，方宗德.網絡化協作任務分解策略和粒度設計[J].計算 機集成制造系統，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] 鄧家提.產品設計的基本理論與技術[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] 曹裕華.面向實體的作戰建模方法[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] 溫嘉佳，陳俊亮，彭泳.基于目標距離評估的啟發式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] 蕭毅鴻，周獻中，張鐵.擴展層級任務網絡規劃的變粒度作戰 任務分解策略[J].火力與指揮控制，2011，7（4）：119-122.

[17] 王小藝，等.防空武器多目標優化分配建模與決策[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].北京工業大學計 算機系，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-），女，碩士，工程師.研究領域：人工智能，

決策分析.