王 瑩，毛秉毅

（1.華北理工大學(xué)，唐山 063009；2.燕山大學(xué)，秦皇島 066004）

機器人運動鏈拓撲胚圖的特征字符串描述

王 瑩1,2，毛秉毅2

（1.華北理工大學(xué)，唐山 063009；2.燕山大學(xué)，秦皇島 066004）

0 引言

現(xiàn)代機構(gòu)學(xué)的主要任務(wù)是為創(chuàng)造現(xiàn)代機械系統(tǒng)的新機構(gòu)提供理論和實際有效的方法，并在此基礎(chǔ)上產(chǎn)生滿足特定要求的新機構(gòu)。確定機構(gòu)拓撲結(jié)構(gòu)是機械創(chuàng)新設(shè)計所要解決的關(guān)鍵問題[1]。迄今為止許多理論和方法已經(jīng)被提出，最具代表性的有Franke標記法、阿蘇爾桿組法、二桿鏈轉(zhuǎn)化法、有限對稱群理論法、對偶圖法和單開鏈單元法等。

目前，作為機構(gòu)設(shè)計主要手段的機構(gòu)拓撲圖型綜合已成為十分重要的研究課題和方向，F(xiàn)reudenstein[2]，Tsai[3]等較早提出用圖理論開展機構(gòu)型綜合。Gogu[4]采用線性變換的思想，系統(tǒng)研究了并聯(lián)機構(gòu)的自由度和型綜合問題。Johnson用決策樹推導(dǎo)出用于平面機構(gòu)型綜合的關(guān)聯(lián)桿組，并通過圖型綜合，綜合出許多新穎的平面機構(gòu)。路懿和Leinonen[5]采用該方法推導(dǎo)出用于平面和空間機構(gòu)構(gòu)型綜合的統(tǒng)一關(guān)聯(lián)桿組，并采用鄰接矩陣，由關(guān)聯(lián)桿組推導(dǎo)出大量運動鏈拓撲胚圖和拓撲圖。在基于拓撲圖型的機構(gòu)構(gòu)型綜合中，圖的同構(gòu)判斷一直是困擾專家和學(xué)者們的難題。目前已提出的方法有，基于矩陣相似理論的同構(gòu)判斷方法[6]、基于編碼的同構(gòu)判斷方法[7]、哈明串法[8]等，這些方法都是從運動鏈拓撲圖出發(fā)的。

運動鏈拓撲胚圖是構(gòu)建拓撲圖和運動鏈的基本框架和有效工具。1988年，Yan[9]提出運動鏈拓撲胚圖的概念。丁玲和路懿[10]從鄰接矩陣的經(jīng)典理論出發(fā)，提出利用路徑數(shù)組進行拓撲胚圖同構(gòu)判斷的方法。該方法在進行判斷前，需先計算圖的任意頂點之間的路徑數(shù)矩陣，數(shù)學(xué)模型結(jié)構(gòu)相對復(fù)雜。本文在對運動鏈拓撲胚圖基本結(jié)構(gòu)分析的基礎(chǔ)上，提出特征字符串的概念，描述和表示運動鏈拓撲胚圖，并給出計算拓撲胚圖中頂點和邊的數(shù)量關(guān)系。定義了由特征字符串描述拓撲胚圖及判別同構(gòu)拓撲胚圖的相關(guān)準則，解決運動鏈拓撲胚圖的同構(gòu)判斷問題，從而有效避免后續(xù)拓撲圖綜合中不必要的大量同構(gòu)識別。

1 構(gòu)造拓撲胚圖的相關(guān)參數(shù)及基本概念

1.1 基本連桿和關(guān)聯(lián)桿組的概念

組成運動鏈的基本連桿根據(jù)連接支鏈數(shù)目的多少可分為二元桿、三元桿、四元桿、五元桿和六元桿等，分別用B、T、Q、P和H表示。在運動鏈拓撲胚圖和拓撲圖中，這些基本連桿都由1個自由度的轉(zhuǎn)動副連接。所不同的是，運動鏈拓撲胚圖（Contracted Graph，簡稱CG）不含有二元桿B，只含有三元以上的基本連桿。在拓撲胚圖中，每個基本連桿用一個頂點表示，這些點彼此通過一些曲線連接起來。

關(guān)聯(lián)桿組（Associated Linkages，簡稱AL）是基本連桿的組合。一些含有效基本連桿的平面和空間機構(gòu)的關(guān)聯(lián)桿組已確定[11]，如表1所示。其中，n6，n5，n4和n3分別表示基本連桿H、P、Q、T的數(shù)量；n和ne分別表示拓撲胚圖中頂點和曲線的數(shù)量。可見，關(guān)聯(lián)桿組可以表示為n6H+n5P+n4Q+n3T+n2B。因H、P、Q、T分別需連接6、5、4、3條曲線，所以n和ne可由下式求出：

表1 一些已知關(guān)聯(lián)桿組中n3, n4, n5, n6, n, ne的值[11]

1.2 特征字符串的概念

特征字符串是由n個字符串組成的數(shù)組，每個字符串對應(yīng)拓撲胚圖的一個頂點，并包括一串?dāng)?shù)字。每一串?dāng)?shù)字可以由一個或幾個數(shù)字組成，其中每個數(shù)字表示兩個不同頂點連接的曲線數(shù)目。例如，特征字符串{213,32, 211, 12}可用來表示圖1中的CG 1，是由4個字符串組成的數(shù)組。其中，第1個字符串包括一串?dāng)?shù)字213，對應(yīng)于CG 1中的H頂點，表示基本連桿H與T、Q、P分別由2、1、3條曲線相互連接；同樣，第2個字符串包括一串?dāng)?shù)字32，對應(yīng)于CG 1中的P頂點，表示基本連桿P與H、T、Q分別由3、0、2條曲線相互連接；第3個字符串包括一串?dāng)?shù)字211，對應(yīng)于CG 1中的Q頂點，表示基本連桿Q與P、H、T分別由2、1、1條曲線相互連接；第4個字符串包括一串?dāng)?shù)字12，對應(yīng)于CG 1中的T頂點，表示基本連桿T與Q、P、H分別由1、0、2條曲線相互連接。

2 拓撲胚圖的結(jié)構(gòu)及其特征字符串描述

2.1 拓撲胚圖的結(jié)構(gòu)

每個拓撲胚圖一般都是由一個基圓，n個頂點和ne條曲線構(gòu)成，如圖1所示?；诒?中的n3，n4，n5，n6，n和ne的值，拓撲胚圖的結(jié)構(gòu)可描述如下：

1）一個基圓C；

2）對應(yīng)于關(guān)聯(lián)桿組中各基本連桿的n個頂點；

3）連接n個頂點的ne條曲線，任一表示H，P，Q和T的頂點和其它頂點必須總共連接6，5，4和3條曲線。

一般在構(gòu)造拓撲胚圖時，盡量將n個頂點分布到基圓的圓周上。這樣，可以簡化拓撲胚圖的構(gòu)造，也容易對拓撲胚圖進行同構(gòu)識別。

圖1 對應(yīng)于關(guān)聯(lián)桿組H+P+Q+T的拓撲胚圖

圖1為對應(yīng)于表1中No.7關(guān)聯(lián)桿組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關(guān)聯(lián)桿組的參數(shù)值。

觀察CG 2～CG 9，CG 1i和CG 3i發(fā)現(xiàn)它們也都符合拓撲胚圖的結(jié)構(gòu)要求，都是表1中No.7關(guān)聯(lián)桿組H+P+Q+T推導(dǎo)出的拓撲胚圖，區(qū)別在于4個頂點在基圓上的排列方式以及頂點之間的連接方式不同。

2.2 拓撲胚圖的特征字符串描述

由拓撲胚圖不含二度點的獨特特性，只要能夠準確描述代表基本連桿的頂點的相對位置和連接方式，就可以推導(dǎo)和引出拓撲胚圖。由1.2節(jié)可知，特征字符串的結(jié)構(gòu)滿足這樣的要求。規(guī)定按頂點在基圓上分布的逆時針方向，從基圓圓周頂部的頂點開始，將描述各個頂點連接方式的字符串依次列出，就可得到描述拓撲胚圖的特征字符串。表2為描述圖1中的拓撲胚圖的特征字符串。

表2 描述圖1中拓撲胚圖的特征字符串

可見，特征字符串具有以下性質(zhì)：

1）每個特征字符串所包含字符串的個數(shù)與拓撲胚圖中頂點的數(shù)目相同，與對應(yīng)的關(guān)聯(lián)桿組的基本連桿數(shù)目相同，都為n。

2）特征字符串中每個字符串對應(yīng)拓撲胚圖的一個頂點，包括一個或幾個數(shù)字，各數(shù)字之和等于該頂點所需連接的曲線數(shù)目。

3）在特征字符串中，第i（i＜n）個字符串的最后一個數(shù)字和第i+1個字符串的第一個數(shù)字相同，第1個字符串的第一個數(shù)字和第n個字符串的最后一個數(shù)字相同。

4）特征字符串中n個字符串的所有數(shù)字之和等于2ne。

圖2是表1中No.15關(guān)聯(lián)桿組H+6T所對應(yīng)的一些有效的拓撲胚圖，它們彼此不同且非同構(gòu)。表3是圖2中的拓撲胚圖所對應(yīng)的特征字符串。通過觀察發(fā)現(xiàn)，拓撲胚圖CG 3/1和CG 3/2的特征字符串相同，拓撲胚圖CG 5/1、CG 5/2和CG 5/3的特征字符串相同。

由此可以得出，每個拓撲胚圖都可以用一個特征字符串描述，但每個特征字符串并不是只能引出一個拓撲胚圖的結(jié)論。

很顯然，由同一個特征字符串描述的不同的拓撲胚圖是非同構(gòu)的，通過觀察法很容易判斷。

圖2 對應(yīng)于關(guān)聯(lián)桿組H+6T的拓撲胚圖

表3 描述圖2中拓撲胚圖的特征字符串

3 拓撲胚圖的同構(gòu)判斷

一般情況下，同一組關(guān)聯(lián)桿組可推導(dǎo)出幾個不同的拓撲胚圖，但這些拓撲胚圖并不都是有效的，必須判別其同構(gòu)關(guān)系。如果兩個拓撲胚圖的結(jié)構(gòu)相同或是對稱，它們一定是同構(gòu)拓撲胚圖。用CG xi表示CGx的同構(gòu)拓撲胚圖，在拓撲胚圖綜合過程中，CG xi必須清除。圖1中的CG 1i和CG 1，CG 3i和CG 3結(jié)構(gòu)對稱，互為同構(gòu)關(guān)系。所以，需要將CG 1i和CG 3i清除。

3.1 同構(gòu)判斷的前提條件

在運動鏈基于胚圖的綜合方法中，拓撲胚圖的同構(gòu)判斷是關(guān)鍵環(huán)節(jié)。在進行同構(gòu)判斷時，有些特征通過觀察法就可以判斷，比如組成運動鏈構(gòu)件的類型和數(shù)量。首先，觀察需進行同構(gòu)判斷的拓撲胚圖的頂點數(shù)量和類型是否一致，如果頂點數(shù)量和類型不同，就可以直接得出拓撲胚圖不同構(gòu)的結(jié)論。這就說明進行拓撲胚圖同構(gòu)判斷的前提是，拓撲胚圖是由同一組關(guān)聯(lián)桿組推導(dǎo)出的，圖上各頂點的類型和數(shù)量相同，連接各頂點的曲線總數(shù)也一樣。

3.2 特征字符串判斷拓撲胚圖同構(gòu)的條件

3.2.1 特征字符串不同

假設(shè)CG x和CG y分別是由同一組關(guān)聯(lián)桿組下的兩個不同的特征字符串x和特征字符串y引出的拓撲胚圖。如果特征字符串x和y滿足以下條件，CG x和CG y一定互為同構(gòu)關(guān)系。

1）順次將特征字符串y中的n個字符串中的一個或幾個字符串從最左邊移動到最右邊(在不改變需移動字符串前后順序的前提下)，得到新的特征字符串y1，y1中的所有數(shù)字與x相同。

2）將第2步得到的特征字符串y1中所有數(shù)字按從右到左逆序排列，得到新的特征字符串y2，y2中的所有數(shù)字與x相同。

表3中No.1i特征字符串{312, 21, 112, 23}對應(yīng)圖1中CG 1i，No.1特征字符串{213, 32, 211, 12}對應(yīng)圖1中CG 1。首先將No.1i特征字符串的第1個字符串312移動到該字符串的最右邊，得到新的字符串{21, 112, 23, 312}。然后將新得到的字符串中的所有數(shù)字按從右到左逆序排列，得到新的字符串{213, 32, 211, 12}，與No.1特征字符串相同，所以CG 1i和CG 1一定互為同構(gòu)關(guān)系。

3.2.2 特征字符串相同

對于特征字符串x中的所有數(shù)字與特征字符串y完全相同的情況，也就是同一特征字符串的情況，可以引出不同的拓撲胚圖，從而引出不同的運動鏈，在2.2節(jié)中已討論。如何判斷同一特征字符串下拓撲胚圖是否同構(gòu)，僅僅依據(jù)上述條件1）和2）顯然是無法完成的。假設(shè)CG x和CG y是同一特征字符串表示下的拓撲胚圖，可以采用以下方法進行同構(gòu)判斷：

在拓撲胚圖基圓上以開始點為起點，沿著圓周按逆時針或順時針方向?qū)Ω鱾€頂點按（1,2,…,n）進行編號。

將連接各個頂點的每條曲線用兩端的頂點編號表示，因為ne值代表拓撲胚圖中曲線數(shù)目，所以有ne對數(shù)字。

3）如果不考慮數(shù)字的順序，CG x中的所有ne對數(shù)字都能在CG y中找到，那么CG x和CG y互為同構(gòu)關(guān)系，否則為非同構(gòu)關(guān)系。

3.3 拓撲胚圖同構(gòu)判斷實例

3.3.1 實例1

圖3(a)和(b)是兩個10桿的運動鏈。通過鄰接矩陣理論和路徑數(shù)組的方法已判斷了兩圖是非同構(gòu)的[8]。文獻[7]中畫出了兩圖的拓撲胚圖，如圖3(c)和(d)所示。下面用特征字符串來判斷。

首先，觀察兩個拓撲胚圖，都是由6個頂點和9條曲線組成的，說明組成運動鏈的構(gòu)件數(shù)量相同；同時，6個頂點均是三元桿T，說明組成運動鏈的構(gòu)件類型相同。滿足進行拓撲胚圖同構(gòu)判斷的前提條件。然后，寫出圖3(c)的特征字符串為{111,111,111,111,111,111}，圖3(d)的特征字符串為{111,111,111,111,111,111}。

圖3 兩個10桿運動鏈和對應(yīng)的拓撲胚圖

顯然，兩個拓撲胚圖是由同一特征字符串表示的。由3.2.2的方法進行判斷，過程如下：

1）沿拓撲胚圖基圓順時針方向?qū)Ω鱾€頂點進行了編號，如圖3(c)和(d)所示。

如果我們將圖3(c)和(d)的所有頂點均布在基圓圓周上，按本文構(gòu)造拓撲胚圖的方法繪制出的拓撲胚圖如圖4所示，通過觀察法很容易判斷兩圖是非同構(gòu)的。

圖4 頂點分布在基圓上的拓撲胚圖

3.3.2 實例2

圖5(a)、(b)和(c)是表1中No.14關(guān)聯(lián)桿組H+3Q+2T的三個拓撲胚圖，其中，(a)圖的特征字符串a(chǎn)為{11112,211,111,1111,1111,111}，(b)圖的特征字符串b為{111,112,21111,111,1111,1111}，(c)圖的字符串c為{21111,111,1111,1111,111,112}。顯然，三個字符串是不同的。要判斷它們是否同構(gòu)，按照3.2.1的方法，將特征字符串b的最左側(cè)的三個字符串111、112和21111按原字符串前后順序不變，移動到b的最右側(cè)，得到新的特征字符串b1為{111,1111,1111,111,112,21111}；將b1中所有數(shù)字按從右到左逆序排列，得到新的特征字符串b2為{11112,211,111,1111,1111,111}。顯然，b2中的所有數(shù)字與a相同。

圖5 關(guān)聯(lián)桿組H+3Q+2T的三個拓撲胚圖

同理，采用相同的方法，將c的最左側(cè)的第一個字符串21111移動到c的最右側(cè)，得到新的特征字符串c1為{111,1111,1111,111,112,21111}，顯然，c1和b1中的所有數(shù)字相同，按逆序排列后，所有數(shù)字和b2相同，也就是和a相同。因此，三個拓撲胚圖是同構(gòu)關(guān)系。

4 特征字符串與鄰接矩陣的比較

一個n×n階的鄰接矩陣可用來表示一個含n個基本連桿的拓撲胚圖[10]。圖6是圖1中CG 1和CG 1i的鄰接矩陣和特征字符串。

圖6 圖1中CG 1的鄰接矩陣和特征字符串

表示一個含n個基本連桿的拓撲胚圖，用一個n×n階的鄰接矩陣，其數(shù)學(xué)模型和數(shù)學(xué)關(guān)系相對復(fù)雜。應(yīng)用特征字符串來描述時，只需要一個一維數(shù)組就可以，其結(jié)構(gòu)和準則相對簡單。而且，從鄰接矩陣中判別拓撲胚圖的同構(gòu)非常困難，而通過觀察法很容易從特征字符串中判別拓撲胚圖的同構(gòu)，可避免很多不必要的勞動。

5 結(jié)論

1）基于運動鏈拓撲胚圖支鏈上不含二度點的特性，提出了特征字符串的概念。并制定相關(guān)規(guī)則，用特征字符串準確描述代表基本連桿的頂點的相對位置，表示運動鏈拓撲胚圖。

2）每個拓撲胚圖都可以用一個特征字符串來描述，但每個特征字符串并不是只能描述一個拓撲胚圖。

3）根據(jù)指定的判斷準則，采用特征字符串法進行拓撲胚圖同構(gòu)判斷，和鄰接矩陣法比較，數(shù)學(xué)模型簡單，方法有效，判斷準確。

[1]楊廷力.機器人機構(gòu)拓撲結(jié)構(gòu)學(xué)[M].北京:機械工業(yè)出版社,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]羅玉峰,楊廷力,曹惟慶.用關(guān)聯(lián)度和關(guān)聯(lián)度碼識別運動鏈同構(gòu)[J].機械工程學(xué)報,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]丁玲,路懿,崔維,等.運動鏈拓撲胚圖的同構(gòu)判斷[J].機械工程學(xué)報,2012,48(3):70-74.

[11]路懿,毛秉毅,翟旭.閉環(huán)機構(gòu)關(guān)聯(lián)桿組與冗余約束的關(guān)系[J].燕山大學(xué)學(xué)報,2013,37(4):299-304.

Characteristic strings description of robotic kinematic chain topology embryonic graphs

WANG Ying1,2, MAO Bing-yi2

在機構(gòu)基于胚圖的綜合方法中，判別拓撲胚圖的同構(gòu)關(guān)系是一個難題。提出特征字符串的概念，用于描述含較多基本連桿的拓撲胚圖?；谶\動鏈拓撲胚圖支鏈上不含二度點的特性，制定相關(guān)規(guī)則，用特征字符串準確描述代表基本連桿的頂點的相對位置，引出拓撲胚圖。制定判別同構(gòu)拓撲胚圖的相關(guān)準則，論證了拓撲胚圖同構(gòu)的條件。舉實例對同一特征字符串和不同特征字符串描述的拓撲胚圖進行了同構(gòu)判斷。通過與鄰接矩陣方法比較，證明特征字符串法簡單、有效。

拓撲胚圖；同構(gòu)；特征字符串；鄰接矩陣

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

2015-03-04

國家自然科學(xué)基金：多手足并聯(lián)機器人型綜合與協(xié)調(diào)作用理論及應(yīng)用研究（51175447）

王瑩（1981 -），女，講師，博士研究生，研究方向為機器人機構(gòu)學(xué)和并聯(lián)機器人拓撲結(jié)構(gòu)學(xué)。

TH112

A

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