孫 浩 原 野 張 琦 張小貝
1.上海大學通信與信息工程學院,上海,2004442.上海飛機設計研究院,上海,201210
航空電氣線路互聯系統(electrical wiring interconnection systems,EWIS)是指安裝在飛機上任何區域,在兩個或多個端接點之間傳輸電能(包含數據和信號)的各種導線電纜、端接器件、支撐器件的組合,EWIS的設計與布置直接影響飛機的經濟性、可靠性和安全性[1-3]。傳統依靠人工的設計方式存在設計周期長、易出錯、無法得到最優路徑等問題[4]。隨著科技的發展,人工智能算法逐漸被應用于自動布線,克服了人工規劃的不足。
自動布線的核心是路徑搜索算法。雖然迪杰斯特拉算法[5](Dijkstra)、A*算法[6]、快速搜索隨機樹算法[7](rapidly-exploring random trees,RRT)等傳統路徑搜索算法可以做到無干涉的最短路徑,但顯然無法滿足實際布線工程的需要,為此國內外學者對傳統算法進行了適應性改造,使其滿足不同的布線需求。董宗然等[8]將布線約束反映在網格能量值中,代入最短路徑快速算法(shortest path faster algorithm, SPFA)距離松弛函數的計算,從而將布線約束納入考慮,但對布線約束向網格能量值的映射過程缺少詳細介紹。劉瀟等[9]、劉佳順等[10]改進RRT算法,使隨機樹能夠貼著障礙物表面拓展,便于線束捆扎固定,又對規劃出的路徑點進行位置修正,讓路徑更加平滑,但難考慮更加復雜的約束。吳宏超等[11]改進A*算法的估價函數,使其與彎折和方向有關,通過在設備周圍設置吸引區和排除危險設備周圍的點,讓線纜靠近或遠離,具有不錯的效果。KANG等[12]先用Dijkstra算法規劃避障的最短路徑,再用拉普拉斯平滑算法平滑布線路徑,使線纜的連續性得到提高,但較為簡單,沒有考慮更多布線約束。王發麟等[13]以線纜間電磁干擾最小且整體線纜束質量最小為目標,采用改進粒子群算法進行整體尋優并獲取線纜的具體路徑,但規劃過程需要較多迭代,計算時間長,不利于實際應用,且是非確定性算法,可能會產生無效解。如何減少線纜的機械損傷,一直是學者們的研究重點。姜康等[14]在A*算法的估價函數中加入彎折因子、剛性因子以約束線纜彎折,加入干涉因子以避免與障礙物及布線空間的邊界發生干涉。楊旭等[15]對線纜的彎折進行了詳細分析,綜合考慮了彎線槽單位長度的材料成本、工藝成本、質量成本,用以減少線纜彎折損傷,同時對障礙物的棱角做膨脹處理,用以在線纜和障礙物尖銳處留出空隙,以減少線纜磕碰損傷。KIM等[16]在設計船舶管道時以線纜長度和彎折個數為學習目標,使用強化學習規劃最為經濟安全的路徑。綜上,國內外學者為線纜路徑規劃提供了多樣化的解決思路,但是上述方法或難獲得最優路徑,或考慮約束不全面,或算法復雜,難以實際應用,且對更加復雜的電氣約束如電磁干擾、線纜間的相互作用等情況的研究甚少。
本文對航空EWIS自動布線技術進行研究,提出了基于改進A*算法的航空線纜路徑規劃方法。該方法首先采用柵格法將布線空間均勻離散化;之后對柵格點進行權值編碼,以描述柵格點周圍的環境因素;然后根據線纜受不同環境因素的影響程度,計算表征了不同布線約束的綜合權值,用以改進A*算法;同時在A*算法的估價函數中加入彎折因子和剛性因子,以約束線纜的彎折;最后對規劃出的路徑進行擬合曲線優化調整以適應飛機曲面,從而獲得最終的布線結果。所提方法有助于EWIS實現從人工設計向自動化、智能化設計的升級。
同所有機電產品的線纜一樣,航空線纜路徑規劃的最基本要求也是在布線空間內自動規劃一條避開所有障礙物的端到端的路徑。不同的是,飛機飛行時強振動的環境要求線纜必須能夠被可靠固定;飛機內部密集的管路、復雜的電磁環境要求線纜盡量避開危險區域;而且相較于立方體結構,飛機接近圓形的機身也為路徑規劃增加了難度。綜合以上因素,在設計航空線纜路徑規劃算法時,本文主要考慮了如下布線約束:①避障,不與空間中的其他設備發生干涉;②貼近結構件,避免懸空,以便捆扎固定;③保持原方向,盡量避免轉彎,轉彎半徑必須大于線纜的最小彎曲半徑;④禁止小于90°的彎折,盡量大轉彎角度;⑤盡量避開高溫、高濕、強電磁等區域;⑥滿足與互斥線纜的隔離距離和盡量與兼容線纜保持共同路徑;⑦線路長度盡量短。
如圖1所示,本文設計了復雜約束下基于改進A*算法的線纜路徑規劃方法,主要包括如下步驟。
步驟1:創建布線模型,導入線纜接線表信息。
步驟2:對布線空間模型進行均勻柵格化處理,建立結構件包裝盒模型,根據柵格點與結構件包裝盒的相對空間位置,為柵格點分配不同的權值。
步驟3:建立接線終端包裝盒模型,將布線空間劃分為待布線空間區域和非布線空間區域。
步驟4:利用改進的A*算法詳細規劃線纜路徑,并對A*算法輸出的線纜路徑作擬合曲線處理。
步驟5:遵循線纜模型的繪制方式,將布線結果在CAD軟件中驅動生成。

圖1 總體流程圖
包裝盒算法的基本思想是使用規則的矩形包圍不規則圖形,從而構造不規則圖形的邊界,被廣泛用于干涉檢測等方面[17]。柵格法的基本思想是將連續的二維空間或者三維空間分解成若干個相同大小的離散的基本單元,因其分解快速、操作簡單、便于計算而被廣泛用于離散環境模型的構建[18]。本文首先使用包裝盒算法框定模型范圍,再使用均勻密度的柵格線將三維布線空間劃分為相同大小的立方體,如圖2a所示。采用柵格法對自由空間進行處理不僅可以很好地描述各種復雜的環境,而且可以將布線約束反映到柵格點的權值上[19],以圖2b為例(黑色線為設備輪廓,紅色線為設備包裝盒),賦予盒內的網格點最高的權值,以避免被路徑搜索算法采樣,達到避障效果。同理,將設備包裝盒上的點賦予較低的權值,使其易被采樣,從而使線纜能夠貼近結構件,便于捆扎固定。實際中飛機線束有很大比例是依附于機身結構固定的,而方形包裝盒難以完美地構造圓形機身的輪廓邊界,為此本文設計了適用于曲面的扇形包裝盒,如圖2c所示。采用半徑稍小的圓與圓形機身構成一個封閉的扇形,認為到圓心的距離d不小于圓形包裝盒半徑r且小于機身半徑R的點即扇形區內的柵格點是可依附于機身固定的,賦予較低的權值以便于被采樣。除避障與貼壁約束外,其他更加復雜的布線約束也可通過進一步的權值劃分來更加精細地描述。
為保證路徑的精度,需要以較小的粒度劃分柵格,但在三維空間中,每個維度上等分的個數每增加1,立方體數就隨之增加3n2+3n+1,其中n為粒度改變前每個維度上均勻劃分的密度。立方數量的暴增不僅耗費存儲空間,更會降低路徑搜索算法的效率。為此本文通過構建包含起點和終點的包裝盒,將布線空間分為盒內待布線空間和盒外非布線空間,以降低搜索成本,如圖2d所示,其計算公式為
(1)
式中,xmin、xmax、ymin、ymax、zmin、zmax為起點和終點坐標的最小、最大值;d為調整包裝盒邊界范圍的參數;X、Y、Z為盒內待布線空間的坐標范圍。

(a)均勻柵格化 (b)可依附性

(c)機身包裝盒(正視圖) (d)布線空間劃分圖2 空間預處理示意圖
路徑規劃本質上是對周圍環境信息綜合分析的過程,為實現更加復雜的布線約束,需要對自由空間進行精密的描述,對柵格點進行高效的編碼,使其攜帶更多的環境信息。以圖3為例,柵格點A受到磁和熱的共同作用,同時它還處于設備的可依附點位上。若待規劃線纜經過點A,則該點也同時處于與已存在的互斥線纜E產生信號串擾的區間內和被已存在的兼容線纜F吸引的區間內(圖中僅標識了磁和熱輻射的作用范圍)。為在點A同時描述上述信息,采用圖4所示的十六進制編碼方式對柵格點進行編碼。

圖3 布線環境

圖4 權值編碼與解碼系統
編碼碼文由兩部分組成:固定區碼文和擴展區碼文。固定區碼文跟布線模型有關,在模型預制好時便已固定下來。鑒于本文所考慮的布線約束,固定區碼文主要考慮可依附性、電磁強度、熱度3個因素。擴展區碼文是根據布線環境變化而變化的,在布線空間中新敷設一條線纜就需更新相應區域的擴展區碼文,其主要作用是約束已存在的線纜與待規劃線纜之間的位置關系,防止信號串擾和幫助兼容線纜盡可能地走在一起,規整線束。擴展區碼文由一系列線纜類型和相隔距離的固定組合構成。
(1)可依附性表示這一柵格點是否易于線纜捆扎固定。布線空間內設備眾多,為降低模型預處理后的復雜度,本文只標識3類點,如圖2b所示,即不可達點、可依附點、懸空點,分別用F、2、8標識:
(2)
式中,d1為柵格點到設備的最近距離,采用相隔x個柵格來相對刻畫;s為可依附性編碼。
此點位具有最高的優先級,若此位標記為F,則表示此點位于設備內不可經過,后續的碼文也就無需考慮。
(2)電磁強度和熱度表示此柵格點受電磁和熱源的輻射程度,均采用0-F的遞增序列表示從弱到強。準確地獲取電纜敷設空間中磁場和溫度場的分布對電纜路徑規劃十分重要,但卻十分困難且不是本文分析的重點。本文簡單地將強度的變化與距離掛鉤加以模擬分析,如圖5a所示。假設輻射源中心強度為F,輻射強度i隨距離衰減分成4個檔位(可根據需求進一步擴展),外圍方形包裝盒框定了輻射源的作用范圍,編碼數值計算方式如下:
(3)
空間內可能還存在多個磁場(熱度場)疊加的情形,采用線性疊加的方式對編碼數值進行加減修改,上限為F,表達式如下:
I=min(i1+i2+,…,+in,F)
(4)
式中,d2為柵格點與電磁輻射源的最近距離;in為電磁輻射源n在柵格點處的強度編碼;I為電磁輻射疊加后柵格點的實際編碼。熱度編碼同理。
(3)線纜類型。采用0-F的十六進制編碼指示16種線纜。
(4)相隔距離表示當前柵格點與某類線纜的距離大小,如圖5b所示。以線纜為中心向外擴張,劃分四層作用區間,0-F的遞增序列表示距離由遠到近,F表示與線纜重合,其編碼數值tR的計算方式與式(3)一致。擴展區的編碼設計方式考慮了不同類型的線纜,在編碼時相互隔離互不影響,而當兩個同類線纜共同作用于一個柵格點時選取大值作為此柵格點的編碼,如下:
TR=max(t1,R,t2,R,…,tn,R)
(5)
式中,tR為柵格點與線纜R的相隔距離編碼;n表示有n條R型線纜共同作用于當前柵格點;TR為線纜作用區間疊加后柵格點的實際編碼。
因而,對一個柵格點而言擴展區的線纜類型是不重復的。

(a)輻射分布 (b)線纜作用區間圖5 距離場分布
綜上,網格劃分和編碼完成之后,整個模型空間就形成了一個具有不同“勢能”的場,用三維數組S[α(x,y,z)]表示,其中α(x,y,z)表示對格點(x,y,z)的編碼。以圖3中的點A、點B為例,點A可編碼為0X299ECFC,點B可編碼為0X85CEFF9。
A*算法在搜索過程中加入了與問題有關的啟發性信息,縮短了盲目搜索的過程,可以快速找到端到端的最短路徑,在路徑規劃任務中得到了廣泛的應用[6]。A*算法搜索的原理是,在周圍相鄰的點云中選擇估價函數最小的節點作為下一步路徑,其一般估價函數為
f(n)=g(n)+h(n)
(6)
其中,f(n)為節點n的估價函數,它表示從起點經由節點n到達終點的代價估計,由從起點到達節點n的代價g(n)和從節點n到達終點的最短路徑的估計代價h(n)組成。A*算法通過維護Open表和Closed表來實現節點的篩選,Open表為一個按照估價函數升序排列的優先隊列,用于存儲待擴展的備選節點信息,Closed表用于存儲已擴展的節點。具體執行步驟如下:
(1)將起始節點加入Open表中,如果Open表不為空,則循環執行步驟(2)~步驟(4),否則搜索失敗,程序退出。
(2)選取Open表中估價函數最小的節點n。
(3)如果節點n為終點,則向前回溯到起點,返回找到的路徑,程序退出。
(4)如果節點n不是終點,則將節點n從Open表中刪除并加入Closed表。以節點n為中心,遍歷節點n的所有鄰近節點,如果某個鄰近節點已在Closed表中,則忽略該節點,否則計算該節點的g值。之后判斷該節點是否已在Open表中,是則與其原有g值比較,選取小的g值作為新g值,并更新其父節點;否則計算該節點的估價函數f,將該節點加入Open表中,并設置其父節點為節點n。
傳統A*算法追求的目標只有路徑最短,難以滿足實際工程需要,因此本文對A*算法的估價函數進行改進,使其兼顧布線約束要求,改進后的估價函數為
(7)

(8)
(9)
q*(n)=
(10)
h(n)=|xn-xgoal|+|yn-ygoal|+|zn-zgoal|
(11)

新的估價函數由二維擴展為三維,并且需要在滿足剛性因子p*(n)的條件下。p*(n)=0的主要作用在于保證線纜的彎折半徑要大于線纜的最小彎折半徑,對于滿足的點n,p*(n)=0,否則p*(n)=1。為了彎折得更加平滑,忽略小于90°的彎折點。對于90°到180°的彎折,給一個隨角度增加而減小的懲罰q*(n),用于促使線纜增大彎折角度,而且本身作為彎折的懲罰項,可以促使線纜減少彎折,這可以顯著減小線纜的損傷。
3.2.1柵格權值解碼系統
飛機上的線纜在敷設時,出于安全性和可靠性考慮,要根據導線的電流、電磁場、熱場、余度等不同特性進行綜合設計,本文通過圖4所示的解碼碼文解構線纜不同的屬性。
解碼規則與編碼規則類似,也是由固定區和擴展區兩部分組成。固定區的解碼碼文與編碼碼文兩相對應,固定區的碼文考慮線纜受可依附性、電磁強度、熱度的影響程度,通過β1、β2、β3三項加權系數來衡量。擴展區的碼文由一系列線纜類型和影響因子的固定組合構成,線纜類型表明待布線纜會受到該類線纜的影響,影響程度由影響因子決定。
(1)β1、β2、β3均為[0,1]常數,數值越大表明受影響程度越嚴重。由β2、β3的取值可知,受電磁或熱度影響的柵格點并非直接排除,即磁場區和熱度區也可穿越,一切由數值計算決定。
(2)線纜類型取值0-F,對應編碼中的16種線纜。影響因子β則根據線纜間的作用關系而定,同類相吸取值[-1,0],異類相斥取值[0,1]。與編碼的數值配合,在計算式(8)時分別給予負向增益和正向增益,從而促使待布線纜靠近或者遠離某類線纜。
改進后A*算法的解碼流程如圖6中標示顏色部分所示。首先依次計算固定區的可依附性權值、電磁強度權值、熱度權值;然后檢查擴展區解碼碼文的線纜類型是否在當前柵格點的編碼碼文中,存在則計算影響權值,否則檢查下一項,權值計算方式為,將該項的十六進制編碼轉化為十進制并與解碼的對應權重相乘;最后將所有項求和得到該柵格點的總權重,如式(9)所示。

圖6 改進后A*算法搜索流程
3.2.2剛性因子
如圖7a中MN段所示,剛性因子[14-15]主要用來解決因兩次連續彎折過近而導致無法滿足線纜最小彎曲半徑的問題。如圖7b所示,某一線纜的直徑為r0,最小彎曲半徑為R0,經過一個角度α的拐角,則兩側至少預留出的直線段長度為
(12)
為避免兩次連續彎折過近,需要在彎折時向前搜索到上一拐點(第一個拐點搜索到起點為止)。根據式(12)計算上一拐點的最短預留直線段長度,判斷兩個拐點之間的距離是否大于此次彎折最短預留直線長度和上一彎折最短預留直線長度之和,否則取消此次彎折。

(a)連續彎折 (b)拐角圖7 剛性因子及最小彎折半徑
前文從彎折數量和彎折角度方面對彎折做出了諸多限制,已可以很大程度上避免連續多次近距離彎折情況,即階梯形路徑。但是由于柵格離散化的原因,搜索得到的路徑是由一系列的線段構成的,在貼合機身結構進行布線時,還是會無法避免地產生圖8a所示的階梯形路徑。文獻[11,20-21]都采用類似可視圖的思想減少路徑控制點,從而實現對路徑的平滑處理,但此類方法不僅會破壞路徑的貼壁特性,而且顯然無法解決曲面的階梯路徑問題。為此本文根據路徑控制點的位置特點,利用相似三角形原理,將機身扇形包裝盒內的路徑控制點做貼合曲面處理,如圖8b所示。已知線纜直徑r0,機身圓心A坐標、最小彎曲半徑R0、路徑控制點B坐標,將路徑控制點B沿AB的延長線移動至點C處。考慮線纜本身直徑,則AC長度為R0-r0,根據相似三角形原理易得點C坐標:
(13)
式中,xA、yA、zA為點A的坐標值,其余同理。
將點C作為線纜新的路徑控制點替換點B。如此檢查位于機身包裝盒內的所有路徑控制點便可獲得一圈貼著機身蒙皮的新路徑控制點。

(a)階梯路徑 (b)擬合曲線處理圖8 貼合機身輪廓處理(正視圖)Fig.8 Fit the fuselage contour processing(front view)
仿真實驗在Windows11 64位系統、CPU AMD R7-5800H、主頻3.2 GHz、運行內存16 GB的計算機平臺上進行,采用Python3.7作為開發語言。為了驗證本文方法的有效性,首先在二維網格圖上進行算法性能驗證,再在三維飛機數模上進行可行性驗證。根據線纜特性,按照嚴重(|β|∈[1,0.7))、較重(|β|∈[0.7,0.5))、一般(|β|∈[0.5,0.3))、較輕(|β|∈[0.3,0))和無感(|β|∈0)的區間劃分線纜受環境因素的影響程度。
首先在一定β值下驗證算法對布線約束的實現,再以可依附性和熱敏感度為例,調整其β值,驗證算法對線纜特性的實現。實驗結果如圖9所示,實驗方式采用控制變量法,每次實驗都在前一步的基礎上進行。假設待規劃線纜的半徑為2 mm,最小彎曲半徑為20 mm,與線纜E互斥,與線纜F兼容。二維網格的分辨率為30 cm × 30 cm。
由圖9可以看到,加入彎折因子后,規劃路徑的彎折數由7個減少為3個,且彎折角度均為大彎角,不僅減少了對線纜的損傷也增加了線纜的平滑度。加入貼壁約束后,線纜選擇貼著結構件走線,大大方便了后期的捆扎固定。加入互斥線纜后,線纜會盡量遠離該線纜,防止信號串擾。加入兼容線纜后,線纜會盡量地與之走在一起,形成線束。加入溫度場后,對熱敏感的線纜會盡量遠離熱源。疊加電磁輻射場后,對磁和熱都敏感的線纜會走磁和熱相對平衡的路徑。加入剛性因子規范后,線纜彎折滿足最小彎曲半徑。然后分別減小熱敏感度β值和增大貼壁性β值以模擬實際情況下不同線纜具有不同特性的情況,算法能夠根據參數的變化做出靈敏反應,如圖9i和圖9j所示。綜上,改進后的A*算法能夠應對復雜的布線約束,規劃滿足不同線纜特性需求的路徑。

(a)傳統A*算法 (b)加入彎折因子

(c)加入貼壁約束 (d)加入互斥線纜隔離

(e)加入兼容線纜吸引 (f)加入熱敏感隔離

(g)加入磁敏感隔離 (h)加入剛性因子
應用前文所述的改進A*算法,在圖10所示的飛機貨艙段模型下進行仿真驗證(內部的紅色方塊和藍色方塊分別用以模擬熱源和電磁源,同時為了方便觀察隱去了其余設備)。首先采用均勻柵格法將布線空間均勻地分為80 cm×80 cm×40 cm的離散空間并作為算法的搜索空間,三維環境較二維網格圖法的搜索方向由8個增加為26個,復雜度大大增大。然后在布線空間中設置6條線纜進行仿真測試,接線關系及線纜參數如表1所示,其中將信號線與電源線視為互斥線纜,要求保持一定隔離距離,而同類線互相兼容,盡量合并。最后基于CATIA二次開發將規劃路徑可視化。為了展現本文方法的改進效果與優越性,與傳統A*算法和文獻[11]所提方法進行對比。文獻[11]所考慮約束與本文研究相近且具有良好的應用效果。不同方法的布線結果如圖10所示,仿真結果中的一些關鍵參數總結如表2所示。其中,貼壁占比表示貼附于結構件的電纜長度與總長度之比,用于評估是否易于固定,其統計方法如下:
(14)
式中,m為線纜分段總數;li為貼壁段i的長度;Lz為線纜總長度。
是否是貼壁段則通過線段的兩端點的權值判斷。電纜與輻射源以及互斥電纜之間是否串擾通過它們之間的最近距離來判定,假設距離小于4 cm會發生串擾。是否違反剛性因子則通過式(12)判定。
由圖10可以看出,傳統A*算法規劃線纜存有大量彎折和無法固定的飛線,互斥線纜之間存在重合路徑,規劃路徑不可用。文獻[11]方法規劃的線纜在彎折和貼壁性上有了很大改善,彎折點數量明顯減少且線纜能夠沿著設備架和機身結構進行布線,但互斥線纜之間仍存在交叉,沿著圓形機身布線的線纜擬合效果不佳。本文方法規劃線纜的平滑度和連續性最好,接近真實線纜效果,且兼容線纜合并走線形成了線束,互斥線纜以及信號線與輻射源之間保持了一定隔離距離。由表2數據分析可得,本文方法因為要滿足一些布線約束而無法選擇最短路徑,在長度上有所增加,但是在布線質量上有了較大改進,較傳統A*算法貼壁占比平均增加48.40%,線纜彎折個數平均減少6.50個,線纜均滿足隔離要求和最小彎曲半徑。對比文獻[11],除線纜長度外,本文方法整體上優于文獻[11]方法,進一步驗證了本文方法的優越性。另外,文獻[11]考慮到了線纜和輻射源之間隔離要求,但沒有考慮線纜之間的隔離以及合并要求,因而本文方法可以解決的布線約束更加全面。

(a)傳統A*算法布線 (b)文獻[11]方法布線 (c)本文方法布線

(d)傳統A*算法線纜 (e)文獻[11]方法線纜 (f)本文方法線纜圖10 不同方法布線結果對比

表1 接線表

表2 不同方法布線結果統計
為有效解決航空線纜自動化布線過程中面臨的各種復雜布線約束,本文提出了基于改進A*算法的航空線纜路徑智能規劃方法。該方法充分利用布線空間的三維離散柵格地圖,將對線纜的避障、貼壁、隔磁、防熱、同類合并、異類隔離等約束融入進柵格點的權值中。通過權值編碼系統對柵格點進行編碼,使其能夠攜帶體現周圍環境情況的信息。再通過反映待布線纜屬性信息的解碼系統從柵格點權值中提取有用信息。通過改進A*算法的估價函數使得編碼系統和解碼系統能夠相互交互,發揮作用。同時在A*算法的估價函數中加入了對彎折角度和轉彎半徑的考量以減少線纜彎折損傷。最后對規劃出的路徑進行曲線擬合,以貼合飛機曲面輪廓。仿真結果表明,本文方法能夠應對線纜自動化布線過程中的各種復雜布線約束,規劃滿足實際工程需要的線纜。本文方法較為依賴地圖精度,用包裝盒算法構建復雜外形設備的輪廓會增加非實體空間,導致在描述設備影響范圍時容易有較大誤差,因此后續需要進一步研究地圖的構建。