基于概率推理的不確定性任務(wù)分配評價方法

賀毅輝,潘明聰,2,徐 偉,彭 輝

(1.解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院,南京210007;2.南京陸軍指揮學(xué)院作戰(zhàn)實驗中心,南京210045)

基于概率推理的不確定性任務(wù)分配評價方法

賀毅輝1,潘明聰1,2,徐 偉1,彭 輝1

(1.解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院,南京210007;2.南京陸軍指揮學(xué)院作戰(zhàn)實驗中心,南京210045)

作戰(zhàn)任務(wù)的分解與分配是指揮決策中的重要過程,隨著戰(zhàn)場環(huán)境復(fù)雜度的增加,確定環(huán)境下的任務(wù)分配方法已不能適應(yīng)作戰(zhàn)需求。針對不確定性任務(wù)分配問題,分析作戰(zhàn)任務(wù)分解、分配和執(zhí)行過程中的多種不確定性因素,給出相應(yīng)的形式化描述。在此基礎(chǔ)上,提出一種基于概率推理的適應(yīng)度計算方法,具體分析各種不確定性任務(wù)成功執(zhí)行概率的計算過程,并給出算例進行驗證。仿真結(jié)果表明,該方法能有效解決任務(wù)分配問題,并對任務(wù)分配方案進行定量評價。

不確定性;形式化描述;任務(wù)分配;概率推理;適應(yīng)度

1 概述

作戰(zhàn)任務(wù)的分解、分配與執(zhí)行是作戰(zhàn)指揮的重要過程,尤其是在戰(zhàn)場信息化提高、環(huán)境復(fù)雜度增加以及參與作戰(zhàn)的人員與設(shè)備多樣化的現(xiàn)代戰(zhàn)場情況下。這樣的現(xiàn)狀就要求指揮員能夠?qū)ψ鲬?zhàn)任務(wù)進行合理的分解、重組、排序和分配,以此確定何種執(zhí)行體或人員在何時與何地開始何種任務(wù),從而達到順利完成作戰(zhàn)任務(wù)的目的。目前,國內(nèi)外針對任務(wù)分配問題提出了許多方法,文獻[1]提出了一種分布式的任務(wù)分配方法,用于解決任務(wù)和成員動態(tài)變化時的任務(wù)分配問題,但沒有考慮任務(wù)和智能體Agent發(fā)生變化時帶來的不確定性問題;文獻[2]用決策論方法來解決特殊環(huán)境中的任務(wù)分配問題,文中作者假定所有Agent具有相同的能力,且任務(wù)分配和執(zhí)行過程中Agent能力不會發(fā)生變換;文獻[3-4]提出了在動態(tài)環(huán)境下基于智能體能力的任務(wù)分配方法,雖然方法能夠適應(yīng)動態(tài)環(huán)境下的任務(wù)分配,但沒有充分考慮任務(wù)分配過程中其他的不確定性。國內(nèi)學(xué)者研究的任務(wù)分配方法,主要有如匈牙利算法[5]、層次分析法[6]、多屬性決策方法[7]等,但這些方法均是在作戰(zhàn)任務(wù)信息和執(zhí)行人員信息充分的條件下進行的研究[8]。

在實際指揮決策中,任務(wù)分配過程往往存在多種不確定因素,傳統(tǒng)的分配方法已經(jīng)不能適應(yīng)戰(zhàn)場需求。鑒于此,本文利用與或樹描述任務(wù)分解結(jié)構(gòu)以及任務(wù)間的關(guān)系,分析任務(wù)分解、分配和執(zhí)行過程中不確定性因素,并給出相應(yīng)的形式化描述。在此基礎(chǔ)上,提出一種基于概率推理的適應(yīng)度(fitness)計算方法,具體分析各種不確定性任務(wù)成功執(zhí)行概率的計算過程,并給出一個算例驗證該方法的正確性。

2 問題分析與符號定義

在實際作戰(zhàn)背景下,作戰(zhàn)任務(wù)分配是一個動態(tài)變化前反饋的過程。圖1表示作戰(zhàn)任務(wù)分解、分配和執(zhí)行的流程,從圖中可以看出每個部分相互聯(lián)系,而且戰(zhàn)場態(tài)勢的變化將導(dǎo)致作戰(zhàn)任務(wù)的變更。因此,如何正確描述任務(wù)分解以及合理表示各種不確定性將影響作戰(zhàn)指揮決策的效率。

圖1 作戰(zhàn)任務(wù)分解、分配與執(zhí)行流程

2.1 基于與或樹的任務(wù)分解描述

作戰(zhàn)任務(wù)分解是任務(wù)組織形成的重要步驟之一,它通過將復(fù)雜任務(wù)轉(zhuǎn)化為較簡單的任務(wù),一方面可以緩解單個執(zhí)行體Agent完成任務(wù)的壓力,便于任務(wù)的分配和執(zhí)行;另一方面,當(dāng)戰(zhàn)場態(tài)勢發(fā)生變化時,便于整個任務(wù)組織的調(diào)整。作戰(zhàn)任務(wù)分解的實質(zhì)是將任務(wù)變成一系列的可由Agent單獨或協(xié)同完成的任務(wù),并且包含了任務(wù)間的各種邏輯依賴關(guān)系。為體現(xiàn)作戰(zhàn)任務(wù)分解的實質(zhì),本文采用“與或分解樹”的表示方法。圖2是任務(wù)的與或分解樹表示。

圖2 任務(wù)的與或分解樹表示

在任務(wù)分解樹中任務(wù)用節(jié)點表示,節(jié)點內(nèi)為任務(wù)名稱。任務(wù)間如果是順序關(guān)系,則用虛線箭頭連接節(jié)點,如圖3(a)中,任務(wù)T4完成后才能執(zhí)行任務(wù)T2。文中討論的順序關(guān)系僅限在同層次任務(wù)間;任務(wù)間如果是與關(guān)系,則在箭頭線之間用圓弧連接,如圖3(b)中,任務(wù)Ta與任務(wù)Tb的完成標(biāo)志著任務(wù)T的完成;任務(wù)間如果是或關(guān)系,如圖3(c)中,子任務(wù)T4或子任務(wù)T5的完成均標(biāo)志著任務(wù)T的完成[9]。

圖3 與或分解樹中的任務(wù)關(guān)系

2.2 不確定因素分析與形式化描述

在實際的作戰(zhàn)背景下,很多因素都將影響任務(wù)分配方案的形成,當(dāng)作戰(zhàn)任務(wù)和執(zhí)行人員發(fā)生變化時,不確定性因素也將有所不同[10]。全面合理地分析任務(wù)分配過程中存在的不確定性因素,能夠為任務(wù)分配方案的選取奠定基礎(chǔ)。

(1)作戰(zhàn)任務(wù)存在的不確定性

由于戰(zhàn)場態(tài)勢的千變?nèi)f化將導(dǎo)致偵察到的情報信息可能存在誤差,因此根據(jù)情報信息制定的作戰(zhàn)任務(wù)同樣存在不確定性,從而使得由作戰(zhàn)任務(wù)分解得到的子任務(wù)具有不確定性。

定義1元任務(wù)指不可再分解、可由單個智能體Agent執(zhí)行的任務(wù),即任務(wù)分解樹中葉子節(jié)點代表的任務(wù),如圖2中元任務(wù)T1,T2,…,T5。

元任務(wù)集合為:TM={T1,T2,…,Tm},其中,m為元任務(wù)的個數(shù);智能體集合為:A={A1,A2,…,An},其中,n為智能體的個數(shù)。

定義2任務(wù)的存在概率,表示由總?cè)蝿?wù)分解得到的子任務(wù)Ti是否存在的概率。本文用來處理任務(wù)存在的不確定性。

(2)作戰(zhàn)任務(wù)執(zhí)行的不確定性

由于在任務(wù)執(zhí)行過程中存在許多未知與不可控的因素,例如,任務(wù)執(zhí)行體Agent的執(zhí)行能力影響任務(wù)能否成功被執(zhí)行,而執(zhí)行能力又受到戰(zhàn)場環(huán)境等不確定因素的影響,因此任務(wù)的執(zhí)行具有不確定性。

定義3任務(wù)成功被執(zhí)行概率γTiAj,表示元任務(wù)Ti由智能體Aj執(zhí)行成功的概率?？紤]到不同任務(wù)分配給不同執(zhí)行體時,任務(wù)成功被執(zhí)行的概率有所不同。為方便討論假設(shè)當(dāng)任務(wù)分配方案確定后,該概率值即被確定。在本文中,γ′Ti和γTi分別表示元任務(wù)Ti初始成功被執(zhí)行的概率和在考慮順序關(guān)系對元任務(wù)Ti的影響后成功被執(zhí)行的概率。

(3)子任務(wù)對父任務(wù)影響的不確定性

由任務(wù)分解樹可以看出,任務(wù)的執(zhí)行情況由其子任務(wù)決定。子任務(wù)成功被執(zhí)行往往意味著父任務(wù)的完成。但是相反地,如果子任務(wù)未成功被執(zhí)行卻不意味著父任務(wù)一定不能完成,從而決定了子任務(wù)對父任務(wù)的影響具有不確定性。

定義4 與關(guān)系下子任務(wù)執(zhí)行成功影響因子ωTi,表示若子任務(wù)間存在與關(guān)系,子任務(wù)Ti執(zhí)行成功對父任務(wù)執(zhí)行的影響,主要用來處理子任務(wù)的執(zhí)行對父任務(wù)影響的不確定性。

其中,Ti為具有同一父任務(wù)且相互之間為與關(guān)系的所有子任務(wù)。

(4)作戰(zhàn)任務(wù)之間關(guān)系的不確定性

圖2中顯示任務(wù)之間存在多種關(guān)系,如順序關(guān)系、與關(guān)系以及或關(guān)系等。其中,與、或關(guān)系的作用體現(xiàn)在子任務(wù)對父任務(wù)的影響,而順序關(guān)系則使同一層次上不同任務(wù)之間存在作用與影響。本文主要討論任務(wù)之間的影響,因此,與、或關(guān)系是確定的,也即順序關(guān)系是不確定的。

定義5元任務(wù)順序二元組＜Ti,Tj＞,表示在任務(wù)分解樹中存在一條由葉節(jié)點Ti指向葉節(jié)點Tj的有向虛線邊,即任務(wù)Tj須在任務(wù)Ti完成之后執(zhí)行,如圖2中存在順序二元組＜T4,T2＞。所有的順序二元組構(gòu)成集合SEQ,其數(shù)學(xué)表達式如下:SEQ= {＜Ti,Tj＞|存在節(jié)點Ti指向Tj的虛線邊}

定義6后序節(jié)點集合(Set of Later-Sequence, SLS),表示所有順序二元組＜Ti,Tj＞中節(jié)點Tj的集合。

定義7 順序關(guān)系存在的概率β＜Ti,Tj＞,本文考慮的順序僅存于元任務(wù)之間,因此,β＜Ti,Tj＞表示元任務(wù)Ti與元任務(wù)Tj之間存在順序關(guān)系的概率,本文主要用來處理任務(wù)間關(guān)系的不確定性。

(5)作戰(zhàn)任務(wù)執(zhí)行時間的不確定性

在作戰(zhàn)任務(wù)分解、分配與執(zhí)行過程中,通常會考慮關(guān)于任務(wù)執(zhí)行時間的開始、結(jié)束和持續(xù)長短等因素。而不同任務(wù)對于執(zhí)行時間有不同的約束,受到如執(zhí)行體作戰(zhàn)能力、任務(wù)規(guī)模以及作戰(zhàn)環(huán)境等多種因素的影響,因此作戰(zhàn)任務(wù)執(zhí)行時間具有不確定性。本文將此類不確定性與任務(wù)執(zhí)行的不確定性聯(lián)合考慮,體現(xiàn)在任務(wù)被成功執(zhí)行的概率上。

3 基于概率推理的適應(yīng)度計算

在確定了任務(wù)分解樹的結(jié)構(gòu)、元任務(wù)序列以及不確定性概率值后,接下來需要根據(jù)智能體(Agent)執(zhí)行能力表進行任務(wù)分配。已知元任務(wù)個數(shù)為m,智能體個數(shù)為n,假設(shè)智能體Agentj可以執(zhí)行不同元任務(wù),而元任務(wù)Ti能夠同時分配給不同智能體,因此可能存在的分配方案數(shù)為nm。顯然,隨著n與m的增加,可選擇的任務(wù)分配方案數(shù)指數(shù)級增加,因此任務(wù)分配問題為NP問題。而人工智能領(lǐng)域內(nèi)智能搜索方法是解決NP問題的有效手段,而智能搜索算法中關(guān)鍵步驟是適應(yīng)度的計算[11]。

3.1 不同關(guān)系下的概率推理

與或樹中任務(wù)之間包含與、或以及順序等關(guān)系,而任務(wù)之間的影響與作用也是通過這些關(guān)系進行傳遞的。如圖3(a)中,任務(wù)T2和T3之間具有順序關(guān)系,則可以認為任務(wù)T2是否被成功執(zhí)行將影響任務(wù)T3的執(zhí)行。因此在任務(wù)與或分解樹中,同層次的任務(wù)之間存在相互作用。另外,子任務(wù)對父任務(wù)同樣存在影響。由于相互作用與影響的任務(wù)可能存在多個,為不失一般性,本文將圖3擴展成圖4所示的情況,并給出不同關(guān)系下概率推理的過程。

圖4 擴展后的與或分解樹中任務(wù)關(guān)系

(1)順序關(guān)系

如圖4(a)所示,元任務(wù)Ti需在元任務(wù)Tj之后執(zhí)行,因此元任務(wù)Tj的執(zhí)行結(jié)果將影響元任務(wù)Ti的執(zhí)行,則元任務(wù)Ti的成功被執(zhí)行的概率γTi可以用式(1)表示。

對于元任務(wù)Tj而言,由于不存在指向節(jié)點Tj的虛線,則:

可以看出,式(2)是式(1)中β＜Ti,Tj＞=0的情況。

(2)與關(guān)系

如圖4(b)所示,元任務(wù)Ti,Tl與Tj等之間兩兩存在與關(guān)系,即任務(wù)T完成的前提是元任務(wù)Ti,Tl與Tj等同時完成。以元任務(wù)Ti為例,考慮任務(wù)存在的不確定性、成功被執(zhí)行的不確定性以及對父任務(wù)影響的不確定性,用p(T)Ti表示子任務(wù)Ti對父任務(wù)T的影響,見式(3)。由于子任務(wù)之間存在與關(guān)系,則任務(wù)T成功被執(zhí)行的概率p(T)可用式(4)表示。

(3)或關(guān)系

如圖4(c)所示,元任務(wù)Ti,Tl與Tj等之間兩兩存在或關(guān)系,即任務(wù)T完成的前提為元任務(wù)Ti,Tl與Tj中任意一個完成。以元任務(wù)Ti為例,用p(T)Ti表示子任務(wù)Ti的執(zhí)行對父任務(wù)T的影響,具體見式(5)。由于子任務(wù)之間存在或關(guān)系,因此任務(wù)T成功被執(zhí)行的概率p(T)可用式(6)表示。

(4)與或關(guān)系

如圖4(d)所示,元任務(wù)之間同時存在與關(guān)系以及或關(guān)系,本文首先將元任務(wù)之間為與關(guān)系的節(jié)點看作一個節(jié)點T′,利用式(3)和式(4)計算節(jié)點T′成功被執(zhí)行概p(T′),然后再利用式(5)和式(6)計算節(jié)點T成功被執(zhí)行概率p(T)。

3.2 適應(yīng)度的計算步驟

根據(jù)之前的論述可知任務(wù)分配是一個NP問題,而解決NP問題的有效手段是采用智能搜索算法。在一般的智能搜索算法中都會涉及到適應(yīng)度的計算,本文討論的適應(yīng)度也即總?cè)蝿?wù)成功被執(zhí)行的概率p(T)。具體的計算過程是在上節(jié)介紹概率推理的基礎(chǔ)上,結(jié)合與或分解樹結(jié)構(gòu)進行概率傳遞。

步驟1初始化

確定與或分解樹中葉子節(jié)點也即元任務(wù)集合TM,并為元任務(wù)存在概率αTi、初始成功執(zhí)行概率γ′Ti、順序二元組＜Ti,Tj＞存在的概率β＜Ti,Tj＞以及子任務(wù)Ti對父任務(wù)Ta的影響概率p(Ta|Ti)賦值。

步驟2更新概率值

由于元任務(wù)之間可能存在順序關(guān)系,而順序關(guān)系又能夠影響元任務(wù)的成功被執(zhí)行概率,因此需要對元任務(wù)的成功執(zhí)行概率進行更新。如果元任務(wù)Ti∈TM∩SLS,則利用式(1)進行初始成功被執(zhí)行概率的更新;如果元任務(wù)Ti∈TM且Ti?TM∩SLS,則利用式(2)進行初始成功被執(zhí)行概率的更新。

步驟3概率推理與傳遞

根據(jù)式(7)可知,本文中的適應(yīng)度即根節(jié)點代表的總?cè)蝿?wù)成功被執(zhí)行的概率。因此,由葉節(jié)點出發(fā),利用式(4)和式(6)進行概率推理得到根節(jié)點成功被執(zhí)行的概率。具體推理與傳遞規(guī)則如下:如果節(jié)點之間僅存在與關(guān)系,利用式(4)向上進行推理;如果節(jié)點之間僅存在或關(guān)系,利用式(6)向上進行推理;如果節(jié)點之間既存在與關(guān)系又存在或關(guān)系,則根據(jù)3.1節(jié)的(4)中提出的規(guī)則向上進行推理。

經(jīng)過以上3個步驟即可計算出總?cè)蝿?wù)成功被執(zhí)行的概率p(T),即適應(yīng)度fitness。

4 仿真實驗及結(jié)果分析

為驗證本文提出方法的有效性,本文假設(shè)已經(jīng)得到如圖2所示的總?cè)蝿?wù)T的分解樹,則元任務(wù)集合TM={T1,T2,…,T5},SEQ={＜T4,T2＞},SLS= {T2}v。各概率初始值見表1。

表1 概率初始值

通過3.2節(jié)步驟2可以計算出γT1=0.95,γT2= 0.83,γT3=0.94,γT4=0.92,γT5=0.95,從而根據(jù)步驟3可以計算出根節(jié)點成功被執(zhí)行的概率p(T),即fitness=0.904。

由以上的計算過程可知,本文提出的適應(yīng)度計算方法能夠計算總?cè)蝿?wù)的成功執(zhí)行概率。為更好地體現(xiàn)本文提出的適應(yīng)度計算方法能夠有效地利用到遺傳算法中,現(xiàn)將采用本文適應(yīng)度計算過程的遺傳算法與文獻[12]中提出的基于能力的任務(wù)分配方法進行比較。文獻[12]采用基于Agent能力的任務(wù)分配方法,主要目的是使Agent能力效能最大化,從而在最大程度上滿足任務(wù)需求。

本文進行5組仿真對比實驗,每組實驗數(shù)據(jù)中Agent的能力值與各不確定性概率值不變,不同組實驗數(shù)據(jù)間,需要改變不確定性概率值。每組均模擬計算100次,記錄每次總?cè)蝿?wù)的成功執(zhí)行概率值,進行統(tǒng)計并計算總?cè)蝿?wù)成功執(zhí)行概率的平均值,統(tǒng)計結(jié)果如圖5所示。

圖5 仿真實驗結(jié)果對比

從圖5可以看出,5次實驗中基于遺傳算法計算的總?cè)蝿?wù)成功執(zhí)行概率的平均值比基于文獻[12]提出的基于能力的方法計算值高,說明本文基于概率推理的適應(yīng)度計算方法能夠應(yīng)用到遺傳算法中,并能夠有效解決作戰(zhàn)任務(wù)分配問題。

5 結(jié)束語

為更好地實現(xiàn)作戰(zhàn)任務(wù)的合理分配,本文從描述作戰(zhàn)任務(wù)分解的方法出發(fā),分析了在作戰(zhàn)任務(wù)分解、分配和執(zhí)行過程中存在的多種不確定性因素,并給出了各類不確定性因素的數(shù)學(xué)表達形式。作戰(zhàn)任務(wù)分配問題是一個典型的NP問題,而智能搜索算法是解決NP問題的有效手段。因此,提出了一種基于概率推理的適應(yīng)度計算方法,并給出了一個算例驗證提出的方法。在算例的基礎(chǔ)上,與其他任務(wù)分配方法進行仿真實驗對比,結(jié)果表明,本文提出的方法能夠有效地應(yīng)對任務(wù)分解、分配和執(zhí)行過程中的各類不確定性問題。下一步將重點研究如何處理任務(wù)分配過程中更多的不確定性因素。

[1] Macarthur K S,Stranders R,Ramchurn S D,et al.A DistributedAnytimeAlgorithmforDynamicTask Allocation in Multi-agent Systems[C]//Proceedings of the 25th AAAI Conference on Artificail Intelligence. San Francisco,USA:[s.n.],2011:85-90.

[2] Chapman A C,Micillo R A,Kota R,et al.Decentralized Dynamic Task Allocation:A Practical Game-theoretic Approach[C]//Proceedings of AAMAS’09.Budapest, Hungary:[s.n.],2009:16-20.

[3] Oliverra D,Ferreir A P R,Bazzaz A L C.A Swarm Based Approach for Task Allocation in Dynamic Agents Organizations[C]//ProceedingsofAAMAS’04. New York,USA:[s.n.],2004:1252-1253.

[4] Zhang Dandan,XieGuangming,YuJunzhi,etal. Adaptive Task Assignment for Multiple Mobile Robots via Swarm Intelligence Approach[J].Robotics and Autonomous Systems,2007,55(7):572-588.

[5] 朱德通.最優(yōu)化模型與實驗[M].上海:同濟大學(xué)出版社,2003.

[6] 邊馥萍,侯文華,梁馮珍.數(shù)學(xué)模型方法與算法[M].北京:高等教育出版社,2005.

[7] 徐澤水.不確定多屬性決策方法及應(yīng)用[M].北京:清華大學(xué)出版社,2004.

[8] 張 利,陳士明,張建軍.不確定多因素下的多屬性決策在任務(wù)分配中的應(yīng)用[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版,2008,31(6):851-853.

[9] 馮 磊.CGF協(xié)同行為建模關(guān)鍵技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2011.

[10] 張大川,張榮國,黃付亮,等.PSO算法在子任務(wù)分配中的應(yīng)用[J].計算機工程,2011,37(24):183-186.

[11] 蔡益朝,張維明,劉 忠,等.基于遺傳算法的實體分群問題的求解方法[J].計算機工程,2007,33(5): 4-6.

[12] 陶雪麗,鄭延斌.基于能力及任務(wù)需求的多Agent任務(wù)分配方法[J].計算機應(yīng)用與軟件,2012,29(11): 181-184.

編輯 金胡考

Assessment Method of Uncertain Task Allocation Based on Probabilistic Reasoning

HE Yihui1,PAN Mingcong1,2,XU Wei1,PENG Hui1
(1.Command Information System College,PLA University of Science and Technology,Nanjing 210007,China; 2.Operations Research Center,Nanjing Army Command College,Nanjing 210045,China)

Decomposition and allocation of combat tasks play important roles in process of command and decision.With the increasing complexity of the battlefield environment,methods of task allocation under certain environment are no longer able to meet the needs of the commander.In order to solve this problem,this paper analyzes the uncertainty existing in the process of decomposition,allocation and execution of tasks,and gives the formal description of each uncertainty with mathematical method.On this basis,it proposes a method of calculating the fitness based on probabilistic reasoning.This method can be used in intelligent algorithm to assess the scheme of task allocation in quantity.Finally,the example verifies the reasonability and effectiveness of the proposed method.

uncertainty;formal description;task allocation;probabilistic reasoning;fitness

賀毅輝,潘明聰,徐 偉,等.基于概率推理的不確定性任務(wù)分配評價方法[J].計算機工程, 2015,41(2):31-35.

英文引用格式:He Yihui,Pan Mingcong,Xu Wei,et al.Assessment Method of Uncertain Task Allocation Based on Probabilistic Reasoning[J].Computer Engineering,2015,41(2):31-35.

1000-3428(2015)02-0031-05

:A

:TP391

10.3969/j.issn.1000-3428.2015.02.007

江蘇省自然科學(xué)基金資助項目(BK2011120)。

賀毅輝(1973-),男,教授,主研方向:指揮信息系統(tǒng),作戰(zhàn)仿真;潘明聰、徐 偉,碩士;彭 輝,講師、博士。

2014-01-21

:2014-04-25E-mail:xuwei_9002@163.com