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

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

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

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

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

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

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

不確定性;形式化描述;任務分配;概率推理;適應度

1 概述

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

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

2 問題分析與符號定義

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

圖1 作戰任務分解、分配與執行流程

2.1 基于與或樹的任務分解描述

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

圖2 任務的與或分解樹表示

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

圖3 與或分解樹中的任務關系

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

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

(1)作戰任務存在的不確定性

由于戰場態勢的千變萬化將導致偵察到的情報信息可能存在誤差,因此根據情報信息制定的作戰任務同樣存在不確定性,從而使得由作戰任務分解得到的子任務具有不確定性。

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

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

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

(2)作戰任務執行的不確定性

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

定義3任務成功被執行概率γTiAj,表示元任務Ti由智能體Aj執行成功的概率。考慮到不同任務分配給不同執行體時,任務成功被執行的概率有所不同。為方便討論假設當任務分配方案確定后,該概率值即被確定。在本文中,γ′Ti和γTi分別表示元任務Ti初始成功被執行的概率和在考慮順序關系對元任務Ti的影響后成功被執行的概率。

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

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

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

其中,Ti為具有同一父任務且相互之間為與關系的所有子任務。

(4)作戰任務之間關系的不確定性

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

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

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

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

(5)作戰任務執行時間的不確定性

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

3 基于概率推理的適應度計算

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

3.1 不同關系下的概率推理

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

圖4 擴展后的與或分解樹中任務關系

(1)順序關系

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

對于元任務Tj而言,由于不存在指向節點Tj的虛線,則:

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

(2)與關系

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

(3)或關系

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

(4)與或關系

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

3.2 適應度的計算步驟

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

步驟1初始化

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

步驟2更新概率值

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

步驟3概率推理與傳遞

根據式(7)可知,本文中的適應度即根節點代表的總任務成功被執行的概率。因此,由葉節點出發,利用式(4)和式(6)進行概率推理得到根節點成功被執行的概率。具體推理與傳遞規則如下:如果節點之間僅存在與關系,利用式(4)向上進行推理;如果節點之間僅存在或關系,利用式(6)向上進行推理;如果節點之間既存在與關系又存在或關系,則根據3.1節的(4)中提出的規則向上進行推理。

經過以上3個步驟即可計算出總任務成功被執行的概率p(T),即適應度fitness。

4 仿真實驗及結果分析

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

表1 概率初始值

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

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

本文進行5組仿真對比實驗,每組實驗數據中Agent的能力值與各不確定性概率值不變,不同組實驗數據間,需要改變不確定性概率值。每組均模擬計算100次,記錄每次總任務的成功執行概率值,進行統計并計算總任務成功執行概率的平均值,統計結果如圖5所示。

圖5 仿真實驗結果對比

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

5 結束語

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

[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] 朱德通.最優化模型與實驗[M].上海:同濟大學出版社,2003.

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

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

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

[9] 馮 磊.CGF協同行為建模關鍵技術研究[D].長沙:國防科學技術大學,2011.

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

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

[12] 陶雪麗,鄭延斌.基于能力及任務需求的多Agent任務分配方法[J].計算機應用與軟件,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

賀毅輝,潘明聰,徐 偉,等.基于概率推理的不確定性任務分配評價方法[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

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

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

2014-01-21

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