基于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．