機(jī)器人運(yùn)動鏈拓?fù)渑邎D的特征字符串描述

王 瑩，毛秉毅

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

機(jī)器人運(yùn)動鏈拓?fù)渑邎D的特征字符串描述

王 瑩1,2，毛秉毅2

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

0 引言

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

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

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

1 構(gòu)造拓?fù)渑邎D的相關(guān)參數(shù)及基本概念

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

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

關(guān)聯(lián)桿組（Associated Linkages，簡稱AL）是基本連桿的組合。一些含有效基本連桿的平面和空間機(jī)構(gòu)的關(guān)聯(lián)桿組已確定[11]，如表1所示。其中，n6，n5，n4和n3分別表示基本連桿H、P、Q、T的數(shù)量；n和ne分別表示拓?fù)渑邎D中頂點(diǎn)和曲線的數(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)拓?fù)渑邎D的一個頂點(diǎn)，并包括一串?dāng)?shù)字。每一串?dāng)?shù)字可以由一個或幾個數(shù)字組成，其中每個數(shù)字表示兩個不同頂點(diǎn)連接的曲線數(shù)目。例如，特征字符串{213,32, 211, 12}可用來表示圖1中的CG 1，是由4個字符串組成的數(shù)組。其中，第1個字符串包括一串?dāng)?shù)字213，對應(yīng)于CG 1中的H頂點(diǎn)，表示基本連桿H與T、Q、P分別由2、1、3條曲線相互連接；同樣，第2個字符串包括一串?dāng)?shù)字32，對應(yīng)于CG 1中的P頂點(diǎn)，表示基本連桿P與H、T、Q分別由3、0、2條曲線相互連接；第3個字符串包括一串?dāng)?shù)字211，對應(yīng)于CG 1中的Q頂點(diǎn)，表示基本連桿Q與P、H、T分別由2、1、1條曲線相互連接；第4個字符串包括一串?dāng)?shù)字12，對應(yīng)于CG 1中的T頂點(diǎn)，表示基本連桿T與Q、P、H分別由1、0、2條曲線相互連接。

2 拓?fù)渑邎D的結(jié)構(gòu)及其特征字符串描述

2.1 拓?fù)渑邎D的結(jié)構(gòu)

每個拓?fù)渑邎D一般都是由一個基圓，n個頂點(diǎn)和ne條曲線構(gòu)成，如圖1所示。基于表1中的n3，n4，n5，n6，n和ne的值，拓?fù)渑邎D的結(jié)構(gòu)可描述如下：

1）一個基圓C；

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

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

一般在構(gòu)造拓?fù)渑邎D時，盡量將n個頂點(diǎn)分布到基圓的圓周上。這樣，可以簡化拓?fù)渑邎D的構(gòu)造，也容易對拓?fù)渑邎D進(jìn)行同構(gòu)識別。

圖1 對應(yīng)于關(guān)聯(lián)桿組H+P+Q+T的拓?fù)渑邎D

圖1為對應(yīng)于表1中No.7關(guān)聯(lián)桿組H+P+Q+T的拓?fù)渑邎D。由圖1中CG 1可以看到，該拓?fù)渑邎D由一個基圓C，均布在其上的代表基本連桿H、P、Q、T的4個點(diǎn)和連接它們的9條曲線組成，且表示H、P、Q、T的頂點(diǎn)分別連接6，5，4和3條曲線，符合表1中No.7關(guān)聯(lián)桿組的參數(shù)值。

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

2.2 拓?fù)渑邎D的特征字符串描述

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

表2 描述圖1中拓?fù)渑邎D的特征字符串

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

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

2）特征字符串中每個字符串對應(yīng)拓?fù)渑邎D的一個頂點(diǎn)，包括一個或幾個數(shù)字，各數(shù)字之和等于該頂點(diǎn)所需連接的曲線數(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)的一些有效的拓?fù)渑邎D，它們彼此不同且非同構(gòu)。表3是圖2中的拓?fù)渑邎D所對應(yīng)的特征字符串。通過觀察發(fā)現(xiàn)，拓?fù)渑邎DCG 3/1和CG 3/2的特征字符串相同，拓?fù)渑邎DCG 5/1、CG 5/2和CG 5/3的特征字符串相同。

由此可以得出，每個拓?fù)渑邎D都可以用一個特征字符串描述，但每個特征字符串并不是只能引出一個拓?fù)渑邎D的結(jié)論。

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

圖2 對應(yīng)于關(guān)聯(lián)桿組H+6T的拓?fù)渑邎D

表3 描述圖2中拓?fù)渑邎D的特征字符串

3 拓?fù)渑邎D的同構(gòu)判斷

一般情況下，同一組關(guān)聯(lián)桿組可推導(dǎo)出幾個不同的拓?fù)渑邎D，但這些拓?fù)渑邎D并不都是有效的，必須判別其同構(gòu)關(guān)系。如果兩個拓?fù)渑邎D的結(jié)構(gòu)相同或是對稱，它們一定是同構(gòu)拓?fù)渑邎D。用CG xi表示CGx的同構(gòu)拓?fù)渑邎D，在拓?fù)渑邎D綜合過程中，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)判斷的前提條件

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

3.2 特征字符串判斷拓?fù)渑邎D同構(gòu)的條件

3.2.1 特征字符串不同

假設(shè)CG x和CG y分別是由同一組關(guān)聯(lián)桿組下的兩個不同的特征字符串x和特征字符串y引出的拓?fù)渑邎D。如果特征字符串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完全相同的情況，也就是同一特征字符串的情況，可以引出不同的拓?fù)渑邎D，從而引出不同的運(yùn)動鏈，在2.2節(jié)中已討論。如何判斷同一特征字符串下拓?fù)渑邎D是否同構(gòu)，僅僅依據(jù)上述條件1）和2）顯然是無法完成的。假設(shè)CG x和CG y是同一特征字符串表示下的拓?fù)渑邎D，可以采用以下方法進(jìn)行同構(gòu)判斷：

在拓?fù)渑邎D基圓上以開始點(diǎn)為起點(diǎn)，沿著圓周按逆時針或順時針方向?qū)Ω鱾€頂點(diǎn)按（1,2,…,n）進(jìn)行編號。

將連接各個頂點(diǎn)的每條曲線用兩端的頂點(diǎn)編號表示，因?yàn)閚e值代表拓?fù)渑邎D中曲線數(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 拓?fù)渑邎D同構(gòu)判斷實(shí)例

3.3.1 實(shí)例1

圖3(a)和(b)是兩個10桿的運(yùn)動鏈。通過鄰接矩陣?yán)碚摵吐窂綌?shù)組的方法已判斷了兩圖是非同構(gòu)的[8]。文獻(xiàn)[7]中畫出了兩圖的拓?fù)渑邎D，如圖3(c)和(d)所示。下面用特征字符串來判斷。

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

圖3 兩個10桿運(yùn)動鏈和對應(yīng)的拓?fù)渑邎D

顯然，兩個拓?fù)渑邎D是由同一特征字符串表示的。由3.2.2的方法進(jìn)行判斷，過程如下：

1）沿拓?fù)渑邎D基圓順時針方向?qū)Ω鱾€頂點(diǎn)進(jìn)行了編號，如圖3(c)和(d)所示。

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

圖4 頂點(diǎn)分布在基圓上的拓?fù)渑邎D

3.3.2 實(shí)例2

圖5(a)、(b)和(c)是表1中No.14關(guān)聯(lián)桿組H+3Q+2T的三個拓?fù)渑邎D，其中，(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的三個拓?fù)渑邎D

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

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

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

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

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

5 結(jié)論

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

2）每個拓?fù)渑邎D都可以用一個特征字符串來描述，但每個特征字符串并不是只能描述一個拓?fù)渑邎D。

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

[1]楊廷力.機(jī)器人機(jī)構(gòu)拓?fù)浣Y(jié)構(gòu)學(xué)[M].北京:機(jī)械工業(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)度碼識別運(yùn)動鏈同構(gòu)[J].機(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]丁玲,路懿,崔維,等.運(yùn)動鏈拓?fù)渑邎D的同構(gòu)判斷[J].機(jī)械工程學(xué)報,2012,48(3):70-74.

[11]路懿,毛秉毅,翟旭.閉環(huán)機(jī)構(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

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

拓?fù)渑邎D；同構(gòu)；特征字符串；鄰接矩陣

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

2015-03-04

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

王瑩（1981 -），女，講師，博士研究生，研究方向?yàn)闄C(jī)器人機(jī)構(gòu)學(xué)和并聯(lián)機(jī)器人拓?fù)浣Y(jié)構(gòu)學(xué)。

TH112

A

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