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

(1.西安電子科技大學(xué) 機(jī)電工程學(xué)院，陜西 西安 710071；2.桂林電子科技大學(xué) 機(jī)電工程學(xué)院，廣西壯族自治區(qū) 桂林 541004；3.廣西制造系統(tǒng)與先進(jìn)制造技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西壯族自治區(qū) 桂林 541004)

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

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

1 問題建模和約束分析

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

(a) 使用剛度大的材料

(b) 使用剛度小的材料

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

(1)

其中，d4表示護(hù)套的厚度。R1和R2的計(jì)算公式為

(2)

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

(3)

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

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

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

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

(4)

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

2 布線路徑規(guī)劃

2.1 改進(jìn)A*算法中估價(jià)函數(shù)的確定

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

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

(5)

其中，g(n)表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的移動(dòng)代價(jià)；h(n)表示從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)移動(dòng)代價(jià)。使用歐氏距離函數(shù)LAB來表示，其優(yōu)點(diǎn)是搜索出的路徑折彎較少，其公式為

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

(6)

提出改進(jìn)后的估價(jià)函數(shù)f*(n)可表示為

(7)

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

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

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

(8)

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

(9)

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

(10)

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

(11)

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

(12)

(a) 135°拐角

(b) 90°拐角

2.2 搜索空間自動(dòng)處理算法

圖3 棱角節(jié)點(diǎn)位置示意圖

圖4 距離補(bǔ)償值δ的計(jì)算示意圖

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

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

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

(13)

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

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

(14)

同理，推廣出距離補(bǔ)償值δ的表達(dá)式為

(15)

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

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

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

2.3 拐角節(jié)點(diǎn)合理性判定算法

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

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

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

步驟2 初始化Open表和Closed表，并將起始節(jié)點(diǎn)放入Open表。

步驟3 判斷Open表是否為空；若為空，則計(jì)算結(jié)束；否則繼續(xù)搜索，并進(jìn)入下一步驟。

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

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

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

步驟7 結(jié)合起始、目標(biāo)節(jié)點(diǎn)和Closed表中的父子節(jié)點(diǎn)關(guān)系，找出路徑控制點(diǎn)并依次連接。

2.5 獲取線纜束及各分支線纜的實(shí)際路徑

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

3 實(shí)例驗(yàn)證

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

表1 線纜參數(shù)

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

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

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

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

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

(a) 線纜束路徑視圖

4 結(jié)束語

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