蘭斌

摘要：針對目前白車身焊接機器人路徑規(guī)劃不合理的問題，總結(jié)歸納了不同算法的優(yōu)點和不足，改進了貪婪算法容易進入局部最優(yōu)的缺陷，并提出一種基于刪除最大的距離的路徑規(guī)劃新算法。結(jié)合實際生產(chǎn)線車身側(cè)圍焊點布局，用兩種算法作了對比分析，最后用DELMIA軟件進行了實例驗證。

關(guān)鍵詞：白車身；路徑規(guī)劃；TSP問題；貪婪算法

前言

隨著社會經(jīng)濟和科學(xué)技術(shù)的快速發(fā)展，焊接機器人技術(shù)不管是在研究領(lǐng)域還是工程實踐領(lǐng)域都有了很大的提高。焊接機器人在白車身焊接上的運用，很大程度上提高了焊接質(zhì)量，改善了工人的勞動條件，提高了生產(chǎn)效率。而點焊以其獨特的成本優(yōu)勢使得它成為了目前國內(nèi)的各大汽車組裝廠的主要焊接方式。然而在實際生產(chǎn)過程中，傳統(tǒng)的點焊機器人一般采用路采用在線示教方法對機器人的路徑進行規(guī)劃和仿真，由于工作任務(wù)和工作環(huán)境的復(fù)雜性，并且多臺機器人還需避免相互干涉和碰撞，因此，實際工作中需對機器人反復(fù)調(diào)試，從而會導(dǎo)致機器人路徑的設(shè)計工作量大、效率低，且不便于優(yōu)化、無法并行工作[1]。本文在對點焊機器人和車身進行虛擬建模的基礎(chǔ)上，提出基于刪除最大距離的新型算法，并編寫算法實現(xiàn)程序，在DELMIA軟件仿真中實現(xiàn)點焊機器人路徑自動規(guī)劃，在很大程度上提高點焊機器人的路徑規(guī)劃設(shè)計效率，提高了點焊機器人的工作效率。

1.白車身焊接特點

焊接工藝是整車制造廠四個工藝之一，是白車身加工制造的重要環(huán)節(jié)，白車身焊接包括對發(fā)動機倉，前底板，后地板，側(cè)圍，頂棚和五門一蓋等零部件或零部件總成的裝配焊接。本文就側(cè)圍工位機器人點焊具有如下特點：

1.1工作環(huán)境復(fù)雜。側(cè)圍工位主要運用點焊機器人進行自動化焊接，焊接工位包括機器人群組，工裝夾具，車身工件，傳輸裝置等。機器人的活動范圍是有限的，特別是在多臺機器人在同一工位上執(zhí)行操作的時候，往往會對機器人的路徑規(guī)劃造成很大的困難。

1.2焊點數(shù)量多。每個焊接工位上面有多臺機器人，每臺機器人負責(zé)的焊點一般二十個左右。

1.3使用的焊接方法多。包括電阻點焊、激光焊、CO2氣體保護焊等等。其中電阻點焊因其獨特的成本優(yōu)勢，良好的焊接性能，是目前國內(nèi)整車廠中應(yīng)用最廣泛的焊接方式。

1.4對焊接技術(shù)要求高。對焊接產(chǎn)品有高的尺寸精度要求，對焊縫接頭有高的性能要求，對批量化焊接生產(chǎn)有高品質(zhì)的要求，對焊接過程有高節(jié)拍、高效率的要求[2]。

一臺整車的焊點數(shù)有4000～5000個，每個人或是每臺機器人負責(zé)的焊點一般二十多個，因此對車身焊點的路徑規(guī)劃顯得很重要，一個好的路徑不僅能節(jié)省人力、物力、財力，更重要的是能節(jié)省時間，提高效率和生產(chǎn)效益。

2.路徑優(yōu)化數(shù)學(xué)模型及優(yōu)化算法

2.1.TSP旅行商問題基本思想和數(shù)學(xué)模型

旅行商問題（TSP）是組合優(yōu)問題中典型的NP-完全問題，是許多領(lǐng)域內(nèi)復(fù)雜工程優(yōu)化問題的抽象形式。TSP問題是這樣描述的：設(shè)有n個城市，一個旅行商從其中一個城市出發(fā)，最后回到出發(fā)的城市，其余n-1個城市，有且只能經(jīng)過一次，目標(biāo)是所經(jīng)過的路徑距離最短，這就是著名的旅行商問題（TSP）。用圖論的語言來描述，正權(quán)圖G=（V，E，W）中，包含圖G中每個點至少一次的一條環(huán)路稱為旅行商環(huán)路，一條具有最小權(quán)和的旅行商環(huán)路稱為最佳旅行商環(huán)路，求最佳旅行商回路的問題稱為旅行商問題（TSP）。而具有最小權(quán)和的哈密頓回路稱為最佳哈密頓回路問題[3]。

旅行商問題（TSP）的數(shù)學(xué)模型描述如下：

設(shè)G=< V，E> 為賦權(quán)圖，V={1，2，...，n}為頂點的集合，E為邊的集合。各頂點間距離 已知（ >0， ，i，j V），并設(shè)

這里，S是V頂點集合的任意的一個子集，第一個約束意味著對每個頂點而言，僅有一條邊進和一條邊出，后一約束則保證了沒有任何子回路解的產(chǎn)生。于是，滿足上述約束的解構(gòu)成了一條哈密頓回路。

2.2.改進貪婪算法及實現(xiàn)

求解TSP旅行商問題的解法很多，主要分為精確解法和近似解法兩大類。精確算法能得到TSP的精確解，對于TSP的一些特殊情況，業(yè)已研究出一系列非常優(yōu)美的結(jié)果，如：機器排序問題（Gilmore等，1964）、二分圖情形（Lawler，1971）、平面TSP中的一些特例（Burkard，1989），等等?？山馇樾蔚慕Y(jié)果都已經(jīng)成為了成熟的定理。還有一些其他的精確算法如：線性規(guī)劃算法、動態(tài)規(guī)劃法、分之界定算法等。近似算法包括插入算法，最近鄰算法，Clark&Wright算法，雙生成樹算法等。到了八十年代往后，出現(xiàn)了很多智能算法，如：神經(jīng)網(wǎng)絡(luò)算法，模擬退火算法，遺傳算法，蟻群算法等[4]。上述算法各有各的特點和應(yīng)用范圍，精確算法能得到TSP的精確解，但是當(dāng)維數(shù)n增大時，運算所用的時間成指數(shù)級增長，近似算法能較好的解決時間復(fù)雜度的問題，但是要犧牲一定的精度，智能算法則能在大型復(fù)雜工程問題時表現(xiàn)出其獨特的優(yōu)勢，得到滿足精度要求的解。

貪婪算法又叫貪心算法。貪婪算法（greedy algorithm）是一種解決最優(yōu)化問題的近似方法[5]。它是一種逐步構(gòu)建最優(yōu)解的方法，在對問題求解時，總是做出當(dāng)前看來最好的選擇。，貪婪算法并不要求對所有問題都能得到整體最優(yōu)解，而是某種意義上的局部最優(yōu)解，在大量實際應(yīng)用中，能得到問題的整體最優(yōu)解或者是整體最優(yōu)解的近似解[6]。

貪婪算法在每個決策階段作出的決策不可更改，作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion），也稱貪婪因子。在路徑規(guī)劃中，路徑的最小值即為貪婪因子。具體的算法流程如下：

Step1：輸入n*n維距離矩陣D（對角元素為0的對稱矩陣）和解矩陣X（和D矩陣同維數(shù)的0矩陣）。

Step2：選擇任一頂點作為出發(fā)點，比較其他頂點與當(dāng)前點的距離，選擇最小距離的頂點相連。解矩陣X中對應(yīng)連接的邊賦值為1.

Step3：若最小距離的頂點已經(jīng)在已連接的路徑中，則賦值這個距離為無窮大，循環(huán)Step2.最終得到解矩陣X。

3.基于刪除最大距離算法技術(shù)方案研究

總結(jié)以上算法，本文作者提出了一種基于刪除最大距離的焊接機器人路徑優(yōu)化的近似算法。應(yīng)用于較小維數(shù)的路徑優(yōu)化，新算法的時間復(fù)雜度為O（ ），能較快的收斂，并且思路簡單，操作方便?；趧h除最大距離算法與貪婪算法有相似之處，也容易產(chǎn)生局部解，經(jīng)過改進，較小維數(shù)上能避免局部最優(yōu)解的產(chǎn)生。在某種程度上，解要比貪婪算法更優(yōu)。具有一定的應(yīng)用價值。

基于刪除最大距離算法流程如下：

Step1.構(gòu)造一個n*n維距離矩陣D（對角線元素為0的對稱矩陣）和解矩陣X（和D矩陣同維數(shù)的全1矩陣）。并對距離矩陣中元素從小到大進行排序。

Step2.選出最長距離，即最長邊，兩個頂點如果各連接的邊數(shù)多于兩條，則刪除當(dāng)前最長邊，并把解矩陣中的當(dāng)前位置元素賦值為0.循環(huán)直至所有滿足要求的邊都刪除完為止。

Step3.在執(zhí)行完Step2之后會出現(xiàn)兩種情況：

3.1所有頂點都連接兩條邊，滿足哈密頓回路，刪除最長邊，形成開環(huán)，得到需要的解矩陣。

3.2某一個或多個頂點連接邊數(shù)多余兩條或者形成局部環(huán)，形成局部最優(yōu)解。

①某一個頂點或多個頂點連接邊數(shù)多余兩條處理如下。

找出當(dāng)前頂點所連接邊中最長的一條，在保證當(dāng)前頂點連接邊的另一頂點所連接邊數(shù)大于一條時，刪除當(dāng)前邊，直到當(dāng)前頂點所連邊數(shù)等于1為止。

②形成局部環(huán)處理。刪除局部環(huán)中最長邊。

③至此形成了兩條以上的由數(shù)個頂點連接的開環(huán)。找出每條開環(huán)的端點，計算不在同一條環(huán)的各個端點之間的距離，選擇最短的連接，直至所剩端點為2為止，形成一條開環(huán)鏈。得到需要的解矩陣。

基于刪除最大距離算法流程圖如下：

4.仿真實例驗證

DELMIA數(shù)字制造解決方案可以使制造部門設(shè)計數(shù)字化產(chǎn)品的全部生產(chǎn)流程，在部署任何實際材料和機器之前進行虛擬演示。DELMIA軟件由兩個相互關(guān)聯(lián)的獨立軟件DPE（Digital Process Engineer ）和DPM（Digital Process Manufacture）組成。

Robotics模塊是一個基于物理的、可伸縮的三維機器人仿真解決方案?？捎糜趯?fù)雜的，多設(shè)備機器人工作單元進行建模和離線編程。利用Robotics可快速和圖形化的構(gòu)造各種應(yīng)用工作單元作業(yè)，如焊接、噴涂、搬運、打磨和裝配等。下圖表示利用DELMIA/Robotics對車身焊接側(cè)圍某工位的路徑仿真畫面。

本文的焊點分布來自某整車制造企業(yè)焊裝生產(chǎn)線側(cè)圍總成工位SJ12機器人焊接焊點布局。焊接方式為點焊，生產(chǎn)節(jié)拍為70S。其中兩層焊焊點10個，三層焊焊點7個。本文采用基于刪除最大距離算法所求路徑與改進貪婪算法和某整車制造企業(yè)生產(chǎn)線生產(chǎn)的路徑進行對比，對比的標(biāo)準(zhǔn)是路徑總和最短。

距離矩陣D是通過焊點坐標(biāo)計算出來的，取D的上三角T矩陣如下：

基于刪除最大距離算法的距離總長和貪婪算法距離總長對比，從表1中可看出，貪婪算法從1～17作為起始點，刪除最大距離算法較貪婪算法更優(yōu)。

5.結(jié)論

路徑規(guī)劃的算法有很多，針對不同的具體情況，各有各的優(yōu)勢和不足。本文解決了貪婪算法容易陷入局部最優(yōu)的問題，并提出了一種基于刪除最大距離的新算法。使用matlab編程實現(xiàn)，調(diào)用DELMIA/Robotics模塊對汽車車身側(cè)圍某一工位點焊機器人路徑進行了仿真，兩種算法進行對比分析。分析結(jié)果表明，基于刪除最大距離的算法能比較好的優(yōu)化路徑，滿足路徑規(guī)劃的要求。

參考文獻：

[1]張勇智，韓贊東.白車身裝焊單元點焊機器人路徑規(guī)劃研究.機械設(shè)計與制造，2006.

[2]海江，羅生斌.白車身側(cè)圍工位焊接機器人路徑優(yōu)化研究[J].制造業(yè)自動化，2005，27（7）：35-38.

[3]管琳，白艷萍.用分支定界法求解旅行商問題.中北大學(xué)學(xué)報，2007，28（2）：104-107.

[4]馬良.旅行推銷員問題的算法綜述.數(shù)學(xué)的實踐與認識，2000，30（2）：156-165.

[5]Jean-claude Agnese，Pascal Brousse.Sch- eduling Techniques for a Constellation Visibil-ities[R].ASS98-303，1998.

[6]http：//baike.baidu.com/view/298415.htm？fromId=1628576.