一種運動鏈拓撲對稱性識別方法

吳昌軍，鄧濤，許輝，張露

（1.重慶交通大學 機電與車輛工程學院，重慶 400074；2.重慶交通大學 航空學院，重慶 400074）

對運動鏈進行綜合是獲得機械裝置新構(gòu)型的主要途徑之一[1-2]。在過去幾十年里，許多有效的綜合方法被陸續(xù)提出。運動鏈之間的等效結(jié)構(gòu)即同構(gòu)被認為是此過程中的一個主要難題，為此學者們對其展開了大量研究[3]。然而頂點（構(gòu)件）的等效結(jié)構(gòu)即拓撲對稱性頂點在一定程度上被忽略，但這并不意味著拓撲對稱性沒有研究的價值[4]。事實上，識別同一鏈中的拓撲對稱性不僅能加快運動鏈的綜合，而且有助于機構(gòu)的枚舉[5]。

群論法[6-7]主要以排列組合為理論基礎(chǔ)來識別構(gòu)件的對稱性，原理簡單，有效性高。然而對于一個n桿鏈來說，頂點標號的排列有n!種，并且排列的數(shù)量會隨著頂點的增加而顯著增加。盡管這些群論法都提出了一套屬于自己的準則來減少不必要的排列，但在某些情況下，排列的數(shù)量仍然是驚人的。構(gòu)件的完全關(guān)聯(lián)鏈表法[8]是通過對鄰接構(gòu)件的層層嵌套來獲得某一構(gòu)件的唯一表示。此方法有效性非常高，但構(gòu)件的完全關(guān)聯(lián)鏈表是一個結(jié)構(gòu)量而非數(shù)值量，并且當n較大時，此鏈表的結(jié)構(gòu)非常復雜而且冗長。對比兩構(gòu)件的鏈表需要比較兩表的層數(shù)以及層數(shù)中各鄰接構(gòu)件的組成情況，這意味著此過程將耗費較多的時間。關(guān)系碼法[9-10]是將某一頂點相鄰接的各頂點的權(quán)值按大小排列以形成此頂點的識別碼，比完全關(guān)聯(lián)鏈表法更簡單、更高效。一級關(guān)系碼的權(quán)值為頂點的度，二級碼的權(quán)值為一級碼，以此可推廣到更高階的關(guān)系碼。然而桿件數(shù)量越大，判定所需的關(guān)系碼級數(shù)也越高。級數(shù)的增加會導致其長度的顯著增加，一些10 桿拓撲圖的IV 級碼已經(jīng)達到60 多位，更重要的是該方法在某些情況下已經(jīng)出現(xiàn)誤判。一種基于廣度優(yōu)先生成樹的方法[11]是通過比較構(gòu)件廣度生成樹的結(jié)構(gòu)特征來進行構(gòu)件的對稱性判定。它計算量小，便于計算機實現(xiàn)，然而當構(gòu)件數(shù)量較大時，廣度優(yōu)先搜索算法的內(nèi)存耗量較大。重標法[12]是根據(jù)提出的一些特定的規(guī)則對運動鏈重新標號，隨后對新舊矩陣進行對比判定對稱性。這種方法可靠性較高，對判定條件的充分性有足夠的理論依據(jù)。然而這些重標規(guī)則十分復雜和繁瑣，涉及大量抽象概念，并且可能會出現(xiàn)好幾種重標的可能，此時效率相對較低。三次冪向量序列（Cubic power vector sequence，CPVS）法[13]是利用鄰接矩陣的三次冪序列作為構(gòu)件的不變量。它效率高，復雜度低，但在判定某些復鉸時會出現(xiàn)誤判。連桿鄰接串法[14]是一種將漢明矩陣簡化表示為數(shù)字串來識別構(gòu)件對稱性的方法，效率高，計算簡單。但對于度較大的構(gòu)件來說，連桿鄰接串非常長，尤其是在大型運動鏈的情況下。此外，如果一階漢明連桿鄰接串失敗，需要二階漢明鄰接串，這使得判定過程變得更加復雜。連桿識別碼（Link identification number，LIN）法[4]是一種構(gòu)件的唯一數(shù)值鏈路標識碼，此標識碼可用來檢測機構(gòu)。然而，該方法僅適用于不超過10 個構(gòu)件的運動鏈。

總體來說，機械結(jié)構(gòu)設(shè)計迫切需要一種簡單，高效和可靠的拓撲對稱性識別方法。然而一方面，針對拓撲對稱性的研究較少，它們大都為同構(gòu)性檢測方法的附加產(chǎn)品。另一方面，現(xiàn)存的對稱性檢測方法大都都涉及一些抽象的概念和復雜的中間參數(shù)比較，且隨著桿副數(shù)量增大，一些方法的效率和有效性會大大降低，很難兼顧簡便性和可靠性。因此，本文基于連桿鄰接矩陣提出了一種新的拓撲對稱性識別方法，即是通過運算獲得一種拓撲對稱性識別碼。它是運動鏈構(gòu)件的一個不變量，不隨著構(gòu)件標號的改變而改變。若兩構(gòu)件的對稱性識別碼相同，則它們是同構(gòu)的，否則是非同構(gòu)的。此方法簡單、高效且整個判定過程在計算機上極易實現(xiàn)。

1 運動鏈的描述

1.1 運動鏈的拓撲圖描述

對于單鉸運動鏈來說，將其桿件表示為頂點，運動副表示為實線便轉(zhuǎn)化成了其對應(yīng)的運動鏈拓撲圖，例如瓦特鏈及其對應(yīng)的拓撲如圖1 所示。

圖1 瓦特鏈及其拓撲圖

在復鉸運動鏈中，若將復鉸等效為一構(gòu)件，并用空心圓表示便得到了其對應(yīng)的雙色拓撲圖[15]，如圖2所示。

圖2 一種復鉸運動鏈及其拓撲圖

基于上述復鉸表達，對于行星輪系來說，只需將齒輪副表示為虛線用于區(qū)分單鉸的實線便可得其對應(yīng)的拓撲圖[16]，如圖3 所示的辛普森行星輪系及其拓撲圖。

圖3 辛普森行星輪系及其拓撲圖

1.2 運動鏈的矩陣描述

本節(jié)將介紹運動鏈的兩種矩陣描述，即連桿鄰接矩陣A（Adjacency matrix）和連桿漢明矩陣H（Hamming matrix）。運動鏈拓撲圖的連桿鄰接矩陣A是其最基礎(chǔ)的矩陣，大多數(shù)識別方法都以它為已知量或輸入量，其元素aij取值為

式中：i和j為連桿標號或頂點標號，i和j為從1 到n的整數(shù)，n為運動鏈的連桿總數(shù)；aij的不同取值代表了不同的運動副類型。

連桿鄰接矩陣的每一行代表了該標號的連桿是否與其他標號的連桿直接連接。圖1 所示的瓦特鏈連桿鄰接矩陣為

20 世紀90 年代，數(shù)字通信領(lǐng)域的漢明技術(shù)被引入到機械領(lǐng)域，并誕生出了漢明矩陣H[17]，近年來被推廣到包含移動副的運動鏈同構(gòu)識別之中[18]。它的元素hij表示連桿i和連桿j各自連接關(guān)系的不同程度。以連桿鄰接矩陣為已知，hij定義為連桿鄰接矩陣的第i行和第j行所有列中不同元素的總和，即：

例如，對于上述瓦特鏈連桿鄰接矩陣中的第1 行和第2 行來說，其第1、2、3、4、6 列的元素都不同，故h12=1+1+1+1+1=5。同理可得圖1 的漢明矩陣，即

2 識別碼的獲得流程與對稱性識別

2.1 識別碼的獲得流程

本文的拓撲對稱性識別碼TSRC（Topological symmetry recognition code）獲得流程如圖4 的階段1 和階段2 所示。

圖4 構(gòu)件拓撲對稱性識別流程

階段1 為從連桿鄰接矩陣中導出本方法的初始量（初始矩陣），階段2 為獲得拓撲對稱性識別碼的運算過程，這個兩階段可細分為以下7 個步驟。

步驟1 由式（1）寫出運動鏈或是運動鏈拓撲圖的連桿鄰接矩陣A，并將其作為本方法的輸入量。

理論上，連桿鄰接矩陣與運動鏈拓撲圖是一一對應(yīng)關(guān)系，它包含了拓撲圖中所有的拓撲信息。因此，絕大多數(shù)的方法都以此為輸入量。但連桿鄰接矩陣的元素并不能作為判定方法的最終量，因其主要只表達了行列號所對應(yīng)的桿件是否直接連接，而實際上兩桿的關(guān)系遠不止如此。要準確地描述兩桿的相互關(guān)系還需將其放入整個拓撲圖中考慮。于是不同的方法從連桿鄰接矩陣中提取了不同的特征信息，這些特征信息的差異導致了識別能力的高低。此外，事實證明使用簡單單一信息量的方法都已經(jīng)出現(xiàn)反例[13-14]。因此為獲得較高的識別能力，本文從連桿鄰接矩陣中提取了多種不同的信息量作為初始量以形成TSRC，見步驟2 與步驟3。

步驟2 計算連桿鄰接矩陣的3 次方陣A3，圖1的A3表達式為

在連桿鄰接矩陣A的m次方陣中，其元素（aij）m的幾何意義為頂點i與頂點j之間距離為m條邊的路徑數(shù)目[17]，如圖1 中A3的元素（a12）3表示連桿1 與連桿2 之間存在5 條距離為3 的路徑，即為（1-2-1-2），（1-2-3-2），（1-4-1-2），（1-4-3-2），（1-6-1-2）。高次鄰接矩陣揭示了拓撲圖中連桿之間更寬泛的連接關(guān)系。因其參與決定元素值的頂點更多，比鄰接矩陣元素更能代表一個頂點的周邊環(huán)境信息，故它被選作本方法的初始量之一。此外，此處取m為3 的主要目的是為了兼顧信息量與計算量。m越大會導致計算量越大，但m次矩陣中所包含的信息量并不會隨著m的增加而顯著增加。

步驟3 由式（3）和式（4）的連桿鄰接矩陣中導出漢明矩陣H。

因以高次鄰接矩陣為基礎(chǔ)的判定方法在某些情況下已經(jīng)失效，這證明其信息量并不足以判定某些實例的拓撲對稱性。因此，本方法引入了漢明矩陣作為第二初始量。它揭示了拓撲圖中桿與桿之間總體連接關(guān)系的不同，其有異于連桿鄰接矩陣。

步驟4 計算漢明矩陣的平方陣H2。

由于以漢明矩陣為判定依據(jù)的一階漢明連桿鄰接串在10 桿鏈中已經(jīng)失效[14]，證明直接利用一階漢明矩陣元素作為最終量的方法也有其適用范圍。于是本文將漢明矩陣平方，放大了拓撲圖中更多的細節(jié)特征，這將有助于提高識別方法的識別能力。

步驟5 求積矩陣H2·A3，圖1 的積矩陣為

由步驟2～ 步驟4 已獲得包含兩種不同信息量的矩陣，本文采用將其相乘的方式獲得一個全新的矩陣。若兩矩陣有一方不同，則將導致乘積不同，從而獲得不同的判定結(jié)果。

步驟6 將積矩陣H2·A3各行中的元素按降序排列得積矩陣行序列RS（Sequence of row），圖1的積矩陣行序列RS 為

對元素排序的目的是消除因元素順序不同而產(chǎn)生的不同識別碼TSRC 和進一步導致的誤判。如積矩陣第二行與第三行的元素分別為1 104，302，782，428，778，302 與428，782，302，1 104，302，778，顯然它們元素組成相同，僅是元素位置不同。若不對它們排序而直接進行后續(xù)運算，則前者識別碼為11 468，后者為13 492。這說明頂點2 與頂點3 不是拓撲對稱關(guān)系，但這與由圖1 中得出的結(jié)論是相互矛盾的，即為一錯誤結(jié)論。

步驟7 將上述行序列RS 中的元素rs乘以相應(yīng)的拓撲因子k，并將所得的乘積求和以獲得拓撲圖的拓撲對稱性識別碼TSRC，即

式中拓撲因子k定義為從1 到n的整數(shù)。

定義拓撲因子并乘以RS 是避免在元素組成不同而和相同的情況下產(chǎn)生相同的TSRC。如兩RS分別為[1 2 3]和[1 1 4]，前者的TSRC 為14，后者為15。若無拓撲因子，則兩者的TSRC 和都為6。圖1 各構(gòu)件的拓撲對稱性識別碼TSRC 如表1 所示。

表1 圖1 各構(gòu)件的TSRC 值

2.2 頂點的拓撲對稱性識別

頂點的拓撲對稱性是指同一拓撲圖中頂點間的等效性。若將某一運動鏈拓撲圖的頂點分別作特殊標記后，獲得的新運動鏈拓撲圖為同構(gòu)[19]，那么這些頂點即為拓撲對稱性頂點。如圖1 中瓦特鏈的頂點1 與頂點4 被標記為機架，見圖5。顯然圖5a）與圖5b）為同構(gòu)關(guān)系，這意味著頂點1 與4 拓撲對稱。

圖5 瓦特鏈形成的兩種同構(gòu)機構(gòu)

因拓撲圖頂點的標號是任意的，所以同一拓撲圖的頂點標號共有n!種?？紤]到圖的幾何意義，頂點之間的相互位置和連接方式等結(jié)構(gòu)信息在拓撲圖中是恒定不變的[13]。故由圖的結(jié)構(gòu)信息并通過一系列數(shù)學方法所衍生得的TSRC 是頂點的一個數(shù)學不變量。所謂“不變量”是指TSRC 的值與拓撲圖中頂點標號的順序無關(guān)，頂點編碼順序發(fā)生變化不會改其TSRC。因此TSRC 可以作為拓撲對稱性的判定依據(jù)。若已知兩頂點是拓撲對稱的，那么它們的識別碼TSRC 應(yīng)相等，反之亦然。其次，如果兩構(gòu)件是非拓撲對稱的，則它們的TSRC 應(yīng)為不相等。

基于上述結(jié)論，從表1 可知頂點1 與4 的TSRC相等，頂點2、3、5、6 的TSRC 也相等，這表明頂點2、3、5、6 也互為為拓撲對稱。

3 判定實例與對比分析

3.1 單鉸運動鏈

單鉸運動鏈取自文獻[14]判定失效的兩實例，如圖6 所示。

圖6 單鉸運動鏈實例[14]

該方法判定圖6a）的10 桿運動鏈共有7 組拓撲對稱性構(gòu)件，即（1）（2，7，10）（3，9）（4）（5）（6）（8）；圖6b）共有9 組拓撲對稱性構(gòu)件，即（1）（2，7）（3）（4）（5）（6）（8）（9）（10）。后圖6a）被更正為8 組對稱性構(gòu)件，即（1）（2，10）（3，9）（4）（5）（6）（7）（8）；圖6b）被更正為沒有拓撲對稱性構(gòu)件。

由2.1 節(jié)可得出圖6 各構(gòu)件的拓撲對稱性識別碼TSRC，如表2 和表3 所示。

表2 圖6a）各構(gòu)件的TSRC 值

表3 圖6b）各構(gòu)件的TSRC 值

由表2 和表3 可知：圖6a）實例中，共存在2 組TSRC 值相等的構(gòu)件，即（2，10）（3，9），這意味著它們?yōu)橥負鋵ΨQ性構(gòu)件組（拓撲對稱性構(gòu)件組是指處于同一組內(nèi)的各構(gòu)件互為拓撲對稱）；圖6b）中構(gòu)件的TSRC 互不相等，即頂點間互不拓撲對稱。這與文獻[14]更正后的正確結(jié)論一致?；谖墨I[14]，復現(xiàn)出的圖6a）的漢明矩陣及其連桿一階漢明串為

連桿一階漢明串由兩部分組成，第一部分為漢明矩陣對應(yīng)的行和，第二部分為漢明矩陣對應(yīng)行的元素組成情況。由上可知圖6a）中存在兩組相等的連桿一階漢明串，即（2，7，10）與（3，8，9），這意味著同一組內(nèi)的構(gòu)件連接關(guān)系相同，但事實上從圖中可以看出構(gòu)件8 與構(gòu)件3、9 的連接關(guān)系并不相同，構(gòu)件3、9 都與公共構(gòu)件4 相鄰接。最終，前期未能正確區(qū)分出構(gòu)件3、8、9 的連桿一階漢明串導致了連桿鄰接串（見表4）錯誤地識別出構(gòu)件2、7、10 為拓撲對稱。由上可見漢明矩陣只表現(xiàn)出了連桿間的總體連接特性（構(gòu)件3、8、9 都與1 二副桿，2 三幅桿相鄰接），而細節(jié)特征（構(gòu)件8 不與構(gòu)件4 相鄰接）在一定程度上已被忽略。

表4 圖6a）各構(gòu)件的連桿鄰接串

總的來說，文獻[14]是一種僅以漢明矩陣為依據(jù)的拓撲對稱性判定方法。盡管它簡單，效率高，但它卻存在有效性低的嚴重問題，畢竟有效性才是對于一種方法最本質(zhì)的要求。后來，雖然經(jīng)過改進得到的2 階連桿鄰接串成功區(qū)分了該反例，但這也加大了計算量。相反，本文中的方法包含了更多的拓撲信息，這是成功區(qū)分這兩對反例的關(guān)鍵。更重要的是本方法同樣簡潔高效，并且對比TSRC 比對比冗長的連桿鄰接串更加容易。

3.2 復鉸運動鏈

復鉸運動鏈取自文獻[13]中判定失效的實例。該方法判定圖7a）頂點9 和頂點10 是拓撲對稱的，圖7b）中頂點沒有拓撲對稱關(guān)系。而事實上由拓撲圖特性可知圖7a）沒有拓撲對稱關(guān)系，圖7b）中存在5 組拓撲對稱性頂點，即（1，3）（2）（4，8，9，10）（5，7）（6）。

圖7 復鉸運動鏈實例

圖7 各頂點的拓撲對稱性識別碼TSRC 分別列于表5 與表6 中。

表5 圖7a）各頂點的TSRC 值

表6 圖7b）各頂點的TSRC 值

由表5 和表6 可知：圖7a）中頂點的TSRC 互不相等，即頂點互不拓撲對稱；圖7b）存在3 組TSRC 相等的頂點，即（4，8，9，10）（5，7）（1，3）為拓撲對稱性頂點組。這與由拓撲圖特性得出的結(jié)論一致。

由文獻[13]復現(xiàn)出圖7a）的CPVS值，見表7。頂點9 和10 的CPVS 相等，即為文獻指出的潛在相似性（對稱性）頂點。最終根據(jù)潛在相似性頂點和其能形成的所有可能的排列組合構(gòu)建判定矩陣以排除實際頂點中有相等的CPVS 卻不對稱的情況，但在上述例子中這種排除效果似乎并不明顯以致得出頂點9 和頂點10 拓撲對稱的錯誤結(jié)論。

表7 圖7a）各頂點的CPVS 值

總的來說，此方法[13]對具有較少構(gòu)件的運動鏈非常有效。但當構(gòu)件數(shù)或潛在相似頂點數(shù)增加時，排列組合的所有可能將大大增加，判定的工作量也將顯著增加。此外，判定過程是矩陣與矩陣的比較，這比本文中數(shù)字與數(shù)字的比較更加復雜。另一方面，通過比較和排序得到的這些潛在相似性頂點也可能是非相似頂點，這意味著CPVS 的篩選能力還有待提高。更重要的是該方法也存在有效性不足的問題。然而對于本方法來說，相同的TSRC 即代表相似性，并且不需要矩陣元素的后續(xù)排列和組合，這使得本方法更加簡潔高效。

3.3 行星輪系

行星輪系的實例來自于參考文獻[13]，如圖8所示。圖8a）包含1 個復合鉸鏈，4 個齒輪副；圖8b）僅包含4 個齒輪副。由文獻知圖8 存在4 組拓撲對稱性頂點，（1）（2，4）（3，5）（6，7）；圖8b）不存在拓撲對稱性頂點。

圖8 行星輪系實例

上述實例各頂點的拓撲對稱性識別碼TSRC 列于表8 和表9 中。

表8 圖8a）各頂點的TSRC 值

表9 圖8b）各頂點的TSRC 值

由表8、表9 可知，圖8a）中存在3 組TSRC 值相等的頂點，即（6，7）（2，4）（3，5），它們?yōu)橥負鋵ΨQ性頂點組；圖8b）中頂點的TSRC 互不相等，即頂點互不拓撲對稱，此結(jié)果與文獻[13]一致。

4 結(jié)論

1）本方法創(chuàng)造性地對漢明矩陣進行平方運算以獲得運動鏈的更多細節(jié)信息，并將漢明矩陣的平方陣與鄰接矩陣的立方陣相乘獲得了一個全新的包含大量拓撲特征的積矩陣。并定義了拓撲因子，將拓撲因子與積矩陣行序列的乘積求和得到運動鏈構(gòu)件的不變量，即運動鏈拓撲對稱性識別碼TSRC。

2）本方法邏輯簡單易理解，開發(fā)本方法的計算機程序非常容易，即使對于僅有編程基礎(chǔ)的人員來說也是如此。通過計算機程序，只需輸入連桿鄰接矩陣即可實現(xiàn)自動識別，過程簡單，高效，準確。

3）對于其他方法失效的實例，本方法仍舊能夠成功識別。方法的有效性經(jīng)過了大量的實例驗證，其中包括全部8 桿、10 桿1 自由度運動鏈，9 桿2 自由度運動鏈，含2 個復鉸的8 桿1 自由度運動鏈，6 桿1 自由度齒輪鏈。但因篇幅限制，并未詳述。

4）本方法易推廣到其他類型運動鏈的拓撲對稱性識別中，如含移動副和凸輪副的運動鏈等，只需簡單修改連桿鄰接矩陣形式即可。然而，本方法目前只在平面運動鏈中做了大量的驗證，對于空間運動鏈的拓撲對稱性，尚需更深入的研究。