機(jī)器人制孔自適應(yīng)蟻群路徑規(guī)劃算法*

劉艷梅，王 鑫，馬躍晏

（沈陽航空航天大學(xué)自動化學(xué)院，沈陽 110136）

機(jī)器人制孔自適應(yīng)蟻群路徑規(guī)劃算法*

劉艷梅，王 鑫，馬躍晏

（沈陽航空航天大學(xué)自動化學(xué)院，沈陽 110136）

隨著現(xiàn)代飛機(jī)制造制孔技術(shù)的不斷發(fā)展，對制孔效率、定位精度及加工質(zhì)量提出更高的要求。采用CATIA軟件建立飛機(jī)部件模型，提出自適應(yīng)蟻群算法并應(yīng)用于機(jī)器人制孔路徑規(guī)劃設(shè)計中。仿真實驗表明，信息素?fù)]發(fā)因子的大小對算法的全局搜索能力及收斂速度有直接影響，提出的自適應(yīng)蟻群算法通過動態(tài)調(diào)整信息素?fù)]發(fā)因子，充分改善了制孔方式的無目的性、生成的路徑質(zhì)量低等一些不足之處，從而實現(xiàn)機(jī)器人制孔路徑規(guī)劃的最優(yōu)。

CATIA，自適應(yīng)蟻群算法，機(jī)器人制孔，路徑規(guī)劃

0 引言

在飛機(jī)裝配制孔方面，傳統(tǒng)的人工制孔方法已經(jīng)不能滿足現(xiàn)代飛機(jī)制造業(yè)的需求。隨著機(jī)器人技術(shù)的不斷發(fā)展，機(jī)器人自動制孔已被應(yīng)用于飛機(jī)制造業(yè)，除了能夠滿足飛機(jī)生產(chǎn)的數(shù)量大、時間緊的要求，還提升了飛機(jī)裝配過程中制孔的定位精度以及質(zhì)量，延長了飛機(jī)零部件的使用壽命。在國際上，機(jī)器人自動制孔系統(tǒng)已經(jīng)十分成熟，并被廣泛應(yīng)用于軍用飛機(jī)、民航飛機(jī)的實際生產(chǎn)中。在我國，對機(jī)器人自動制孔技術(shù)的研究相對落后，在飛機(jī)裝配制造中的應(yīng)用開發(fā)也存在不足。20世紀(jì)90年代以來，國內(nèi)開始陸續(xù)引進(jìn)自動制孔設(shè)備，但并未形成生產(chǎn)力，飛機(jī)裝配仍然以手工裝配為主。而國外自動制孔技術(shù)和設(shè)備的研制與應(yīng)用已經(jīng)達(dá)到了較高的水平。在機(jī)器人制孔的研究領(lǐng)域里，路徑規(guī)劃算法［1］是目前研究領(lǐng)域中最重要的部分。路徑規(guī)劃的一般性問題是按照一定的評價標(biāo)準(zhǔn)，機(jī)器人制孔從起點運動到終點，能夠安全，高效地完成制孔任務(wù)。路徑規(guī)劃算法的種類繁多，目前，國內(nèi)外提出了很多算法，如蟻群算法、遺傳算法［2］和粒子群算法等解決機(jī)器人制孔路徑規(guī)劃問題。20世紀(jì)90年代意大利學(xué)者Dorigo和V.Maniezzo最早提出了蟻群算法［3］，是一種源自于自然界的蟻群覓食行為的活動規(guī)律啟發(fā)提出的模擬進(jìn)化算法。蟻群算法作為新式的優(yōu)化算法，它的正反饋性、協(xié)同性和隱含的并行性使其具備不錯的發(fā)展?jié)摿?，靈活性讓它在解決組合優(yōu)化問題上擁有杰出的適應(yīng)性。但是傳統(tǒng)的蟻群算法存在許多不足之處，需要進(jìn)一步改進(jìn)，因此，針對傳統(tǒng)蟻群算法的改進(jìn)是目前研究方向熱點之一。

本文基于CATIA軟件建立飛機(jī)零部件模型［4］，并提取所需要的制孔點位置，通過蟻群算法對設(shè)計出的零部件進(jìn)行路徑規(guī)劃。由于蟻群算法容易出現(xiàn)收斂速度慢和搜索全局最優(yōu)值能力低，所以提出一種自適應(yīng)的動態(tài)調(diào)整該算法中的信息素?fù)]發(fā)因子策略，然后通過不斷地迭代，螞蟻以更大的概率選擇一條最短路徑來實現(xiàn)機(jī)器人自動制孔。

1 飛機(jī)部件模型的建立

CATIA軟件的功能是飛機(jī)產(chǎn)品建模軟件中最強(qiáng)大的一款，能夠?qū)崿F(xiàn)整個飛機(jī)制造的工業(yè)設(shè)計流程，提供全流程開發(fā)的工作環(huán)境。通過建立數(shù)字化的開發(fā)環(huán)境，給使用者提供了一個面向整個設(shè)計制造過程，并對每個部分進(jìn)行模擬仿真，并通過電子通信實現(xiàn)工程人員和非工程人員的信息交流，及時處理出現(xiàn)的問題。本文基于某飛機(jī)部件，在CATIA中創(chuàng)建工藝數(shù)模，針對不同的孔類型進(jìn)行設(shè)計，得到所有的制孔類型，并拾取所有機(jī)器人制孔的孔位點，如圖1所示。

圖1 飛機(jī)零部件模型

基于CATIA軟件建立上述飛機(jī)零部件模型，然后提取所需要的制孔點的點位坐標(biāo)。機(jī)器人制孔的制孔過程實際上就是路徑規(guī)劃問題。而路徑規(guī)劃的優(yōu)劣直接影響其智能化程度的水平，所以選擇一種最優(yōu)的路徑規(guī)劃算法對于機(jī)器人制孔來說，至關(guān)重要。

2 蟻群算法基本原理

蟻群算法是一種基于群體智能尋優(yōu)的啟發(fā)式搜索算法［5］。該算法根據(jù)螞蟻覓食的原理，任意兩點表示螞蟻的起點和終點，初始階段群體根據(jù)相同概率均勻地選擇每條路徑，螞蟻在尋找食物所經(jīng)過的路徑上釋放一種揮發(fā)性分泌物（稱信息素，該物質(zhì)隨時間的推移逐漸揮發(fā)消失，信息素濃度的大小表示路徑的遠(yuǎn)近）。其信息素量決定前行方向，并且螞蟻在尋找食物的過程中會感知信息素強(qiáng)度。螞蟻選擇下一個節(jié)點是通過轉(zhuǎn)移概率，依次類推，最終選擇移動到終點。每條路徑上通過螞蟻的數(shù)量由信息素濃度決定，濃度越高螞蟻選擇該路徑的可能性就越大。螞蟻選擇當(dāng)前路徑的概率會隨著信息素的揮發(fā)和遺留相應(yīng)發(fā)生變化。不斷地更新信息素導(dǎo)致多個路徑上的螞蟻都逐步湊集到最短路徑上，即找到一條可行的最短路徑。通過簡單的模型分析蟻群如何通過信息交流與傳遞的協(xié)作尋找食物，最終獲得蟻穴與食物之間最短路徑的過程。如圖2所示。

圖2 模擬螞蟻覓食原理圖

設(shè)螞蟻從A點出發(fā)，食物在E點。BH、HD距離為1，BC、CD距離為0.5。假設(shè)30只螞蟻由A到E，30只螞蟻由E到A，螞蟻速度設(shè)為1。在t=0時刻，每一條路徑的信息素都為0。第1批從A出發(fā)的螞蟻選擇路徑BHD和BCD概率相同，且螞蟻數(shù)各為15。同理，從E出發(fā)的螞蟻，假設(shè)選擇路徑DHB和DCB的螞蟻數(shù)各為15。在t=1時刻，第2批從A出發(fā)的螞蟻會發(fā)現(xiàn)在路徑BH的信息素強(qiáng)度為15。由第1批從B經(jīng)C向D的15只螞蟻和從D經(jīng)C向B的15只螞蟻共同留在路徑AB的信息素強(qiáng)度為30。由于路徑BC的信息素強(qiáng)度高，則第2批30只螞蟻選擇BC這條路徑的概率要高于選擇BH的概率。同理，第2批從E出發(fā)的30只螞蟻也會有20只螞蟻選擇路徑DCB，有10只螞蟻選擇路徑DHB。通過不斷地循環(huán)，BCD路徑上聚集的信息素強(qiáng)度越來越大，最終所有螞蟻都選擇走這條路徑。如圖2可以看出，螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象。通過這種正反饋機(jī)制，螞蟻最終可以發(fā)現(xiàn)最佳路徑，且絕大多數(shù)的螞蟻都會沿著同一條路徑到達(dá)食物源。

3 基于自適應(yīng)蟻群算法的機(jī)器人制孔路徑規(guī)劃

典型的路徑規(guī)劃是指，在具有障礙物的工作環(huán)境下，按照一定的評價標(biāo)準(zhǔn)，尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的無碰撞路徑。路徑規(guī)劃的優(yōu)劣直接影響機(jī)器人制孔［6］的定位精確、效率程度，所以機(jī)器人制孔要選擇一種優(yōu)秀的路徑規(guī)劃算法。目前已存在許多優(yōu)化算法用來解決該問題，但某些算法存在一定的局限性。本文在充分分析各種算法優(yōu)缺點基礎(chǔ)上，用自適應(yīng)蟻群算法進(jìn)行設(shè)計路徑規(guī)劃，從而找到一條最優(yōu)路徑實現(xiàn)機(jī)器人制孔來完成飛機(jī)零部件。

蟻群算法主要依據(jù)信息正反饋原理和某種啟發(fā)式算法的有機(jī)結(jié)合。正反饋原理是強(qiáng)調(diào)解的性能，但易出現(xiàn)堵塞和停滯現(xiàn)象。蟻群算法出現(xiàn)不足之處的根本原因是解決問題時易出現(xiàn)早熟和局部收斂現(xiàn)象。為解決這一問題，在王穎等的論文［7］中，說明了自適性蟻群算法的基本思想。在蟻群算法的基礎(chǔ)上，引入自適應(yīng)調(diào)整策略，在求解的過程中，解決蟻群算法的局部和全局搜索能力及其收斂速度。而針對路徑規(guī)劃問題，蟻群算法中揮發(fā)因子的大小直接關(guān)系到蟻群算法在求解問題時的全局搜索能力，或者局部搜索能力以及收斂速度。為了解決傳統(tǒng)蟻群算法出現(xiàn)的問題，在參考文獻(xiàn)［8］中提出了各種不同的更新信息素?fù)]發(fā)因子的策略?？紤]到算法的全局搜索能力和收斂速度等問題，提出了自適應(yīng)的對蟻群算法中揮發(fā)因子ρ的值進(jìn)行改變，可以對傳統(tǒng)蟻群算法的不足進(jìn)行改進(jìn)，此算法屬于自適應(yīng)算法。

自適應(yīng)蟻群算法路徑規(guī)劃具體實現(xiàn)過程如下：

3.1 自適應(yīng)蟻群算法初始化

在算法的初始時，假設(shè)在各個路徑上的信息素濃度都是相等的。設(shè)螞蟻的數(shù)目為m只，分別放在n個孔位點上；令初始時刻t=0；循環(huán)次數(shù)計數(shù)器NC=0，則最大代數(shù)為NCmax；信息素強(qiáng)度初值

在每次循環(huán)過程中，將m只螞蟻分散到n個制孔點的位置，這一條件通過列表tabek來實現(xiàn)，并記錄每一輪模擬螞蟻k已經(jīng)走過的各個制孔點，其中k=（1，2，3，…，m）。該列表存儲了 t時刻前每只螞蟻在本次循環(huán)過程中訪問過的所有制孔點位置，借此可以限制在本次循環(huán)過程中再次訪問已經(jīng)訪問過的制孔點。同時，由于列表涵蓋了每只螞蟻經(jīng)過制孔點的順序，計算每只螞蟻在本次循環(huán)中走過的總路徑長度，并得到蟻群算法優(yōu)化的當(dāng)前解。

3.2 選擇下一個制孔點

螞蟻k的轉(zhuǎn)移概率決定制孔點i是否訪問下一個制孔點j。定義在t=0時刻，某一只螞蟻k由點i移動到點j的概率Pijk與能見度和信息素有關(guān)，其表達(dá)式為：

式中，ηij為計算各個孔位點之間的距離（i，j）上的先驗知識或稱為能見度，其值與時間無關(guān)，而與孔位點間的距離有關(guān)，即ηij=1/dij，dij是點i和j之間的距離；α為啟發(fā)式因子，表示路徑上殘留信息素的相對重要性，其值反應(yīng)了隨機(jī)性因素在路徑搜索中的作用；β為期望啟發(fā)式因子，表示路徑的能見度的重要性，其值反應(yīng)蟻群在路徑搜索中確定性因素的作用；Jk（i）為螞蟻k在制孔點i之前沒有訪問過的制孔點位置的集合，與列表相關(guān)聯(lián)；allowedk表示下一步訪問的制孔點，列表tabek中已經(jīng)訪問到的除外。

3.3 自適應(yīng)蟻群算法揮發(fā)因子調(diào)節(jié)策略

在蟻群算法中，衡量信息素?fù)]發(fā)速度的參數(shù)是信息素?fù)]發(fā)因子，因而ρ的大小對算法的執(zhí)行時間、全局搜索能力及收斂速度有直接的影響。傳統(tǒng)蟻群算法在搜素過程中進(jìn)行多次迭代，而且每次迭代都需要多只螞蟻一起搜索，這樣降低了該算法的收斂速度。該算法在處理規(guī)模龐大時，由于信息素不斷揮發(fā)，逐漸減少到0，從而不再被搜索，這樣會導(dǎo)致一些路徑很少或從來沒被訪問到，因此，大大地降低了該算法的全局搜索能力。一般情況下ρ的初始值的取值范圍在0.1～0.9之間，初始值不同所得到的路徑長度就有所不同。所以對初始值從0.1～0.9進(jìn)行實驗，得到相對應(yīng)的路徑長度，如圖3所示。

圖3 揮發(fā)因子ρ與路徑長度的關(guān)系圖

由圖3可以看出，ρ值在0.1～0.6范圍內(nèi)得到曲線較理想，在0.7～0.9的曲線不理想，而在0.4與0.5時得到的路徑長度最為理想。由此可知，通過改變揮發(fā)因子ρ值的大小來達(dá)到想要的最優(yōu)路徑效果。即設(shè)置初始值ρ=0.4，這樣可以避免局部搜索情況的出現(xiàn)。當(dāng)全局搜索經(jīng)過多次還是沒有達(dá)到想要的結(jié)果，并出現(xiàn)傳統(tǒng)蟻群算法的收斂速度慢和全局最優(yōu)解的搜素能力低等問題，提出了一種自適應(yīng)蟻群算法。即對信息素?fù)]發(fā)因子ρ進(jìn)行適當(dāng)?shù)母淖?。其表達(dá)式為：

這樣可以防止ρ過大，路徑上信息素?fù)]發(fā)速度快，螞蟻之間的相互影響變小，算法收斂的收斂速度變慢，甚至使算法最終解的優(yōu)化程度降低；ρ過小，路徑上的信息素保留時間長，有可能再次搜索到已有路徑，從而對算法的隨機(jī)性能和全局搜索能力產(chǎn)生不利影響。

3.4 更新信息素

信息素作為螞蟻進(jìn)行群體信息交流的重要手段，也是實現(xiàn)路徑選擇的重要依據(jù)。每只螞蟻在t時刻依據(jù)轉(zhuǎn)移概率選擇下一制孔點，并在t+1時刻到達(dá)終點。經(jīng)過n個時刻，路徑（i，j）上的信息素將進(jìn)行更新，其表達(dá)式為：

式中 ρ∈（0，1），稱信息素?fù)]發(fā)因子，即表示每個連接上的信息素濃度自動減弱的過程，而1-ρ代表依次循環(huán)中信息素的揮發(fā)程度是孔位點i和點j之間的路徑（i，j）在 t時刻的信息素強(qiáng)度為所有螞蟻在路徑（i，j）上單位長度的信息素量為第 k 只螞蟻在（t，t+n）時間段留在路徑（i，j）上單位長度的信息素量。M.Dorigo提出了3種不同的螞蟻算法模型，依據(jù)不同的信息激素更新的策略分別是螞蟻圈模型、螞蟻數(shù)量模型及螞蟻密度模型，其差別是運用不同的求法求解根據(jù)全局整體的路徑優(yōu)化，使螞蟻完成一次迭代后更新所有路徑上的信息素。其采用螞蟻圈模型表達(dá)式為：

式中，Q為信息素強(qiáng)度；Lk為第k只螞蟻完成一次循環(huán)走過路徑的長度。從式（2）和式（3）中可以看出，對于某一條路徑（i，j）的信息素強(qiáng)度取決于上一次循環(huán)完成后的信息素強(qiáng)度和本次循環(huán)過程中信息素的積累在本次循環(huán)過程中，如果經(jīng)過這條路徑的螞蟻數(shù)量多，則留下的信息素量就相對大；經(jīng)過這條路徑的螞蟻在本次循環(huán)過程中走過的總路徑越短，則對這條路徑信息素強(qiáng)度的貢獻(xiàn)就越大。

3.5 滿足迭代終止條件，輸出結(jié)果。否則NC=NC+1，轉(zhuǎn)3.2，進(jìn)行下一代進(jìn)化

自適應(yīng)蟻群算法提高了傳統(tǒng)算法的性能。隨著時間的漸漸進(jìn)行，傳統(tǒng)的蟻群算法在全局搜素過程中，螞蟻存留下來的信息素會慢慢消失在搜素的范圍內(nèi)，使得該算法的全局搜素能力降低。自適應(yīng)蟻群算法通過改變信息素?fù)]發(fā)因子策略，增強(qiáng)了該算法的全局搜素能力和全局收斂速度，實現(xiàn)了一條最短路徑。

4 機(jī)器人制孔路徑規(guī)劃仿真結(jié)果

為了驗證自適應(yīng)蟻群算法的有效性，本文設(shè)計并實現(xiàn)了機(jī)器人制孔路徑規(guī)劃仿真實驗。實驗中選取的參數(shù)為：螞蟻群體的個數(shù)m=100，啟發(fā)式因子α=2，自啟發(fā)式因子β=3，常數(shù) Q=1，迭代次數(shù)NC=500。本文采用自適應(yīng)蟻群算法設(shè)計路徑規(guī)劃，并在MATLAB軟件的平臺下進(jìn)行仿真。仿真結(jié)果表明，改進(jìn)后的蟻群算法比傳統(tǒng)蟻群算法具有更好的搜索最優(yōu)解的能力。如圖4是大多數(shù)螞蟻選擇前往目標(biāo)點的一條路徑，是該工作環(huán)境模型下所能找到的最優(yōu)路徑，即完成機(jī)器人制孔的一條最短路徑。

圖4 自適應(yīng)蟻群算法優(yōu)化路徑

對上述算法中ρ進(jìn)行測試，ρ值的大小直接影響算法的收斂性和搜素能力。本文自適應(yīng)蟻群算法在最優(yōu)解、路徑長度上都有所改善。為了更加直接地展現(xiàn)自適應(yīng)蟻群算法在搜索過程中具有一定的方向性，可通過仿真，得到自適應(yīng)蟻群算法和基本蟻群算法的收斂性曲線圖，如下頁圖5、圖6所示。

圖5 蟻群算法收斂圖

圖6 自適應(yīng)蟻群算法收斂圖

通過仿真結(jié)果對傳統(tǒng)算法和自適應(yīng)算法的收斂曲線進(jìn)行對比分析，容易看出，傳統(tǒng)蟻群算法的機(jī)器人路徑規(guī)劃最短路徑長度為1 360.796 0，而自適應(yīng)蟻群算法的機(jī)器人路徑規(guī)劃的最短路徑長度為1 328.512 1。自適應(yīng)蟻群算法比傳統(tǒng)蟻群算法更精確、更穩(wěn)定。從計算時間和規(guī)劃路徑來看，自適應(yīng)蟻群算法規(guī)劃機(jī)器人路徑收斂速度更快，使用的時間更少，全程路徑長度更短，明顯優(yōu)于傳統(tǒng)蟻群規(guī)劃方法，并解決了全局搜索能力和收斂速度慢的問題。

5 結(jié)論

本文通過CATIA軟件對飛機(jī)零部件進(jìn)行三維建模。針對機(jī)器人制孔路徑規(guī)劃問題，提出了自適應(yīng)蟻群算法，即適當(dāng)?shù)貙λ阉鬟^程中信息素因子ρ進(jìn)行改變，使傳統(tǒng)蟻群算法更容易搜索目標(biāo)，并提高該算法的收斂速度和搜索全局最優(yōu)值的能力。從時間和空間來看，提高了收斂性和搜索能力等特性，表明自適應(yīng)蟻群算法克服傳統(tǒng)蟻群算法的缺點，為機(jī)器人制孔路徑規(guī)劃提供了指導(dǎo)。經(jīng)仿真結(jié)果可以看出，通過提出的自適應(yīng)蟻群算法，對設(shè)計出的零部件得到了一條最優(yōu)路徑來實現(xiàn)機(jī)器人制孔，并取得較好的效果。

［1］于雷，任波，魯藝.自適應(yīng)蟻群算法的多機(jī)協(xié)同空戰(zhàn)目標(biāo)分配方法［J］.火力與指揮控制，2008，33（6）：49-51.

［2］楊敬輝，洪炳镕，樸松昊.基于遺傳模糊算法的機(jī)器人局部避障規(guī)劃［J］.哈爾濱工業(yè)大學(xué)學(xué)報，2004，36（7）：946-948.

［3］TAN G Z，HE H，SLOMAN A.Ant colony system algorithm for real-time globally optimal path planning of mobile robots［J］.Automatica Sinica，2007，33（3）：279-285.

［4］韓志仁，郭文杰.基于MBD飛機(jī)裝配自動制孔路徑規(guī)劃研究［J］.機(jī)械設(shè)計與制造，2015，10（10）：201-203.

［5］吳小文，李擎.果蠅算法和5種群智能算法的尋優(yōu)性能研究［J］.火力與指揮控制，2013，38（4）：17-20.

［6］彭喜元，彭宇.群智能理論及應(yīng)用［J］.電子學(xué)報，2003，31（12）：35-37.

［7］王穎，謝劍英.一種自適應(yīng)蟻群算法及其仿真研究［J］.系統(tǒng)仿真學(xué)報，2002，14（1）：31-33.

［8］LI Y J，WU T J.Anadaptiveant colonysystem algorithm for continuous-space optimization problems ［J］.Journal of Zhejiang University Science，2003，4（1）：40-46.

Research on Adaptive Ant Colony Algorithm in Robot Hole Making Path Planning

LIU Yan-mei，WANG Xin，MA Yue-yan
（School of Automation，Shenyang Aerospace University，Shenyang 110136，China）

With the development of aircraft manufacturing industry robot technology，in the process of modern aircraft manufacturing hole making technology has become more high efficiency，more accurate positioning and more high processing quality，in this paper，the CATIA software is used to build the aircraft component model，adaptive ant colony algorithm is proposed and applied to the design of robot path planning to get the shortest path between the origin and destination point.Simulation experiment result shows that the size of pheromone volatile factor has a direct influence on the global search ability and convergence speed of the algorithm.So adaptive ant colony algorithm adjusts the dynamic of pheromone volatile factor to improve the non-purpose of the way of making holes，the low path quality，and realizes the optimal path planning of robot hole making.

CATIA，adaptive ant colony algorithm，robot hole making，path planning

1002-0640（2017）10-0142-05

V262.4

A

10.3969/j.issn.1002-0640.2017.10.030

2016-09-15

2016-10-22

航空科學(xué)基金資助項目（2015ZE54026）

劉艷梅（1974- ），女，吉林松原人，博士，副教授。研究方向：系統(tǒng)建模與控制。