一种基于最小冲突集的约束冲突消解方法

刘晓平， 季 浩， 石 慧

（合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）

在协同设计中，不同设计者在网络化平台上依据各自经验和理解对产品进行分工设计，实际过程中存在着大量相互影响、相互制约的约束关系。笔者所在的团队在多年协同模板理论的研究过程中逐渐发现协同模板中约束关系的复杂 性[1]，当在协作过程中不同的设计选择发生冲突时，如果设计者们对约束信息的组织关系把握不清楚，无疑会增加冲突消解的难度和设计过程的反复，降低协同设计的效率。

为了保证并行产品设计顺利进行，文献[2]采用改进的区间传播算法用于实时在线检测冲突，在约束网络中没有冲突时，给出传播后变量的取值范围。文献[3]提出利用基于最小冲突集修补的算法，求解动态变化的约束满足问题。但事实上都不能使设计者在变更约束的同时清楚了解约束条件之间的关系，而在约束信息发生冲突时，及时、准确地提取约束信息的制约关系、辅助设计者利用已有的知识进行协商调整约束信息是建立以人为中心的冲突消解方法的关键。

本文主要工作是从最小冲突集的角度出发，分析最小冲突集元素个数范围和判定方法，并结合交边算法[4]实现对最小冲突集的提取，通过算例说明最小冲突集，该方法对建立以人为中心进行控制和管理约束信息、消解约束冲突的有效性。

1 相关概念和性质

1.1 相关概念

一个工程设计问题实际上是多个约束条件满足问题，即对满足约束条件

1.2 相关性质

为了方便描述和证明最小冲突集的相关性质，这里先给出交边算法的数学描述和Helly 定理。

下面给出在交边算法中提取最小冲突集时所用到的一些性质：

最小冲突集元素个数k 不小于2 是显然。

若 1k d＞ + ，由最小冲突集的定义知

Ω ( d ,k)= ∅， Ωi( d , k− 1)≠∅， i = 1,… ,， k − 1≥ d+1。

所以最小冲突集的元素个数k 满足2 ≤ k ≤ d+1。

表1 约束冗余的判断方法

对于 L1= L2的情况，通过指向 L1,L2所表示 区域的法向量是否相同来判断冗余。

性质1 说明在d 维约束条件中，如果存在最小冲突集， 其元素个数k 的应该满足 2 ≤ k ≤ d+1。性质2 指出判断元素个数范围为 [2, d+1]的冲突集方法，其证明由交边算法的数学描述中易得。性质3 用来化简冗余约束。在利用交边算法判断原约束集为冲突的同时，利用上述性质提取出最小冲突集和冗余约束。

2 约束冲突消解方法

本文在上述性质的基础上，结合交边算法提取最小冲突集和冗余约束，到达消解约束的目的。以下是约束冲突消解方法：

（1） 根据信息的属性确定约束信息的维数d，由性质2 得最小冲突集的元素个数范围。

（2） 将约束信息用改进的交边算法，进行求解、检测冲突和记录相关信息。改进的交边算法的非形式的描述如下：

Step 6 在记录信息中依据上述的性质，化简冗余约束信息，并提取 2k = 的最小冲突集。

Step 7 选取k s= 的最小冲突集，满足：

Step 8 若 s ≤ d+1，则转Step 7。否则算法结束。

（3） 由记录的信息，去除冗余信息并提取最小冲突集。

（4） 对最小冲突集中的约束序号进行编码，通过对编码的运算，方便以后查找关键的约束信息。

（5） 设计者依照保留最多的约束、指定的约束等准则或要求，进行协商消解冲突。

3 算法示例

下面给出一个算例，假设设计者在进行约束冲突消解时，以保留最多约束条件为准则。

例：

由于线性约束是2 维的，只可能存在元素个数是2 或3 的最小冲突集。通过改进的交边算法判定该约束集是冲突的，并得到如表2 的矛盾信息记录。

表2 矛盾信息记录

对最小冲突集中的约束进行01 编码：

将编码相加得：11010221，因有3 个最小冲突集，每个约束至多参与2 个最小冲突集，所以至少要剔除两个约束，才能使得冲突消解。所以依据保留最多约束条件的准则，应当剔除约束条 件 L2, L3,L6。

图1 约束条件的直观图

4 结 束 语

为了使设计者在协同设计中能清晰地把握约束信息的制约关系，有效地去除冗余信息、消解约束冲突。本文从最小冲突集的角度出发，在分析最小冲突集的相关性质和交边算法的基础上，提出了利用改进交边算法提取最小冲突集，方便设计者按照一定的准则去除冲突约束信息。由于对最小冲突集剔除部分约束信息，需要建立在设计者的相关知识和准则上，并且在约束信息非常多的情况下，设计者不容易利用抽象思维完全把握约束信息之间的关系，而可视化具有细致、完善地展现约束信息，使设计者清晰、直观地了解约束信息之间的关系，所以下一步工作将考虑结合约束信息可视化手段，研究可视约束信息、交互式处理冲突的方法。

[1] 刘晓平, 石 慧, 毛峥强. 协同模板中的信息可视化[J]. 计算机辅助设计与图形学学报, 2005, 17(10)： 2334-2338.

[2] 朱湘毅, 唐 泉, 陈文培, 等. 并行工程中基于约束的冲突检测研究[J]. 机械科学与技术, 2000, 19(5)： 849-852.

[3] 孙吉贵, 高 健, 张永刚. 一个基于最小冲突修补的动态约束满足求解算法[J]. 计算机研究与发展, 2007, 44(12)： 2078-2084.

[4] 宋恩民, 黄文奇. 判断具有多线性约束条件的凸空间是否为空的交边算法[J]. 计算机学报, 1996, 19(9)： 704-708.

[5] Dimitri P Bertsekas, Angelia Nedic, Asuman E Ozdaglar. Convex analysis and optimization [M]. 北京： 清华大学出版社, 2006. 112-165.