一種含復鉸運動鏈同構判定的新方法

李安明，孫 偉，侯 宇，黃 森

（武漢科技大學機械自動化學院，湖北 武漢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 結論

提出了一種含復鉸運動鏈描述和判定的新方法，并給出了通過改進鄰接矩陣求解最短距離矩陣的算法。通過比較運動鏈的特征碼、最短距離矩陣的和列陣、最短距離矩陣的特征值特征向量是否相等來判定同構。案例證明了此方法的正確性與高效性。相比其它同構判定法，計算既簡便又有效。并且對于對稱性較高的運動鏈，此方法依然有效。