孫 浩 原 野 張 琦 張小貝

1.上海大學(xué)通信與信息工程學(xué)院,上海,2004442.上海飛機(jī)設(shè)計(jì)研究院,上海,201210

0 引言

航空電氣線路互聯(lián)系統(tǒng)(electrical wiring interconnection systems,EWIS)是指安裝在飛機(jī)上任何區(qū)域,在兩個(gè)或多個(gè)端接點(diǎn)之間傳輸電能(包含數(shù)據(jù)和信號(hào))的各種導(dǎo)線電纜、端接器件、支撐器件的組合,EWIS的設(shè)計(jì)與布置直接影響飛機(jī)的經(jīng)濟(jì)性、可靠性和安全性[1-3]。傳統(tǒng)依靠人工的設(shè)計(jì)方式存在設(shè)計(jì)周期長(zhǎng)、易出錯(cuò)、無(wú)法得到最優(yōu)路徑等問(wèn)題[4]。隨著科技的發(fā)展,人工智能算法逐漸被應(yīng)用于自動(dòng)布線,克服了人工規(guī)劃的不足。

自動(dòng)布線的核心是路徑搜索算法。雖然迪杰斯特拉算法[5](Dijkstra)、A*算法[6]、快速搜索隨機(jī)樹(shù)算法[7](rapidly-exploring random trees,RRT)等傳統(tǒng)路徑搜索算法可以做到無(wú)干涉的最短路徑,但顯然無(wú)法滿足實(shí)際布線工程的需要,為此國(guó)內(nèi)外學(xué)者對(duì)傳統(tǒng)算法進(jìn)行了適應(yīng)性改造,使其滿足不同的布線需求。董宗然等[8]將布線約束反映在網(wǎng)格能量值中,代入最短路徑快速算法(shortest path faster algorithm, SPFA)距離松弛函數(shù)的計(jì)算,從而將布線約束納入考慮,但對(duì)布線約束向網(wǎng)格能量值的映射過(guò)程缺少詳細(xì)介紹。劉瀟等[9]、劉佳順等[10]改進(jìn)RRT算法,使隨機(jī)樹(shù)能夠貼著障礙物表面拓展,便于線束捆扎固定,又對(duì)規(guī)劃出的路徑點(diǎn)進(jìn)行位置修正,讓路徑更加平滑,但難考慮更加復(fù)雜的約束。吳宏超等[11]改進(jìn)A*算法的估價(jià)函數(shù),使其與彎折和方向有關(guān),通過(guò)在設(shè)備周圍設(shè)置吸引區(qū)和排除危險(xiǎn)設(shè)備周圍的點(diǎn),讓線纜靠近或遠(yuǎn)離,具有不錯(cuò)的效果。KANG等[12]先用Dijkstra算法規(guī)劃避障的最短路徑,再用拉普拉斯平滑算法平滑布線路徑,使線纜的連續(xù)性得到提高,但較為簡(jiǎn)單,沒(méi)有考慮更多布線約束。王發(fā)麟等[13]以線纜間電磁干擾最小且整體線纜束質(zhì)量最小為目標(biāo),采用改進(jìn)粒子群算法進(jìn)行整體尋優(yōu)并獲取線纜的具體路徑,但規(guī)劃過(guò)程需要較多迭代,計(jì)算時(shí)間長(zhǎng),不利于實(shí)際應(yīng)用,且是非確定性算法,可能會(huì)產(chǎn)生無(wú)效解。如何減少線纜的機(jī)械損傷,一直是學(xué)者們的研究重點(diǎn)。姜康等[14]在A*算法的估價(jià)函數(shù)中加入彎折因子、剛性因子以約束線纜彎折,加入干涉因子以避免與障礙物及布線空間的邊界發(fā)生干涉。楊旭等[15]對(duì)線纜的彎折進(jìn)行了詳細(xì)分析,綜合考慮了彎線槽單位長(zhǎng)度的材料成本、工藝成本、質(zhì)量成本,用以減少線纜彎折損傷,同時(shí)對(duì)障礙物的棱角做膨脹處理,用以在線纜和障礙物尖銳處留出空隙,以減少線纜磕碰損傷。KIM等[16]在設(shè)計(jì)船舶管道時(shí)以線纜長(zhǎng)度和彎折個(gè)數(shù)為學(xué)習(xí)目標(biāo),使用強(qiáng)化學(xué)習(xí)規(guī)劃最為經(jīng)濟(jì)安全的路徑。綜上,國(guó)內(nèi)外學(xué)者為線纜路徑規(guī)劃提供了多樣化的解決思路,但是上述方法或難獲得最優(yōu)路徑,或考慮約束不全面,或算法復(fù)雜,難以實(shí)際應(yīng)用,且對(duì)更加復(fù)雜的電氣約束如電磁干擾、線纜間的相互作用等情況的研究甚少。

本文對(duì)航空EWIS自動(dòng)布線技術(shù)進(jìn)行研究,提出了基于改進(jìn)A*算法的航空線纜路徑規(guī)劃方法。該方法首先采用柵格法將布線空間均勻離散化;之后對(duì)柵格點(diǎn)進(jìn)行權(quán)值編碼,以描述柵格點(diǎn)周圍的環(huán)境因素;然后根據(jù)線纜受不同環(huán)境因素的影響程度,計(jì)算表征了不同布線約束的綜合權(quán)值,用以改進(jìn)A*算法;同時(shí)在A*算法的估價(jià)函數(shù)中加入彎折因子和剛性因子,以約束線纜的彎折;最后對(duì)規(guī)劃出的路徑進(jìn)行擬合曲線優(yōu)化調(diào)整以適應(yīng)飛機(jī)曲面,從而獲得最終的布線結(jié)果。所提方法有助于EWIS實(shí)現(xiàn)從人工設(shè)計(jì)向自動(dòng)化、智能化設(shè)計(jì)的升級(jí)。

1 航空線纜布線問(wèn)題分析

同所有機(jī)電產(chǎn)品的線纜一樣,航空線纜路徑規(guī)劃的最基本要求也是在布線空間內(nèi)自動(dòng)規(guī)劃一條避開(kāi)所有障礙物的端到端的路徑。不同的是,飛機(jī)飛行時(shí)強(qiáng)振動(dòng)的環(huán)境要求線纜必須能夠被可靠固定;飛機(jī)內(nèi)部密集的管路、復(fù)雜的電磁環(huán)境要求線纜盡量避開(kāi)危險(xiǎn)區(qū)域;而且相較于立方體結(jié)構(gòu),飛機(jī)接近圓形的機(jī)身也為路徑規(guī)劃增加了難度。綜合以上因素,在設(shè)計(jì)航空線纜路徑規(guī)劃算法時(shí),本文主要考慮了如下布線約束:①避障,不與空間中的其他設(shè)備發(fā)生干涉;②貼近結(jié)構(gòu)件,避免懸空,以便捆扎固定;③保持原方向,盡量避免轉(zhuǎn)彎,轉(zhuǎn)彎半徑必須大于線纜的最小彎曲半徑;④禁止小于90°的彎折,盡量大轉(zhuǎn)彎角度;⑤盡量避開(kāi)高溫、高濕、強(qiáng)電磁等區(qū)域;⑥滿足與互斥線纜的隔離距離和盡量與兼容線纜保持共同路徑;⑦線路長(zhǎng)度盡量短。

如圖1所示,本文設(shè)計(jì)了復(fù)雜約束下基于改進(jìn)A*算法的線纜路徑規(guī)劃方法,主要包括如下步驟。

步驟1:創(chuàng)建布線模型,導(dǎo)入線纜接線表信息。

步驟2:對(duì)布線空間模型進(jìn)行均勻柵格化處理,建立結(jié)構(gòu)件包裝盒模型,根據(jù)柵格點(diǎn)與結(jié)構(gòu)件包裝盒的相對(duì)空間位置,為柵格點(diǎn)分配不同的權(quán)值。

步驟3:建立接線終端包裝盒模型,將布線空間劃分為待布線空間區(qū)域和非布線空間區(qū)域。

步驟4:利用改進(jìn)的A*算法詳細(xì)規(guī)劃線纜路徑,并對(duì)A*算法輸出的線纜路徑作擬合曲線處理。

步驟5:遵循線纜模型的繪制方式,將布線結(jié)果在CAD軟件中驅(qū)動(dòng)生成。

圖1 總體流程圖

2 布線空間預(yù)處理

2.1 布線空間均勻離散化

包裝盒算法的基本思想是使用規(guī)則的矩形包圍不規(guī)則圖形,從而構(gòu)造不規(guī)則圖形的邊界,被廣泛用于干涉檢測(cè)等方面[17]。柵格法的基本思想是將連續(xù)的二維空間或者三維空間分解成若干個(gè)相同大小的離散的基本單元,因其分解快速、操作簡(jiǎn)單、便于計(jì)算而被廣泛用于離散環(huán)境模型的構(gòu)建[18]。本文首先使用包裝盒算法框定模型范圍,再使用均勻密度的柵格線將三維布線空間劃分為相同大小的立方體,如圖2a所示。采用柵格法對(duì)自由空間進(jìn)行處理不僅可以很好地描述各種復(fù)雜的環(huán)境,而且可以將布線約束反映到柵格點(diǎn)的權(quán)值上[19],以圖2b為例(黑色線為設(shè)備輪廓,紅色線為設(shè)備包裝盒),賦予盒內(nèi)的網(wǎng)格點(diǎn)最高的權(quán)值,以避免被路徑搜索算法采樣,達(dá)到避障效果。同理,將設(shè)備包裝盒上的點(diǎn)賦予較低的權(quán)值,使其易被采樣,從而使線纜能夠貼近結(jié)構(gòu)件,便于捆扎固定。實(shí)際中飛機(jī)線束有很大比例是依附于機(jī)身結(jié)構(gòu)固定的,而方形包裝盒難以完美地構(gòu)造圓形機(jī)身的輪廓邊界,為此本文設(shè)計(jì)了適用于曲面的扇形包裝盒,如圖2c所示。采用半徑稍小的圓與圓形機(jī)身構(gòu)成一個(gè)封閉的扇形,認(rèn)為到圓心的距離d不小于圓形包裝盒半徑r且小于機(jī)身半徑R的點(diǎn)即扇形區(qū)內(nèi)的柵格點(diǎn)是可依附于機(jī)身固定的,賦予較低的權(quán)值以便于被采樣。除避障與貼壁約束外,其他更加復(fù)雜的布線約束也可通過(guò)進(jìn)一步的權(quán)值劃分來(lái)更加精細(xì)地描述。

為保證路徑的精度,需要以較小的粒度劃分柵格,但在三維空間中,每個(gè)維度上等分的個(gè)數(shù)每增加1,立方體數(shù)就隨之增加3n2+3n+1,其中n為粒度改變前每個(gè)維度上均勻劃分的密度。立方數(shù)量的暴增不僅耗費(fèi)存儲(chǔ)空間,更會(huì)降低路徑搜索算法的效率。為此本文通過(guò)構(gòu)建包含起點(diǎn)和終點(diǎn)的包裝盒,將布線空間分為盒內(nèi)待布線空間和盒外非布線空間,以降低搜索成本,如圖2d所示,其計(jì)算公式為

(1)

式中,xmin、xmax、ymin、ymax、zmin、zmax為起點(diǎn)和終點(diǎn)坐標(biāo)的最小、最大值;d為調(diào)整包裝盒邊界范圍的參數(shù);X、Y、Z為盒內(nèi)待布線空間的坐標(biāo)范圍。

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

(c)機(jī)身包裝盒(正視圖) (d)布線空間劃分圖2 空間預(yù)處理示意圖

2.2 柵格權(quán)值編碼系統(tǒng)

路徑規(guī)劃本質(zhì)上是對(duì)周圍環(huán)境信息綜合分析的過(guò)程,為實(shí)現(xiàn)更加復(fù)雜的布線約束,需要對(duì)自由空間進(jìn)行精密的描述,對(duì)柵格點(diǎn)進(jìn)行高效的編碼,使其攜帶更多的環(huán)境信息。以圖3為例,柵格點(diǎn)A受到磁和熱的共同作用,同時(shí)它還處于設(shè)備的可依附點(diǎn)位上。若待規(guī)劃線纜經(jīng)過(guò)點(diǎn)A,則該點(diǎn)也同時(shí)處于與已存在的互斥線纜E產(chǎn)生信號(hào)串?dāng)_的區(qū)間內(nèi)和被已存在的兼容線纜F吸引的區(qū)間內(nèi)(圖中僅標(biāo)識(shí)了磁和熱輻射的作用范圍)。為在點(diǎn)A同時(shí)描述上述信息,采用圖4所示的十六進(jìn)制編碼方式對(duì)柵格點(diǎn)進(jìn)行編碼。

圖3 布線環(huán)境

圖4 權(quán)值編碼與解碼系統(tǒng)

編碼碼文由兩部分組成:固定區(qū)碼文和擴(kuò)展區(qū)碼文。固定區(qū)碼文跟布線模型有關(guān),在模型預(yù)制好時(shí)便已固定下來(lái)。鑒于本文所考慮的布線約束,固定區(qū)碼文主要考慮可依附性、電磁強(qiáng)度、熱度3個(gè)因素。擴(kuò)展區(qū)碼文是根據(jù)布線環(huán)境變化而變化的,在布線空間中新敷設(shè)一條線纜就需更新相應(yīng)區(qū)域的擴(kuò)展區(qū)碼文,其主要作用是約束已存在的線纜與待規(guī)劃線纜之間的位置關(guān)系,防止信號(hào)串?dāng)_和幫助兼容線纜盡可能地走在一起,規(guī)整線束。擴(kuò)展區(qū)碼文由一系列線纜類型和相隔距離的固定組合構(gòu)成。

(1)可依附性表示這一柵格點(diǎn)是否易于線纜捆扎固定。布線空間內(nèi)設(shè)備眾多,為降低模型預(yù)處理后的復(fù)雜度,本文只標(biāo)識(shí)3類點(diǎn),如圖2b所示,即不可達(dá)點(diǎn)、可依附點(diǎn)、懸空點(diǎn),分別用F、2、8標(biāo)識(shí):

(2)

式中,d1為柵格點(diǎn)到設(shè)備的最近距離,采用相隔x個(gè)柵格來(lái)相對(duì)刻畫(huà);s為可依附性編碼。

此點(diǎn)位具有最高的優(yōu)先級(jí),若此位標(biāo)記為F,則表示此點(diǎn)位于設(shè)備內(nèi)不可經(jīng)過(guò),后續(xù)的碼文也就無(wú)需考慮。

(2)電磁強(qiáng)度和熱度表示此柵格點(diǎn)受電磁和熱源的輻射程度,均采用0-F的遞增序列表示從弱到強(qiáng)。準(zhǔn)確地獲取電纜敷設(shè)空間中磁場(chǎng)和溫度場(chǎng)的分布對(duì)電纜路徑規(guī)劃十分重要,但卻十分困難且不是本文分析的重點(diǎn)。本文簡(jiǎn)單地將強(qiáng)度的變化與距離掛鉤加以模擬分析,如圖5a所示。假設(shè)輻射源中心強(qiáng)度為F,輻射強(qiáng)度i隨距離衰減分成4個(gè)檔位(可根據(jù)需求進(jìn)一步擴(kuò)展),外圍方形包裝盒框定了輻射源的作用范圍,編碼數(shù)值計(jì)算方式如下:

(3)

空間內(nèi)可能還存在多個(gè)磁場(chǎng)(熱度場(chǎng))疊加的情形,采用線性疊加的方式對(duì)編碼數(shù)值進(jìn)行加減修改,上限為F,表達(dá)式如下:

I=min(i1+i2+,…,+in,F)

(4)

式中,d2為柵格點(diǎn)與電磁輻射源的最近距離;in為電磁輻射源n在柵格點(diǎn)處的強(qiáng)度編碼;I為電磁輻射疊加后柵格點(diǎn)的實(shí)際編碼。熱度編碼同理。

(3)線纜類型。采用0-F的十六進(jìn)制編碼指示16種線纜。

(4)相隔距離表示當(dāng)前柵格點(diǎn)與某類線纜的距離大小,如圖5b所示。以線纜為中心向外擴(kuò)張,劃分四層作用區(qū)間,0-F的遞增序列表示距離由遠(yuǎn)到近,F表示與線纜重合,其編碼數(shù)值tR的計(jì)算方式與式(3)一致。擴(kuò)展區(qū)的編碼設(shè)計(jì)方式考慮了不同類型的線纜,在編碼時(shí)相互隔離互不影響,而當(dāng)兩個(gè)同類線纜共同作用于一個(gè)柵格點(diǎn)時(shí)選取大值作為此柵格點(diǎn)的編碼,如下:

TR=max(t1,R,t2,R,…,tn,R)

(5)

式中,tR為柵格點(diǎn)與線纜R的相隔距離編碼;n表示有n條R型線纜共同作用于當(dāng)前柵格點(diǎn);TR為線纜作用區(qū)間疊加后柵格點(diǎn)的實(shí)際編碼。

因而,對(duì)一個(gè)柵格點(diǎn)而言擴(kuò)展區(qū)的線纜類型是不重復(fù)的。

(a)輻射分布 (b)線纜作用區(qū)間圖5 距離場(chǎng)分布

綜上,網(wǎng)格劃分和編碼完成之后,整個(gè)模型空間就形成了一個(gè)具有不同“勢(shì)能”的場(chǎng),用三維數(shù)組S[α(x,y,z)]表示,其中α(x,y,z)表示對(duì)格點(diǎn)(x,y,z)的編碼。以圖3中的點(diǎn)A、點(diǎn)B為例,點(diǎn)A可編碼為0X299ECFC,點(diǎn)B可編碼為0X85CEFF9。

3 基于改進(jìn)A*算法的路徑規(guī)劃

3.1 A*算法簡(jiǎn)介

A*算法在搜索過(guò)程中加入了與問(wèn)題有關(guān)的啟發(fā)性信息,縮短了盲目搜索的過(guò)程,可以快速找到端到端的最短路徑,在路徑規(guī)劃任務(wù)中得到了廣泛的應(yīng)用[6]。A*算法搜索的原理是,在周圍相鄰的點(diǎn)云中選擇估價(jià)函數(shù)最小的節(jié)點(diǎn)作為下一步路徑,其一般估價(jià)函數(shù)為

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

(6)

其中,f(n)為節(jié)點(diǎn)n的估價(jià)函數(shù),它表示從起點(diǎn)經(jīng)由節(jié)點(diǎn)n到達(dá)終點(diǎn)的代價(jià)估計(jì),由從起點(diǎn)到達(dá)節(jié)點(diǎn)n的代價(jià)g(n)和從節(jié)點(diǎn)n到達(dá)終點(diǎn)的最短路徑的估計(jì)代價(jià)h(n)組成。A*算法通過(guò)維護(hù)Open表和Closed表來(lái)實(shí)現(xiàn)節(jié)點(diǎn)的篩選,Open表為一個(gè)按照估價(jià)函數(shù)升序排列的優(yōu)先隊(duì)列,用于存儲(chǔ)待擴(kuò)展的備選節(jié)點(diǎn)信息,Closed表用于存儲(chǔ)已擴(kuò)展的節(jié)點(diǎn)。具體執(zhí)行步驟如下:

(1)將起始節(jié)點(diǎn)加入Open表中,如果Open表不為空,則循環(huán)執(zhí)行步驟(2)～步驟(4),否則搜索失敗,程序退出。

(2)選取Open表中估價(jià)函數(shù)最小的節(jié)點(diǎn)n。

(3)如果節(jié)點(diǎn)n為終點(diǎn),則向前回溯到起點(diǎn),返回找到的路徑,程序退出。

(4)如果節(jié)點(diǎn)n不是終點(diǎn),則將節(jié)點(diǎn)n從Open表中刪除并加入Closed表。以節(jié)點(diǎn)n為中心,遍歷節(jié)點(diǎn)n的所有鄰近節(jié)點(diǎn),如果某個(gè)鄰近節(jié)點(diǎn)已在Closed表中,則忽略該節(jié)點(diǎn),否則計(jì)算該節(jié)點(diǎn)的g值。之后判斷該節(jié)點(diǎn)是否已在Open表中,是則與其原有g(shù)值比較,選取小的g值作為新g值,并更新其父節(jié)點(diǎn);否則計(jì)算該節(jié)點(diǎn)的估價(jià)函數(shù)f,將該節(jié)點(diǎn)加入Open表中,并設(shè)置其父節(jié)點(diǎn)為節(jié)點(diǎn)n。

3.2 改進(jìn)型A*算法

傳統(tǒng)A*算法追求的目標(biāo)只有路徑最短,難以滿足實(shí)際工程需要,因此本文對(duì)A*算法的估價(jià)函數(shù)進(jìn)行改進(jìn),使其兼顧布線約束要求,改進(jìn)后的估價(jià)函數(shù)為

(7)

(8)

(9)

q*(n)=

(10)

h(n)=|xn-xgoal|+|yn-ygoal|+|zn-zgoal|

(11)

新的估價(jià)函數(shù)由二維擴(kuò)展為三維,并且需要在滿足剛性因子p*(n)的條件下。p*(n)=0的主要作用在于保證線纜的彎折半徑要大于線纜的最小彎折半徑,對(duì)于滿足的點(diǎn)n,p*(n)=0,否則p*(n)=1。為了彎折得更加平滑,忽略小于90°的彎折點(diǎn)。對(duì)于90°到180°的彎折,給一個(gè)隨角度增加而減小的懲罰q*(n),用于促使線纜增大彎折角度,而且本身作為彎折的懲罰項(xiàng),可以促使線纜減少?gòu)澱?這可以顯著減小線纜的損傷。

3.2.1柵格權(quán)值解碼系統(tǒng)

飛機(jī)上的線纜在敷設(shè)時(shí),出于安全性和可靠性考慮,要根據(jù)導(dǎo)線的電流、電磁場(chǎng)、熱場(chǎng)、余度等不同特性進(jìn)行綜合設(shè)計(jì),本文通過(guò)圖4所示的解碼碼文解構(gòu)線纜不同的屬性。

解碼規(guī)則與編碼規(guī)則類似,也是由固定區(qū)和擴(kuò)展區(qū)兩部分組成。固定區(qū)的解碼碼文與編碼碼文兩相對(duì)應(yīng),固定區(qū)的碼文考慮線纜受可依附性、電磁強(qiáng)度、熱度的影響程度,通過(guò)β1、β2、β3三項(xiàng)加權(quán)系數(shù)來(lái)衡量。擴(kuò)展區(qū)的碼文由一系列線纜類型和影響因子的固定組合構(gòu)成,線纜類型表明待布線纜會(huì)受到該類線纜的影響,影響程度由影響因子決定。

(1)β1、β2、β3均為[0,1]常數(shù),數(shù)值越大表明受影響程度越嚴(yán)重。由β2、β3的取值可知,受電磁或熱度影響的柵格點(diǎn)并非直接排除,即磁場(chǎng)區(qū)和熱度區(qū)也可穿越,一切由數(shù)值計(jì)算決定。

(2)線纜類型取值0-F,對(duì)應(yīng)編碼中的16種線纜。影響因子β則根據(jù)線纜間的作用關(guān)系而定,同類相吸取值[-1,0],異類相斥取值[0,1]。與編碼的數(shù)值配合,在計(jì)算式(8)時(shí)分別給予負(fù)向增益和正向增益,從而促使待布線纜靠近或者遠(yuǎn)離某類線纜。

改進(jìn)后A*算法的解碼流程如圖6中標(biāo)示顏色部分所示。首先依次計(jì)算固定區(qū)的可依附性權(quán)值、電磁強(qiáng)度權(quán)值、熱度權(quán)值;然后檢查擴(kuò)展區(qū)解碼碼文的線纜類型是否在當(dāng)前柵格點(diǎn)的編碼碼文中,存在則計(jì)算影響權(quán)值,否則檢查下一項(xiàng),權(quán)值計(jì)算方式為,將該項(xiàng)的十六進(jìn)制編碼轉(zhuǎn)化為十進(jìn)制并與解碼的對(duì)應(yīng)權(quán)重相乘;最后將所有項(xiàng)求和得到該柵格點(diǎn)的總權(quán)重,如式(9)所示。

圖6 改進(jìn)后A*算法搜索流程

3.2.2剛性因子

如圖7a中MN段所示,剛性因子[14-15]主要用來(lái)解決因兩次連續(xù)彎折過(guò)近而導(dǎo)致無(wú)法滿足線纜最小彎曲半徑的問(wèn)題。如圖7b所示,某一線纜的直徑為r0,最小彎曲半徑為R0,經(jīng)過(guò)一個(gè)角度α的拐角,則兩側(cè)至少預(yù)留出的直線段長(zhǎng)度為

(12)

為避免兩次連續(xù)彎折過(guò)近,需要在彎折時(shí)向前搜索到上一拐點(diǎn)(第一個(gè)拐點(diǎn)搜索到起點(diǎn)為止)。根據(jù)式(12)計(jì)算上一拐點(diǎn)的最短預(yù)留直線段長(zhǎng)度,判斷兩個(gè)拐點(diǎn)之間的距離是否大于此次彎折最短預(yù)留直線長(zhǎng)度和上一彎折最短預(yù)留直線長(zhǎng)度之和,否則取消此次彎折。

(a)連續(xù)彎折 (b)拐角圖7 剛性因子及最小彎折半徑

3.3 路徑優(yōu)化處理

前文從彎折數(shù)量和彎折角度方面對(duì)彎折做出了諸多限制,已可以很大程度上避免連續(xù)多次近距離彎折情況,即階梯形路徑。但是由于柵格離散化的原因,搜索得到的路徑是由一系列的線段構(gòu)成的,在貼合機(jī)身結(jié)構(gòu)進(jìn)行布線時(shí),還是會(huì)無(wú)法避免地產(chǎn)生圖8a所示的階梯形路徑。文獻(xiàn)[11,20-21]都采用類似可視圖的思想減少路徑控制點(diǎn),從而實(shí)現(xiàn)對(duì)路徑的平滑處理,但此類方法不僅會(huì)破壞路徑的貼壁特性,而且顯然無(wú)法解決曲面的階梯路徑問(wèn)題。為此本文根據(jù)路徑控制點(diǎn)的位置特點(diǎn),利用相似三角形原理,將機(jī)身扇形包裝盒內(nèi)的路徑控制點(diǎn)做貼合曲面處理,如圖8b所示。已知線纜直徑r0,機(jī)身圓心A坐標(biāo)、最小彎曲半徑R0、路徑控制點(diǎn)B坐標(biāo),將路徑控制點(diǎn)B沿AB的延長(zhǎng)線移動(dòng)至點(diǎn)C處?？紤]線纜本身直徑,則AC長(zhǎng)度為R0-r0,根據(jù)相似三角形原理易得點(diǎn)C坐標(biāo):

(13)

式中,xA、yA、zA為點(diǎn)A的坐標(biāo)值,其余同理。

將點(diǎn)C作為線纜新的路徑控制點(diǎn)替換點(diǎn)B。如此檢查位于機(jī)身包裝盒內(nèi)的所有路徑控制點(diǎn)便可獲得一圈貼著機(jī)身蒙皮的新路徑控制點(diǎn)。

(a)階梯路徑 (b)擬合曲線處理圖8 貼合機(jī)身輪廓處理(正視圖)Fig.8 Fit the fuselage contour processing(front view)

4 算法測(cè)試與仿真

仿真實(shí)驗(yàn)在Windows11 64位系統(tǒng)、CPU AMD R7-5800H、主頻3.2 GHz、運(yùn)行內(nèi)存16 GB的計(jì)算機(jī)平臺(tái)上進(jìn)行,采用Python3.7作為開(kāi)發(fā)語(yǔ)言。為了驗(yàn)證本文方法的有效性,首先在二維網(wǎng)格圖上進(jìn)行算法性能驗(yàn)證,再在三維飛機(jī)數(shù)模上進(jìn)行可行性驗(yàn)證。根據(jù)線纜特性,按照嚴(yán)重(|β|∈[1,0.7))、較重(|β|∈[0.7,0.5))、一般(|β|∈[0.5,0.3))、較輕(|β|∈[0.3,0))和無(wú)感(|β|∈0)的區(qū)間劃分線纜受環(huán)境因素的影響程度。

4.1 算法性能驗(yàn)證

首先在一定β值下驗(yàn)證算法對(duì)布線約束的實(shí)現(xiàn),再以可依附性和熱敏感度為例,調(diào)整其β值,驗(yàn)證算法對(duì)線纜特性的實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果如圖9所示,實(shí)驗(yàn)方式采用控制變量法,每次實(shí)驗(yàn)都在前一步的基礎(chǔ)上進(jìn)行。假設(shè)待規(guī)劃線纜的半徑為2 mm,最小彎曲半徑為20 mm,與線纜E互斥,與線纜F兼容。二維網(wǎng)格的分辨率為30 cm × 30 cm。

由圖9可以看到,加入彎折因子后,規(guī)劃路徑的彎折數(shù)由7個(gè)減少為3個(gè),且彎折角度均為大彎角,不僅減少了對(duì)線纜的損傷也增加了線纜的平滑度。加入貼壁約束后,線纜選擇貼著結(jié)構(gòu)件走線,大大方便了后期的捆扎固定。加入互斥線纜后,線纜會(huì)盡量遠(yuǎn)離該線纜,防止信號(hào)串?dāng)_。加入兼容線纜后,線纜會(huì)盡量地與之走在一起,形成線束。加入溫度場(chǎng)后,對(duì)熱敏感的線纜會(huì)盡量遠(yuǎn)離熱源。疊加電磁輻射場(chǎng)后,對(duì)磁和熱都敏感的線纜會(huì)走磁和熱相對(duì)平衡的路徑。加入剛性因子規(guī)范后,線纜彎折滿足最小彎曲半徑。然后分別減小熱敏感度β值和增大貼壁性β值以模擬實(shí)際情況下不同線纜具有不同特性的情況,算法能夠根據(jù)參數(shù)的變化做出靈敏反應(yīng),如圖9i和圖9j所示。綜上,改進(jìn)后的A*算法能夠應(yīng)對(duì)復(fù)雜的布線約束,規(guī)劃滿足不同線纜特性需求的路徑。

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

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

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

(g)加入磁敏感隔離 (h)加入剛性因子

4.2 算法可行性驗(yàn)證

應(yīng)用前文所述的改進(jìn)A*算法,在圖10所示的飛機(jī)貨艙段模型下進(jìn)行仿真驗(yàn)證(內(nèi)部的紅色方塊和藍(lán)色方塊分別用以模擬熱源和電磁源,同時(shí)為了方便觀察隱去了其余設(shè)備)。首先采用均勻柵格法將布線空間均勻地分為80 cm×80 cm×40 cm的離散空間并作為算法的搜索空間,三維環(huán)境較二維網(wǎng)格圖法的搜索方向由8個(gè)增加為26個(gè),復(fù)雜度大大增大。然后在布線空間中設(shè)置6條線纜進(jìn)行仿真測(cè)試,接線關(guān)系及線纜參數(shù)如表1所示,其中將信號(hào)線與電源線視為互斥線纜,要求保持一定隔離距離,而同類線互相兼容,盡量合并。最后基于CATIA二次開(kāi)發(fā)將規(guī)劃路徑可視化。為了展現(xiàn)本文方法的改進(jìn)效果與優(yōu)越性,與傳統(tǒng)A*算法和文獻(xiàn)[11]所提方法進(jìn)行對(duì)比。文獻(xiàn)[11]所考慮約束與本文研究相近且具有良好的應(yīng)用效果。不同方法的布線結(jié)果如圖10所示,仿真結(jié)果中的一些關(guān)鍵參數(shù)總結(jié)如表2所示。其中,貼壁占比表示貼附于結(jié)構(gòu)件的電纜長(zhǎng)度與總長(zhǎng)度之比,用于評(píng)估是否易于固定,其統(tǒng)計(jì)方法如下:

(14)

式中,m為線纜分段總數(shù);li為貼壁段i的長(zhǎng)度;Lz為線纜總長(zhǎng)度。

是否是貼壁段則通過(guò)線段的兩端點(diǎn)的權(quán)值判斷。電纜與輻射源以及互斥電纜之間是否串?dāng)_通過(guò)它們之間的最近距離來(lái)判定,假設(shè)距離小于4 cm會(huì)發(fā)生串?dāng)_。是否違反剛性因子則通過(guò)式(12)判定。

由圖10可以看出,傳統(tǒng)A*算法規(guī)劃線纜存有大量彎折和無(wú)法固定的飛線,互斥線纜之間存在重合路徑,規(guī)劃路徑不可用。文獻(xiàn)[11]方法規(guī)劃的線纜在彎折和貼壁性上有了很大改善,彎折點(diǎn)數(shù)量明顯減少且線纜能夠沿著設(shè)備架和機(jī)身結(jié)構(gòu)進(jìn)行布線,但互斥線纜之間仍存在交叉,沿著圓形機(jī)身布線的線纜擬合效果不佳。本文方法規(guī)劃線纜的平滑度和連續(xù)性最好,接近真實(shí)線纜效果,且兼容線纜合并走線形成了線束,互斥線纜以及信號(hào)線與輻射源之間保持了一定隔離距離。由表2數(shù)據(jù)分析可得,本文方法因?yàn)橐獫M足一些布線約束而無(wú)法選擇最短路徑,在長(zhǎng)度上有所增加,但是在布線質(zhì)量上有了較大改進(jìn),較傳統(tǒng)A*算法貼壁占比平均增加48.40%,線纜彎折個(gè)數(shù)平均減少6.50個(gè),線纜均滿足隔離要求和最小彎曲半徑。對(duì)比文獻(xiàn)[11],除線纜長(zhǎng)度外,本文方法整體上優(yōu)于文獻(xiàn)[11]方法,進(jìn)一步驗(yàn)證了本文方法的優(yōu)越性。另外,文獻(xiàn)[11]考慮到了線纜和輻射源之間隔離要求,但沒(méi)有考慮線纜之間的隔離以及合并要求,因而本文方法可以解決的布線約束更加全面。

(a)傳統(tǒng)A*算法布線 (b)文獻(xiàn)[11]方法布線 (c)本文方法布線

(d)傳統(tǒng)A*算法線纜 (e)文獻(xiàn)[11]方法線纜 (f)本文方法線纜圖10 不同方法布線結(jié)果對(duì)比

表1 接線表

表2 不同方法布線結(jié)果統(tǒng)計(jì)

5 結(jié)語(yǔ)

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