基于DCSP的編隊武器兼容性約束協調*

隋江波，高波，薛魯強

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

0 引言

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

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

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

1．1 CSP 與DCSP

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

設有 n 個變量 x1，x2，…，xn，各變量相應的值域為 D1，D2，…，Dn，變量間的約束關系由 C1，C2，…，Cm表示，其中每個約束包含集合{x1，x2，…，xn}的一個子集{xi，…，xj}和一個約束關系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);變量間的約束關系分布在Agent內或Agent之間，當Al知道約束關系 Ck時，表示為Known(Ck，Al)。DCSP的解是分配給問題中所有變量的一組滿足Agent間及Agent內的所有約束的賦值，即?Ai，?xj存在關系 belongs(xj，Ai)，當 xj的賦值是 dj∈Dj時，?Ck，?Al，Known(Ck，Al)都有 Ck被滿足［7］。

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

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

式中:

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

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

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

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

2 算法設計

2.1 求解DCSP的AB算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法步驟如下:

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

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

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

3 算法仿真與分析

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

續表Continued table

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

按照目標Agent的威脅值排序對各個Agent變量進行新的賦值更新，并進行約束一致性檢查，最終得到的解為:x1=6，x2={7，16}，x3=2，x4=28，x5={5，14}，x6=1，x7=25，x8=19，x9=15，x10={10，24}。

最終可以提交的作戰方案只有13個。從仿真結果來看，基于異步回溯的約束滿足算法具有下述優點:在滿足作戰方案之間兼容性約束的條件下，能夠將作戰效能更高的方案分配給目標;在滿足作戰方案之間兼容性約束的條件下，能夠對相對威脅值大的目標分配更多的作戰方案;是一種分布式約束滿足算法，在某些武器受損導致方案不能執行的情況下，依舊能夠對其他方案之間的兼容性約束滿足進行處理。

4 結束語

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

［1］ 毛昭軍，李云芝．基于多agent系統的艦艇編隊防空輔助決策系統［J］．系統工程與電子技術，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］ 王勇，蔡自興，周育人，等．約束優化進化算法［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］．安徽:中國科學技術大學，2007．

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