復(fù)雜決策任務(wù)層級(jí)分解動(dòng)態(tài)控制策略與算法

黃孝鵬 周獻(xiàn)中

(1.中船重工第七二四研究所 系統(tǒng)總體部，江蘇 南京210003;2.南京大學(xué) 控制與系統(tǒng)工程系，江蘇 南京210093)

1 引言

在復(fù)雜決策任務(wù)求解流程中，對(duì)決策任務(wù)進(jìn)行合理、有序地分解，有助于深入理解問(wèn)題，簡(jiǎn)化問(wèn)題結(jié)構(gòu)，降低全局計(jì)算代價(jià)，實(shí)現(xiàn)快速有效求解。目前，國(guó)內(nèi)外文獻(xiàn)中常見(jiàn)的任務(wù)分解方法主要是針對(duì)工作流意義下的任務(wù)分解，或假定任務(wù)已經(jīng)分解完畢而直接進(jìn)行任務(wù)匹配等［1-4］。在這些從不同角度、層面提出的任務(wù)分解方法中，有的是根據(jù)個(gè)人經(jīng)驗(yàn)、行為偏好、知識(shí)結(jié)構(gòu)、態(tài)勢(shì)感知與理解等由決策者進(jìn)行任務(wù)分解;有的是通過(guò)多智能體(Multi-Agent)、數(shù)學(xué)規(guī)劃、模式識(shí)別等技術(shù)由計(jì)算機(jī)動(dòng)態(tài)、自動(dòng)地進(jìn)行任務(wù)分解。但這些分解方法多為籠統(tǒng)地討論某種分解方法，以求適用于所有的決策問(wèn)題，實(shí)踐中并不全都可行。在實(shí)際應(yīng)用中，針對(duì)結(jié)構(gòu)化決策問(wèn)題，其求解過(guò)程可不需要人的參與，故可實(shí)現(xiàn)其分解過(guò)程的完全自動(dòng)化、程序化;但針對(duì)半(非)結(jié)構(gòu)化決策問(wèn)題，其求解過(guò)程必須要有人的參與，特別是人的感知、判斷、推理、綜合、創(chuàng)造、直覺(jué)等能力的參與，故對(duì)這類決策問(wèn)題的分解不能實(shí)現(xiàn)完全自動(dòng)化、程序化。

針對(duì)決策任務(wù)分解，以任務(wù)求解為驅(qū)動(dòng)，綜合考慮求解主體(參與決策活動(dòng)的人件和計(jì)算機(jī)軟件)的求解能力和決策任務(wù)的結(jié)構(gòu)特征等因素對(duì)決策任務(wù)進(jìn)行層級(jí)分解，可為決策任務(wù)流程規(guī)劃與設(shè)計(jì)提供理論支撐，也是對(duì)傳統(tǒng)決策任務(wù)分解模式提出的新挑戰(zhàn)。

2 基本思想

圖1 決策任務(wù)分解

決策任務(wù)層級(jí)分解的基本思想是綜合考慮決策任務(wù)的結(jié)構(gòu)特征、環(huán)境約束、分解方式、求解主體的求解能力以及子任務(wù)間的聯(lián)系等因素，以任務(wù)求解為驅(qū)動(dòng)把總體任務(wù)細(xì)化成若干具體的、層次清晰明確的、相互獨(dú)立的(同層子任務(wù)間無(wú)直接消息傳遞)、易執(zhí)行的子任務(wù)，且上一層次的子任務(wù)對(duì)下一層次的全部或某些子任務(wù)起著支配作用，最后經(jīng)綜合整理得到一種遞階的樹(shù)狀層級(jí)結(jié)構(gòu)，如圖1所示。這往往也是決策者最想獲得的結(jié)果。

3 相關(guān)概念

3.1 決策任務(wù)分解相關(guān)概念

定義1:決策任務(wù)(Decision Task，DT)。決策任務(wù)是指依據(jù)可實(shí)現(xiàn)的途徑或具體的可實(shí)現(xiàn)方法來(lái)實(shí)現(xiàn)特定決策目標(biāo)所需完成的工作。

為便于研究，把決策任務(wù)的主要特征形式化表示為一個(gè)七元組，即:

其中DId、DN、DG、DC分別表示決策任務(wù)的標(biāo)識(shí)符、名稱、目標(biāo)與環(huán)境約束;DK是決策任務(wù)的知識(shí)集(包括任務(wù)的初始條件和中間結(jié)果)，其中DG也包括完成任務(wù)所必須得到的知識(shí);DA是操作集(接收相應(yīng)的輸入，經(jīng)過(guò)信息處理產(chǎn)生輸出，通過(guò)操作完成任務(wù));DT表示時(shí)間約束，DT=［Ts，Te］，Ts≤Te，以滿足快速(敏捷)決策的時(shí)間要求。

定義2:子任務(wù)(Subtask，ST)。子任務(wù)是由決策任務(wù)按某種規(guī)則(時(shí)間屬性、空間屬性、主體屬性和客體屬性等)分解后得到的任務(wù)序列。所有子任務(wù)操作集的輸出并集必須覆蓋目標(biāo)集且不同的子任務(wù)間是獨(dú)立的，即:STi={STi|STi=DT，Ordi}(其中Ordi為子任務(wù)間的與、或、循環(huán)等次序)，且STi∩STj≠?(i≠j)?？尚问交枋鰹?

其中STId，STN，STG，STC，STK，STA，STT分別表示子任務(wù)STi的標(biāo)識(shí)符、名稱、目標(biāo)、環(huán)境約束、知識(shí)集、操作集和時(shí)間約束。

定義3:任務(wù)分解(Task Decomposition，TD)。對(duì)于決策任務(wù)DT，若?DT'={ST'1，ST'2，…，ST'n}，為DT在某特定規(guī)則作用下的一個(gè)覆蓋;若?DT'=ST'i}=DT，則稱DT'為DT在某特定規(guī)則作用下的一個(gè)任務(wù)分解。當(dāng)然，分解后得到的子任務(wù)集應(yīng)具備完整性、獨(dú)立性、可解性、協(xié)調(diào)性等特性。

3.2 人件相關(guān)概念

定義4:人件(Humanware，Hw)。人件是指參與決策活動(dòng)的人。它可以是最終的決策者，也可以是在決策任務(wù)求解過(guò)程中提供信息支持、功能支持或算法支持的各類人員［5］。

“人件”是從決策角度出發(fā)研究參與決策活動(dòng)的人，是相對(duì)于承擔(dān)決策任務(wù)求解功能的軟件而提出的概念，也是針對(duì)新型決策系統(tǒng)中人機(jī)高效協(xié)作問(wèn)題所提出的概念。

定義5:人件服務(wù)(Humanware Service，HwS)。人件作為決策系統(tǒng)組成要素時(shí)，其特定功能(如決策功能等)的網(wǎng)絡(luò)賦能形態(tài)就是人件服務(wù)。其形式化描述如下:

其 中，Id，Name，Category，F(xiàn)unction，Inputs，Outputs，QoS分別為人件服務(wù)的標(biāo)識(shí)、名稱、類別、功能描述、輸入、輸出、服務(wù)質(zhì)量。

同理，軟件服務(wù)(Software Service，SwS)可形式化描述為:

當(dāng)然，軟件服務(wù)SwSi和人件服務(wù)HwSj之間是可組態(tài)的，其服務(wù)組合CSk的基本控制結(jié)構(gòu)有串行、并行、選擇及循環(huán)等四種。針對(duì)某子任務(wù)求解，在服務(wù)調(diào)用選擇時(shí)先調(diào)用SwS，經(jīng)判斷，如不能達(dá)到使命任務(wù)求解的目標(biāo)，再調(diào)用高級(jí)服務(wù)HwS。若針對(duì)某粗粒度的子任務(wù)，也可能會(huì)將HwS和SwS兩者進(jìn)行組合封裝，然后調(diào)用。

4 原則與目標(biāo)

4.1 原則

根據(jù)決策任務(wù)的自身結(jié)構(gòu)與特征、環(huán)境、人件服務(wù)與軟件服務(wù)的求解能力，提出以下任務(wù)分解原則:①層次性，指決策任務(wù)先可劃分為若干子任務(wù)，子任務(wù)按其結(jié)構(gòu)與特征決定是否進(jìn)行再劃分，形成層級(jí)結(jié)構(gòu)，使復(fù)雜決策任務(wù)分解為多個(gè)相對(duì)簡(jiǎn)單的、易于處理的子任務(wù)。②弱耦合，分解后的子任務(wù)間關(guān)聯(lián)度要盡可能小。③組合性，子任務(wù)的適當(dāng)組合能構(gòu)成一個(gè)較粗粒度的任務(wù)。④均衡性，指同層次上的任務(wù)粒度、規(guī)模、求解難易程度要盡量均衡，以避免某一任務(wù)求解開(kāi)銷過(guò)大，導(dǎo)致求解主體任務(wù)負(fù)載量不均衡，影響整體求解效率。

4.2 目標(biāo)

任務(wù)分解的目標(biāo)是按照某種規(guī)則，設(shè)計(jì)一種為實(shí)現(xiàn)決策任務(wù)快速、高效求解且能符合決策者認(rèn)知特征的最佳分解。設(shè)DT按照某種規(guī)則P分解的最終結(jié)果為(ST'1，ST'2，…，ST'n)，若最終子任務(wù)ST'i的分解開(kāi)銷(時(shí)間、成本等)函數(shù)為C(ST'i)(i=1，2，…，n)，則任務(wù)分解的目標(biāo)為在規(guī)則P作用下的總體代價(jià)函數(shù)值最優(yōu)且不超過(guò)限定值C，即:

4.3 相關(guān)定理及規(guī)則

定理1:決策任務(wù)分解后子任務(wù)的解空間也是原決策任務(wù)的解空間。

規(guī)則1:任務(wù)一致化規(guī)則。主要解決在任務(wù)分解過(guò)程中產(chǎn)生的上下級(jí)任務(wù)的不一致和沖突等問(wèn)題，主要包括任務(wù)剪枝規(guī)則、繼承規(guī)則和沖突規(guī)則等。這些規(guī)則都存放在任務(wù)分解庫(kù)中，供創(chuàng)建任務(wù)分解樹(shù)時(shí)提取和使用。

(1)任務(wù)剪枝規(guī)則。主要針對(duì)子任務(wù)間的“或”關(guān)系，根據(jù)公式(1)計(jì)算出每個(gè)分支的開(kāi)銷，保留最小開(kāi)銷分支，去除其他分支并刪除該“或”分支的根節(jié)點(diǎn)以得到最優(yōu)分解，此時(shí)上級(jí)任務(wù)也需添加其沒(méi)有的下級(jí)任務(wù)屬性來(lái)保證一致性。

針對(duì)任務(wù)分解樹(shù)的某個(gè)存在“或”關(guān)系的分支，依據(jù)剪枝規(guī)則，設(shè)計(jì)剪枝算法J如下:

Step1:如子任務(wù)間是“或”關(guān)系;

Step2:計(jì)算各子任務(wù)的求解開(kāi)銷，選出最小求解開(kāi)銷節(jié)點(diǎn);

Step3:刪除其他子任務(wù)節(jié)點(diǎn)，將分支根節(jié)點(diǎn)的標(biāo)號(hào)改為最小求解開(kāi)銷節(jié)點(diǎn)標(biāo)號(hào)，結(jié)束。

(2)任務(wù)沖突規(guī)則。如果下級(jí)任務(wù)和上級(jí)任務(wù)存在屬性沖突，為保持一致性，可以下級(jí)任務(wù)屬性為基礎(chǔ)，約減上級(jí)沖突的任務(wù)屬性(向上沖突消解策略);或以上級(jí)任務(wù)屬性為基礎(chǔ)，約減下級(jí)沖突的任務(wù)屬性(向下沖突消解策略)。

(3)任務(wù)繼承規(guī)則。在構(gòu)造任務(wù)分解樹(shù)的過(guò)程中，新分解的下級(jí)子任務(wù)繼承上級(jí)子任務(wù)的權(quán)限。

4.4 特殊約束

在某特定領(lǐng)域(如軍隊(duì)作戰(zhàn)指揮決策領(lǐng)域等)，針對(duì)某些特定的使命任務(wù)，由于不同參戰(zhàn)單元的作戰(zhàn)業(yè)務(wù)能力是不同的，在進(jìn)行任務(wù)分解時(shí)存在以下兩個(gè)約束，需予以考慮。

規(guī)則2:肯定約束。如:Must_Do(HSi，STj)表示子任務(wù)STj必須由HSi來(lái)執(zhí)行。

規(guī)則3:否定約束。如:Cannot_Do(HSi，STj)表示子任務(wù)STj不能由HSi來(lái)執(zhí)行。

5 策 略

根據(jù)任務(wù)分解的基本思想、概念體系、原則和目標(biāo)、定理及所設(shè)定的相關(guān)規(guī)則等，綜合考慮決策任務(wù)的結(jié)構(gòu)特征、環(huán)境、人件服務(wù)和軟件服務(wù)的求解能力等因素，研究基于人件服務(wù)的復(fù)雜決策任務(wù)層級(jí)分解策略，需有一套充分利用軟件服務(wù)和人件服務(wù)各自優(yōu)勢(shì)的協(xié)同策略，達(dá)到人與計(jì)算機(jī)之間的求解均衡，既不增加人的負(fù)擔(dān)，又可以讓人充分相信整個(gè)決策任務(wù)求解流程的合理性和正確性。

設(shè)定任務(wù)分解需滿足以下條件和約束:①對(duì)任一決策任務(wù)，至少存在一個(gè)對(duì)應(yīng)的任務(wù)分解結(jié)果。②每次只有一個(gè)子任務(wù)參與服務(wù)庫(kù)的匹配。③每個(gè)服務(wù)(包括人件服務(wù)和軟件服務(wù)的服務(wù)組合CSk)每次只參與一個(gè)子任務(wù)的匹配。④服務(wù)庫(kù)里供給的服務(wù)不小于子任務(wù)的服務(wù)需求。為研究方便，設(shè)置任務(wù)分解計(jì)數(shù)器以統(tǒng)計(jì)任務(wù)最終分解結(jié)果的規(guī)模，它包括層數(shù)計(jì)數(shù)器M和最終子任務(wù)個(gè)數(shù)計(jì)數(shù)器N，初始值令M=1，N=1。

5.1 任務(wù)分割點(diǎn)尋求算法

設(shè)決策任務(wù)共有k個(gè)操作，從k個(gè)操作中選出可把任務(wù)初始信息作為輸入信息的操作，組成操作集DA，DA包含的操作數(shù)即任務(wù)分解的可能路徑的個(gè)數(shù)。輸入信息是指初始任務(wù)A、任務(wù)的初始條件和目標(biāo);輸出結(jié)果是指分解的子任務(wù)集、各子任務(wù)的輸入信息和輸出信息。

任務(wù)分割點(diǎn)尋求的啟發(fā)式算法F表示如下:

Step1:設(shè)定初始任務(wù)節(jié)點(diǎn)A，進(jìn)行賦值，轉(zhuǎn)Step2。

Step2:若操作i的輸入信息等于任務(wù)初始信息，k++，轉(zhuǎn)Step3;否則轉(zhuǎn)Step4。

Step3:令A(yù)ctions等于操作i，若當(dāng)前所有信息等于任務(wù)DG的所需全部信息時(shí)，在Actions中尋找一組操作覆蓋任務(wù)目標(biāo)集DG的操作集，得到可行操作集，運(yùn)用剪枝算法J求最優(yōu)，break，轉(zhuǎn)Step4。

Step4:算法停止。

5.2 任務(wù)分解算法

針對(duì)需由軟件服務(wù)、人件服務(wù)、人件服務(wù)與軟件服務(wù)的組合來(lái)完成的復(fù)雜決策任務(wù)，其任務(wù)分解算法A如下:

Step1:設(shè)DT為一個(gè)決策任務(wù)。

Step2:根據(jù)算法F得到DT的初始分解，DT={ST1，ST2，…，STn}，M++。

Step3:從i=1開(kāi)始，判斷STi與軟件服務(wù)庫(kù)中服務(wù)能否匹配，如匹配，則將其存儲(chǔ)到緩沖庫(kù)中，記錄每次匹配成功的子任務(wù)個(gè)數(shù)Ai，N1=ΣAi，1≤i＜n，轉(zhuǎn)Step4;否則轉(zhuǎn)Step5。

Step4:判斷i=n是否成立，如成立，則轉(zhuǎn)Step8;否則i++，轉(zhuǎn)Step3。

Step5:判斷與人件服務(wù)庫(kù)能否相匹配，如匹配，則將其存儲(chǔ)到緩沖庫(kù)中，記錄每次匹配成功的子任務(wù)個(gè)數(shù)Aj，N2=ΣAj，1≤j＜m，轉(zhuǎn)Step4;否則轉(zhuǎn)Step6。

Step6:判斷與人件服務(wù)和軟件服務(wù)的組合服務(wù)能否相匹配，如匹配，則將其存儲(chǔ)到緩沖庫(kù)中，記錄每次匹配成功的子任務(wù)個(gè)數(shù)Ak，N3=ΣAk，1≤k＜q，轉(zhuǎn)Step4;否則轉(zhuǎn)Step7。

Step7:將不能匹配的子任務(wù)，根據(jù)算法F進(jìn)行再分解。令STi={ST'ij}，M++，調(diào)用自身算法A，判斷是否完全匹配成功，如果能完全匹配，轉(zhuǎn)Step4;否則繼續(xù)Step7。當(dāng)某子任務(wù)被執(zhí)行次數(shù)超過(guò)Z(Z為正整數(shù)，可根據(jù)問(wèn)題規(guī)模大小設(shè)定)次時(shí)，需調(diào)整分解策略，繼續(xù)Step7，判斷是否完全匹配成功，如果能完全匹配，轉(zhuǎn)Step4，以避免算法中可能會(huì)出現(xiàn)的“死循環(huán)”。

Step8:任務(wù)分解結(jié)束，將結(jié)果進(jìn)行綜合整理，輸出任務(wù)分解樹(shù)M及N=N1+N2+N3的值。

任務(wù)分解算法流程如圖2所示。

在算法執(zhí)行過(guò)程中，最好的情況是一次分解就能完全匹配，算法復(fù)雜性為O(N);最壞的情況是每個(gè)子任務(wù)均不能和軟件服務(wù)、人件服務(wù)匹配，算法復(fù)雜性為O(M×N)。

圖2 任務(wù)分解算法流程

6 應(yīng)用

以時(shí)敏目標(biāo)(Time Sensitive Target，TST)打擊為背景構(gòu)建應(yīng)用想定，運(yùn)用本文的研究結(jié)果給出某TST打擊的任務(wù)分解，為設(shè)計(jì)TST快速打擊流程提供一種科學(xué)依據(jù)。TST打擊是一項(xiàng)復(fù)雜任務(wù)，可劃分為發(fā)現(xiàn)目標(biāo)、識(shí)別目標(biāo)、跟蹤目標(biāo)、快速制定決策方案、交戰(zhàn)和效果評(píng)估等六個(gè)子任務(wù)，同時(shí)每個(gè)子任務(wù)也是一個(gè)復(fù)合任務(wù)，需要對(duì)其做進(jìn)一步的分解以設(shè)計(jì)TST快速打擊流程。運(yùn)用研究結(jié)果，得到某TST快速打擊的最終任務(wù)分解如圖3所示，其中M=4，N=18，目標(biāo)識(shí)別、確定有效打擊時(shí)間、態(tài)勢(shì)評(píng)估、武器選擇、打擊方案生成、打擊方案預(yù)評(píng)估、確定打擊方案等任務(wù)可由人來(lái)完成。

1 KAIVAN KAMALI，DAN VENTURA，AMULYA GARGA，etc.Geometric task decomposition in a multi-agent environment［J］.Applied Artificial Intelligence，2006，20(5):437-456.

2 DYLAN ALEXANDER SIMON，NATHANIEL DDAW.Neural correlates of forward planning in a spatial decision task in humans［J］.The Journal of Neuroscience，2011，31(14):5526-5539.

3 JIANG CHUNFENG，ZHAO YULAN.Task decomposition and allocation in tactical team based on layered agent［C］//International Conference on Electronic＆Mechanical Engineering and Information Technology(EMEIT)，2011:1942-1944.

4 CHEN JIANPING，YANG YIMIN，WEI LIANG.Research on the approach of task decomposition in soccer robot system［C］//2010 International Conference on Digital Manufacturing＆Automation(ICDMA)，2010:284-289.

5 黃孝鵬，周獻(xiàn)中，楊潔，等.人機(jī)協(xié)同決策系統(tǒng)中人件及人件服務(wù)的概念體系研究［C］//中國(guó)系統(tǒng)工程學(xué)會(huì)第十七屆學(xué)術(shù)年會(huì)，2012.

6 石純一，張偉.基于Agent的計(jì)算［M］.北京:清華大學(xué)出版社，2007.

7 KIM YE HOON，CHO SE HYOUNG，CHOI SEUNG HWAN，etc.Software robot in a PDA for human interaction and seamless service［C］//The 16th IEEE International Conference on Robot＆Human Interactive Communication，2007:968-973.

8 AGRAWAL A，AMEND M，DAS M，etc.W S-BPEL extension for people version 1.0［EB/OL］.(2007)［2010-04-10］.http://www.ibm.com/developer works/web services/library/specification/ws-bpel4people.

9 黃孝鵬，周獻(xiàn)中，田衛(wèi)萍.基于人件服務(wù)的人機(jī)協(xié)同決策系統(tǒng)有關(guān)問(wèn)題研究［C］//第三屆C4ISR技術(shù)論壇，2011.

10 黃孝鵬，周獻(xiàn)中，陸曉明，等.從“以人為本”角度理解和認(rèn)識(shí)決策系統(tǒng)演化趨勢(shì)——兼談人機(jī)協(xié)同決策系統(tǒng)的構(gòu)建［J］.系統(tǒng)科學(xué)學(xué)報(bào)，2013(1):35-39.

11 曾廣平，涂序彥，王洪泊.“軟件人”研究及應(yīng)用［M］.北京:科學(xué)出版社，2007.