最短路徑算法在電阻片落料系統(tǒng)中的應(yīng)用

朱菊香

（常州鐵道高等職業(yè)技術(shù)學(xué)校機(jī)電工程系，江蘇 常州213011）

0 引言

落料是利用沖裁取得一定外形的制件或坯料的沖壓方法，在電阻片生產(chǎn)中經(jīng)常會(huì)用到這一制造工藝。以某公司PT06電阻片的生產(chǎn)為例，它需要經(jīng)過(guò)兩次落料，第一次落料一次剔除基板上的不合格品，第二次落料將基板上剩余的合格品一次性沖落。在第一次落料時(shí)，需要知道不合格電阻的位置，并以較短的時(shí)間或運(yùn)動(dòng)路徑來(lái)沖除不合格品。

本文利用Prime最小生成樹(shù)算法來(lái)解算沖壓機(jī)構(gòu)的最短運(yùn)行路徑，縮短了落料過(guò)程的時(shí)間，尤其在基板不良品較多時(shí)，效果明顯。

1 落料系統(tǒng)的工作流程

整個(gè)落料系統(tǒng)是基于X—Y導(dǎo)軌結(jié)構(gòu)的，包括機(jī)架、基板夾具、移動(dòng)工作臺(tái)、導(dǎo)軌、絲杠、氣壓沖頭及步進(jìn)電機(jī)等。PT06電阻片的基板為長(zhǎng)方形的環(huán)氧樹(shù)脂印制板，其上共印制了12行20列共240個(gè)碳膜電阻片?；鍔A具用來(lái)放置待測(cè)的電阻片基板，在其下方按電阻片在基板上的位置排列了測(cè)試探針。

工作流程如下：（1）電阻片基板進(jìn)入基板夾具定位；（2）測(cè)試探針升至測(cè)試高度；（3）系統(tǒng)掃描測(cè)試探針處的檢測(cè)信號(hào)大小，獲得每個(gè)電阻片的阻值及不合格品在基板上位置；（4）氣壓沖頭到達(dá)基板上方，根據(jù)不合格品的位置信息沖落廢品；（5）電阻片基板退出夾具，送至成品區(qū)批量落料。以上過(guò)程中耗時(shí)最多的便是沖落不合格品的過(guò)程。

2 不合格品的定位

基板上的電阻片是通過(guò)20路運(yùn)算放大電路來(lái)采樣的，每次采樣采集某一行電阻片的阻值，這樣共采樣12次后便能獲得所有240個(gè)電阻片的阻值。控制器通過(guò)控制20片多路模擬開(kāi)關(guān)CD4067的通道地址，將12行的測(cè)試探針信號(hào)連接至運(yùn)放電路。

通過(guò)兩個(gè)參數(shù)便可判斷不合格電阻片的位置信息。第一個(gè)參數(shù)為該電阻片所對(duì)應(yīng)的CD4067的通道地址，第二個(gè)參數(shù)為該CD4067模擬輸出端所對(duì)應(yīng)的模數(shù)轉(zhuǎn)換器的通道號(hào)。將這兩個(gè)通道參數(shù)合并，便可得到不合格電阻片在基板上的位置，如圖1所示。

圖1 電阻片位置示意圖

圖中，左側(cè)的0000～1100是CD4067的通道地址，0000代表選通第0個(gè)模擬通道，1100代表選通第11個(gè)模擬通道。CD4067的通道地址也代表了電阻片在基板上的行位置。上方AIN0～AIN19是20片CD4067模擬輸出端對(duì)應(yīng)的ADC通道號(hào)，代表了電阻片在基板上的列位置。若CD4067的第1個(gè)通道選通，則行碼為0001，又發(fā)現(xiàn)PA7通道所對(duì)應(yīng)的AD轉(zhuǎn)換值超出了5%的范圍，即模擬通道7的采樣值超標(biāo)，則轉(zhuǎn)換成電阻片的位置為（1，7），即第1行、第7列。

3 最短路徑解算

可通過(guò)行列碼來(lái)儲(chǔ)存不合格電阻片的位置信息。若CD4067的第1個(gè)通道選通，則行碼為0001，又發(fā)現(xiàn)第7個(gè)通道的采樣數(shù)據(jù)超出了合格范圍，則第1行、第7列的電阻片為不合格品，記行列碼為（1，7）。

為了縮短工作臺(tái)移動(dòng)的時(shí)間，節(jié)省電力和提高工作效率，需要對(duì)工作臺(tái)的移動(dòng)路徑作出規(guī)劃，即要找出一條最短路徑，并將該路徑存入不合格電阻片隊(duì)列中供控制程序讀取，使得按該隊(duì)列順序可在最短的時(shí)間內(nèi)將不合格電阻片沖除。

圖2為不合格電阻片組成的一個(gè)圖數(shù)據(jù)結(jié)構(gòu)示例。

圖2 不合格電阻片組成的圖結(jié)構(gòu)

圖中每個(gè)頂點(diǎn)代表一個(gè)不合格電阻片，頂點(diǎn)與頂點(diǎn)之間的權(quán)值為這兩個(gè)電阻片之間的距離。如第1行第1列頂點(diǎn)與第3生成的。顯然，遍歷所有頂點(diǎn)的最短路徑為（1，1）、（4，1）、（2，2）、（3，3）、（1，4）。

遍歷所有頂點(diǎn)又使路徑達(dá)到最短的算法在數(shù)據(jù)結(jié)構(gòu)中被稱(chēng)為求解最小生成樹(shù)。構(gòu)造最小生成樹(shù)有多種算法，這些算法往往都利用了最小生成樹(shù)的 MST性質(zhì)，即先假設(shè)N＝（V，｛E｝）為一個(gè)聯(lián)通圖，U是頂點(diǎn)集V的一個(gè)非空子集，若（u，v）是一條具有最小權(quán)值（最短路徑）的邊，則其中u∈U，v∈V－U，必存在一棵包含邊（u，v）的最小生成樹(shù)。

本設(shè)計(jì)采用的Prime算法即是利用MST性質(zhì)求解最小生成樹(shù)（最短路徑）的算法。它假設(shè)N＝（V，｛E｝）是聯(lián)通網(wǎng)，TE是N 上最小生成樹(shù)中邊的集合，Prime算法從U＝｛u0｝（u0∈V），TE＝｛空｝開(kāi)始，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V－U的邊（u，v）∈E中找一條代價(jià)最小的邊（u0，v0）并入TE，直至U＝V為止。

此時(shí)，TE中必有n－1條邊，且T＝（V，｛TE｝）為N的最小生成樹(shù)，也即本設(shè)計(jì)要求解的最短路徑。

軟件系統(tǒng)找出這一最短路徑之后，將這些頂點(diǎn)（電阻片位置）的行列坐標(biāo)按遍歷次序存入一個(gè)隊(duì)列當(dāng)中，提供給步進(jìn)電機(jī)控制模塊讀取。

為支持Prime算法，需要一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)來(lái)描述電阻片狀態(tài)。一般情況下，圖的數(shù)據(jù)結(jié)構(gòu)可由鄰接矩陣、鄰接表或多重鄰接表來(lái)表示。本設(shè)計(jì)中采用鄰接表來(lái)存儲(chǔ)圖數(shù)據(jù)。若用鄰接矩陣，因采用數(shù)組的方式來(lái)存儲(chǔ)數(shù)據(jù)，所以需要占用240個(gè)存儲(chǔ)單元，而不合格電阻片畢竟為數(shù)不多，因此會(huì)使鄰接矩陣產(chǎn)生大量無(wú)用的“0”元素。而若采用鏈接存儲(chǔ)結(jié)構(gòu)的鄰接表可避免這樣的問(wèn)題出現(xiàn)。鄰接表的節(jié)點(diǎn)數(shù)可隨不合格電阻片的數(shù)目動(dòng)態(tài)調(diào)整。對(duì)于圖2所示的情形，用鄰接表來(lái)存儲(chǔ)的形式如圖3所示。圖3表示的是一個(gè)無(wú)向重聯(lián)通圖，第一列框左邊的序號(hào)代表節(jié)點(diǎn)編號(hào)，框內(nèi)信息為不合格電阻片位置，右側(cè)各框中的信息分別為節(jié)點(diǎn)編號(hào)、權(quán)值（節(jié)點(diǎn)間距離）、下一個(gè)節(jié)點(diǎn)的存儲(chǔ)地址。

圖3 不合格電阻片的鄰接表結(jié)構(gòu)

4 結(jié)語(yǔ)

大量試驗(yàn)表明，落料系統(tǒng)應(yīng)用最短路徑解算方法之后取得了較好的效果。最短路徑求解的應(yīng)用，有效縮短了氣動(dòng)沖壓頭在X—Y導(dǎo)軌上的移動(dòng)行程，由此帶來(lái)的好處不僅為縮短空程時(shí)間，電力消耗也得到降低，設(shè)備維護(hù)周期也變得更長(zhǎng)。因電阻片產(chǎn)量巨大，即使在每個(gè)環(huán)節(jié)僅節(jié)省數(shù)十秒的空程時(shí)間，最后也能獲得可觀的經(jīng)濟(jì)效益。

［1］張曉敏．構(gòu)建整體化的自動(dòng)化測(cè)試平臺(tái)［J］．中國(guó)高新技術(shù)企業(yè)，2010（22）：24－25．

［2］嚴(yán)蔚敏，吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）［M］．北京：清華大學(xué)出版社，2011．

［3］王安敏，牛傳猛，崔偉．基于X－Y工作平臺(tái)的步進(jìn)電機(jī)閉環(huán)控制系統(tǒng)［J］．微電機(jī)，2010，43（1）：103－105．

［4］殷人昆，陶永雷，謝若陽(yáng)，等．?dāng)?shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC＋＋語(yǔ)言描述）［M］．北京：清華大學(xué)出版社，1999．

［5］王昊，李昕．集成運(yùn)放應(yīng)用電路設(shè)計(jì)360例［M］．北京：電子工業(yè)出版社，2007．