Vol.24 No.4 陈梦等：并行设计中冲突的一致性检测算法 481 定理2若c[u>c',4,2是u的一个分割，即4 模型的收敛性.结合定理2可以进一步降低冲 +☑，≠0,4Uh=u及4∩2=☑，则一定存在 突检测的复杂性，提高算法的效率. c",使得c[u>c",c"[w>c' 算法2冲突的一致性检测算法. 证明略. PROC Consis 定理2表明了将独立事件单独处理，不会 A=BUE 影响最终的结果，因而可以将相对独立的约束 WHILE DO 关系进行进一步分割，当独立分割集各自的局 NUM-num(A)） 部一致性满足时，全局一致性得到保证， IFe∈E and 'eccn THEN执行e 令Y=BUE,符号表示集合Y中元素的数 Fnum(A)<NUM THEN发生冲突，结 令 束检测 算法1 ELSE A=A-(eve)and eSc PROC Sep END WHILE j=0 END PROC. FOR i=1 to |Y DO visited [Y ]=False 设计变量按照算法2，当不发生冲突时，得 FOR i=1 to DO 到的最终情态集为设计变量的一致性区间；否 IF visited[Y]=False THEN new A[+]{建立 则，给出发生冲突的变量与约束 独立事件集合} 遍历以Y为顶点的连通图，写人独立事件 2应用实例 集4A] 在某部件各个质量模块的布局设计问题 END FOR 中，既需要考虑重量要求；同时又要兼顾质心约 END PROC 变量即为约束集合中独立事件集的数目， 束以及转动惯量约束.图1为某部件布局的简 化模型，包括模块1、模块2和模块3三个模块. 通过确定独立事件，可以缩减冲突检测模型的 规模，加快问题的解决在模型状态转换的过程 设三者的质量分别为m1,m2和m;模块1的质心 距离坐标原点的距离为r,模块2的质心距离坐 中，采用区间算法的方法，进一步加快冲突的查 标原点的距离为r 找 定义11fR→R为一个映射，称F:I(Fy一 F)为映射f的区间扩展，若满足对于II∈ IF),r∈L,∈I,,r∈In∈IF),下式成立：r r2,…,ra)FI1,2,…,In). 图1某部件布局的简化模型 定义12R上的关系p,将p估计函数记作 Fig.1 Simple model of the component location apx(p),apx(p)为包含区间p的最小F区间. 定义13R上的关系p,记p的收缩函数关 尺寸约束：r+r2≤50， 系p:lF)→lF),p(w=apx(pn. 质心约束：mr1=m, 关系p可以是一个区间，也可以是一个映 转动惯量约束：m+mr=J. 射.当p是一个映射时，pnu的意义为u在映射p 其中变量的取值范围满足如下要求：∈ 的、在作用下而产生的结果. [22,40],2∈[13.7,25]，m1∈[2.71,8.98]，m2∈ 定理3对于(u,y,p)eI(F),以下性质成立： [4.34,14.4] p(u)Cu (1) 建立冲突检测模型如图2所示初始变量的 uop=p(u)Op (2) 取值范围由库所R,R,M,M表示；约束关系 uCv→p(w)Cp(y） (3) r+r2≤50，mr1=mr,mr+m22=J分别用变迁 p((u)=p(w) (4) T,T,T表示.根据定理3与算法2，采用区间算 证明略. 法进行冲突一致性检测时，可以串行执行变迁 定理3保证了采用区间算法求解冲突检测 过程，从而直接发现导致冲突的约束关系，通过 放松或改变约束条件消除冲突公 陈梦等 并行设计 中冲 突 的一致性检测算法 定 理 若 。 尸， ， 是 的一个分割 ， 即 羊 ， 。 羊 ， “ 跳 及 二 ， 则一定存在 ，， ， 使得 ，，， ，， 几 证 明 略 定理 表 明 了将独 立事件单独处理 ， 不会 影响最终的结果 ， 因而可 以将相对独 立 的约束 关系进行进一步分割 ， 当独 立分割集各 自的局 部一致性满足 时 ， 全局 一致性得到保证 ， 令 ， 符号 习表示集合 中元素的数 目 算法 川 到 口 』建立 独立事件集合 遍历 以 为 顶点 的连 通 图 ， 写人独立 事件 集 ’ 变量即为约束集合 中独 立事件集 的数 目 ， 通过确定独 立事件 ， 可 以 缩减 冲突检测 模型 的 规模 ， 加快问题的解决 在模型状态转换的过程 中 ， 采用 区 间算法 的方法 ， 进一步加快冲突的查 找 定 义 一 为一个映射 ， 称 月 一 双刃 为映射厂的 区 间扩展 ， 若满足对于五二… 任 双月 ， 任石乃任几 ，… ， 任 任双月 ， 下式成立 ， 八 ，… ，乙 任尸仅二 ，… 定 义 上 的关系 ， 将 估计 函数记作 伽 ， 叩 勿 为包含 区 间 的最小 区 间 定 义 上 的关系 ， 记 的收缩 函数关 系声峨月 月 一 ， 声 一 勿 · 关系 可 以 是一个 区 间 ， 也 可 以 是一个 映 射 当 是一个映射时 ， 。 的意义为 在 映射户 的 、 在作用下 而产生 的结果 定 理 对于 ，扔任双月 ” ， 以 下性质成立 声 。 一声 冷万 声力 月挤 二 声 证 明 略 定理 保证 了采用 区 间算法求解 冲突检测 模型 的收敛性 结合定理 可 以进一步降低 冲 突检测 的复杂性 ， 提高算法 的效率 算法 冲突的一 致性检测算法 叼 任 三 ， 执行 发生 冲突 ， 结 束检测 一 ‘ 月 设计变量按照 算法 ， 当不发生 冲突时 ， 得 到的最终情态集为设计变量 的一致性 区 间 否 则 ， 给 出发生 冲突的变量与约束 应用实例 在 某 部件各个质量模 块 的布局 设计 问题 中 ， 既需要考虑重量要求 同时又要兼顾质心 约 束 以及转动惯量约束 图 为某部件布局 的简 化模型 ， 包括模块 、 模块 和模块 三个模块 设三者 的质量分别 为 ，， 和 模块 的质心 距离坐标原点的距离为 ，， 模块 的质心距离坐 标原点 的距离为 口口 曰日 图 某部件布局 的简化模型 · 尺 寸约束 八‘ ， 质心 约束 ，八 ， 转动 惯量约束 对 雌 其 中变 量 的取值 范 围满 足 如 下 要 求 ， ， 八 任 ， ， 任 ， ， 任 ， 建立 冲突检测模型 如 图 所示 初始变量 的 取 值 范 围 由 库 所凡尸，肠 ，从 表 示 约 束 关 系 ‘ ， ， 八 ， 武 污 分 别 用 变 迁 不工 ，兀表示 根据定理 与算法 ， 采用 区 间算 法进行 冲突一致性检测 时 ， 可 以 串行执行变迁 过程 ， 从而直接发现导致 冲突的约束关系 ， 通过 放松或改变约束条件消除冲突