-
摘要: 本文研究了有向拓扑网络中具有非匹配扰动的二阶多智能体系统固定时间一致跟踪问题. 基于固定时间扰动观测器, 估计系统匹配扰动, 其次引入正弦补偿函数设计非奇异分布协议, 在避免系统奇异性的同时克服了非匹配扰动, 使多智能体系统实现固定时间一致跟踪. 最后通过仿真验证了算法的有效性.Abstract: This paper investigates the fixed-time consensus tracking problem for second-order multi-agent system with mismatched perturbations in directed topology networks. Based on the fixed-time disturbance observer, the system is estimated to match the disturbance. Secondly, a sine compensation function is introduced to design a nonsingular distribute protocol, the unmatched disturbances were overcome while avoiding the singularity of the system, so that the multi-agent system achieves fixed-time consensus tracking. Finally, simulation is included to demonstrate the performance of the new algorithm.
-
对于概念格来说, 即使是一个小的数据集可能产生大量的形式概念[1].这是源于其存在高组合复杂性和结构.最坏的情况可以达到 ($|G|, |M|$分别为对象和属性的总数).此外, 产生的形式概念的数量和概念之间关系的复杂性使得最终格的分析十分困难[2].
为简化概念格, 现有的研究主要采用了知识约简的方法.所谓知识约简, 就是针对不同的目的要求, 保持知识库分类能力不变, 删除其中不相关或不重要的属性, 使知识表示简化的同时又不丢失基本信息.
已有研究者研究了从给定的二元形式背景[3]、决策形式背景[4-5]、模糊形式背景[6-7]、实决策形式背景[8]中约简生成形式概念. Dias和Vieira[9]提出了一种分析概念格约简的方法.它是基于存在于原始与约简后的形式背景, 或概念格间的特有的蕴含集合的.通过这些蕴含集合, 设计的约简方法能够显现数据信息的保持、消失、增加及变化.他们从方法论的角度分析了三类约简技术, 强调了其在转换时的共同之处. Konecny[10]的研究表明, 虽然有各种扩展, Ganter和Wille的概念格属性约简和解释依然是优于基于可辨识矩阵约简的. Singh等[11]提出了一种在形式概念分析中用模糊属性减少形式概念数目的方法.其以香农熵计算模糊形式概念的权重.用计算的权重选择粒约简模糊形式概念.结果表明, 所提出的方法得到的结果与Levenshtein距离法以及区间值模糊形式概念的方法一致, 但计算复杂度更低.因为是基于属性的, 这些方法的结果很难直观地、易于理解地反映出对象——属性关系(即形式概念)的重要程度.
就目前的结果来说, 关注重要概念选择以至于对概念格进行分解的研究较为鲜见. Babin和Kuznetsov[12]引进了概念稳定性来测度概念的重要性. Belohlavek和Macko[1]利用权重研究了重要的概念并讨论其应用. Dias和Viera[13]提出基于连接的对象相似(JBOS)方法约简形式概念的数目. Li等[14]讨论了加权概念格及其应用. Kang等[15]提出一种在不同粒度下减少模糊概念格大小的方法. Li等[16]提出了一种采用K-medoids聚类来压缩近似概念格的方法. Martin等[17]提出一种使用Levenshtein距离测度模糊概念格的变化的方法. Singh等[18]推出了一个使用香农熵来计算给定模糊形式概念的权重的方法, 选择根据所计算出来的权重的粒度约简模糊形式概念. Aswani等[19]新近提出了在形式背景上用非负矩阵分解约简知识, 但仅提出了一个思想, 对矩阵存在与约束条件尚无探讨.
将概念格与因子分析联系起来的是Keprt和Snášel[20].他们提出了基于形式概念分析计算非层次二元因子分析的方法.尽管计算概念格本身也是十分繁杂的, 它仍然帮助加快了二元因子分析的计算. Belohlavek和Vychodil[21]提出了一个有序数据的矩阵分解和因子分析的方法.这些因子对应于输入数据的形式概念成为数量最少的因子, 并可以十分简单的解释分解.
由于图能较好地描述三维CAD模型的几何、拓扑乃至语义信息, 近年来基于图的模型表征和检索方法受到了更多关注[22-23].典型的用于CAD模型检索的工作有属性邻接图[24-27]、完全二分图[28]、扩展特征树[29]等描述子方法.这些基于图的检索方法尽管可以采用各种"图结构"较好地表征模型的几何、拓扑乃至语义信息, 但最终都要通过繁琐的图匹配来实现对应模型间的相似性比较, 十分复杂而耗时, 因此这些检索方法效率很低.虽然有文献[24, 27]对CAD模型用向量化表征在一定程度上可提高匹配和检索效率, 但其只能表达模型的整体形状, 当模型较大型且复杂时, 其局部细节特征描述能力不足, 局部特征信息不突出.检索精度和检索效率存在一定程度的矛盾.徐静等提出了一种基于装配结构相似的零件三维模型检索方法[30], 借鉴化学符号表示零件功能表面、相对位置、朝向以及面与面之间拓扑关系, 并对装配结构进行编码, 建立检索机制, 但随着零件复杂程度增加编码变得十分庞杂.近来朱文博等[31]利用机械零件形状和工艺的特点, 将复杂的机械零件拆分成若干相对简单的形体, 随后再进行匹配检索.然而有些零件形状非常复杂, 使得拆分较困难, 而且拆分后可能破坏形状的完整性, 因此要使该方法具有更广泛的适应性, 还需后续更深入地研究.皇甫中民等[32-33]提出一种基于图谱及空间词袋表征的CAD模型层次特征描述子构建和检索方法, 同时基于图索引过滤机制对三维CAD模型局部检索方法进行了研究.
现有的三维模型检索方法大多关注网格模型.然而, 在制造业中三维实体模型更有可能重用.构造立体几何(Constructive solid geometry, CSG)和边界表示法(Boundary representation, B-rep)是两个流行的三维实体模型描述手段. CSG允许建模者创建一个复杂的表面或用布尔操作合成对象. B-rep是通过一定的限制表示形状的实体建模方法.一个实体集连接表面元素、实体和非实体之间的边界为一体.由于产品模型数据交换标准(STEP)在一个产品的生命周期提供了一种机制来呈现和交换数据, 不同的B-rep模型用STEP很容易交换.鉴于一个三维实体模型的CSG描述是不唯一的, 通常用B-rep表示和分析实体模型[34-35].此外, 面邻接图(Face adjacency graphs, FAGs)可以很容易地从B-rep模型建立, 现有的图或子图匹配可以用于三维模型的形状比较. FAGs是一个有序对是一组用其属性描述模型表面的顶点集, $E_{f}$是一组用其属性描述模型边的边的集合.因此, 一些基于FAGs的三维实体模型检索方法被提了出来[24, 36-39].
然而, 在一个实际的复杂模型中观察到的数以百计的面, 以及其有限的面粒度(如多边形平面和圆柱面), 产生的FAGs具有很大的规模和很高的复杂性.最近提出的解决这个问题的方法是分割三维实体模型为一组大粒度的面区域以取代CAD模型的面[40-41].在三维模型被分解为一组面区域后, 三维形状检索的另一个任务是面区域之间的形状匹配.研究者将区域属性代码引入表示CAD模型的面区域. CAD模型主要是由常规的几何面(如平面、圆柱、圆锥和球体)构成, 机械零件的拓扑结构取决于邻接面的类型, 对CAD模型面和区域描述是可行的.此外, 区域属性代码很容易创建, 并且区域代码的比较比子图匹配的模型形状比较要快.于是, 区域属性代码相似性就是两个比较模型之间的相似性.在面区域方法中, 三维分割对三维形状检索是必不可少的, 因为它能用增加模型元素的粒度来明显降低CAD模型的复杂性, 并且提取的面区域通常包含一些有效模型比较的语义信息[30].尽管如此, 三维分割本身的巨大工作量却也无法回避.本文提出的功能表面划分零件与面区域方法相类似, 重要形式概念确定的关键结构关注关键"分割", 可以有效地减少分割带来的工作量, 提高检索效率.
零件功能表面具有功能和结构的双重属性, 从功能上讲, 功能表面直接体现零件的基本功能; 从几何上讲, 功能表面是实现零件基本功能的最小造型单元, 这些功能表面及其空间布局决定了零件功能的物理结构.因此, 在相似零件检索过程中, 可只用功能表面及其相互关系作为评价零件相似性的特征.
本文拟在功能表面及其相互关系构成的零件工程图结构模型映射的形式背景上研究概念格因子, 进而找出反应零件本质特征的关键结构, 以此提高零件模型检索的效率.
1. 预备知识
概念格存在于形式背景, 形式背景反映的是对象、属性的二元关系, 其实质上是一个关于对象、属性的布尔矩阵.
定义1. 一个布尔代数是一个非空集合$\beta$和两个定义在$\beta$上的二元运算$\vee$与$\wedge$构成的数学系统$(\beta, \vee, \wedge)$, 其满足下列条件:
1) $\forall a, b\in \beta$, $a\vee b=b\vee a$, $a\wedge b=b\wedge a$;
2) , $a\vee (b\wedge c)=(a\vee b)\wedge (a \vee c)$;
3) $\exists 0, 1\in \beta, 0\neq 1$, $\forall a\in \beta$, $a\vee 0=a$, $a\wedge 1=a$;
4) $\forall a\in \beta$, $\exists a^{c} \in \beta$, $a\vee a^{c}=1$, $a\wedge a^{c}=0$.
如果$\beta$只包含两个元素, 则称它为二元布尔代数, 记为$\beta _{0}$.
定义2. 上的矩阵称为布尔矩阵.所有$m$行、$n$列的布尔矩阵构成的集合记为.
定义3. $\beta _{0}$上的一个有序$n$元组是一个$n$维布尔向量.
令$M_{r}= [\mu_{ij}]\in \{0, 1\}^{m\times n}$.
这里被称作第$i$行布尔向量, 称作第$j$列布尔向量.也使用表示的第$i$行($j$列)布尔向量.
定义2[42]. 如果并且$V=[\nu_{ij}]\in\{0, 1\}^{m\times n}$, 矩阵$U$和$V$的布尔和定义为
$ U+V=[\mu_{ij}\vee \nu_{ij}]\in\{0, 1\}^{m\times n} $
(1) 布尔乘积为
$ \begin{align}&B=U\circ V=[b_{ij}]\in\{0, 1\}^{m\times n}, \nonumber\\ &b_{ij}=\vee ^{k}_{t=1}(\mu_{it}\wedge \nu_{tj}) \end{align} $
(2) 定义5[43]. 如果和$M=\{w_{1}, \cdots, w_{n}\}$是对象和属性集, $I$是$G$和$M$间的二元关系, 那么三元组$(G, M, I)$称作形式背景. 的形式概念是一对集合$(A, B), A\subseteq G, B\subseteq M$, 满足
$A'=B$并且.其中$A$称为概念$(A, B)$的外延, $B$称为概念$(A, B)$的内涵.
所有$(G, M, I)$的形式概念集合用${ß}(G, M, I)$表示.
因为$G$和$M$间的二元关系可以用布尔矩阵表示, 所以对应的布尔矩阵也用$I$表示.也就是说, $I$的元$I_{ij}=1$当且仅当$(g_{i}, w_{j})$属于关系$I$, 不属于关系$I$则$I_{ij}=0$.
概念格因子分解将着手于形式背景布尔矩阵的分解, 因此, 下面引入布尔矩阵分解的概念.
布尔矩阵分解的目的是对给定的$I\in\{0, 1\}^{n\times m}$, 找出$U\in\{0, 1\}^{n\times k}$和$V\in\{0, 1\}^{k\times m}$使得
$ I\cong U\circ V $
(3) 这里的$\cong$表示可以按一定程度近似的分解, 也就是说对象$i$有属性$j$当且仅当存在$l$个因子使得$l$应用于$i$和$j$是$l$的一种具体表示.
例1. 表 1是一个形式背景, 它可以表示为布尔矩阵并分解为两个布尔矩阵的乘积.
表 1 一个形式背景Table 1 An example of formal context$a$ $b$ $c$ $d$ $e$ 1 $\times$ $\times$ 2 $\times$ $\times$ $\times$ 3 $\times$ $\times$ $\times$ $\times$ 4 $\times$ $\times$ 为形式背景布尔矩阵..
2. 概念格因子分解及算法
定理1. (乘积展开式)如果$M_{r}$能表示为两个矩阵的布尔乘积, 那么
$ Mr=U\circ V=U[:, 1]\circ V[1, :]+U[:, 2]\circ V[2, :]+ \nonumber\\ \quad \quad \cdots+U[:, k]\circ V[k, :]= \sum\limits_{t=1}^{k}{U[:, t]\circ V[t, :]} $
(4) 证明. 定理可直接由式(1)和(2)得到.
定义6. 如果$(A, B)$是一个形式概念, 则分别对应一个对象(属性)布尔列(行)向量和${\pmb{q}}=[q_{1}~q_{2}~\cdots~q_{n}]$.其中
$ \begin{align*}& p_{i}=\begin{cases} 1,&g\in A:(w\in B)(g, w)\in I \\ 0,&\mbox{否则} \\ \end{cases} \\& q_{j}= \begin{cases} 1,&w\in B:(g\in A)(g, w)\in I \\ 0,&\mbox{否则} \\ \end{cases} \end{align*} $
也可以视为对象(属性)列(行)矩阵.
定理2. 假设$(A, B)$是一个形式概念, ${\pmb{p}}=[p_{1}~ p_{2}~\cdots~p_{m}]^{\rm {T}}$, 是对应的布尔列、行矩阵, 存在
$ {\pmb{p}}\circ{\pmb{q}}=[b_{ij}]\in\{0, 1\}^{m\times n}, b_{ij} =p_{i}\wedge q_{j} $
(5) 证明. 由定义6及布尔矩阵乘积定义可知式(5)成立.
例2. 对例1的形式背景有形式概念$(\{1, 2, 3\}, \{a, b\})$, 则, , .
根据文献[43]所有的对象形式概念集、属性形式概念集定义为
$ O(G, M, I)=\{(\{g\}'', \{g\}')\mid g\in G\}, \nonumber\\ A(G, M, I) =\{(\{w\}', \{w\}'')\mid w\in M \} $
(6) 定义7. 如果$F$是一个形式概念集合, 由属于$F$的概念$(A, B)$的对象布尔列向量为列构成矩阵记为$A_{F}$, 属性布尔行向量为行构成矩阵记为$B_{F}$.
对象、属性形式概念是概念格分解的强制性因子.
定理3[44]. (强制性因子)对, 如果$I=A_{F}\circ B_{F}$, 那么.
定理4. (有限分解)对于形式背景上的对象和属性形式概念$O(G, M, I)$, $A(G, M, I)$, 有, 和为$O(G, M, I), A(G, M, I)$的对象(属性)布尔列(行)矩阵, $k=|O(G, M, I)|, t=|A(G, M, I)|$.
证明. 令$(A_{k}, B_{k})\in O(G, M, I)$是一个形式概念, 我们有和$q_{k}=[q_{1}~q_{2}~\cdots ~q_{n}]$使得.由于$(A_{k}, B_{k})$是对象概念, 所以可以按对象序排序, , 根据定理1式(4): $U[:, 1]\circ V[1, :]+U[:, 2]\circ$ $ V[k, :]=U\circ V=M_{r}$, 其中$p_{k}$除重复的外, 按序对应每个对象, $U[:, k]\circ V[k, :]$覆盖所有"1"矩形, 即映射所有可能的属性, 故有.同理可证属性形式概念成立.
定理5. 对于形式背景$(G, M, I)$, 或者$F=A(G, M, I)$.
证明. 由定理4可直接得到结果.
定理6. (优化因子)如果是$F$概念的布尔列(行)矩阵, 存在$I^{*}$的的概念对象、属性集合包含在的对应概念对象、属性集中, 那么这样循环的$O(G, M, I)$对象概念构成$I$的较$O(G, M, I)$更小的分解.结论对同样成立.
证明. 由定理5知$I=A_{F}\circ B_{F}, F=O(G, M, I)$, 而且, 表明$O(G, M, I)$中的可以加入分解因子集合.当$I^{*}=\mathit{\pmb{0}}$时表明作为分解因子新的对象概念集合已完全能表示$I$. , 显然, 是更小的分解.
对于属性形式概念可以用同样的方法证明.
由于有下列定理的结论, 我们有必要估计分解的近似程度.
定理7[45-46]. 分解布尔矩阵$I$为一个$n\times k$二元矩阵$U$和$k \times m$二元矩阵$V$, $I =U\circ V$, 具有尽可能小$k$的问题是NP-hard, 相应的决策问题(即对给定的$I$和正整数$k$决定是否存在一个分解的具有内在维度$k$)是NP-complete.
假设$C$是一个形式概念集合$C\subseteq {ß}(G, M, I)$, 是由$C$的形式概念覆盖的$I$的1的数量.
因子分解近似程度定义为: $Ap(I, F) = Area(F)/Area({ß}(G, M, I))$.
根据前面的结果, 可以给出概念格因子分解的算法.
算法1. 概念格因子分解算法.
输入. 形式背景$(G, M, I)$布尔矩阵$I$.
输出. 概念格因子集合$F$.
1) 设定形式背景$(G, M, I)$, 对于每一个$g\in G, w\in M$, 求出, ;
2) 计算公共集合$F=O(G, M, I)\cap A(G, M, I)$;
3) 求$I^{*}=I-A_{F}\circ B_{F}$;
4) 如果$I^{*}\neq \textbf{0} $, 对于$(G, M, I^{*})$的每一个, 求出$O^{*}(G, M, I^{*})=\{(\{g\}'', \{g\}')|g\in G\}$和$A^{*}(G, M, I^{*})=\{(\{w\}', \{w\}''|w\in M)\}$;
5) 取$F^{*}=O^{*}(G, M, I^{*})\cap A^{*}(G, M, I^{*})$, 如果有且$C\subseteq A, D\subseteq B, (A, B) \in O(G, M, I)$, 那么$F=F\cup(C, D)$, 继续步骤3)计算;
6) 如果$I^{*}=\textbf{0}$表明有最小分解, $F$即为优化因子概念集合;
7) 如果$I^{*}\neq \textbf{0}$且没有满足$C\subseteq A, D\subseteq B, (A, B)\in O(G, M, I)$, 表明最小分解无法确定, 则可计算近似程度.
例3. 我们以文献[46]中的例子(Example 1)为例来演示算法的求解过程. ,
$O(G, M, I) = \{(\{1, 5\}, \{a, b, d\}), $ $(\{6\}, \{a, b, e\})\}$,
$A(G, M, I) = \{(\{1, 2, 5, 6\}, \{a\})$, , $(\{3, 5\}, \{b, c\})$, , $(\{2, 6\}, \{a, e\})\}$.
$ \begin{align*}I^{*}=\, &\begin{bmatrix} 0&1\\ 0&1\\ 1&0\\ 0&1\\ 1&1\\ 0&0 \end{bmatrix}\circ\begin{bmatrix} 0&1&1&0&0\\ 0&0&0&1&0 \end{bmatrix}= \\[2mm]&\begin{bmatrix} 0&0&0&1&0\\ 0&0&0&1&0\\ 0&1&1&0&0\\ 0&0&0&1&0\\ 0&1&1&1&0\\ 0&0&0&0&0 \end{bmatrix}, \\[2mm]I-I^{*}=\, &\begin{bmatrix} 1&1&0&0&0\\ 1&0&0&0&1\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 1&0&0&0&0\\ 1&1&0&0&1 \end{bmatrix}\end{align*} $
.
$O^{*}(G, M, I^{*})=\{(\{1, 6\}, \{a, b\}), (\{2, 6\}, \{a, $ $e\}), (\{1, 2, 5, 6\}, \{a\}), (\{6\}, \{a, b, e\})\}$,
$A^{*}(G, M, I^{*})=\{(\{1, 2, 5, 6\}, \{a\}), (\{1, 6\}, \{a, $ $b\}), (\{2, 6\}, \{a, e\})\}$.
.
其中有 $\{a, e\})\in $ $A(G, M, I), $ $\{a, e\})\}$
$ \begin{align*}I^{*}=\, &\left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ 0&1&1&1\\ 1&0&0&0\\ 0&1&0&0\\ 1&1&1&0\\ 0&0&1&1 \end{array}} \right]\circ~\left[ {\begin{array}{*{20}{c}} 0&1&1&0&0\\ 0&0&0&1&0\\ 1&0&0&0&0\\ 1&0&0&0&1 \end{array}} \right]=\\ &\qquad\qquad\left[ {\begin{array}{*{20}{c}} 1&0&0&1&0\\ 1&0&0&1&1\\ 0&1&1&0&0\\ 0&0&0&1&0\\ 1&1&1&1&0\\ 1&0&0&0&1 \end{array}} \right], \\& I-I^{*}=\left[ {\begin{array}{*{20}{c}} 0&1&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&1&0&0&0 \end{array}} \right] \end{align*} $
得到$(\{1, 6\}, \{b\})$, 而, 因此概念格分解因子为, .这个例子的分解, 因子仍为属性形式概念.
值得一提的是, 我们这里求出的分解因子并不一定是最优的, 读者容易验证$F=\{(\{1, 5, 6\}, \{a, b\}), (\{1, 2, 4, 5\}, \{d\}), (\{2, 6\}, \{a, e\}), $ 也是一个分解.我们的方法只是确定可以找出一个比原概念格小得多的因子集合.
3. 因子分解应用于零件三维CAD模型检索
零件三维CAD模型的检索可以通过对工程图视图结构模型的"并"运算, 构造零件三维结构模型并进行编码, 通过零件三维模型结构码的匹配实现检索.一般来讲这种编码的量是十分巨大的.因此, 找出反应零件特征的关键结构对提高检索效率是十分有益的.图 1为功能表面视图表达实例, 图 1中分别用大写字母$P$、$C$、$H$和$S$表示平面、圆柱面、孔和槽[30].视图表达时, 法线(轴线)平行于投影面形成的视图称为功能表面的剖面视图, 垂直于投影面形成的视图称为功能表面的外形视图.功能表面间的拓扑关系通过连接边的凹凸性表示, 约定:凹边用"0"标记, 凸边用"1"标记.两相连功能表面均为回转面时, 拓扑关系通过回转面是内表面还是外表面来定义, 并用"!"标记.
图 1 几个常用零件功能表面的视图表达Fig. 1 View expression of functional surfaces of several common parts功能表面间的位置关系包括方位关系和领域关系.方位关系通过方位矢量的空间方位关系来定义, 有平行(∥)、同轴(⊙)、垂直(⊥)和偏斜(∠).领域关系指功能表面占据的空间区域间的关系, 领域关系的种类与方位关系类型有关, 二元领域关系见表 2, 表 3[30].因为平面功能表面占据区域的长度为0, 所以平面—回转面间的相遇、重叠、共点关系合并为相遇.两垂直平面之间不定义二元领域关系, 并用"!"标记.符号"!$\sharp$"表示两功能表面拓扑相连, 而符号"$\sharp$"则表示拓扑不相连.符号"?"表示功能表面间的位置关系不能通过单个视图确定.
表 2 功能表面二元领域关系(1)Table 2 Two-dimensional domain relation of functional surface (1)同轴, 平行 关系含义 分离 相遇 重叠 共点 字母标记 $s$ $m$ $o$ $c$ 图示 
表 3 功能表面二元领域关系(2)Table 3 Two-dimensional domain relation of functional surface (2)同轴, 平行 关系含义 分离 相遇 重叠 共点 字母标记 $s$ $m$ $o$ $c$ 图示 
分布关系有线性分布($l$)、圆周分布($p$)、矩形阵列分布($r$)和对称分布($m$).分布关系用符号"::"标识.
将图 1零件工程图的功能表面进行标记, 再根据判断拓扑相连功能表面的几何条件、功能表面间位置关系的确定方法以及分布关系的定义, 得到零件工程图结构模型如图 2所示.
如果将零件工程图的功能表面看作是对象, 功能表面间的关系看作是属性, 就可以构造零件工程图结构模型的形式背景, 进而用概念格分析不同功能面集合间的关系.
这种转换是比较直接的:
1) 对给定零件的工程图结构模型找出所有功能表面建立对象集合$G$, 所有的功能表面间关系为属性集合$M$;
2) 如果$g\in G$, 且与某功能表面有关系$w$, 则$(g, w)\in I$.
$l\parallel m$ $1\perp b$ $!\perp b$ $0\odot m$ $\sharp\odot s$ $C_{1} $ 0 $1$ 1 1 0 $C_{2}$ 0 1 0 1 0 $C_{3} $ 0 0 1 0 0 $P_{1}$ 0 0 0 1 1 $P_{2}$ 0 0 0 1 1 $P_{3}$ 1 1 0 0 0 $P_{4}$ 0 1 0 0 0 $H$ 1 0 0 0 0 与一般概念格一样, 零件工程图结构模型形式背景上的概念格也存在形式概念数量较大的问题, 因此, 我们将用因子分解的方法找出能反映零件特征的集对——因子概念.
$O(G, M, I)=\{(\{C_{1}\}, \{1 \perp b, ! \perp b, 0\odot m\})$, $(\{C_{1}, C_{2}\}, \{1 \perp b, 0\odot m\})$, , , , $(\{ P_{3}, H\}, \{1//m\})\}$
, ,
, , ,
$ \begin{align*}I^{*}=\, &\left[ {\begin{array}{*{20}{c}} 0&1&1&0\\ 0&1&0&0\\ 0&0&1&0\\ 0&0&0&1\\ 0&0&0&1\\ 1&1&0&0\\ 0&1&0&0\\ 1&0&0&0 \end{array}} \right]\circ \left[ {\begin{array}{*{20}{c}} 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&1 \end{array}} \right]=\\[2mm] &\left[ {\begin{array}{*{20}{c}} 0&1&1&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&1\\ 0&0&0&1&1\\ 1&1&0&0&0\\ 0&1&0&0&0\\ 1&0&0&0&0 \end{array}} \right], \\I-I^{*}=&\left[ {\begin{array}{*{20}{c}} 0&0&0&1&0\\ 0&0&0&1&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0\\ 0&0&0&0&0 \end{array}} \right]\end{align*} $
因此有, 且, .
令$F =F\cup F^{*}, $
$ \begin{align*}I^{*}=\, &\begin{bmatrix} 0&1&1&0&1\\ 0&1&0&0&1\\ 0&0&1&0&0\\ 0&0&0&1&0\\ 0&0&0&1&0\\ 1&1&0&0&0\\ 0&1&0&0&0\\ 1&0&0&0&0 \end{bmatrix}\circ\begin{bmatrix} 1&0&0&0&0\\ 0&1&0&0&0\\ 0&0&1&0&0\\ 0&0&0&1&1\\ 0&0&0&1&0 \end{bmatrix}=\\[2mm]&\begin{bmatrix} 0&1&1&1&0\\ 0&1&0&1&0\\ 0&0&1&0&0\\ 0&0&0&1&1\\ 0&0&0&1&1\\ 1&1&0&0&0\\ 0&1&0&0&0\\ 1&0&0&0&0 \end{bmatrix}, \\ I-&I^{*}=\textbf{0} \end{align*} $
概念格因子为$\{(\{P_{3}, H\}, \{1//m \})$, , (图 3中黑点圈表示的结点).
从图中可以看出, 平面$P_{3}$与四个孔$H$间凸边平行相遇; 圆柱面$C_{1}, C_{2}$分别和平面$P_{3}, P_{4}$凸边垂直偏斜; 圆柱面$C_{1}$和$C_{3}$垂直偏斜; 平面$P_{1}$与$P_{2}$拓扑不相连$\backslash$同轴分离、凹边同轴相遇; 圆柱面$C_{1}, C_{2}$凸边垂直偏斜、具有凹边同轴相遇的特性足以刻画拉杆轴的功能特征.同理可以计算出摆轴和波导开关转子的关键结构(概念格因子).
摆轴概念格因子为$\{(\{C_{1}, P_{1}\}, \{0\odot s\})$, , , $(\{C_{2}, P_{1}\}, \{1\odot m\})\}$.
波导开关转子概念格因子为, , , $(\{C_{1}, C_{4}\}, \{1//c\})$, .
零件三维CAD模型相似性是将功能面邻接图和功能面定性几何约束图中各顶点之间的最短路径定义为一个子结构, 通过对子结构进行编码, 构成了零件装配结构的分支结构码, 以分支结构码的匹配程度作为零件结构的相似度量, 检索相似结构的零件[47-49].
分支结构码相似度定义为
$ S_{ij}=\frac{c_{ij}}{c_{i}+c_{j}-c_{ij}} $
(7) 式中$c_{ij}$表示零件$i, j$关键结构码相同的数目, 表示零件$i, j$的分支结构码数目.
算法2. 零件三维CAD模型检索算法
1) 建立零件装配结构模型.通过交互方式定义功能表面.可先对模型进行简化或直接通过交互方式定义功能表面间的拓扑关系.功能表面间的定性几何约束采用自动提取和交互定义相结合的方法.
2) 根据编码方法, 通过系统自动生成零件结构码.
零件的结构码包括基本结构码和定性几何约束结构码两类.基本结构码是基于功能面邻接图的结构编码; 定性几何约束结构码是基于定性几何约束图的结构编码.
3) 概念格因子分解:将结构码转化为形式背景, 对形式背景进行概念格因子分解, 求出最小因子即关键结构.
4) 利用关键结构码实现零件全结构、子结构和相似结构检索.计算基本分支结构码相似度.
4. 实例验证
为验证本文算法的可行性, 将模型一、二(图 6, 图 7)与自行开发的机械零件检索系统零件库中的零件进行相似性检索.将模型一、二与零件库中所有的零件(9 010个)一一进行相似性比较.表 5和表 6是模型库中部分零件与模型一、二的相似度值.
表 5 模型库中部分零件与模型一的相似度值Table 5 Similarity value of part and model 1 in the model base
表 6 模型库中部分零件与模型二的相似度值Table 6 Similarity value of part and model 2 in the model base
图 8是波导开关转子的关键结构分图.其关键结构为, 孔和上下平面及内圆柱面凸平行相遇(图 8(a)); , 顶端圆柱面和小平面凸垂直偏斜(图 8(b)); $(\{C_{2}, C_{3}, P_{2}, P_{3}\}, \{0\odot m\})$, 顶端的两个圆柱面与平台凹同轴相遇(图 8(c)); $(\{C_{1}, $ , 体内半圆柱面与外圆柱面凸平行共点(图 8(d)); , 两个主要圆柱面与主要平面凸同轴相遇(图 8(e)).
实验结果表明, 该方法具有较高的计算效率和判断精度, 对孔、洞、槽以及棱柱类的零件能取得很好的效果.本文将基于图的描述方法和关键结构结合起来, 与单独基于子图匹配的检索方法相比, 在检索效率上有很大提高.但是对一些不规则的几何体应用本文的方法时, 在提取关键结构时往往出现较多的小面片, 而这些小面片并不反映零件的主要特征.另外, 对于不规则形状零件, 最后形成的相关功能面结构的数量也非常多, 这也会影响后续的匹配和检索.
由于基于功能表面的装配结构进行编码是需要在检索之前完成的, 且编码对空间占用十分有限, 因此空间复杂度较低.算法的时间复杂度主要取决于概念格因子的获取.
在算法1第1)步计算属性、对象概念集, 需$m+n$次.对于最坏情况2)、3)步可能计算$2\times \max(m, n)$次, 4)、5)步最多$n(n+1)/2+m(m+1)/2$.也就是说计算时间复杂度.由于都用到了结构编码, 我们将算法与文献[40]进行了比较.
其零件检索采用两个策略: 1)将分割区域的全体组合作为一个基本检索单元, 加入到区域结构倒排索引中. 2)将零件中每个邻接区域结构对看成一个子结构, 建立零件的二元区域结构索引, 通过对邻接区域结构对倒排记录表求交集, 实现包含3个及以上区域结构的整体子结构查询.第一种策略, 由于组合爆炸, 其复杂度没有优势.策略二区域结构本身粒度较大, 虽然减少了匹配的次数, 但出错的概率增加了.
将模型一和模型二在VisualC++, ACIS和HOOPS环境下进行检索.实验用微机CPU为Intel 3.30 GHz, 内存为4.0 GB.表 7, 表 8是两种方法检索比较的结果.
表 7 在模型库中搜索的与模型一相似的零件与耗时Table 7 The parts and time consuming that are similar to model 1 in the model base
表 8 在模型库中搜索的与模型二相似的零件与耗时Table 8 The parts and time consuming that are similar to model 2 in the model base
5. 实验分析
实验的目的是测试检索算法的有效性.在图 9中的检索算法查准率—查全率(precision-recall)曲线表示了八个不同概念节点的情形:节点数量是2 (图中标为$n=2$, 其他类似), 4, 6, 7, 8, 9, 11和15.图中参数$k$意为零件关键结构的数量.查准率—查全率曲线的与零件的节点数量相关.当节点的数量从2增加到6时, 性能显著降低.从$n=8$算法的性能变得不稳定并降低很快.所以在检索复杂零件时, 算法并不是十分有效, 特别是零件有超过8的节点.究其原因是, 在我们的模型背景中, 概念节点的数量是基本计算单元.概念节点越多、越相似, 精度较低. 图 10的$n-k$表明, 随着$n$值的增加, $k$开始增加, 并且增长率变化越来越大.特别是在$k$大于9后.所以很明显, 在零件关键结构(关键特性)小于9时, 检索算法具有良好的性能, 否则效果不能令人满意.不过, 这已经可以满足一般实际应用要求.
图 9 不同概念节点数的查准率{查全率曲线Fig. 9 Precision rate-recall (precision-recall) curves of the number of difierent conceptual nodes6. 结论
概念格理论是一种有效的数据分析和知识处理的工具, 在人工智能的许多研究领域已经被成功地运用.但在实际中, 一个中等大小的输入数据集通常可以产生相当大的一组形式概念, 这直接影响着它的应用.本文引入了形式背景布尔矩阵分解的概念, 讨论基于对象概念、属性概念的概念格因子分解的特性, 并提出了概念格因子发现的方法和近似测度的公式, 给出了相应的概念格因子生成算法.通过实例把本文提出的因子分解理论应用于零件模型检索, 优点是可以用较少的结构较高的效率确定被查找的对象.本文进一步扩充了概念格的约简理论(是对概念格无前置条件的约简), 对概念格的研究和应用都有重要意义.
-
[1] Zheng Y F, Chen W D. Mobile robot team forming for crystallization of proteins. Autonomous Robots, 2007, 23(1): 69−78 doi: 10.1007/s10514-007-9031-1 [2] Smith R S, Hadaegh F Y. Control of deep-space formation-flying spacecraft; relative sensing and switched information. Journal of Guidance, Control, and Dynamics, 2005, 28(1): 106−114 doi: 10.2514/1.6165 [3] 黄勤珍. 离散时间多智能体系统的一致性. 自动化学报, 2012, 38(7): 1127−1133Huang Qin-Zhen. Consensus analysis of multi-agent discrete-time systems. Acta Automatica Sinica, 2012, 38(7): 1127−1133 [4] Cao Y C, Yu W W, Ren W, Chen G R. An overview of recent progress in the study of distributed multi-agent coordination. IEEE Transactions on Industrial Informatics, 2013, 9(1): 427−438 doi: 10.1109/TII.2012.2219061 [5] 董涛, 李小丽, 赵大端. 基于事件触发的三阶离散多智能体系统一致性分析. 自动化学报, 2019, 45(7): 1366−1372Dong Tao, Li Xiao-Li, Zhao Da-Duan. Event-triggered consensus of third-order discrete-time multi-agent systems. Acta Automatica Sinica, 2019, 45(7): 1366−1372 [6] Hong Y G, Hu J P, Gao L X. Tracking control for multi-agent consensus with an active leader and variable topology. Automatica, 2006, 42(7): 1177−1182 doi: 10.1016/j.automatica.2006.02.013 [7] Hu J P, Hong Y G, Feng G. Distributed dynamic control for leaderless multi-agent consensus with star-like topology. Asian Journal of Control, 2008, 10(2): 233−237 doi: 10.1002/asjc.21 [8] Wu Y, Wang Z, Ding S, Zhang H G. Leader-follower consensus of multi-agent systems in directed networks with actuator faults. Neurocomputing, 2018, 275: 1177−1185 doi: 10.1016/j.neucom.2017.09.066 [9] Du H B, Li S H, Qian C J. Finite-time attitude tracking control of spacecraft with application to attitude synchronization. IEEE Transactions on Automatic Control, 2011, 56(11): 2711−2717 doi: 10.1109/TAC.2011.2159419 [10] Zhao L W, Hua C C. Finite-time consensus tracking of second-order multi-agent systems via nonsingular TSM. Nonlinear Dynamics, 2014, 75(1-2): 311−318 doi: 10.1007/s11071-013-1067-5 [11] Yu H, Shen Y, Xia X. Adaptive finite-time consensus in multi-agent networks. Systems & Control Letters, 2013, 62(10): 880−889 [12] Yu S, Long X. Finite-time consensus for second-order multi-agent systems with disturbances by integral sliding mode. Automatica, 2015, 54: 158−165 doi: 10.1016/j.automatica.2015.02.001 [13] Hua C C, Sun X L, You X, Guan X P. Finite-time consensus control for second-order multi-agent systems without velocity measurements. International Journal of Systems Science, 2017, 48(2): 337−346 doi: 10.1080/00207721.2016.1181224 [14] Wang X, Li S, Lam J. Distributed active anti-disturbance output consensus algorithms for higher-order multi-agent systems with mismatched disturbances. Automatica, 2016, 74: 30−37 doi: 10.1016/j.automatica.2016.07.010 [15] Zhang L L, Hua C C, Guan X P. Distributed output feedback consensus tracking prescribed performance control for a class of nonlinear multi-agent systems with unknown disturbances. IET Control Theory and Applications, 2016, 10(8): 877−883 doi: 10.1049/iet-cta.2015.1120 [16] Polyakov A. Nonlinear feedback design for fixed-time stabilization of linear control systems. IEEE Transactions on Automatic Control, 2011, 57(8): 2106−2110 [17] Wang H, Yu W W, Wen G H, Chen G R. Fixed-time consensus tracking of multi-agent systems under a directed communication topology. In: Proceedings of the 12th IEEE International Conference on Control and Automation. Kathmandu, Nepal: IEEE, 2016. 186−191 [18] Zuo Z Y. Nonsingular fixed-time consensus tracking for second-order multi-agent networks. Automatica, 2015, 54: 305−309 doi: 10.1016/j.automatica.2015.01.021 [19] Liu J, Zhang Y L, Sun C Y, Yu Y. Fixed-time consensus of multi-agent systems with input delay and uncertain disturbances via event-triggered control. Information Sciences, 2019, 480: 261−272 doi: 10.1016/j.ins.2018.12.037 [20] Hong H F, Yu W W, Yu X H, Wen G H, Alsaedi A. Fixed-time connectivity-preserving distributed average tracking for multi-agent systems. IEEE Transactions on Circuits and Systems II: Express Briefs, 2017, 64(10): 1192−1196 doi: 10.1109/TCSII.2017.2661380 [21] Shang Y L. Fixed-time group consensus for multi-agent systems with non-linear dynamics and uncertainties. IET Control Theory & Applications, 2017, 12(3): 395−404 [22] Yang H Y, Zhang Z X, Zhang S Y. Consensus of second-order multi-agent systems with exogenous disturbances. International Journal of Robust and Nonlinear Control, 2011, 21(9): 945−956 doi: 10.1002/rnc.1631 [23] Zuo Z Y, Han Q L, Ning B D, Ge X H, Zhang X M. An overview of recent advances in fixed-time cooperative control of multiagent systems. IEEE Transactions on Industrial Informatics, 2018, 14(6): 2322−2334 doi: 10.1109/TII.2018.2817248 [24] Ni K J, Liu L, Liu C X, Liu J. Fixed-time leader-following consensus for second-order multiagent systems with input delay. IEEE Transactions on Industrial Electronics, 2017, 64(11): 8635−8646 doi: 10.1109/TIE.2017.2701775 [25] Wei X Y, Yu W W, Wang H, Yao Y Y, Mei F. An observer-based fixed-time consensus control for second-order multi-agent systems with disturbances. IEEE Transactions on Circuits and Systems II: Express Briefs, 2019, 66(2): 247−251 doi: 10.1109/TCSII.2018.2831922 [26] Inoue S, Hirano M, Kijima K, Takashina J. A practical calculation method of ship maneuvering motion. International Shipbuilding Progress, 1981, 28(325): 207−222 doi: 10.3233/ISP-1981-2832502 [27] Zuo Z Y, Tie L. A new class of finite-time nonlinear consensus protocols for multi-agent systems. International Journal of Control, 2014, 87(2): 363−370 doi: 10.1080/00207179.2013.834484 [28] Zuo Z Y, Tie L. Distributed robust finite-time nonlinear consensus protocols for multi-agent systems. International Journal of Systems Science, 2016, 47(6): 1366−1375 doi: 10.1080/00207721.2014.925608 期刊类型引用(11)
1. 王昊，李新凯，张宏立，杨加秀，窦磊. 基于动态尺度观测器的多无人机立体包含控制. 北京航空航天大学学报. 2025(02): 655-667 . 
百度学术2. 耿超，武永宝，孙佳，刘剑，薛磊. 抗干扰的多智能体系统固定时间分布式优化算法. 控制与决策. 2024(02): 527-535 . 百度学术3. 赵华荣，彭力，吴治海，谢林柏，于洪年. 随机时延下多输入多输出多智能体系统事件触发双向编队. 控制与决策. 2024(04): 1251-1259 . 百度学术4. 时侠圣，孙长银，穆朝絮. 扰动线性多智能体系统的分布式资源分配算法. 中国科学:信息科学. 2024(04): 911-926 . 百度学术5. 石井龙，刘志杰，郭皓晨，刘剑. 动态事件触发下的一阶非线性多智能体系统设定时间一致性. 工程科学学报. 2024(09): 1604-1612 . 百度学术6. 徐世昊，关英姿，浦甲伦，韦常柱. VTHL运载器再入返回预设时间滑模控制. 航空学报. 2023(07): 154-167 . 百度学术7. 孙梦薇，任璐，刘剑，孙长银. 切换拓扑下动态事件触发多智能体系统固定时间一致性. 自动化学报. 2023(06): 1295-1305 . 本站查看8. 郑维，张志明，刘和鑫，张明泉，孙富春. 基于线性变换的领导-跟随多智能体系统动态反馈均方一致性控制. 自动化学报. 2022(10): 2474-2485 . 本站查看9. 石尚，李慧，闵惠芳，徐胜元，孙永辉. 不确定Chua电路系统的固定时间自适应参数估计. 控制理论与应用. 2022(08): 1551-1560 . 百度学术10. 侯惠清，欧阳自根. 二阶非线性多智能体系统的固定时间领导-跟随集群. 南华大学学报(自然科学版). 2021(01): 56-63 . 百度学术11. 杨娜娜，孟新友，王璇. 执行器饱和多智能体系统的自适应学习一致性算法. 计算机应用研究. 2021(09): 2737-2740 . 百度学术其他类型引用(13)
-
下载:
下载:
计量
- 文章访问数: 1475
- HTML全文浏览量: 604
- PDF下载量: 501
- 被引次数: 24
