基于MBD的檢測路徑規(guī)劃方法研究

屈力剛，胡寶慧，李 亮

（1.沈陽航空航天大學 機電工程學院，沈陽 110136；2.中航工業(yè)中國空空導彈研究院，洛陽 471000）

0 引言

MBD的定義是指基于模型的信息定義技術，基于MBD建立的全三維環(huán)境不但能夠提高檢測效率還可以確保檢測結果的正確性，將三維實體模型導入三坐標測量機輔助軟件中，可以實現(xiàn)離線路徑規(guī)劃。檢測路徑規(guī)劃是數(shù)字化檢測中一道關鍵步驟，它對檢測效率的影響起到絕對性作用。在現(xiàn)場進行實際檢測操作中，三坐標測量機測頭角度的頻繁變換以及路徑的長短都會影響到檢測的精度和效率，如果只考慮路徑的長短而忽視三坐標測頭角度的頻頻變更，那么得到的不一定是最佳測量路徑，說明路徑規(guī)劃其實是一個測頭方向和路徑距離的組合優(yōu)化問題[1]。國內(nèi)外有很多學者對路徑規(guī)劃進行了研究，Requicha[2]采用貪婪式聚類算法，對檢測點進行檢測方向分集，直至所有檢測點都明確了各自的檢測方向；紀小剛[3]等人將最短路徑距離為核心思想，提出用遺傳算法來完成路徑的優(yōu)化；曾德標[4]等人對模擬退火算法進行了完善，優(yōu)化選擇了測頭檢測方向等。本文提出通過K-means算法與余弦相似度結合，將同一個測頭位姿下測點劃分集合，由于構造一個特征的所有點都能夠在同一個測頭位姿下檢測，所以在進行測頭位姿規(guī)劃中只需要知道每一個特征向量的測頭位姿方向即可，實現(xiàn)在路徑規(guī)劃過程中降低工作量提高檢測效率。蟻群算法[5]是一種仿生算法，該算法是通過螞蟻在找食過程中的行為提出來的，它可以在行走的路徑上產(chǎn)生有利出種族內(nèi)通信的激素，在最短路徑上的螞蟻來往頻率往往多于其他路徑上的螞蟻，原因是最短路徑上留下的通信激素多容易被其他螞蟻發(fā)現(xiàn)并效仿。因此本文采用蟻群算法對得到的測頭位姿集進行集內(nèi)和集間測量點間路徑優(yōu)化。

1 測頭位姿規(guī)劃

1.1 可達性測頭位姿

一般對于測頭位姿來說，要保證所有待檢測點都能進行檢測，盡量規(guī)避檢測過程中產(chǎn)生干涉和碰撞，選擇一個合理的測頭位姿有利于對接下來路徑規(guī)劃提供方便。可達性測頭位姿是指三坐標測量機測頭虛擬成在檢測點無限延長的一條射線，并且與測頭位姿方向相反。在檢測過程中，測頭沒有和零件產(chǎn)生摩擦碰撞，所形成射線的方向就是這個檢測點的可達位姿。根據(jù)前面的原理介紹，我們能夠獲得某個檢測點的全部可達位姿的射線，并且它們最終都會匯集到一個錐空間中，也就是說我們能夠知道每一個檢測點的可達測頭位姿。最后把獲得的全部可達位姿集合進行求交運算，這樣能夠減少重復測頭位姿從而降低個數(shù)。

設p是檢測點，n是檢測點在零件上的外法矢，l是測針的軸線方向，n和l之間的角度為（n，l）。值得注意的是，測頭位姿方向需要和這個檢測點法線之間形成的角度不大于90°，即（n，l）≤90°，若超過這個范圍即是不可達測頭位姿。檢測點聚類通常可以用可達性錐原理來完成，它須要按照測頭轉動最低刻度來把所有點可達性錐進行離散進而獲得可達位姿。三坐標測量機可以保證的測量方向為有限和離散[6]，接下來令全部檢測點的可達位姿通過求交運算一一分析其可達性。在本文研究中，水平面內(nèi)轉動角度即水平角設定為A，豎直平面內(nèi)擺動角度即垂直角設定為B，測頭的檢測方向為水平角和垂直角的組合（A，B），A和B都有最低轉動刻度值，由于采用的測頭轉動最低刻度為15°，即每一個檢測點可達性錐都能夠組合離散出特別多的可達位姿，便會造成接下來求交計算量異常復雜，因此本文選擇以下算法去完成檢測點的聚類。

圖1 點P的可達測頭位姿原理圖

1.2 測頭位姿選擇

關于傳統(tǒng)K-means算法已有的缺陷，許多人提出了改善辦法，但在本文中并不適用，深入研究提出了余弦相似度與K-means結合的優(yōu)化算法。通過衡量兩個特征向量之間的法向夾角的相似性叫做余弦相似度[7]，如果余弦相似度為1，那么這兩個特征的方向是一樣的；如果余弦相似度是0，兩個向量的方向是垂直的；所以余弦相似度范圍在0-1區(qū)間，且無限接近于1兩個特征方向無限接近；然后通過K-means算法將方向無限接近的特征聚類劃分，即可在同一個測頭位姿下測量。

有數(shù)據(jù)集包含了n個特征對象的數(shù)據(jù)集合，并且每一個特征對象都有m維特征屬性，sil（i=1，2，3，…，n；l=1，2，3，…，m）那么代表第i個代表對象的第l維屬性。特征對象si與sj的余弦相似度為：

對特征方向進行相似度衡量，首先對屬性進行標準化處理，避免不同屬性量綱對結果造成偏差的影響，標準化后屬性s*il的公式為：公式中max(sil)指l維屬性中最大值，min(sil)指l是維屬性中最小值。

圖2 余弦相似度示意圖

K-means聚類流程：

1）任意選擇k個聚類數(shù)目，并將選擇的這k個特征對象作為初始的聚類中心。

2）求出每一個特征向量和這k個聚類中心點的余弦相似度，同中心點相似度最接近的特征向量會被劃分到當前類別里。

3）重新求得每一個類別中新的聚類中心點，將每一個類別中全部特征對象的平均值定義為新的中心點，前后進行比較，如果中心點不變那么算法結束，中心點改變將返回第一步。

但是在這個算法中，首先要確定k的取值。

圖3 K-means聚類原理示意圖

為此本文將引用類內(nèi)內(nèi)聚度和類間分離度兩個概念，因為最大化類內(nèi)內(nèi)聚度和類間分離度能夠使聚類效果較好。而輪廓系數(shù)方法[8]，可以同時包含內(nèi)內(nèi)聚度和類間分離度。

2 測量路徑規(guī)劃

2.1 集合內(nèi)路徑規(guī)劃Inpathi

為各個測頭位姿下的集合內(nèi)部路徑規(guī)劃Inpathi，流程如下所示：

在一個集合內(nèi)隨機選取為該路徑的起始點和pote為終止點，添加前一個測頭位姿集合內(nèi)終點areai-1和下一個測頭位姿下起始點areai+1采用最近鄰法求出集合內(nèi)路徑。

重復第一步，但要注意的是，隨機選取點時跳過已選點不能重復選取，對形成的所有路徑作比較，選擇最短路徑。

將這個集合內(nèi)的起止點與選取最短路徑集合內(nèi)的起止點保持一致，目的是為了使求出來的局部最優(yōu)路徑能夠，在全局路徑規(guī)劃中也可以保持較優(yōu)。

當測頭和零件不產(chǎn)生碰撞時，兩個檢測點之間距離disij便是兩點之間的路徑長度。但在實際操作中，不能不考慮檢測精度，所以在檢測路徑中必須添加靠近和回退路徑badis。

最終用公式表示為:

圖4 集內(nèi)順序規(guī)劃流程圖

2.2 集合間路徑規(guī)劃Outpathi,i+1

求解集合間最短路徑，可以歸類于TSP問題，在本文研究中將各個集合的幾何中心點投影到一個平面上，這樣就可以形成以往TSP問題中的一個節(jié)點，將投影到固定平面的所有節(jié)點，構造一個二維點陣，然后采用蟻群算法對形成的二維點陣路徑進行優(yōu)化。蟻群算法實現(xiàn)的主要步驟如下：

1）把路徑信息原始化，設置螞蟻個數(shù)為m，節(jié)點個數(shù)為n。

2）螞蟻k在經(jīng)過每一個節(jié)點時都要按照概率來進行選擇下一個要訪問的節(jié)點，那么在t時螞蟻k從節(jié)點i選擇到節(jié)點j的概率為：

allowed=（0，1，2，…，n-1）為螞蟻k還沒有到達的節(jié)點，即接下來可選取的節(jié)點。α為通信啟發(fā)因子，β為期望啟發(fā)因子，為螞蟻k在t時間i與j之間遺留的通信激素量，為i與j之間距離啟發(fā)程度。

3）求出每一只螞蟻的預期函數(shù)值，找到并記錄目前最佳值。

4）螞蟻在t時間內(nèi)結束一次輪回，各列軌跡上通信激素量調(diào)整原則為下：

公式中，ρ為軌跡持久性，1-ρ為信息殘余因子，為k只螞蟻在這次輪回中殘余在i與j之間路徑上的通信激素量。

5）令n=n+1，對i與j之間路徑，設置為?τij=0。

6）當n＜節(jié)點數(shù)，則轉到第2步；否則結束。

通過以上算法進行仿真實驗，在零件模型上取點得到圖5(a)集間二維點陣的路徑，未經(jīng)蟻群算法優(yōu)化前，距離為839.8297；蟻群算法優(yōu)化后的路徑距離為519.9644，如圖5(b)所示；經(jīng)蟻群算法優(yōu)化路徑自然順暢，測點路徑上縮短為原來的61.91%。

圖5 集合間路徑優(yōu)化效果圖

3 結論

將零件模型導入三坐標測量機軟件中，選取了幾組特征進行現(xiàn)場離線路徑規(guī)劃，圖6(a)所示為未使用本文提出的算法路徑圖，圖6(b)所示為規(guī)劃后的路徑圖，通過表1能夠看出本文研究的算法可以得出較優(yōu)的檢測路徑和較少的檢測時間，極大地提高了檢測效率，在離線路徑規(guī)劃中避免了測頭損壞等損失。

表1 優(yōu)化路徑前后對比表

圖6 使用三坐標測量機現(xiàn)場檢測路徑圖