基于DCSP的編隊(duì)武器兼容性約束協(xié)調(diào)*

隋江波，高波，薛魯強(qiáng)

(海軍航空工程學(xué)院a．指揮系;b.兵器科學(xué)與技術(shù)系，山東煙臺(tái) 264001)

0 引言

編隊(duì)武器兼容性約束，是由于編隊(duì)多平臺(tái)多種軟、硬武器之間在作戰(zhàn)空域、作戰(zhàn)時(shí)域和作戰(zhàn)頻域上相互干擾而產(chǎn)生的武器之間的沖突約束，最終可能導(dǎo)致武器作戰(zhàn)使用失敗。如何解決編隊(duì)武器兼容性約束是編隊(duì)作戰(zhàn)武器協(xié)同運(yùn)用決策問(wèn)題的關(guān)鍵技術(shù)之一。文獻(xiàn)［1］提出了基于多智能體(multi-agent system，MAS)技術(shù)的分布式編隊(duì)防空輔助決策系統(tǒng)，并對(duì)編隊(duì)中各平臺(tái)自身防空計(jì)劃采用并行比較消解沖突的方法，實(shí)現(xiàn)了編隊(duì)防空計(jì)劃中本艦武器兼容性約束的協(xié)調(diào)，但對(duì)編隊(duì)平臺(tái)之間的武器兼容性約束問(wèn)題未能解決。

編隊(duì)武器兼容性約束協(xié)調(diào)，目的是使編隊(duì)作戰(zhàn)方案中各類武器能夠相互兼容，不發(fā)生沖突，保證作戰(zhàn)效能的充分發(fā)揮。編隊(duì)多種軟硬武器資源分布于編隊(duì)內(nèi)部多個(gè)平臺(tái)之上，它們之間的交互與協(xié)同主要依靠實(shí)時(shí)通信。因而，編隊(duì)武器兼容性約束協(xié)調(diào)可以作為一個(gè)處于分布式環(huán)境中的約束滿足問(wèn)題(constraint satisfaction problem，CSP)［2］來(lái)研究。本文提出了一種基于異步回溯(asynchronous backtracking，AB)［3］的分布式約束滿足算法，對(duì)編隊(duì)武器兼容性約束滿足問(wèn)題應(yīng)用異步回溯獲得一個(gè)初始可行解，然后以作戰(zhàn)效能最優(yōu)為原則，增添新的方案，并進(jìn)行約束一致性檢查，逐步擴(kuò)展可行解為全局滿意解，最終得到不存在武器兼容性約束的編隊(duì)協(xié)同作戰(zhàn)方案。

1 編隊(duì)武器兼容性約束滿足問(wèn)題

1．1 CSP 與DCSP

CSP 是 1974 年 Montanari［4］在圖像處理中首先提出的，它是由一系列變量、變量相應(yīng)的值域以及變量之間的約束關(guān)系組成，目標(biāo)是為這些變量找到一組或多組滿足所有約束關(guān)系的賦值［5］。

設(shè)有 n 個(gè)變量 x1，x2，…，xn，各變量相應(yīng)的值域?yàn)?D1，D2，…，Dn，變量間的約束關(guān)系由 C1，C2，…，Cm表示，其中每個(gè)約束包含集合{x1，x2，…，xn}的一個(gè)子集{xi，…，xj}和一個(gè)約束關(guān)系R?Di×…×Dj。求解CSP就是尋找一組或全部對(duì)所有變量的賦值，使所有的約束都得到滿足［6］。

分布式約束滿足問(wèn)題(distributed constraint satisfaction problem，DCSP)是變量和約束都分布在不同自治Agent中的CSP，其定義如下:

n個(gè) Agent表示為 A1，A2，…，An，m 個(gè)變量為x1，x2，…，xm，m 個(gè)變量的值域?yàn)?D1，D2，…，Dm，變量間的約束仍用C表示;每個(gè)Agent有一個(gè)或多個(gè)變量，每個(gè)變量 xj屬于一個(gè)Ai，表示為 belongs(xj，Ai);變量間的約束關(guān)系分布在Agent內(nèi)或Agent之間，當(dāng)Al知道約束關(guān)系 Ck時(shí)，表示為Known(Ck，Al)。DCSP的解是分配給問(wèn)題中所有變量的一組滿足Agent間及Agent內(nèi)的所有約束的賦值，即?Ai，?xj存在關(guān)系 belongs(xj，Ai)，當(dāng) xj的賦值是 dj∈Dj時(shí)，?Ck，?Al，Known(Ck，Al)都有 Ck被滿足［7］。

1．2 編隊(duì)武器兼容性約束滿足問(wèn)題建模

假設(shè)編隊(duì)武器資源總的分配方案為A，有

式中:

m為交戰(zhàn)方案數(shù)量，n為目標(biāo)數(shù)量。由作戰(zhàn)方案的唯一性，即每個(gè)方案都只針對(duì)一個(gè)目標(biāo)進(jìn)行打擊，可知矩陣A的各個(gè)行向量中只有一項(xiàng)為1，其余各項(xiàng)為0。如果將每一個(gè)作戰(zhàn)方案都作為一個(gè)Agent，則每個(gè)方案Agent均對(duì)應(yīng)唯一的變量，記為xi，i=1，2，…，m。

變量的值域記為 D={0，1}，當(dāng)xi=0時(shí)，該作戰(zhàn)方案取消，當(dāng)xi=1時(shí)，該方案準(zhǔn)備執(zhí)行。

編隊(duì)武器之間的兼容性約束，是由于武器作戰(zhàn)使用過(guò)程的火力沖突、資源共享沖突等引起的，與武器自身沒(méi)有必然聯(lián)系，只有在確定了武器的作戰(zhàn)方案后，預(yù)先模擬估計(jì)武器使用中可能發(fā)生沖突的各種因素，如彈道分布、電磁頻譜分布、作戰(zhàn)時(shí)間等，并與其他武器作戰(zhàn)方案進(jìn)行比較，才能得到武器的兼容性情況。因而編隊(duì)武器兼容性問(wèn)題即為編隊(duì)武器作戰(zhàn)方案之間的約束沖突關(guān)系，記為約束矩陣C，有

編隊(duì)武器兼容性約束滿足問(wèn)題的求解就是尋找一組合適的編隊(duì)武器資源分配方案，使其能夠避免武器之間的相互沖突，并對(duì)來(lái)襲目標(biāo)進(jìn)行有效攔截，更具體一點(diǎn)，就是尋找一組對(duì)方案Agent變量的賦值，使其滿足約束矩陣C中所有約束關(guān)系。

2 算法設(shè)計(jì)

2.1 求解DCSP的AB算法

Yokoo在文獻(xiàn)［8］中對(duì)求解DCSP的各種算法進(jìn)行了詳細(xì)的分析與比較，如AB算法、異步弱承諾搜索 (asynchronous weak-commitment search，AWS)［9］和分布式逃逸算法(distributed breakout，DB)［10］等。這些算法基本上是傳統(tǒng)的約束滿足問(wèn)題的求解算法的分布式擴(kuò)展，其中異步回溯算法是比較常見(jiàn)的一種搜索算法。

在約束滿足問(wèn)題的求解中，如果首先對(duì)變量的一個(gè)子集進(jìn)行一次賦值分配，使其滿足子集中所有變量間的約束，那么這樣的賦值分配就可以稱為一個(gè)局部解。通過(guò)逐個(gè)地增加新的滿足局部解子集中所有變量間約束的變量的賦值，直至擴(kuò)展局部解為全局解，就是問(wèn)題的整個(gè)求解過(guò)程。當(dāng)一個(gè)新的變量的所有賦值都不能滿足局部解子集中的約束時(shí)，就更新最近一個(gè)添加到局部解子集中變量的賦值，這一行為稱為回溯搜索［11］?；厮菟阉魇且粋€(gè)簡(jiǎn)單的深度優(yōu)先樹(shù)搜索算法。

異步回溯算法是由求解約束滿足問(wèn)題的回溯算法而來(lái)，所不同的是，異步回溯算法具有分布性和異步性。分布性是指問(wèn)題僅使用局部通信完成求解，不設(shè)固定的中心Agent對(duì)求解過(guò)程進(jìn)行集中控制;異步性是指Agent異步執(zhí)行和通信，不存在空閑等待其他Agent的時(shí)間。Agent間通信的主要消息類型是ok?消息和nogood消息，ok?消息用來(lái)傳遞當(dāng)前的變量值，nogood消息用來(lái)傳遞新產(chǎn)生的約束。

在異步回溯算法中，變量的優(yōu)先序是預(yù)先定義好的，一般由變量標(biāo)識(shí)的字母順序確定優(yōu)先序，也就是說(shuō)，字母表中排在前面的字母具有較高的優(yōu)先序。高優(yōu)先序Agent通過(guò)ok?消息把它的當(dāng)前賦值傳遞給友鄰低優(yōu)先序Agents。每個(gè)Agent還要維護(hù)一個(gè)agent_view，這是用來(lái)記錄其他Agents的當(dāng)前賦值的。如果一個(gè)Agent的當(dāng)前變量賦值與較高優(yōu)先權(quán)Agent的賦值不一致，該Agent需要更改賦值。如果該Agent沒(méi)有與較高優(yōu)先權(quán)Agent變量值相一致的賦值，那么就產(chǎn)生一個(gè)新的約束，并發(fā)送nogood消息給高優(yōu)先序Agent;于是高優(yōu)先序Agent改變它的當(dāng)前賦值［12］。

在算法中ok?消息只能從高優(yōu)先序Agent發(fā)送給低優(yōu)先序Agent;當(dāng)產(chǎn)生nogood時(shí)，也是nogood中優(yōu)先序最低的Agent接收到nogood消息。AgentAi接收消息ok?和nogood，檢查agent_view，以及回溯的過(guò)程如表1所示。

2．2 基于AB的編隊(duì)武器兼容性約束滿足算法

作為一個(gè)分布式約束滿足問(wèn)題，編隊(duì)武器兼容性約束滿足還具有自身特點(diǎn):

(1)每個(gè)方案Agent都只控制一個(gè)變量;

(2)方案之間的約束都是二元的;

(3)每個(gè)方案Agent都知道所有和自己變量相關(guān)的約束;

表1 異步回溯搜索過(guò)程Table 1 Asynchronous backtracking progress

(4)變量的值域?yàn)閧0，1}。當(dāng)變量取值0時(shí)，表示方案禁用;當(dāng)變量取值1時(shí)，表示方案可用;

(5)方案Agent的優(yōu)先序由目標(biāo)威脅等級(jí)和方案對(duì)目標(biāo)的作戰(zhàn)效能決定。

因此，采用AB算法來(lái)解決編隊(duì)軟硬武器兼容性約束滿足問(wèn)題具有可行性。但還需要根據(jù)編隊(duì)軟硬武器兼容性約束滿足問(wèn)題的特點(diǎn)對(duì)AB算法進(jìn)行改進(jìn)。

由于Agent變量的值域?yàn)閧0，1}，當(dāng)變量xi和xj均取值為1而產(chǎn)生不兼容約束時(shí)，低優(yōu)先級(jí)變量xj將重新選擇取值為0，此時(shí)必然兼容，即滿足二者之間的約束條件。這樣執(zhí)行的后果，將會(huì)導(dǎo)致算法沒(méi)有回溯行為，最終變量賦值雖然滿足所有方案之間的約束關(guān)系，但大部分低優(yōu)先級(jí)的Agent方案將被禁用，這樣可能會(huì)出現(xiàn)威脅值大的目標(biāo)有多個(gè)Agent進(jìn)行攔截，而威脅值小的目標(biāo)卻沒(méi)有Agent攔截的情況，貽誤了戰(zhàn)機(jī)，降低了編隊(duì)整體作戰(zhàn)效能。

為解決這一問(wèn)題，將以作戰(zhàn)方案為Agent的編隊(duì)軟硬武器兼容性約束滿足問(wèn)題轉(zhuǎn)化為以目標(biāo)為Agent的編隊(duì)軟硬武器兼容性約束滿足問(wèn)題，具體建模如下:

n個(gè)來(lái)襲目標(biāo)表示為 T1，T2，…，Tn，每個(gè)目標(biāo)Agent對(duì)應(yīng)一個(gè)變量xi，變量的值域?qū)?yīng)各個(gè)目標(biāo)的作戰(zhàn)方案序列號(hào)。例如目標(biāo)T3所對(duì)應(yīng)的作戰(zhàn)方案為{A2，A8，A15}，則變量 x3對(duì)應(yīng)的值域?yàn)閧2，8，15}。變量間的約束關(guān)系仍用約束矩陣C表示。

此時(shí)結(jié)合AB算法設(shè)計(jì)新的分布式編隊(duì)軟硬武器兼容性算法如表2所示。

表2 基于異步回溯的編隊(duì)武器兼容性約束協(xié)調(diào)算法過(guò)程Table 2 Constraint satisfaction algorithm based on AB(asynchronous backtracking)

算法步驟如下:

(1)對(duì)以目標(biāo)為Agent的編隊(duì)軟硬武器兼容性約束問(wèn)題進(jìn)行異步回溯搜索，獲得問(wèn)題的一個(gè)可行解，此時(shí)解中的變量和變量的賦值分別代表一個(gè)目標(biāo)和該目標(biāo)的一個(gè)作戰(zhàn)方案。

(2)從最高優(yōu)先序Agent開(kāi)始，按照變量賦值所對(duì)應(yīng)方案作戰(zhàn)效能的高低，嘗試對(duì)變量增添一個(gè)新的賦值，進(jìn)行約束一致性檢查。若滿足一致性的要求，則對(duì)目標(biāo)Agent插入該新賦值所對(duì)應(yīng)的方案;若不滿足約束一致性要求，則對(duì)下一個(gè)賦值進(jìn)行嘗試，直到能夠增添一個(gè)新的變量賦值或遍歷值域中所有的變量賦值為止。

(3)繼續(xù)下一優(yōu)先序目標(biāo)Agent的變量賦值增添程序。

3 算法仿真與分析

假設(shè)編隊(duì)武器資源分配算法生成30個(gè)方案對(duì)10個(gè)來(lái)襲目標(biāo)進(jìn)行攔截，每個(gè)方案對(duì)應(yīng)一個(gè)目標(biāo)，目標(biāo)按照威脅值由高到低標(biāo)記為T1～T10，對(duì)同一目標(biāo)，序號(hào)排前的作戰(zhàn)方案作戰(zhàn)效能高?？梢缘玫侥繕?biāo) Agent變量如下:x1={6，22}，x2={7，11，16，30}，x3={2}，x4={8，28}，x5={5，14，17}，x6={1}，x7={3，21，25}，x8={4，19，26，27，19}，x9={9，15，23}，x10={10，12，13，18，20，24}。

相互沖突的方案判斷如表3所示。

表3 相互沖突的武器方案表Table 3 Operational plans with conflict

續(xù)表Continued table

運(yùn)行算法第一步得到的初始可行解為:x1=6，x2=7，x3=2，x4=28，x5=5，x6=1，x7=25，x8=19，x9=15，x10=10。

按照目標(biāo)Agent的威脅值排序?qū)Ω鱾€(gè)Agent變量進(jìn)行新的賦值更新，并進(jìn)行約束一致性檢查，最終得到的解為:x1=6，x2={7，16}，x3=2，x4=28，x5={5，14}，x6=1，x7=25，x8=19，x9=15，x10={10，24}。

最終可以提交的作戰(zhàn)方案只有13個(gè)。從仿真結(jié)果來(lái)看，基于異步回溯的約束滿足算法具有下述優(yōu)點(diǎn):在滿足作戰(zhàn)方案之間兼容性約束的條件下，能夠?qū)⒆鲬?zhàn)效能更高的方案分配給目標(biāo);在滿足作戰(zhàn)方案之間兼容性約束的條件下，能夠?qū)ο鄬?duì)威脅值大的目標(biāo)分配更多的作戰(zhàn)方案;是一種分布式約束滿足算法，在某些武器受損導(dǎo)致方案不能執(zhí)行的情況下，依舊能夠?qū)ζ渌桨钢g的兼容性約束滿足進(jìn)行處理。

4 結(jié)束語(yǔ)

編隊(duì)多平臺(tái)要實(shí)現(xiàn)協(xié)同作戰(zhàn)，必須解決武器之間的兼容性約束問(wèn)題。本文通過(guò)研究編隊(duì)武器兼容性約束滿足算法，進(jìn)一步對(duì)編隊(duì)武器資源分配方案進(jìn)行優(yōu)化。仿真結(jié)果表明，該算法滿足了編隊(duì)武器兼容性協(xié)調(diào)的2個(gè)基本要求:最終武器作戰(zhàn)方案之間不能存在武器兼容性沖突問(wèn)題;在作戰(zhàn)方案之間不存在兼容性沖突問(wèn)題的前提下，盡可能提高編隊(duì)整體作戰(zhàn)效能?；贏B的編隊(duì)武器兼容性約束滿足算法研究的是編隊(duì)武器作戰(zhàn)方案具備5個(gè)特點(diǎn)的簡(jiǎn)單的編隊(duì)武器兼容性約束問(wèn)題，對(duì)復(fù)雜條件下的編隊(duì)武器兼容性約束問(wèn)題，尚需進(jìn)一步研究。

［1］ 毛昭軍，李云芝．基于多agent系統(tǒng)的艦艇編隊(duì)防空輔助決策系統(tǒng)［J］．系統(tǒng)工程與電子技術(shù)，2006，28(11):1704－1708．

［2］ ZHANG W X，WANG G D，XING Z，et al．Distributed Stochastic Search and Distributed Breakout:Properties，Comparison and Applications to Constraint Optimization Problems in Sensor Networks［J］．Artificial Intelligence，2005，161(1－2):55－87．

［3］ YOKOO M，ISHIDA T．Search Algorithms for Agents［M］．Multiagent Systems，Springer，1999:165－199．

［4］ MONTANARI U．Networks of Constraints:Fundamental Properties and Applications to Picture Processing［J］．Information Sciences，1974，7(2):95－132．

［5］ DECHTER R，PEARL J．Network-based Heuristics for Constraint-satisfaction Problems［J］．Artificial Intelligence，1987，34(1):1－38．

［6］ 賀利堅(jiān)，張偉，石純一．DCSP和DCOP求解研究進(jìn)展［J］．計(jì)算機(jī)科學(xué)，2007，34(11):132－136．

［7］ 王勇，蔡自興，周育人，等．約束優(yōu)化進(jìn)化算法［J］．軟件學(xué)報(bào)，2009，20(1):11－29．

［8］ YOKOO M，HIRAYAMA K．Algorithms for Distributed Constraint Satisfaction:A Review［J］．Autonomous A-gents and Multi-Agent Systems，2000，3(2):185－207．

［9］ YOKOO M，DURFEE E H，ISHIDA T，et al．The Distributed Constraint Satisfaction Problem:Formalization and Algorithms［J］．IEEE Transactions on Knowledge Data Engineering，1998，10(5):673－685．

［10］ YOKOO M．Asynchronous Weak-Commitment Search for SolvingDistributed ConstraintSatisfaction Problems［C］∥Proceedings of the First International Conference on Principles and Practice of Constraint Programming，Berlin，Springer-Verlag，1995:88－102．

［11］ 王秦輝．約束滿足及其分布式求解和應(yīng)用研究［D］．安徽:中國(guó)科學(xué)技術(shù)大學(xué)，2007．

［12］ 王秦輝，陳恩紅，王煦法．分布式約束滿足問(wèn)題研究及其進(jìn)展［J］．軟件學(xué)報(bào)，2006，17(10):2029－2039．