一种含复铰运动链同构判定的新方法

李安明，孙 伟，侯 宇，黄 森

（武汉科技大学机械自动化学院，湖北 武汉430081）

1 引言

运动链的同构判定是机构创新、再生运动链必不可少的过程，不当的同构判定方法会导致有价值的新运动链的丢失或造成机构类别的重复。寻找一种既简便有效又便于计算机执行的同构判定方法，成为了当下的一大难题。

国内外很多学者花大量时间与精力进行了研究。文献［1］提出了“规范化”邻接矩阵来判别不含复铰的运动链。文献［2］提出了全等环路法，通过比较环路构件度来判定是否同构：文献［3］用改进Haming数的方法来判定同构：文献［4］提出基于邻接矩阵的特征值特征向量法实现不含复铰运动链的同构判定：文献［5］利用素数邻接矩阵构造了判定矩阵，通过解矢量得到同构构件标号的映射关系，从而判定同构：文献［6］提出了改进环连接方法，通过关节频率、链识别串等结构恒量来判定同构。文献［7］将神经网络引入同构判定中：文献［8］用改进混合免疫法来判定同构，提高了遗传算法的效率：虽然它们各有优点，但也存在缺陷。有的算法原理复杂，计算机化难以实现，有的准确性低、失效率高，尤其对于对称性高的运动链难以准确判定。

提出了一种计算简便，准确性高的同构判定方法，对于对称性较高的运动链仍然有效。用特征码表示运动链的基本特征，作为判定的必要条件。为区分复铰、普通铰且便于求最短距离矩阵，提出了改进邻接矩阵。然后利用邻接矩阵构造了最短距离矩阵作为判定矩阵。由运动链的特征码、最短距离矩阵的和列阵及特征值特征向量来判定运动链是否同构。

2 最短距离矩阵

如图1（b）所示，为10杆含复铰运动链a1对应的双色拓扑图［9］。图中黑色节点对应运动链中的构件，白色节点与其所连线段的组合对应运动链中的复合铰，其余线段则表示运动链的普通较。为区分普通铰和复合铰，令拓扑图中任意两相连黑色节点间的距离为1，任意两黑白相连的节点间距离为0.55。此时，拓扑图中任意两个黑色节点间最短距离的整数部分，表示运动链中两构件之间最短路径所经过的关节个数，若存在小数则表明该路径中存在复合铰。

图1 运动链a1结构简图及其双色拓扑图Fig.1 Structural Sketch and Topological Graph of Kinematic Chain a1

为了区别复铰并反映拓扑图中相邻两黑色节点间的距离关系，提出了一种改进邻接矩阵来描述含复铰的运动链，用A表示。改进邻接矩阵中若构件与构件通过普通铰相连，则元素为1，不相连元素为∞。若通过复合铰相连，则元素为1.1，并且对角线元素为0。运动链a1的改进邻接矩阵为Aa1。

定义1：矩阵中任一元素表示拓扑图任意两节点之间最短路径距离值的矩阵称为最短距离矩阵，用D表示。

采用“插点法”求最短距离矩阵，依次构造出n个矩阵D(0)、使最后得到矩阵为最短距离矩阵。最短距离矩阵更新原理如下：

n是最短距离矩阵。

综上所述，求最短距离矩阵的算法流程可总结如下：

第一步：赋初值，把矩阵A赋值给初始最短距离矩阵D。

第二步：更新最短距离矩阵D(i,j)，

第三步：若k=n，则停止，否则k=k+1，转第二步。

求得运动链a1拓扑图对应的最短距离矩阵为Da1。

其中，Da1()3,7=2.2在拓扑图中表示由节点3到节点7的最短距离为2.2，在运动链中表示由构件3到构件7至少需要经过两个关节，并存在复合铰：右侧为距离之和，表示拓扑图中任意一点到其余所有点的最短距离之和，记为和列阵Sa1。

3 同构判定

由图论相关理论及同构的概念可知，要使两运动链同构，必须含有相同的构件种类、构件数量、构件连接关系。对于构件之间的连接关系已由最短距离矩阵得出，而对于构件种类、构件数量用特征码表示。

定义2：表示运动链构件种类及数量的代码称为特征码，用M表示。

式中：nu-含有u元构件的数量。例如，Ma1=[7,2,1]表示含有7个二元杆、2个三元杆、1个四元杆。运动链同构判定流程，如图2所示。

图2 同构判定流程图Fig.2 Isomorphism Identification Flow Chart.

如图3所示，为两个含复铰的10杆运动链，运动链a1、a2与a3的特征码为Ma1=Ma2=Ma3=[ ]7,2,1，即三个运动链具有相同的构件类型和数量。可求得最短距离矩阵为Da2和Da3。

图3 运动链a2与a3结构简图Fig.3 Structural Sketch of Kinematic Chain a2 and a3

表1 运动链、最短距离矩阵特征值及特征向量Tab.1 Eigenvalues and Eigenvectors of the Shortest Distance Matrices of Chain and

4 案例分析

案例1：如图4所示，为两个含复铰13杆运动链结构简图，其特征码Mb1=Mb2=[3,8]。可求得最短距离矩阵为Db1和Db2。

图4 运动链b1与b2Fig.4 Kinematic Chainb1andb2

图5 运动链c1与c2Fig.5 Kinematic Chainc1andc2

表2 运动链、最短距离矩阵特征值及特征向量Tab.2 Eigenvalues and Eigenvectors of the Shortest Distance Matrices of Chain and

5 结论

提出了一种含复铰运动链描述和判定的新方法，并给出了通过改进邻接矩阵求解最短距离矩阵的算法。通过比较运动链的特征码、最短距离矩阵的和列阵、最短距离矩阵的特征值特征向量是否相等来判定同构。案例证明了此方法的正确性与高效性。相比其它同构判定法，计算既简便又有效。并且对于对称性较高的运动链，此方法依然有效。