基于改進蟻群算法的線纜路徑規劃技術研究

吳保勝，郭 宇，王發麟，宋 倩

南京航空航天大學 機電學院，南京 210016

1 引言

隨著以航空、航天、船舶、電子、兵工等大型電氣系統的飛速發展，現代電氣系統日益復雜化、集成化。大量的電氣設備密集于系統平臺上，用于各設備和部件連接的線纜所傳送的信號越來越多，頻率越來越高，消耗的功率也越來越大，對線纜的敷設提出了更高的要求和挑戰。線纜敷設路徑規劃是一類特殊的帶性能約束的布局問題，其中待定參數多、可行空間復雜，線纜的布局合理性和裝配質量直接關系到產品最終的整機性能和可靠性[1-2]。美國通用電器公司分析歸納飛機發動機發生故障的原因，其中因為線纜管路損壞或失效而產生故障的比例達到了50%[3]。傳統的線纜模裝試驗方法需要大量的人工干預，大大影響了線纜裝配的效率。虛擬環境下的線纜布線設計的出現，能夠實現線纜自動避障，生成滿足工程規則的布線路徑，為解決線纜裝配的布線不合理、效率低下等問題提供了一條有效的解決途徑[4]。

線纜自動敷設的核心是路徑搜索算法。使用智能算法完成線纜路徑的自動求解具有效率高等特點，是當前的研究熱點。國內外的學者對此進行了相關的研究，如Park等[5]在1992年提出了基于Agent的線纜二維設計方法。CONRU等[6]將并行工程的方法應用到線纜的自動布局設計中，并使用遺傳算法進行全局最優路徑的搜索。ILKNUR等[7]針對復雜環境下線纜的布局問題，提出了一種布線路徑的搜索算法，該算法進行約束采樣，然后利用隨機路徑圖法計算出初始路徑，再采用動力學法對布線路徑進行優化，取得了良好的計算效果。韓明晶[8]將A*算法應用到電子制造裝備的三維路徑搜索中，開發了基于UG的布線模塊。白曉蘭等[9]提出了基于工程規則和離散空間的航空發動機管路布局方法。蔡毅等[10]提出了“按面自動布線”和“貼壁干涉自動調整”的方法，但由于布線路徑多、路徑空間交匯復雜等原因，結果仍存在干涉、算法耗時較高等問題。王成恩等[11]提出了一種基于計算幾何、微分幾何和智能優化等思想，實現了對管系的敷設順序與管路路徑的自動求解，取得了較好的效果。徐聯杰等[12]提出了一種基于障礙物碰撞檢測的RRT算法，利用基于碰撞信息進行節點擴展策略和快速繞障，有效解決了復雜結構條件下沿結構件表面的管路自動布局問題。吳宏超等[13]提出了一種基于改進A*算法的管路自動布局方法，將工程規則作為約束條件，分別添加在路徑搜索和路徑優化兩個階段，能較快地獲得一條滿足工程約束的路徑，但是仍未考慮管路之間的相互影響。

近年來，蟻群優化算法（Ant Colony Optimization，ACO）作為一種啟發式搜索算法，具有較強的魯棒性，在路徑搜索問題方面獲得了大量的應用。但基本蟻群算法在三維環境下進行路徑搜索時路徑點容易出現發散現象，為解決該問題，本文提出了一種改進的蟻群算法來完成線纜的路徑規劃，通過引入重力規則來對路徑點進行約束，讓線纜路徑點滿足貼壁規則，然后在抽象化的求解空間里，運用改進的蟻群算法進行路徑搜索，從而規劃出一條合理的布線路徑。為了對本文算法進行測試和驗證，通過實例模型和實驗作了仿真分析。

2 問題描述

布線路徑的求解是線纜布線問題的核心，即在三維環境中求解出一條連接起始點和終點，并滿足布線規范的通路。線纜的路徑求解也可以看作碰撞球干涉檢測問題，即在三維環境中，以路徑離散點為球心，線纜直徑為球直徑，進行碰撞球干涉檢測。如果碰撞球在沿路徑進行掃掠時，不與環境中的障礙物發生干涉或碰撞，那么這條路徑是安全可靠的。為獲取布線空間的環境信息，首先需要對布線空間進行環境建模，建立障礙物和路徑點的抽象模型；為解決基本蟻群算法在三維環境下進行路徑搜索時路徑點的發散性，引入重力規則來對路徑點進行約束，讓線纜路徑點滿足貼壁規則，然后在抽象化的求解空間里，運用改進的蟻群算法進行路徑搜索，從而規劃出一條合理的布線路徑。圖1給出了基于改進蟻群算法的線纜路徑規劃技術總體思路。

圖1 基于改進蟻群算法的線纜路徑規劃技術總體思路

3 布線空間環境建模

3.1 分段式空間劃分

在復雜機電產品中，由于結構件的種類繁多，大小形狀不一，使得布線空間不規則，因此需要對布線環境進行三維空間環境建模。首先對布線空間進行網格化，將三維空間抽象為包含幾何模型空間位置信息的節點，這樣可以更有效地描述線路可能經過的空間點。需要指出的是，如果對整個布線空間進行柵格化，當空間模型較大時，將會占用較大的計算存儲空間，從而降低計算效率。因此，為提高算法效率，先對布線空間進行分段式劃分，然后再對特定的空間區域進行柵格化，而不是對整個空間進行柵格劃分。

將布線空間劃分為若干個子空間的并集：A=A1?A2?A3?…,其中A表示整個布線空間，Ai(i=1,2,3…)為劃分出的各個子空間，如圖2所示。當Ai為線纜布線的固定路徑段時（如線纜的固定卡槽等），線纜經過這段區域將具有直接連通性，在進行路徑搜索時可以跳過該區域。A3作為集線器，當線纜經過該結構時，該路徑段可以看作入口端T1和出口端T2的直接連通，在求解S1S2之間的布線路徑時，無需在此路徑段作過多的算法耗費。這樣S1S2之間的路徑搜索可以簡化為S1T1與S2T2兩段的布線路徑搜索，A1?A2便是本文算法的求解空間。通過對求解空間進行柵格化劃分將大大節約算法的存儲空間。

圖2 布線空間的分段式劃分示意圖

3.2 布線空間柵格化

本文采用文獻[14]提出的空間等分網格法。如圖3所示，首先從產品結構模型中抽象出三維空間模型，將左下角的頂點作為三維空間的坐標原點A，在點A中建立三維坐標系A-xyz。在該坐標系中以A為頂點，沿x軸方向取產品三維結構模型的最大長度AB，沿y軸方向取產品三維結構模型的最大長度AA′，沿z軸方向取產品三維結構模型的最大長度AD，由此構造包含產品三維結構模型的立方體區域ABCD-A′B′C′D′，該區域即為三維布線路徑的規劃空間，如圖3（a）所示。為得到抽象環境模型，需在上述規劃空間ABCDA′B′C′D′的基礎上進行等分操作：沿邊 AB 進行 n 等分，得到n+1個平面Πi(i=0,1,2,…,n)，然后對這n+1個平面沿邊AD進行m等分，沿邊AA′進行l等分，并且求解出里面的交點，平面劃分如圖3（b）所示。

圖3 三維空間環境建模過程

4 基于改進蟻群算法的線纜路徑規劃

4.1 基本蟻群算法

蟻群算法是由Dorigo提出的一種群體智能算法，描述了螞蟻在蟻巢和食物之間尋找出最短路徑的合作行為，螞蟻之間通過信息素的濃度來選擇行駛路徑，該算法具有較強的魯棒性、優良的分布式計算機制、易與其他方法結合等優點[15]。

螞蟻的移動方向是根據各條路徑上信息素的量來決定的，同時根據信息素的量和啟發信息來計算狀態轉移概率。位于節點i的螞蟻通過公式（1）給出的規則選擇下一個將要移動到的節點 j：

其中S根據公式（2）得到：

其中q是在[0,1]區間均勻分布的隨機數；q0的大小決定了利用先驗知識與探索新路徑之間的相對重要性；i、j分別是某一段路徑的起點和終點；ηij=1/dij為能見度，是兩節點i和 j路徑距離的倒數；τij(t)為時間t時由i到 j的信息素強度；allowedk為尚未訪問過的節點集合；α,β為兩常數，分別表示信息素和能見度的加權值。上述狀態轉移規則被稱為偽隨機比例規則。每只螞蟻在走完一步或者到達目標點之后需要對信息素進行更新，路徑( )i,j上信息素按式（3）和（4）進行更新：

其中0＜ρ≤1為信息素的蒸發率，Δτij為第k只螞蟻在路徑i到 j所留下來的信息素。

4.2 線纜路徑規劃

線纜作為具有一定質量的實體，在實際敷設中，線纜的敷設路徑不可能出現沒有附著面的懸空現象。線纜的敷設一般需要依附于一定的實體表面，即有種“重力趨勢”貼近物體表面。如圖4所示，（1）路徑中出現懸空的路徑段，路徑規劃不合理；（2）路徑考慮線纜自重，敷設路徑全程依附于物體表面，符合實際規范，為優質解。故在三維環境中定義重力吸引規則（gravity attraction rule），讓線纜路徑規劃時的空間姿態更滿足實際情況。

圖4 重力規則示意圖

在對線纜或者管路自動敷設路徑求解時，通常的研究方法是先用智能算法求解出線纜起始點至終點的通徑，然后將“貼壁”等諸多規則作為路徑優化的約束條件，以達到敷設線纜實際敷設規范的走線路徑，而本文是在研究線纜實際敷設時的空間姿態基礎上，將“貼壁”以重力約束的形式，直接融合到蟻群算法中，而非將其作為約束條件再對走線路徑進行二次優化。

將螞蟻看作有“質量”的實體，則其運動軌跡必須依附于一定的物體表面或者在地面活動，在選擇路徑點時不僅需要考慮避障，還需考慮路徑點的實際位置。根據重力場的概念：其中，mant表示螞蟻的質量，m0表示網格點的質量，r表示螞蟻與可視域內網格點的距離，k、f表示引力系數。

定義障礙物表面與地面的重力場值為：

將每個網格點看作單位質量的點，則m0=1；將螞蟻看作單位質量的螞蟻，則mant=1；當網格點位于障礙物表面時，為了防止出現分母為0的情況，故在分母中加1；則重力可看作為：

引力隨著距離的變化呈現拋物線式的變化，隨著越來越靠近目標物體，則引力急劇增加，所以引力場也可以表示為：

其中q=(i , j,k)表示任意路徑點的位置，dobs&gro為當前節點垂直方向上距離最近障礙物或地面的距離，且有：

在建立布線空間的抽象化模型時，對障礙物進行了“膨化”處理，螞蟻在障礙物表面進行路徑搜索時，布線路徑與障礙物不會發生干涉。G的值按以下情況確定：

（1）當螞蟻在障礙物表面或者地表上運動時，G=0；

（2）當螞蟻在自由位置點時，G=∞。

螞蟻朝目標點運動，也可看作是一種趨向性運動，故定義目標點的引力場為：

其中ddes=‖q- qdes‖,qdes代表目標點，ddes即當前點到目標點的歐氏距離。重力場的吸引可以表示為：

4.2.1 搜索策略

如圖5所示，若當前點為 pnow(i , j,k)，而平面α為螞蟻搜索下一路徑點的所在平面，則可供選擇的下一路徑點的集合為：

圖5 允許列表示意圖

根據每個網格節點的信息，選取安全的節點寫入允許列表allowed中。

在改進的蟻群算法中，第k只螞蟻從節點i轉移到下一路徑點 j的選擇概率為：

傳統的蟻群算法的啟發信息ηij為該節點到目標點距離的倒數，距離目標點越近ηij的值越大。而使用G(q)不僅使路徑點的選擇更傾向于地表或障礙物表面，而且還能加強算法在獲取最優解時的收斂性。

4.2.2 信息素的表示及更新策略

布線求解空間是由網格節點表征的，這些網格節點即為蟻群算法進行路徑搜索的路徑點。如果將各個離散點間的連接線段作為信息素的連接載體，則會大大增加算法的空間復雜度。為避免這種情況，本文使用節點表示法：將信息素儲存在環境模型的離散點上，任意點對應一個信息素值，而信息素量的大小代表了該離散點對螞蟻的吸引程度。這種信息素的表示方法將大大降低算法的空間復雜度[16]。信息素的更新采用局部更新和全局更新相結合的更新規則。當螞蟻選定下一個路徑點(i , j,k)時，按公式（15）立即更新該路徑點上的信息素值：

其中，0＜ε＜1，ε為一常數。τ0為原始信息素值。

當一次迭代完成，找出本次迭代所得出的最優路徑后，對該路徑進行信息素更新：

lbest為最優路徑的長度值。

5 算法測試與仿真

測試時基于如下運行環境：Intel Core i7-3770，3.40 GHz處理器；內存為4 GB；操作系統為Win7；仿真軟件為MATLAB R2012b。

實驗1對本文所提出的重力吸引規則進行仿真實驗，并和沒有使用該規則的蟻群算法進行了對比，以驗證該方法的有效性和實用性。

建立兩障礙物的空間模型，中心坐標分別為（40，420，75）和（450，40，40）；兩障礙物的長寬高分別為（80，80，150）和（100，80，80）。起始點和終點的位置分別為（0，425，150）和（500，0，80）。表1給出了本次實驗中所使用蟻群算法的主要參數。

表1 參數設置

圖6 實驗1仿真結果

從圖6的仿真結果中可以看出，將基本蟻群算法直接應用到三維空間的線纜敷設時，雖然能搜索出一條連接起始點且不與障礙物發生干涉的布線路徑，但是路徑點大多處于自由狀態，這不符合實際布線的規范和標準。而結合重力規則的蟻群算法所搜索出的路徑始終依附于固定面，布線路徑更加符合線纜敷設的實際規范，路徑規劃效果較好。

實驗2對本文所給出的算法進行仿真。建立障礙物的包圍盒模型，中心位置和長寬高分別如表2所示，其他參數設置參照實驗1中的數據。

表2 障礙物模型參數

圖7（a）、（b）分別從主視圖和俯視圖展示了實驗2仿真的結果；圖7（c）為算法所對應的適應度變化曲線圖。從圖7中可以看出，在多障礙物的環境模型下，改進蟻群算法能較快地搜索出一條安全、合理的布線路徑。三維環境下重力規則的應用，使得整個布線路徑都依附于一定的平面，進一步驗證了改進算法的優越性。

蟻群算法作為群體智能算法，在路徑點的選取中采用可視域內的啟發式搜索，求解出的不一定是全局最優路徑，但卻是符合線纜實際規范的可行解。線纜的自動敷設設計主要是為線纜的實際敷設提供一個可行、優化的敷設方案，即在特定的應用環境或者工作條件下使線纜滿足敷設的約束條件，最短路徑不一定就是最優路徑。在圖7（b）中綠色虛線表示連接S、T之間的理論最優路徑，雖然滿足最短路徑，但是橫跨空間模型的路線，占據了很大的空間，而且在線纜的實際敷設過程中也不方便固定，而采用改進算法求解出的圖中紅色路徑雖然犧牲了線纜長度，但更滿足貼壁的約束規范，有利于卡箍的裝配和線纜的固定等操作。本文算法求解得出的路徑并不是直接作為線纜的實際敷設的最終路徑，還應對路徑點進行選取，使線纜達到平滑順直的空間布局姿態。圖7（d）所示的電器柜模型中線纜實際走線路徑圖，紅色線纜所表示的路徑2雖然達到了路徑最短，但是多數路徑點處于懸空位置，并不符合線纜的空間物理姿態，而且空間占據大，不便于設備的維護操作。藍色線纜所表示的路徑1雖然長度較長，但是走線依附于機柜壁板，這樣有利于后續卡箍等緊固件的安裝，路徑1的走線方式相比較之下更為合理。

6 結束語

（1）本文針對線纜敷設問題，提出了一種基于改進蟻群算法的線纜路徑規劃方法，通過在算法中引入重力規則，能夠較好地完成線纜路徑的搜索；對所提出的方法進行了仿真驗證，取得了良好的效果。

圖7 實驗2仿真結果

（2）三維空間的網格化建模，存在模型的計算量和存儲量較大的缺點。網格的劃分越細則空間的抽象化表示越精確，但數據量也會隨之急劇增大。如何權衡考慮空間精確化和數據量之間的矛盾，是下一步將要進行的研究工作。

（3）本文所給出的算法并未考慮到線纜的機械性能和電氣性能，如何考慮多約束條件下的線纜三維路徑規劃技術也是下一步要研究的內容。

：

[1]寧汝新，劉檢華，唐承統，等.虛擬裝配技術及其應用[J].國防制造技術，2009，4（2）：22-29.

[2]尚煒，寧汝新，劉檢華，等.復雜機電產品中的柔性線纜裝配過程仿真技術[J].計算機輔助設計與圖形學學報，2012，24（6）：822-831.

[3]孔瑞蓮.航空發動機可靠性工程[M].北京：航空工業出版社，2006.

[4]王發麟，廖文和，郭宇，等.線纜虛擬裝配關鍵技術研究現狀及其發展[J].中國機械工程，2016，27（6）：839-851.

[5]Park H，Lee H，Cutkosky M R.Computational support for concurrent engineering of cable harness[C]//Proceedings of the International Computers in Engineering Conference and Exhibit，San Francisco，USA，1992：261-268.

[6]Conru A B.A genetic approach to the cable harness routing problem[C]//Proceedings of the IEEE Conference on Evolutionary Computation，Orlando，USA，1994：200-205.

[7]Ilknur K，Russell G，Ming C，et al.Cable route planning in complex environments using constrained sampling[C]//Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling，2007：395-402.

[8]韓明晶.基于A*算法的電子制造裝備布線研究[D].武漢：華中科技大學，2009.

[9]白曉蘭，張禹.航空發動機管路智能布局[J].機械設計與制造，2013（9）：56-59.

[10]蔡毅，王彥偉，黃正東.基于UG的三維電氣自動布線技術研究[J].計算機工程與應用，2012，48（8）：68-72.

[11]王成恩，柳強，白曉蘭，等.航空發動機復雜約束空間內管路敷設技術[J].計算機集成制造系統，2010，16（11）：2327-2332.

[12]徐聯杰，劉檢華，何永熹，等.一種基于改進快速搜索隨機樹算法的管路自動布局方法[J].圖學學報，2016，37（1）：1-10.

[13]吳宏超，劉檢華，唐承統，等.基于改進A*算法的管路自動布局設計與優化方法[J].計算機集成制造系統，2016，22（4）：945-954.

[14]胡小兵，黃席樾.基于蟻群算法的三維空間機器人路徑規劃[J].重慶大學學報：自然科學版，2004，27（8）：132-135.

[15]Dorigo M，Gambardella L M.Ant colonies for the traveling salesman problem[J].BioSystems，1997，43（2）：73-81.

[16]劉利強，于飛，戴運桃.基于蟻群算法的水下潛器三維空間路徑規劃[J].系統仿真學報，2008，20（14）：3712-3716.