隋江波，高波，薛魯強

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

0 引言

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

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

1 編隊武器兼容性約束滿足問題

1．1 CSP 與DCSP

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

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

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

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

1．2 編隊武器兼容性約束滿足問題建模

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

式中:

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

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

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

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

2 算法設(shè)計

2.1 求解DCSP的AB算法

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

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

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

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

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

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

作為一個分布式約束滿足問題，編隊武器兼容性約束滿足還具有自身特點:

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

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

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

表1 異步回溯搜索過程Table 1 Asynchronous backtracking progress

(4)變量的值域為{0，1}。當變量取值0時，表示方案禁用;當變量取值1時，表示方案可用;

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

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

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

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

n個來襲目標表示為 T1，T2，…，Tn，每個目標Agent對應一個變量xi，變量的值域?qū)鱾€目標的作戰(zhàn)方案序列號。例如目標T3所對應的作戰(zhàn)方案為{A2，A8，A15}，則變量 x3對應的值域為{2，8，15}。變量間的約束關(guān)系仍用約束矩陣C表示。

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

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

算法步驟如下:

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

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

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

3 算法仿真與分析

假設(shè)編隊武器資源分配算法生成30個方案對10個來襲目標進行攔截，每個方案對應一個目標，目標按照威脅值由高到低標記為T1～T10，對同一目標，序號排前的作戰(zhàn)方案作戰(zhàn)效能高。可以得到目標 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

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

按照目標Agent的威脅值排序?qū)Ω鱾€Agent變量進行新的賦值更新，并進行約束一致性檢查，最終得到的解為: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個。從仿真結(jié)果來看，基于異步回溯的約束滿足算法具有下述優(yōu)點:在滿足作戰(zhàn)方案之間兼容性約束的條件下，能夠?qū)⒆鲬?zhàn)效能更高的方案分配給目標;在滿足作戰(zhàn)方案之間兼容性約束的條件下，能夠?qū)ο鄬ν{值大的目標分配更多的作戰(zhàn)方案;是一種分布式約束滿足算法，在某些武器受損導致方案不能執(zhí)行的情況下，依舊能夠?qū)ζ渌桨钢g的兼容性約束滿足進行處理。

4 結(jié)束語

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

［1］ 毛昭軍，李云芝．基于多agent系統(tǒng)的艦艇編隊防空輔助決策系統(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］ 賀利堅，張偉，石純一．DCSP和DCOP求解研究進展［J］．計算機科學，2007，34(11):132－136．

［7］ 王勇，蔡自興，周育人，等．約束優(yōu)化進化算法［J］．軟件學報，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］ 王秦輝．約束滿足及其分布式求解和應用研究［D］．安徽:中國科學技術(shù)大學，2007．

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