一種考慮復雜約束的線纜束路徑規劃方法

楊 旭，周德儉，2，宋 微，陳小勇

(1.西安電子科技大學 機電工程學院，陜西 西安 710071；2.桂林電子科技大學 機電工程學院，廣西壯族自治區 桂林 541004；3.廣西制造系統與先進制造技術重點實驗室，廣西壯族自治區 桂林 541004)

線纜束是多電飛機機載設備的重要組成部分。研究表明，不合理的線纜布局會嚴重影響設備的性能[1-2]。機載設備布線對電磁兼容性能和可靠性的要求很高[3-4]，工程規則約束十分復雜。布線路徑自動規劃技術研究如何在特定的約束條件下，使用路徑規劃算法合理地規劃布線路徑，常用的路徑規劃算法有A*算法[5-6]、隨機路徑圖算法(Probabilistic Roadmap Method，PRM)[7-8]、快速探索隨機樹算法(Rapidly-exploring Random Trees，RRT)[9-10]和遺傳算法[11-12]等。作為路徑規劃領域的經典算法之一，A*算法在電氣布線路徑規劃、機器人路徑規劃、無人機路徑規劃等領域取得了眾多的研究成果。文獻[13]將A*算法與模糊推理相結合，解決了概率地圖模式下的機器人路徑規劃問題。文獻[14]提出了多準則A*算法，用以解決考慮區域內相關性的多準則最短路徑尋徑問題。文獻[15]針對路徑的可達性不明確的問題，提出了包含標準指標的多目標A*算法，取得了很好的效果。

但是，現有的A*算法多針對于單根線纜的路徑規劃[16]，對線纜束路徑規劃的研究較為匱乏，且缺乏考慮復雜工程規則約束的多電飛機機載設備線纜束路徑規劃問題。由于在飛行狀態下，飛機的姿態經常發生變化，布置在機載設備內部狹小空間的線纜束容易發生較大位移，當線纜束附近存在可移動部件時，線纜束可能被其附近的障礙物棱角損傷；此時使用彎線槽來實現線纜圓弧拐角部分的定位和保護十分有利，但尚未有能解決此問題的路徑規劃算法。因此，筆者研究的目的是提出適用于考慮復雜工程規則約束的多電飛機機載設備線纜束路徑規劃的改進A*算法。使用此算法可得到布線總成本最低的最優路徑。

1 問題建模和約束分析

線纜束通常由多根線纜和固定這些線纜的護套或扎線帶組成。使用扎線帶固定時，剛度大的材料捆扎后的預留部分較難與線纜束外表面貼合，占據較大的空間；剛度小的材料占據較小的空間。其橫截面分別如圖1(a)和(b)所示。

(a) 使用剛度大的材料

(b) 使用剛度小的材料

設某線纜束由n種型號的線纜組成。其中，半徑為Ri的線纜有ai根，設這些線纜的最小外接圓半徑為R′，提出線纜束等效半徑r的計算公式為

(1)

其中，d4表示護套的厚度。R1和R2的計算公式為

(2)

其中，d1和d2分別表示扎線帶和其接頭的厚度，d3為捆扎后扎線帶伸出接頭處的長度，α為扎線帶壓縮系數。使用擬物擬人算法來求解R′，首先使用擬物算法將各個小圓模擬成物理世界真實存在的圓餅，將求解最小外接圓的問題轉換為求解勢能極小值的問題[17]。勢能U表示全部M個圓餅的總擠壓彈性勢能。其計算表達式如下：

(3)

其中，uij為第i個和第j個圓餅之間的擠壓彈性勢能，ui表示第i個圓餅的總擠壓彈性勢能。采用擬物算法計算后，若陷入局部勢能極小值，則采用擬人算法繼續計算；兩個算法交替進行，直至求出最小外接圓半徑。在計算得到了R′后，即可求得線纜束等效半徑r。

本研究中的機載設備線纜束布線的工程規則約束如下：① 由于線纜束離金屬底板的距離越小，串擾越小[3]，所以線纜束盡量貼底板敷設，以保證穩定性和電磁兼容性能；② 線纜束與所有障礙物棱角必須保持一定的間隙；③ 線纜束和其中所有線纜的彎曲半徑要大于其允許的最小彎曲半徑；④ 為了防止線纜束因過度彎折而遭到損壞而使用較少彎線槽的個數以降低總成本，應盡量減少線纜束彎曲次數。

對于規則①，將障礙物在二維平面上進行投影，先得到線纜束的主路徑，然后在三維空間進行其分支路徑的路徑規劃；對于規則②，提出搜索空間自動處理算法，首先識別出棱角節點，然后對棱角節點周圍的空間進行處理；對于規則③，計算出線纜束和其內部所有線纜的最小彎曲半徑，取其最大值作為線纜束的最小彎曲半徑，并提出拐角節點合理性判定算法，使布線過程中線纜束各處的彎曲半徑均大于最小彎曲半徑；對于規則④，將彎線槽的材料成本、工藝成本和重量成本考慮進布線總成本中，線纜束彎曲的次數越多，則總成本越高。設布線總成本為無量綱數G，其表達式為

G=α1G1+α2G2+α3G3+α4G4，

(4)

其中，G1～G4分別表示路徑長度成本、彎線槽的材料成本、工藝成本和重量成本；α1～α4表示對應的權重系數，通常都取為1。

2 布線路徑規劃

2.1 改進A*算法中估價函數的確定

A*算法結合了盲目式搜索算法和Dijkstra算法的優點，是一種高效的啟發式路徑搜索算法[18]。它引入了Open表、Closed表和估價函數f(n)。其公式為

f(n)=g(n)+h(n)，

(5)

其中，g(n)表示從起始節點到當前節點的移動代價；h(n)表示從當前節點到目標節點的估計移動代價。使用歐氏距離函數LAB來表示，其優點是搜索出的路徑折彎較少，其公式為

LAB=((Ax-Bx)2+(Ay-By)2)1/2。

(6)

提出改進后的估價函數f*(n)可表示為

(7)

其中，由于得到的線纜束中心線初始路徑中的折彎都是直線折彎，后續要被處理成曲線折彎并在曲線折彎處安裝彎線槽，所以使用Δg(n)表示從起始節點到當前節點的所有直線折彎處理成曲線折彎后減小的路徑長度；s(n)表示從起始節點到當前節點的彎線槽布置成本，包括彎線槽材料成本、工藝成本和重量成本。

如圖2所示，布線路徑中的直線折彎處理成曲線折彎后，路徑的實際長度將會減小Δg。

設某拐角的夾角角度為θ，其取值范圍為[90°，180°]，則Δg(θ)的計算表達式為

(8)

由于搜索方向為8個，θ可能的取值可為135°或90°。如圖2(a)所示，θ為135°時，Δg(θ)為直線段AB的長度與直線段AC的長度之和減去弧BC的長度，其表達式為

(9)

如圖2(b)所示，θ為90°時，Δg(θ)的表達式為

(10)

所以Δg(n)的表達式為

(11)

其中，N1和N2分別表示從起始節點到當前節點的135°和90°拐角點的個數。使用Di表示第i個節點，設其坐標為(xi，yi)。如圖2所示，拐角節點的坐標與其前后兩個節點的坐標存在著對應關系，因此提出基于節點坐標的拐角節點的判定方法如下：若同時滿足xi-xi-1=xi-1-xi-2和yi-yi-1≠yi-1-yi-2，或同時滿足xi-xi-1≠xi-1-xi-2和yi-yi-1=yi-1-yi-2，則Di-1為135°拐角節點，如圖2(a)中的A點；若同時滿足xi-xi-1≠xi-1-xi-2和yi-yi-1≠yi-1-yi-2，則Di-1為90°拐角節點，如圖2(b)中的A*點。設彎線槽單位長度的材料成本、工藝成本、重量成本分別為P1、P2、P3，則其布置成本s(n)的表達式為

(12)

(a) 135°拐角

(b) 90°拐角

2.2 搜索空間自動處理算法

圖3 棱角節點位置示意圖

圖4 距離補償值δ的計算示意圖

步驟1 識別出可能與線纜束發生接觸的障礙物棱角節點。設空間中某個節點D(i，j)的坐標為(i，j)，使用D(i，j)=0表示該處空間有障礙物占據，D(i，j)=1表示該處空間沒有障礙物。如圖3所示，內凹位置的障礙物節點不可能與線纜束發生接觸，如A和B，所以只將外凸的棱角節點視為可能與線纜束發生接觸，如C和D。障礙物棱角節點可分為上、下、左、右、左上、左下、右上、右下等8個方位，在進行預處理時先將搜索空間劃分成柵格模型，使用柵格粒度k來表示柵格的邊長。若同時滿足：D(i，j)=0，D(i-k，j)=1，D(i，j-k)=1，D(i，j+k)=1，則D(i，j)為上棱角節點；若同時滿足D(i，j)=0，D(i-k，j)=1，D(i，j-k)=1，D(i-k，j-k)=1，則D(i，j)為左上棱角節點，如圖3中的C點；同理，識別出其余所有棱角節點。

步驟2 處理棱角節點附近的空間。直線折彎被曲線折彎代替后，該部分線纜束會減小與障礙物棱角的距離，如圖2所示，90°拐角處將減小(21/2-1)(R+r)，大于135°拐角，所以，保證90°拐角處的直線折彎被曲線折彎代替后仍能滿足線纜束與棱角之間的間隙要求即可。引入障礙物柵格擴展半徑e′，其表達式為

e′=e+(2)1/2-1)(R+r)-δ，

(13)

其中，e表示約束條件中的線纜束與棱角的間隙，δ表示距離補償值。以棱角節點為圓心，畫一個半徑為e+((2)1/2-1)(R+r)的圓。假設將該圓內部的所有柵格均處理成障礙物柵格。圖4所示為此圓半徑為2k時的情形，其中，O表示某棱角節點，某90°拐角處的直線折彎被曲線折彎代替后，該部分線纜束離該棱角節點最近的點為M。由于M1和M2之間的區域仍屬于可行區域，此時，距離補償值為M1、M2之間的直線距離δM1M2，其計算表達式為

δM1M2=LOM2-LOM1=2(21/2-1)k。

(14)

同理，推廣出距離補償值δ的表達式為

(15)

其中，ceil()函數表示對括號內的表達式向上取整得到的數值。計算得e′的值之后對所有棱角節點執行如下操作：以棱角節點為圓心，畫一個半徑為e′的圓，將該圓掃過的所有柵格全部處理成障礙物柵格。

圖5 障礙物輪廓變化示意圖

至此完成了搜索空間處理的所有步驟。處理完之后，障礙物的輪廓會增大，某處障礙物的輪廓變化情況如圖5所示，其初始障礙物輪廓線為ABC，處理后的輪廓線為A′-B′-C′-D′-E′-F′-G′。

2.3 拐角節點合理性判定算法

如圖2所示，每個90°和135°拐角兩側至少預留的直線段長度分別是R+r和tan 22.5° (R+r)。引入最小預留直線段長度τ，若路徑中第一個拐角為90°，則該拐角節點與起始節點之間的τ為R+r。若為135°，則τ為tan22.5°(R+r)；若某拐角為90°，它的上一個拐角為135°，則兩者之間的τ為(tan 22.5°+1)(R+r)，同理可計算出其它所有情況下的τ值。若其不大于實際預留的直線段長度τ′，則判定該拐角節點合理；否則，判定不合理，并取消此處的拐角。

2.4 使用改進A*算法獲取線纜束中心線的初始路徑的流程

步驟1 使用提出的搜索空間自動處理算法將布線空間劃分為包含可行空間和障礙物空間。

步驟2 初始化Open表和Closed表，并將起始節點放入Open表。

步驟3 判斷Open表是否為空；若為空，則計算結束；否則繼續搜索，并進入下一步驟。

步驟4 選擇Open表中f*(n)值最小的節點，并將其移入到Closed表中。如果該節點為目標節點，則計算結束；否則進入下一步驟。

步驟5 搜索當前節點的所有相鄰可行節點，分為以下4種情況：① 若某個相鄰可行節點不在Open表中且前面只有一個父節點，則將其加入到Open表中，并作為當前節點的子節點，并轉到步驟3；② 若某個相鄰可行節點不在Open表中且前面有不少于兩個父節點，則使用提出的拐角判定方法判定該節點是否為拐角節點；若不是拐角節點，則將其加入到Open表中，并作為當前節點的子節點，并轉到步驟3；若是拐角節點，則使用提出的拐角節點合理性判定算法判定該拐角節點是否合理，若合理，將其加入到Open表中，并作為當前節點的子節點，并轉到步驟3；否則不將其加入到Open表中，且不作為當前節點的子節點，并轉到步驟3；③ 若某個相鄰可行節點n′在Open表中，進入下一步驟；④ 若某個相鄰可行節點在Closed表中，轉到步驟3。

步驟6 重新計算n′的f*(n′)值，若小于之前的f*(n′)值，更新f*(n′)值，并將n′作為當前節點的子節點；否則將n′移入到Closed表中，并轉到步驟3。

步驟7 結合起始、目標節點和Closed表中的父子節點關系，找出路徑控制點并依次連接。

2.5 獲取線纜束及各分支線纜的實際路徑

首先根據設定的折彎半徑，用曲線折彎，代替初始路徑中的直線折彎，得到線纜束中心線的實際路徑。然后，在三維建模軟件中為線纜束中心線的實際路徑賦予型材，即可得到線纜束的實際路徑。最后根據分支線纜的接口位置可得到各分支線纜的路徑。

3 實例驗證

對某機載設備的線纜束進行布線路徑規劃，結合工程實際得到的布線參數如下：線纜束護套的厚度d4=0.5 mm，彎線槽厚度為1.5 mm；線纜束的每根線纜和線纜束整體的最小彎曲半徑必須分別大于2λiRi和2λr，λ的取值為3.5，各線纜的參數如表1所示。

表1 線纜參數

圖6 線纜束中心線的初始路徑

進而計算得到線纜束等效半徑r為3.5 mm，e′=10 mm；R=25 mm，其中保留了1 mm的安全裕量，進一步得到R*=28.5 mm。設單位長度線纜束的路徑長度成本為1，單位長度彎線槽的材料成本、工藝成本和重量成本分別為1.5，2.5，0.9；分別使用表2中的4種不同路徑搜索算法進行布線，并取柵格粒度k為5 mm，得到的中心線初始路徑如圖6所示，圖中黑色部分為處理后得到的障礙物空間。

由圖6可知，使用算法1和算法2得到的路徑都存在無法使用曲線折彎代替的直線拐角，且算法1得到的路徑無法保證與棱角的距離，故都不能滿足約束條件；算法4為文中提出的基于搜索空間自動處理算法、拐點節點合理性判斷算法和改進估價函數的改進A*算法，如表2所示，使用此算法得到的路徑總耗費為1 832.38，與使用算法3相比，減小了5.1%。

表2 4種算法的布線總成本比較

在UG軟件中得到線纜束的布線路徑，在此基礎上得到各分支線纜的路徑，線纜束路徑視圖和整體路徑視圖分別如圖7(a)和7(b)所示。類似本實例，通過對多種不同類型線纜束的布線路徑進行比較驗證可知，文中提出的算法能在滿足最小彎曲半徑、線纜束與棱角間隙等工程規則約束的前提下得到總成本最低的布線路徑。

(a) 線纜束路徑視圖

4 結束語

為了有效解決多電飛機機載設備中的線纜束布線路徑規劃問題，筆者提出了一種改進A*算法。首先，提出了線纜束布線總成本的計算方法，并改進了傳統A*算法中的估價函數；然后，基于擬物擬人算法計算出線纜束的等效半徑，提出考慮工程規則約束的搜索空間自動處理算法和拐角節點合理性判定算法；最后，提出了使用改進A*算法進行路徑規劃的流程。通過某機載設備線纜束敷設的實例驗證表明，相比較傳統A*算法，筆者所提算法性能更優。