蘭斌

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

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

前言

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

1.白車身焊接特點(diǎn)

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

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

1.2焊點(diǎn)數(shù)量多。每個(gè)焊接工位上面有多臺(tái)機(jī)器人，每臺(tái)機(jī)器人負(fù)責(zé)的焊點(diǎn)一般二十個(gè)左右。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.仿真實(shí)例驗(yàn)證

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

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

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

距離矩陣D是通過(guò)焊點(diǎn)坐標(biāo)計(jì)算出來(lái)的，取D的上三角T矩陣如下：

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

5.結(jié)論

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

參考文獻(xiàn)：

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

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

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

[4]馬良.旅行推銷員問(wèn)題的算法綜述.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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.