劉 杰,張耀中
(1.中國電子科技集團(tuán)公司信息科學(xué)研究院,北京 100086;2.西北工業(yè)大學(xué)電子信息學(xué)院,西安 710129)
基于黑板模型的分布式協(xié)同任務(wù)決策方法研究*
劉 杰1,張耀中2
(1.中國電子科技集團(tuán)公司信息科學(xué)研究院,北京 100086;2.西北工業(yè)大學(xué)電子信息學(xué)院,西安 710129)
基于黑板模型的分布式指揮控制網(wǎng)絡(luò)為未來復(fù)雜環(huán)境下海戰(zhàn)中多平臺(tái)間的高效協(xié)同提供了新思路,通過構(gòu)建應(yīng)用于多航母群聯(lián)合海戰(zhàn)的分布式協(xié)同網(wǎng)絡(luò),對(duì)多航母群聯(lián)合海戰(zhàn)下的系統(tǒng)負(fù)載進(jìn)行了研究,建立了一種多平臺(tái)任務(wù)決策的數(shù)學(xué)模型,采用嵌套遺傳算法進(jìn)行了仿真求解,得到了理想的任務(wù)決策方案。最后對(duì)由于目標(biāo)函數(shù)中內(nèi)部負(fù)載權(quán)重系數(shù)不同取值所引起的不同任務(wù)決策結(jié)果進(jìn)行了比較,驗(yàn)證了將基于黑板模型的分布式協(xié)同網(wǎng)絡(luò)應(yīng)用于多航母海戰(zhàn)協(xié)同決策的科學(xué)性,為分布式海戰(zhàn)協(xié)同決策網(wǎng)絡(luò)的后續(xù)研究工作奠定了基礎(chǔ)。
分布式協(xié)同,黑板模型,決策者,差別變量
隨著海戰(zhàn)平臺(tái)的不斷發(fā)展,多航母戰(zhàn)斗群聯(lián)合海戰(zhàn)將成為未來海戰(zhàn)的發(fā)展趨勢(shì)。如何構(gòu)建高效的指揮控制網(wǎng)絡(luò),實(shí)現(xiàn)多航母、多轟炸機(jī)、多目標(biāo)之間合理的分組與分配,將成為一個(gè)需要重點(diǎn)解決的問題。傳統(tǒng)的集中式指揮網(wǎng)絡(luò)需要旗艦的統(tǒng)一協(xié)調(diào)調(diào)度,一旦旗艦被摧毀,則原有的指揮網(wǎng)絡(luò)也失效,需要指定新的旗艦構(gòu)建新的指揮網(wǎng)絡(luò),極大地浪費(fèi)了時(shí)間,而分布式作戰(zhàn)協(xié)同網(wǎng)絡(luò)可以克服集中式指揮控制網(wǎng)絡(luò)對(duì)旗艦過分依賴的特點(diǎn),即使在某一組作戰(zhàn)單元被摧毀,系統(tǒng)依然可以動(dòng)態(tài)決策。本文以航母指揮所為決策體(Decision-Maker,DM),轟炸機(jī)為執(zhí)行任務(wù)的平臺(tái),待摧毀敵艦為待執(zhí)行的任務(wù),通過改進(jìn)的嵌套遺傳算法求出最優(yōu)的任務(wù)平臺(tái)分組,在此基礎(chǔ)上構(gòu)建使系統(tǒng)負(fù)載最小的最優(yōu)分布式作戰(zhàn)協(xié)同網(wǎng)絡(luò),以充分發(fā)揮系統(tǒng)整體作戰(zhàn)效能。
在編隊(duì)海戰(zhàn)中,編隊(duì)所要執(zhí)行的任務(wù)可用任務(wù)資源需求向量來表述,。執(zhí)行任務(wù)的作戰(zhàn)平臺(tái)可以用平臺(tái)資源能力來進(jìn)行表述,。任務(wù)分配決策系統(tǒng)需要解決的主要問題是作戰(zhàn)任務(wù)和作戰(zhàn)平臺(tái)間的最優(yōu)化匹配問題。任務(wù)-平臺(tái)分配問題的資源匹配原理如圖1所示。
定義效益矩陣A為任務(wù)執(zhí)行精確度矩陣,其中任務(wù)執(zhí)行精確度為表述任務(wù)資源需求向量與平臺(tái)資源能力向量間匹配程度的標(biāo)量。即:
對(duì)于完成某項(xiàng)任務(wù)來說,有些資源是重要資源,有些資源是相對(duì)重要資源,有些資源是不重要資源,因此,可采用加權(quán)平均的方法計(jì)算平均任務(wù)執(zhí)行精確度。
式(2)中,ωil為資源l相對(duì)于完成任務(wù)Ti的權(quán)重系數(shù),假設(shè)決策系統(tǒng)所要執(zhí)行的任務(wù)數(shù)量為n,則所有任務(wù)的權(quán)重系數(shù)構(gòu)成n×L權(quán)重系數(shù)矩陣W。采用xij描述任務(wù)Ti和平臺(tái)Pj的分配情況,當(dāng)xij=1時(shí),表示平臺(tái)Pj分配給任務(wù)Ti,反之,當(dāng)xij=0時(shí)表示平臺(tái)Pj未分配給任務(wù)Ti。
任務(wù)決策問題的目標(biāo)是將任務(wù)匹配給相應(yīng)平臺(tái)來執(zhí)行,原則是最大化任務(wù)平臺(tái)之間的匹配程度,即最大化任務(wù)執(zhí)行精確度。
設(shè)TD為DM-任務(wù)分配矩陣;PD為DM-平臺(tái)分配矩陣;TP為任務(wù)-平臺(tái)分配矩陣。輸入數(shù)據(jù)為資源類型數(shù)目L、任務(wù)資源需求矩陣rT(i,l)平臺(tái)資源能力矩陣rP(i,l)及平臺(tái)速度向量v(j)和任務(wù)位置向量。各個(gè)索引值的取值范圍是:其中Nt和Np為輸入的任務(wù)個(gè)數(shù)和可用的平臺(tái)數(shù)目,m為DM的數(shù)目。
1)DM內(nèi)部負(fù)載
設(shè)分配給DMm的任務(wù)集合為T-m,分配給DMm的平臺(tái)集合為P-m。執(zhí)行任務(wù)Ti∈T-m的內(nèi)部平臺(tái)集為:
①DMm的地理位置中心:
②DMm內(nèi)平臺(tái)Pj和任務(wù)Ti之間的距離:
③DMm執(zhí)行任務(wù)的累積轉(zhuǎn)換延遲:
④DMm執(zhí)行任務(wù)的累積精確度
考慮某決策體內(nèi)部的所有平臺(tái)的任務(wù)資源能力都不能單獨(dú)滿足該決策體內(nèi)某個(gè)任務(wù)的資源需求的情況,這時(shí)需要多個(gè)平臺(tái)合作來完成該任務(wù),為簡便起見,假設(shè)任務(wù)是由決策體內(nèi)按編號(hào)由小到大的平臺(tái)順序執(zhí)行的。當(dāng)執(zhí)行到平臺(tái)j時(shí),任務(wù)Ti對(duì)資源l剩余資源需求應(yīng)為完成該任務(wù)的總資源需求與前面所有平臺(tái)已經(jīng)完成的任務(wù)資源量之差,即:
則內(nèi)部平臺(tái)資源l對(duì)于任務(wù)Ti的滿足程度為:
此時(shí),定義內(nèi)部平臺(tái)的任務(wù)完成的精確度為:
⑤內(nèi)部平臺(tái)對(duì)任務(wù)Ti的執(zhí)行TAS(Task accuracy significance)定義為:
ρ1為DM內(nèi)部負(fù)載的指數(shù)。
⑥D(zhuǎn)Mm的內(nèi)部負(fù)載為:
2)DM外部協(xié)作負(fù)載
②外部執(zhí)行任務(wù)Ti的轉(zhuǎn)換延遲為:
③外部平臺(tái)執(zhí)行任務(wù)Ti的精確度為:
定義當(dāng)執(zhí)行到外部平臺(tái)Pj時(shí),任務(wù)Ti的剩余資源需求矩陣為和前面所有外部平臺(tái)已經(jīng)完成的任務(wù)資源矩陣為。則應(yīng)等于外部平臺(tái)總的資源需求與前面所有外部平臺(tái)已經(jīng)完成的任務(wù)資源量之差,即:
④外部平臺(tái)執(zhí)行任務(wù)Ti的TAS(Task accuracy significance)定義為:
⑤系統(tǒng)外部協(xié)作負(fù)載為:
3)系統(tǒng)總負(fù)載
系統(tǒng)總負(fù)載的計(jì)算公式為:
WIntea(m)和WInter(m)分別為DM的內(nèi)部協(xié)作負(fù)載和外部協(xié)作負(fù)載,α為內(nèi)部協(xié)作負(fù)載的權(quán)重系數(shù),α≤0.5因?yàn)橥獠繀f(xié)作負(fù)載的代價(jià)較高。選擇目標(biāo)函數(shù)為系統(tǒng)總負(fù)載的算術(shù)平方根:
黑板模型結(jié)構(gòu)可以解決多個(gè)智能體協(xié)作完成任務(wù)的并行和分布計(jì)算,并且能夠?qū)崿F(xiàn)異構(gòu)智能體的集成,管理智能體之間的通訊和知識(shí)轉(zhuǎn)換,是一種高效而通用的知識(shí)存儲(chǔ)與處理工具[1]。將黑板模型結(jié)構(gòu)應(yīng)用于基于智能體的分布式規(guī)劃和協(xié)同設(shè)計(jì)問題中,可以取得很好的處理效果,這種協(xié)同規(guī)劃網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。
1)黑板(Blackboard,BB)
黑板的主要功能是對(duì)參與協(xié)同的DM進(jìn)行信息采集。傳遞信息時(shí)采用基于時(shí)間的觸發(fā)機(jī)制。
2)協(xié)調(diào)機(jī)構(gòu)(Coordinator,CC)
協(xié)調(diào)機(jī)構(gòu)的主要功能是對(duì)黑板的信息進(jìn)行采集和分析,并完成平臺(tái)-資源的分配和任務(wù)的分解。不同于集中式指揮控制網(wǎng)絡(luò)中的負(fù)責(zé)全局作戰(zhàn)指揮控制的作戰(zhàn)實(shí)體,協(xié)調(diào)機(jī)構(gòu)是一個(gè)具有信息處理和決策能力的軟件智能體,因此,它本身不具備作戰(zhàn)能力。
3)決策者(Decision-Maker,DM)
DM相當(dāng)于作戰(zhàn)單元集合的司令部,控制著一定數(shù)目的作戰(zhàn)單元,它的主要功能分為兩部分:一是對(duì)內(nèi)部作戰(zhàn)單元進(jìn)行初始資源和任務(wù)分配:二是與黑板及協(xié)調(diào)機(jī)構(gòu)之間的通訊。除了對(duì)所轄的戰(zhàn)斗單元進(jìn)行指揮協(xié)調(diào)外,DM本身還應(yīng)具備作戰(zhàn)能力。
4)任務(wù)(Tasks)
協(xié)調(diào)器根據(jù)上級(jí)指令對(duì)任務(wù)進(jìn)行分解,并將分解后的任務(wù)分配給各個(gè)DM。
5)平臺(tái)(Assets)
分屬一定DM的作戰(zhàn)單元,由DM對(duì)其進(jìn)行資源分配。
首先,協(xié)調(diào)器對(duì)系統(tǒng)任務(wù)進(jìn)行分解,并將資源分組后分配到各個(gè)DM當(dāng)中,DM根據(jù)分配給自身的任務(wù)資源信息進(jìn)行規(guī)劃,得出分配給DM的任務(wù)執(zhí)行時(shí)序列表。當(dāng)分配給某個(gè)DM的資源無法滿足分配給該DM中某任務(wù)的資源需求時(shí),則該任務(wù)的完成需要多個(gè)DM進(jìn)行協(xié)作。此時(shí),該DM向BB發(fā)送請(qǐng)求協(xié)同信號(hào),獲得BB允許后,DM將需要協(xié)同的任務(wù)靜態(tài)信息,發(fā)送到BB中的信息倉庫。這些靜態(tài)信息包括處理時(shí)間、資源需求、有效期限、優(yōu)先級(jí)和在任務(wù)空間中的位置等。然后,BB向CC和需要協(xié)同的DM發(fā)送協(xié)同規(guī)劃啟動(dòng)觸發(fā)信號(hào),信號(hào)的發(fā)送采用基于時(shí)間的觸發(fā)機(jī)制,同時(shí),在全局工作區(qū)發(fā)布相關(guān)任務(wù)信息,如初始狀態(tài)等。在收到觸發(fā)信號(hào)后,需要協(xié)同的DM向BB發(fā)送可共享的設(shè)備信息,如設(shè)備狀態(tài)、設(shè)備在一定時(shí)間內(nèi)的可用性、設(shè)備在任務(wù)空間中的位置等。之后,由CC訪問BB中的全局工作區(qū),BB將全局工作區(qū)中的待協(xié)同任務(wù)列表發(fā)送給CC。在BB接收到DM發(fā)送的可共享設(shè)備信息后,BB將這些設(shè)備信息發(fā)送給CC,同時(shí)CC訪問DM中相應(yīng)設(shè)備的狀態(tài),并將待協(xié)同的DM信息以及可共享設(shè)備放入待調(diào)度隊(duì)列中。待調(diào)度列表更新后由CC啟動(dòng)協(xié)同任務(wù)規(guī)劃程序,程序求解過程中的部分解發(fā)送到BB的相應(yīng)區(qū)域以供訪問。規(guī)劃完成后,CC將協(xié)同任務(wù)-資源調(diào)度信號(hào)以及任務(wù)的執(zhí)行時(shí)序表發(fā)給對(duì)應(yīng)的DM,并更新BB中的任務(wù)狀態(tài)信息。
式(21)是一個(gè)組合優(yōu)化問題,該問題屬于NP-hard問題,可用遺傳算法來求解。為避免陷入局部極值,在算法機(jī)制上采用嵌套遺傳算法(Nested Genetic Algorithm,NGA)。算法包含內(nèi)循環(huán)(ILG)和外循環(huán)(OLG),為方便起見,簡稱外循環(huán)的染色體為外染色體,簡稱內(nèi)循環(huán)的染色體為內(nèi)染色體。則外染色體的目標(biāo)值為外染色體所對(duì)應(yīng)的任務(wù)平臺(tái)分組下所能達(dá)到的最小系統(tǒng)負(fù)載的算術(shù)平方根值,內(nèi)染色體的目標(biāo)值為TD、PD、TP三參數(shù)確定狀態(tài)下系統(tǒng)總負(fù)載的算術(shù)平方根值,外染色體的目標(biāo)值需要通過內(nèi)循環(huán)求得。
外循環(huán)的主要任務(wù)是求解最優(yōu)的任務(wù)平臺(tái)分組,因此,外染色體必須包含任務(wù)/決策體、平臺(tái)/決策體兩項(xiàng)信息。為了避免最優(yōu)染色體在遺傳進(jìn)化過程中被破壞掉,宜采用最優(yōu)保留的遺傳進(jìn)化機(jī)制:即在進(jìn)化過程中,將每一代的最優(yōu)染色體完全地保留下來參與下一代的選擇進(jìn)化。外染色體編碼方式如下:
①外染色體編碼
對(duì)于本問題,可采用整數(shù)交叉編碼的方式。染色體編碼時(shí)應(yīng)該同時(shí)考慮任務(wù)/決策體和平臺(tái)/決策體兩個(gè)參數(shù),所以可利用1×(Np+Nt)維的向量表示一條外染色體。以本文中4個(gè)決策體、7個(gè)平臺(tái)、8個(gè)任務(wù)的仿真為例,運(yùn)用多參數(shù)交叉編碼的方式,可以將這兩個(gè)參數(shù)集中編碼為如下模式:
②外染色體種群初始化
為避免陷入局部極值,采用均勻分布的方式來產(chǎn)生初始種群。定義兩條外染色體間的差別變量來表征兩條外染色體的差別程度:當(dāng)兩條染色體在某個(gè)相同位置上的編碼值相等時(shí),設(shè)置該位置的差別值為0,否則為1,兩條外染色體間的差別值為對(duì)應(yīng)所有位置上的差別值的代數(shù)和。在初始化種群時(shí),可設(shè)定一個(gè)選擇閾值,若新生成某條染色體與其余某染色體間的差別值小于該閾值時(shí),則淘汰該染色體,直至生成一定數(shù)量的初始種群。
ILG主要任務(wù)是求取外染色體的目標(biāo)值并求得對(duì)應(yīng)于外染色體的最優(yōu)的任務(wù)/平臺(tái)分配矩陣。為求得真實(shí)的外染色體目標(biāo)值,必須設(shè)置合理的內(nèi)循環(huán)進(jìn)化代數(shù),一般ILG的進(jìn)化代數(shù)應(yīng)大于OLG的代數(shù),內(nèi)染色體編碼方式和參數(shù)選擇如下:
①內(nèi)染色體編碼
本仿真試驗(yàn)中,可以用一條7×8的染色體來表述參數(shù)TP如下:
其中染色體中的每一位即代表TP矩陣對(duì)應(yīng)的元素,為0則表示任務(wù)沒有分配給該平臺(tái),為1則表示任務(wù)分配給了該平臺(tái)。
NGA算法流程圖如圖3所示。
在航母編隊(duì)執(zhí)行反艦任務(wù)中,假設(shè)由4艘航空母艦出動(dòng)共12架艦載機(jī)對(duì)敵8艘艦艇目標(biāo)實(shí)施攻擊,假設(shè)初始化參數(shù)如表1所示。
表1 輸入?yún)?shù)表
給定內(nèi)部負(fù)載α值時(shí),可以得到系統(tǒng)的最優(yōu)目標(biāo)值進(jìn)化曲線。分別取幾組不同的α值進(jìn)行比較,分析結(jié)果如圖4所示。
表2 任務(wù)平臺(tái)分組分配矩陣
圖4中橫坐標(biāo)為進(jìn)化的代數(shù),縱坐標(biāo)為進(jìn)化中各代的最小目標(biāo)函數(shù)值,即各代中最小的系統(tǒng)總負(fù)載的算術(shù)平方根。
從表1可以看出,當(dāng)α分別取0.1、0.01、0.001時(shí),系統(tǒng)的執(zhí)行效率呈遞減趨勢(shì),因此,不宜過小,通過多次仿真試驗(yàn)的數(shù)據(jù)分析表明,當(dāng)α=0.1時(shí),任務(wù)執(zhí)行效率最高。α=0.1時(shí)的任務(wù)-平臺(tái)-決策體的分組分配矩陣見表2。
從分配結(jié)果表中還可以看出:T1,T2,T4,T5,T6,T8的外部平臺(tái)分配向量各分量的值都為0,代表內(nèi)部平臺(tái)資源數(shù)即能滿足該任務(wù)的精確度閾值要求,不需要外部平臺(tái)來參與協(xié)作執(zhí)行,而T3,T7由于內(nèi)部平臺(tái)資源數(shù)不滿足任務(wù)精確度閾值的要求,需要外部平臺(tái)來參與協(xié)作。此時(shí),可實(shí)現(xiàn)系統(tǒng)負(fù)載的最小化和各組負(fù)載的均勻化,解決了構(gòu)建面向任務(wù)的指揮控制系統(tǒng)過程中的任務(wù)平臺(tái)的最優(yōu)化分組和分配決策問題,驗(yàn)證了算法的正確性。
基于黑板模型的分布式指揮控制網(wǎng)絡(luò)能較好地實(shí)現(xiàn)各參戰(zhàn)決策體間的通訊與協(xié)同,本文構(gòu)建了應(yīng)用于多航母聯(lián)合海戰(zhàn)的分布式作戰(zhàn)協(xié)同網(wǎng)絡(luò),并對(duì)任務(wù)決策過程進(jìn)行了建模,最后采用嵌套遺傳算法進(jìn)行了仿真求解。對(duì)于由不同α取值所引起的不同決策結(jié)果,論文采用了最長平臺(tái)轉(zhuǎn)化時(shí)間、任務(wù)總執(zhí)行率兩個(gè)評(píng)價(jià)指標(biāo),并最終統(tǒng)一成任務(wù)執(zhí)行效率,對(duì)α的合理取值提供了科學(xué)的依據(jù)。對(duì)于將基于黑板模型的指揮控制網(wǎng)絡(luò)應(yīng)用于多航母群聯(lián)合海戰(zhàn)中的任務(wù)決策具有很強(qiáng)的參考價(jià)值。
[1]杜支強(qiáng),張耀中,呂迎迎,等,基于向量調(diào)整法的指揮控制系統(tǒng)任務(wù)決策研究[J].火力與指揮控制,2014,39(8):55-60.
[2]MANDAL S,XU H,KLEINMAN D L,et al.Agent-based distributed framework for collaborative planning [J].Aerospace Conference,2010:1-11.
[3]FEILI Y,F(xiàn)ANG T,KRISHNA R P,Integration of a holonic organizationalcontrolarchitecture and multi-objective evolutionary algorithm for flexible distributed scheduling[J].IEEE Transactionson Systems,Man and Cybernetics-Part A:Systems and Humans,2008,38(5):1001-1017.
[4]FEILI Y,F(xiàn)ANG T,KRISHNA R P.A novel congruent organizational design methodology using group technology and a nested genetic algorithm[J].IEEE Transactions on Systems,Man and Cybernetics-Part A:Systems and Humans,2006,36(1):5-18.
[5]ZHANG Y Z,ZHANG L,DU Z Q.Distributed blackboard decision-making framework for collaborative planning based on nested genetic algorithm[J].Journal of Systems Engineering and Electronics,2015,26(6)1236-1243.
[6]SCHEIDT D ,SCHULTZ K.On optimizing command and control structures,proceedings to 16th ICCRTS:collective C2 in multinational civil-military operations[C]//Québec City,Canada:Command and Control Research Program(CCRP),2011:21-23.
[7]VASSILIOUMS.TheevolutiontowardsdecentralizedC2[C]//Proceedings to 15th ICCRTS:The Evolution of C2,Santa Monica,CA.,CCRP,2010:22-24.
[8]INDIRAMMA M,ANANDAKUMAR K R.Collaborative decision making framework for multi-agent system[C]//International Conference on Computer&Communication Engineering,2008:1140-1146..
[9]YASUDA K,HU L,YIN Y.A grouping genetic algorithm for the multi-objective cell formation problem[J].International Journal of Production Research,2005,43(4):829-853.
[10]JAMES T L,BROWN E C ,KEELING K B.A hybrid grouping genetic algorithm for the cell formation problem[J].Computers&Operations Research,2007,30(7):2059-2079.
[11]TUNNUKIJ T,HICKS C.An Enhanced Grouping Genetic Algorithm for solving the cell formation problem[J].International Journal of Production Research,2009,47(7):1989-2007.
[12]MAHDAVI I,MOHAMMAD M P,MAGHSUD S,et al.Genetic algorithm approach for solving a cell formation problem in cellular manufacturing[J].Expert Systems with Applications,2009,36(3):6598-6604.
[13]FENG C,LIU L,BURNS S.Using genetic algorithms to solve construction time-cost trade-off problems.J.Comput[J].Civil Eng.,1997,11(3):184-189.
[14]ELBELTAGIA E,HEGAZYB T,GRIERSON D.Comparison among five evolutionary-based optimization algorithms[J].Advanced Engineering Informatics,2005,19(1):43-53.
A Collaborative Task Decision-making Method Based on Blackboard Framework
LIU Jie1,ZHANG Yao-zhong2
(1.China Electronics Technology Group Corporation Information Science Academy,Beijing 100086,China;2.School of Electronics and Information,Northwestern Polytechnical University,Xi’an 710129,China)
Blackboard-based distributed command and control network brings a new method to complete the task assignment problem in the naval war.By forming the distributed command and control network of naval war,the system load of the naval war which many aircraft carrier groups take part in is studied,and then the mathematic model of multi-platform task decisions problem is given.A new nested-genetic algorithm is used to simulate the progress of the decision-making.The numerical result shows that the proposed blackboard-based distributed command and control framework can obtains a near-optimal solution for the multi-platform task decisions problem.It will provide groundwork for future research on the task decisions in the future naval collaboration.
distributed collaborative planning,blackboard,decision maker,distinction variability
TP311.5
A
10.3969/j.issn.1002-0640.2017.11.10
1002-0640(2017)11-0043-06
2016-09-23
2016-11-21
航空科學(xué)基金資助項(xiàng)目(2016ZC53031)
劉 杰(1983- ),女,安徽蕪湖人,工程師。研究方向:通信與信息系統(tǒng)開發(fā),導(dǎo)航微系統(tǒng),復(fù)雜系統(tǒng)建模分析等。