[發(fā)明專利]一種全節(jié)點遍歷路徑優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201010594468.X
• 申請日: 2010-12-17
• 公開（公告）號: CN102004839A
• 公開（公告）日: 2011-04-06
• 發(fā)明（設(shè)計）人: 李鵬杰;鄭眾喜
• 申請（專利權(quán)）人: 北京優(yōu)納科技有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京金闕華進專利事務(wù)所(普通合伙) 11224
• 代理人: 吳鴻維

技術(shù)領(lǐng)域

本發(fā)明屬于路徑規(guī)劃領(lǐng)域，特別應(yīng)用于對源和宿沒有特殊規(guī)定的全節(jié)點遍歷路徑規(guī)劃，其模型可應(yīng)用于SMT(表面貼裝技術(shù))自動檢測路徑規(guī)劃等實際問題。

背景技術(shù)

路徑規(guī)劃作為一種抽象的數(shù)據(jù)模型，其原型可以是存在于任一領(lǐng)域的一個規(guī)劃問題，以自動檢測為例，在工業(yè)自動化領(lǐng)域，很多自動檢測過程都是針對一個平面中的多個檢測點檢查，由于大多數(shù)設(shè)備都是串行工作，需要在檢查完一個節(jié)點后再檢查另一個，路徑優(yōu)化的好就可以明顯的節(jié)省時間，提高檢查效率。

以SMT領(lǐng)域，焊點的自動光學(xué)檢測(AOI)為例，絕大多數(shù)檢測設(shè)備的工作方式是，移動X、Y軸使被檢測的電路板(PCB)與取像的工業(yè)相機產(chǎn)生相對運動，移動相機到需要檢查的位置上方進行曝光取像，獲得圖像后再通過檢測算法進行不良檢查。這樣，整個檢查時間就由控制軸移動時間、相機曝光時間、檢測算法時間等3個不同的時間段的總和決定。由于其中的檢測過程是純粹的軟件過程，可以與控制軸的運動過程和相機的報告過程并行處理，也就是在軸運動和相機曝光的同時，計算機運行檢測算法進行不良檢查，而相機曝光時間一般極小(毫秒級)，整個檢查過程的時間花費主要歸結(jié)為控制軸移動的時間。因此，為了提高檢測速度，縮短軸移動距離、提高電機速度就成了最直接有效的方法，任何電機的速度都有其極限，而且高速電機的功率很高，啟動、停止時對設(shè)備機體的沖擊很大，價格也非常昂貴，所以從設(shè)備綜合性能的角度來講，更好的優(yōu)化檢測過程的路徑，縮小軸移動的距離才是縮小檢測時間最高效的手段。

根據(jù)上面介紹的自動檢查方式，可以不失一般性的假設(shè)被檢測的電路板不運動，只有相機在2維平面上進行運動。將相機停下曝光、檢測的過程抽象為一個節(jié)點，相機移動路徑抽象為連接節(jié)點的邊，邊上的值為相機移動的距離。這樣，尋找最優(yōu)路徑的問題就轉(zhuǎn)化為在檢測節(jié)點網(wǎng)絡(luò)中搜尋最優(yōu)的遍歷路徑。由于實際檢測中，相機可以在任意兩個節(jié)點間移動，所以這個網(wǎng)絡(luò)為一個全向全連通圖。又由于裝載、卸載電路板的過程存在，使得相機可以并行的移動到出發(fā)節(jié)點或從最終節(jié)點回到原點，所以遍歷過程的源節(jié)點和宿節(jié)點可以是任意的。

理論上，尋找一個圖的最優(yōu)遍歷路徑是一個NP完全問題，也就是不可能在有限時間得到真正的最優(yōu)解，因此大多數(shù)檢測設(shè)備都是以橫向或者縱向優(yōu)先的方法取得S型路徑，或者從外到內(nèi)獲得螺旋形的路徑。這幾種常用的方法在檢測點足夠密集的情況下與最優(yōu)遍歷路徑比較相似，但是當(dāng)節(jié)點網(wǎng)絡(luò)不是很密集甚至是稀疏的情況下，會帶來很大的浪費，如圖2所示的情況。而在實際的檢測過程中，由于被檢測的電路板形狀、大小經(jīng)常會變化，電路板上元件的布局也非常不固定，所以固定的S型路徑和螺旋型路徑基本上不可能得到最優(yōu)路徑的近似。

發(fā)明內(nèi)容

為了解決上述問題，提高自動檢測效率，本發(fā)明提供了一種高效、可靠的全節(jié)點遍歷路徑尋優(yōu)方法。所述方法具體包括：

一種全節(jié)點遍歷路徑優(yōu)化方法，其特征在于，所述方法包括以下步驟：

步驟A、根據(jù)需要解決的問題構(gòu)建節(jié)點網(wǎng)絡(luò)，在可能出現(xiàn)分支的地方建立節(jié)點，以從一個節(jié)點到另一個節(jié)點的花費作為該有向邊的值；

步驟B、構(gòu)建節(jié)點網(wǎng)絡(luò)的最小生成樹；

步驟C、根據(jù)最小生成樹，以新增邊花費最小為原則，對所有有分支的節(jié)點，逐一去除分支并建立端點間的連接；

步驟D、不斷重復(fù)步驟C直到網(wǎng)絡(luò)的最小生成樹每個節(jié)點都沒有分支，轉(zhuǎn)化為節(jié)點單向隊列，從而生成優(yōu)化后的遍歷路徑。

優(yōu)選的，所述步驟B中的節(jié)點網(wǎng)絡(luò)一般為雙向或者全向網(wǎng)絡(luò)，所述的雙向網(wǎng)絡(luò)是指兩個連通的節(jié)點間的邊是有向的，即對于連通的A、B節(jié)點，無論從A節(jié)點到B節(jié)點還是從B節(jié)點到A節(jié)點都是可行的(如果A、B節(jié)點間是單向連通的，則只能從A到B，不能從B到A)。所述全向網(wǎng)絡(luò)是指網(wǎng)絡(luò)中任一個節(jié)點和網(wǎng)絡(luò)中的所有其他節(jié)點間都是雙向連通的。兩個節(jié)點間的邊代表從一個節(jié)點到另一個節(jié)點間的花費。

其中所述花費是節(jié)點間的距離，在其他應(yīng)用中也可以是時間、金錢等其他代價，所以在本發(fā)明中對于花費并不僅僅限定于節(jié)點之間的距離。

優(yōu)選的，所述步驟B中構(gòu)建最小生成樹的具體步驟為：優(yōu)選但不限于使用Prim算法構(gòu)建網(wǎng)絡(luò)的最小生成樹。

優(yōu)選的，在所述步驟A中，根據(jù)需要解決的問題構(gòu)建節(jié)點網(wǎng)絡(luò)，其方法為：

根據(jù)具體問題，在可能出現(xiàn)分支的地方建立節(jié)點；

以從一個節(jié)點到另一個節(jié)點的花費作為該有向邊的值；

優(yōu)選的，所述步驟C包括以下具體步驟：

(1)根據(jù)構(gòu)建的最小生成樹建立節(jié)點間的連通矩陣；優(yōu)選的，矩陣橫縱坐標(biāo)均為節(jié)點索引，矩陣值代表橫縱坐標(biāo)節(jié)點對間是否連通，連通的值為1，不連通的值為0；