机器人运动链拓扑胚图的特征字符串描述

王 莹，毛秉毅

（1.华北理工大学，唐山 063009；2.燕山大学，秦皇岛 066004）

机器人运动链拓扑胚图的特征字符串描述

王 莹1,2，毛秉毅2

（1.华北理工大学，唐山 063009；2.燕山大学，秦皇岛 066004）

0 引言

现代机构学的主要任务是为创造现代机械系统的新机构提供理论和实际有效的方法，并在此基础上产生满足特定要求的新机构。确定机构拓扑结构是机械创新设计所要解决的关键问题[1]。迄今为止许多理论和方法已经被提出，最具代表性的有Franke标记法、阿苏尔杆组法、二杆链转化法、有限对称群理论法、对偶图法和单开链单元法等。

目前，作为机构设计主要手段的机构拓扑图型综合已成为十分重要的研究课题和方向，Freudenstein[2]，Tsai[3]等较早提出用图理论开展机构型综合。Gogu[4]采用线性变换的思想，系统研究了并联机构的自由度和型综合问题。Johnson用决策树推导出用于平面机构型综合的关联杆组，并通过图型综合，综合出许多新颖的平面机构。路懿和Leinonen[5]采用该方法推导出用于平面和空间机构构型综合的统一关联杆组，并采用邻接矩阵，由关联杆组推导出大量运动链拓扑胚图和拓扑图。在基于拓扑图型的机构构型综合中，图的同构判断一直是困扰专家和学者们的难题。目前已提出的方法有，基于矩阵相似理论的同构判断方法[6]、基于编码的同构判断方法[7]、哈明串法[8]等，这些方法都是从运动链拓扑图出发的。

运动链拓扑胚图是构建拓扑图和运动链的基本框架和有效工具。1988年，Yan[9]提出运动链拓扑胚图的概念。丁玲和路懿[10]从邻接矩阵的经典理论出发，提出利用路径数组进行拓扑胚图同构判断的方法。该方法在进行判断前，需先计算图的任意顶点之间的路径数矩阵，数学模型结构相对复杂。本文在对运动链拓扑胚图基本结构分析的基础上，提出特征字符串的概念，描述和表示运动链拓扑胚图，并给出计算拓扑胚图中顶点和边的数量关系。定义了由特征字符串描述拓扑胚图及判别同构拓扑胚图的相关准则，解决运动链拓扑胚图的同构判断问题，从而有效避免后续拓扑图综合中不必要的大量同构识别。

1 构造拓扑胚图的相关参数及基本概念

1.1 基本连杆和关联杆组的概念

组成运动链的基本连杆根据连接支链数目的多少可分为二元杆、三元杆、四元杆、五元杆和六元杆等，分别用B、T、Q、P和H表示。在运动链拓扑胚图和拓扑图中，这些基本连杆都由1个自由度的转动副连接。所不同的是，运动链拓扑胚图（Contracted Graph，简称CG）不含有二元杆B，只含有三元以上的基本连杆。在拓扑胚图中，每个基本连杆用一个顶点表示，这些点彼此通过一些曲线连接起来。

关联杆组（Associated Linkages，简称AL）是基本连杆的组合。一些含有效基本连杆的平面和空间机构的关联杆组已确定[11]，如表1所示。其中，n6，n5，n4和n3分别表示基本连杆H、P、Q、T的数量；n和ne分别表示拓扑胚图中顶点和曲线的数量。可见，关联杆组可以表示为n6H+n5P+n4Q+n3T+n2B。因H、P、Q、T分别需连接6、5、4、3条曲线，所以n和ne可由下式求出：

表1 一些已知关联杆组中n3, n4, n5, n6, n, ne的值[11]

1.2 特征字符串的概念

特征字符串是由n个字符串组成的数组，每个字符串对应拓扑胚图的一个顶点，并包括一串数字。每一串数字可以由一个或几个数字组成，其中每个数字表示两个不同顶点连接的曲线数目。例如，特征字符串{213,32, 211, 12}可用来表示图1中的CG 1，是由4个字符串组成的数组。其中，第1个字符串包括一串数字213，对应于CG 1中的H顶点，表示基本连杆H与T、Q、P分别由2、1、3条曲线相互连接；同样，第2个字符串包括一串数字32，对应于CG 1中的P顶点，表示基本连杆P与H、T、Q分别由3、0、2条曲线相互连接；第3个字符串包括一串数字211，对应于CG 1中的Q顶点，表示基本连杆Q与P、H、T分别由2、1、1条曲线相互连接；第4个字符串包括一串数字12，对应于CG 1中的T顶点，表示基本连杆T与Q、P、H分别由1、0、2条曲线相互连接。

2 拓扑胚图的结构及其特征字符串描述

2.1 拓扑胚图的结构

每个拓扑胚图一般都是由一个基圆，n个顶点和ne条曲线构成，如图1所示。基于表1中的n3，n4，n5，n6，n和ne的值，拓扑胚图的结构可描述如下：

1）一个基圆C；

2）对应于关联杆组中各基本连杆的n个顶点；

3）连接n个顶点的ne条曲线，任一表示H，P，Q和T的顶点和其它顶点必须总共连接6，5，4和3条曲线。

一般在构造拓扑胚图时，尽量将n个顶点分布到基圆的圆周上。这样，可以简化拓扑胚图的构造，也容易对拓扑胚图进行同构识别。

图1 对应于关联杆组H+P+Q+T的拓扑胚图

图1为对应于表1中No.7关联杆组H+P+Q+T的拓扑胚图。由图1中CG 1可以看到，该拓扑胚图由一个基圆C，均布在其上的代表基本连杆H、P、Q、T的4个点和连接它们的9条曲线组成，且表示H、P、Q、T的顶点分别连接6，5，4和3条曲线，符合表1中No.7关联杆组的参数值。

观察CG 2～CG 9，CG 1i和CG 3i发现它们也都符合拓扑胚图的结构要求，都是表1中No.7关联杆组H+P+Q+T推导出的拓扑胚图，区别在于4个顶点在基圆上的排列方式以及顶点之间的连接方式不同。

2.2 拓扑胚图的特征字符串描述

由拓扑胚图不含二度点的独特特性，只要能够准确描述代表基本连杆的顶点的相对位置和连接方式，就可以推导和引出拓扑胚图。由1.2节可知，特征字符串的结构满足这样的要求。规定按顶点在基圆上分布的逆时针方向，从基圆圆周顶部的顶点开始，将描述各个顶点连接方式的字符串依次列出，就可得到描述拓扑胚图的特征字符串。表2为描述图1中的拓扑胚图的特征字符串。

表2 描述图1中拓扑胚图的特征字符串

可见，特征字符串具有以下性质：

1）每个特征字符串所包含字符串的个数与拓扑胚图中顶点的数目相同，与对应的关联杆组的基本连杆数目相同，都为n。

2）特征字符串中每个字符串对应拓扑胚图的一个顶点，包括一个或几个数字，各数字之和等于该顶点所需连接的曲线数目。

3）在特征字符串中，第i（i＜n）个字符串的最后一个数字和第i+1个字符串的第一个数字相同，第1个字符串的第一个数字和第n个字符串的最后一个数字相同。

4）特征字符串中n个字符串的所有数字之和等于2ne。

图2是表1中No.15关联杆组H+6T所对应的一些有效的拓扑胚图，它们彼此不同且非同构。表3是图2中的拓扑胚图所对应的特征字符串。通过观察发现，拓扑胚图CG 3/1和CG 3/2的特征字符串相同，拓扑胚图CG 5/1、CG 5/2和CG 5/3的特征字符串相同。

由此可以得出，每个拓扑胚图都可以用一个特征字符串描述，但每个特征字符串并不是只能引出一个拓扑胚图的结论。

很显然，由同一个特征字符串描述的不同的拓扑胚图是非同构的，通过观察法很容易判断。

图2 对应于关联杆组H+6T的拓扑胚图

表3 描述图2中拓扑胚图的特征字符串

3 拓扑胚图的同构判断

一般情况下，同一组关联杆组可推导出几个不同的拓扑胚图，但这些拓扑胚图并不都是有效的，必须判别其同构关系。如果两个拓扑胚图的结构相同或是对称，它们一定是同构拓扑胚图。用CG xi表示CGx的同构拓扑胚图，在拓扑胚图综合过程中，CG xi必须清除。图1中的CG 1i和CG 1，CG 3i和CG 3结构对称，互为同构关系。所以，需要将CG 1i和CG 3i清除。

3.1 同构判断的前提条件

在运动链基于胚图的综合方法中，拓扑胚图的同构判断是关键环节。在进行同构判断时，有些特征通过观察法就可以判断，比如组成运动链构件的类型和数量。首先，观察需进行同构判断的拓扑胚图的顶点数量和类型是否一致，如果顶点数量和类型不同，就可以直接得出拓扑胚图不同构的结论。这就说明进行拓扑胚图同构判断的前提是，拓扑胚图是由同一组关联杆组推导出的，图上各顶点的类型和数量相同，连接各顶点的曲线总数也一样。

3.2 特征字符串判断拓扑胚图同构的条件

3.2.1 特征字符串不同

假设CG x和CG y分别是由同一组关联杆组下的两个不同的特征字符串x和特征字符串y引出的拓扑胚图。如果特征字符串x和y满足以下条件，CG x和CG y一定互为同构关系。

1）顺次将特征字符串y中的n个字符串中的一个或几个字符串从最左边移动到最右边(在不改变需移动字符串前后顺序的前提下)，得到新的特征字符串y1，y1中的所有数字与x相同。

2）将第2步得到的特征字符串y1中所有数字按从右到左逆序排列，得到新的特征字符串y2，y2中的所有数字与x相同。

表3中No.1i特征字符串{312, 21, 112, 23}对应图1中CG 1i，No.1特征字符串{213, 32, 211, 12}对应图1中CG 1。首先将No.1i特征字符串的第1个字符串312移动到该字符串的最右边，得到新的字符串{21, 112, 23, 312}。然后将新得到的字符串中的所有数字按从右到左逆序排列，得到新的字符串{213, 32, 211, 12}，与No.1特征字符串相同，所以CG 1i和CG 1一定互为同构关系。

3.2.2 特征字符串相同

对于特征字符串x中的所有数字与特征字符串y完全相同的情况，也就是同一特征字符串的情况，可以引出不同的拓扑胚图，从而引出不同的运动链，在2.2节中已讨论。如何判断同一特征字符串下拓扑胚图是否同构，仅仅依据上述条件1）和2）显然是无法完成的。假设CG x和CG y是同一特征字符串表示下的拓扑胚图，可以采用以下方法进行同构判断：

在拓扑胚图基圆上以开始点为起点，沿着圆周按逆时针或顺时针方向对各个顶点按（1,2,…,n）进行编号。

将连接各个顶点的每条曲线用两端的顶点编号表示，因为ne值代表拓扑胚图中曲线数目，所以有ne对数字。

3）如果不考虑数字的顺序，CG x中的所有ne对数字都能在CG y中找到，那么CG x和CG y互为同构关系，否则为非同构关系。

3.3 拓扑胚图同构判断实例

3.3.1 实例1

图3(a)和(b)是两个10杆的运动链。通过邻接矩阵理论和路径数组的方法已判断了两图是非同构的[8]。文献[7]中画出了两图的拓扑胚图，如图3(c)和(d)所示。下面用特征字符串来判断。

首先，观察两个拓扑胚图，都是由6个顶点和9条曲线组成的，说明组成运动链的构件数量相同；同时，6个顶点均是三元杆T，说明组成运动链的构件类型相同。满足进行拓扑胚图同构判断的前提条件。然后，写出图3(c)的特征字符串为{111,111,111,111,111,111}，图3(d)的特征字符串为{111,111,111,111,111,111}。

图3 两个10杆运动链和对应的拓扑胚图

显然，两个拓扑胚图是由同一特征字符串表示的。由3.2.2的方法进行判断，过程如下：

1）沿拓扑胚图基圆顺时针方向对各个顶点进行了编号，如图3(c)和(d)所示。

如果我们将图3(c)和(d)的所有顶点均布在基圆圆周上，按本文构造拓扑胚图的方法绘制出的拓扑胚图如图4所示，通过观察法很容易判断两图是非同构的。

图4 顶点分布在基圆上的拓扑胚图

3.3.2 实例2

图5(a)、(b)和(c)是表1中No.14关联杆组H+3Q+2T的三个拓扑胚图，其中，(a)图的特征字符串a为{11112,211,111,1111,1111,111}，(b)图的特征字符串b为{111,112,21111,111,1111,1111}，(c)图的字符串c为{21111,111,1111,1111,111,112}。显然，三个字符串是不同的。要判断它们是否同构，按照3.2.1的方法，将特征字符串b的最左侧的三个字符串111、112和21111按原字符串前后顺序不变，移动到b的最右侧，得到新的特征字符串b1为{111,1111,1111,111,112,21111}；将b1中所有数字按从右到左逆序排列，得到新的特征字符串b2为{11112,211,111,1111,1111,111}。显然，b2中的所有数字与a相同。

图5 关联杆组H+3Q+2T的三个拓扑胚图

同理，采用相同的方法，将c的最左侧的第一个字符串21111移动到c的最右侧，得到新的特征字符串c1为{111,1111,1111,111,112,21111}，显然，c1和b1中的所有数字相同，按逆序排列后，所有数字和b2相同，也就是和a相同。因此，三个拓扑胚图是同构关系。

4 特征字符串与邻接矩阵的比较

一个n×n阶的邻接矩阵可用来表示一个含n个基本连杆的拓扑胚图[10]。图6是图1中CG 1和CG 1i的邻接矩阵和特征字符串。

图6 图1中CG 1的邻接矩阵和特征字符串

表示一个含n个基本连杆的拓扑胚图，用一个n×n阶的邻接矩阵，其数学模型和数学关系相对复杂。应用特征字符串来描述时，只需要一个一维数组就可以，其结构和准则相对简单。而且，从邻接矩阵中判别拓扑胚图的同构非常困难，而通过观察法很容易从特征字符串中判别拓扑胚图的同构，可避免很多不必要的劳动。

5 结论

1）基于运动链拓扑胚图支链上不含二度点的特性，提出了特征字符串的概念。并制定相关规则，用特征字符串准确描述代表基本连杆的顶点的相对位置，表示运动链拓扑胚图。

2）每个拓扑胚图都可以用一个特征字符串来描述，但每个特征字符串并不是只能描述一个拓扑胚图。

3）根据指定的判断准则，采用特征字符串法进行拓扑胚图同构判断，和邻接矩阵法比较，数学模型简单，方法有效，判断准确。

[1]杨廷力.机器人机构拓扑结构学[M].北京:机械工业出版社,2004.

[2]Vucina D,Freudenstein F. Application of Graph Theory and Nonlinear Programming to the Kinematic Synthesis of Mechanisms[J].Mechanism and Machine Theory,1991,26(6):553-563.

[3]Tsai L W. Mechanism Design:Enumeration of Kinematic Structures According to Function[M].Boca Raton. Florida:The Chemical Rubber Company Press,2001.

[4]Gogu G. Mobility of Mechanisms:a Critical Review[J].Mechanism and Machine Theory,2005,40(9):1068-1097.

[5]Lu Y, Leinonen T. Type Synthesis of Unif i ed Planar–Spatial Mechanisms by Systematic Linkage and Topology Matrix–Graph Technique[J].Mechanism and Machine Theory,2005,40(10):1145-1163.

[6]Rajesh P S, Linda C S.Reliability and Eff i ciency of the Existing Spectral Methods for Isomorphism Detection[J].ASME Journal of Mechanical Design,2006,128:1246-1252.

[7]罗玉峰,杨廷力,曹惟庆.用关联度和关联度码识别运动链同构[J].机械工程学报,1991,27(2):44-50.

[8]Rao A C. A Genetic Algorithm for Epicylic Gear Trains[J].Mechanism and Machine Theory,2000,38(2):135-147.

[9]Yan H S, Hsu C H.Contracted Graphs of Kinematic Chains with Multiple Joints[J].Mathematical and Computer Modeling,1988,10(9):681-695.

[10]丁玲,路懿,崔维,等.运动链拓扑胚图的同构判断[J].机械工程学报,2012,48(3):70-74.

[11]路懿,毛秉毅,翟旭.闭环机构关联杆组与冗余约束的关系[J].燕山大学学报,2013,37(4):299-304.

Characteristic strings description of robotic kinematic chain topology embryonic graphs

WANG Ying1,2, MAO Bing-yi2

在机构基于胚图的综合方法中，判别拓扑胚图的同构关系是一个难题。提出特征字符串的概念，用于描述含较多基本连杆的拓扑胚图。基于运动链拓扑胚图支链上不含二度点的特性，制定相关规则，用特征字符串准确描述代表基本连杆的顶点的相对位置，引出拓扑胚图。制定判别同构拓扑胚图的相关准则，论证了拓扑胚图同构的条件。举实例对同一特征字符串和不同特征字符串描述的拓扑胚图进行了同构判断。通过与邻接矩阵方法比较，证明特征字符串法简单、有效。

拓扑胚图；同构；特征字符串；邻接矩阵

10.3969/j.issn.1009-0134.2015.07(下).02

2015-03-04

国家自然科学基金：多手足并联机器人型综合与协调作用理论及应用研究（51175447）

王莹（1981 -），女，讲师，博士研究生，研究方向为机器人机构学和并联机器人拓扑结构学。

TH112

A

1009-0134(2015)07(下)-0005-05