姜 康 馬世紀(jì)

合肥工業(yè)大學(xué)汽車與交通工程學(xué)院，合肥，230009

0 引言

電纜的布置和安裝是機(jī)電產(chǎn)品開(kāi)發(fā)設(shè)計(jì)過(guò)程中經(jīng)常遇到的問(wèn)題，隨著機(jī)電產(chǎn)品愈加精細(xì)復(fù)雜，機(jī)電產(chǎn)品的性能和可靠性也越來(lái)越多地受到線纜布置裝配的影響[1]，傳統(tǒng)的布線方式已經(jīng)不適用于復(fù)雜的線纜布局設(shè)計(jì)，因此，使用人工智能算法進(jìn)行線纜布線規(guī)劃成為國(guó)內(nèi)外研究的熱點(diǎn)。

人工智能布線能夠避免傳統(tǒng)布線方式的弊端，高效合理地在布線空間中找到一個(gè)最優(yōu)的路徑，并使其走向合理、長(zhǎng)度最短、固定可靠、檢測(cè)方便[2]。PARK等[3]、CONRU等[4]利用遺傳算法研究了線纜的布置；付宜利等[5]利用粒子群算法進(jìn)行管路自動(dòng)敷設(shè)，實(shí)現(xiàn)了單根管路的自動(dòng)敷設(shè)；權(quán)建州等[6]在構(gòu)建三維可行權(quán)值的基礎(chǔ)上，運(yùn)用改進(jìn)A*算法進(jìn)行布線路徑搜索，并在UG平臺(tái)上通過(guò)二次開(kāi)發(fā)實(shí)現(xiàn)了虛擬環(huán)境中的自動(dòng)布線；DAI等[7]針對(duì)A*算法的搜索速度和準(zhǔn)確度進(jìn)行分析，提出了動(dòng)態(tài)估價(jià)的改進(jìn)方法；李純軍等[8]通過(guò)建立敷設(shè)空間模型和敷設(shè)約束模型來(lái)改進(jìn)A*算法，得到了合理的布線實(shí)現(xiàn)方案。上述研究或側(cè)重于線纜與管道的自動(dòng)布局設(shè)計(jì)，或研究算法在尋徑過(guò)程中的效率和準(zhǔn)確性，很少考慮線纜在實(shí)際布線中的彎折約束以及布線時(shí)的操作空間。

實(shí)際工程應(yīng)用中，最好的經(jīng)濟(jì)性固然是布線的一個(gè)要求，但線纜的敷設(shè)也要盡可能避免過(guò)多彎折對(duì)線纜性能造成損害，同時(shí)考慮布線空間對(duì)布線過(guò)程的影響。因此，使用人工智能算法進(jìn)行線纜路徑規(guī)劃時(shí)，對(duì)線纜彎折情況、布線空間等約束條件的研究是十分必要且有意義的。

本文通過(guò)改進(jìn)A*算法對(duì)復(fù)雜布線空間環(huán)境下的線纜路徑搜索問(wèn)題進(jìn)行了研究，算法考慮了線纜路徑的彎折點(diǎn)與布線空間對(duì)路徑的影響，通過(guò)簡(jiǎn)單路徑仿真與簡(jiǎn)化布線空間的虛擬布線對(duì)算法所求路徑進(jìn)行了驗(yàn)證，實(shí)例結(jié)果表明，改進(jìn)A*算法能得到合理的線纜路徑規(guī)劃方案。

1 線纜布線路徑規(guī)劃問(wèn)題描述

1.1 線纜路徑規(guī)劃概述

路徑規(guī)劃指在有障礙物的工作環(huán)境中尋找一條從起點(diǎn)到終點(diǎn)、無(wú)碰撞地繞過(guò)所有障礙物的運(yùn)動(dòng)路徑的過(guò)程[9]。線纜是機(jī)電產(chǎn)品中連接各類電器元件的介質(zhì)，它在產(chǎn)品空間中的布局和敷設(shè)質(zhì)量是衡量產(chǎn)品整機(jī)性能和可靠性的一個(gè)重要指標(biāo)[10]。對(duì)線纜進(jìn)行路徑規(guī)劃時(shí)，應(yīng)該主要考慮線纜與布線空間內(nèi)其他組件的干涉，以及與其他線纜之間的電氣干涉，同時(shí)，線纜自身的柔性約束也應(yīng)該加以考慮。對(duì)線纜的路徑規(guī)劃約束做出以下定義。

(1)干涉約束IC表示線纜路徑與其他組件的干涉。IC=0表示路徑與布線空間內(nèi)的其他組件無(wú)干涉。

(2)電氣約束EC表示線纜之間相互的電氣干涉。EC=0表示線纜之間不存在電氣干涉。

(3)自身柔性約束FC表示線纜自身的柔性特征所帶來(lái)的約束，包括最小彎曲半徑、線纜的直徑以及線纜彎曲過(guò)程中的受力。

(4) 經(jīng)濟(jì)約束LC表示線纜在布線過(guò)程中路徑的長(zhǎng)度，線纜布線的長(zhǎng)度越小，經(jīng)濟(jì)性越好。

(5)線纜的路徑表示為坐標(biāo)形式，二維柵格圖中的路徑表示為P=P(x,y)，三維空間中的線纜路徑表示為P=P(x,y,z)。

因此，線纜路徑規(guī)劃的數(shù)學(xué)模型可以表示為

(1)

式中，F(xiàn)n,C表示所有的線纜柔性約束；Ln,C表示線纜所有的經(jīng)濟(jì)性約束；opt(·)表示對(duì)所有約束均取最優(yōu)。

根據(jù)式(1)描述的數(shù)學(xué)模型可知，線纜的路徑規(guī)劃可以歸納為在一定的干涉約束、電氣約束、自身柔性約束和經(jīng)濟(jì)約束下獲得一條最短路徑。實(shí)際的線纜路徑規(guī)劃還要考慮線纜布線的靈活性、安全性以及操作空間是否滿足等條件。

1.2 線纜布線問(wèn)題

虛擬布線主要利用人工智能算法在一定的布線空間中進(jìn)行路徑搜索，并依據(jù)已經(jīng)規(guī)劃好的線纜路徑，在產(chǎn)品虛擬模型中進(jìn)行線纜的安裝和敷設(shè)。其主要過(guò)程如下。

(1)模型建立。在三維建模軟件中建立機(jī)電產(chǎn)品的虛擬數(shù)字化模型，構(gòu)建出線纜路徑規(guī)劃的虛擬布線空間。

(2)干涉檢查。主要對(duì)虛擬布線空間進(jìn)行實(shí)體干涉檢查，利用包圍盒理論進(jìn)行模型的干涉檢查，判斷模型之間的最小間隙，便于算法尋徑。

(3)布線空間處理。對(duì)布線空間設(shè)定柵格，將所有零件的包容盒視為障礙物。在二維平面內(nèi)搜索路徑時(shí)，將障礙物投影至平面；三維布線時(shí)，確定障礙物的位置和大小。在線纜直徑確定的情況下，判斷障礙物間距是否允許線纜通過(guò)。

(4)線纜敷設(shè)。根據(jù)已得到的線纜路徑信息，在產(chǎn)品模型的布線空間中進(jìn)行布線，并通過(guò)相關(guān)的軟件獲得線纜長(zhǎng)度等信息。

在線纜的實(shí)際布線過(guò)程中，線纜路徑還受到布線工藝的影響，因此，線纜路徑在布線工藝的約束下才具有實(shí)際意義。常見(jiàn)的典型布線工藝約束有以下幾點(diǎn)[11]：①線纜避免懸空，盡量沿剛性實(shí)體外壁布置，以便捆扎固定；②布線路徑經(jīng)過(guò)處，盡量避免附近存在熱源、電磁干擾；③盡量避免在布線位置處存在鈑金及尖銳棱角；④線纜路徑空間必須大于線纜直徑；⑤考慮溫度、濕度、穿線空間、振動(dòng)摩擦等外部因素對(duì)線纜的影響；⑥線束過(guò)孔時(shí)要加保護(hù)套。

2 基于A*算法的布線路徑搜索

2.1 算法介紹

A*算法結(jié)合了Dijkstra算法和BFS算法的優(yōu)點(diǎn)，將Dijkstra算法靠近終點(diǎn)的節(jié)點(diǎn)和BFS算法靠近目標(biāo)點(diǎn)的節(jié)點(diǎn)的信息結(jié)合起來(lái)，并引入了估價(jià)函數(shù)F(n)=G(n)+H(n)對(duì)搜索的位置節(jié)點(diǎn)進(jìn)行評(píng)估，其中，G(n)表示從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的代價(jià)，稱為代價(jià)函數(shù)[12]；H(n)表示從當(dāng)前節(jié)點(diǎn)n到目標(biāo)點(diǎn)的啟發(fā)式評(píng)估代價(jià)，稱為啟發(fā)函數(shù)。A*算法的關(guān)鍵在于啟發(fā)函數(shù)的確定，不同的啟發(fā)函數(shù)會(huì)對(duì)A*算法產(chǎn)生不同的效果。一般來(lái)說(shuō)，啟發(fā)函數(shù)應(yīng)該滿足以下條件[13]：

H(n)≤H*(n)

(2)

其中，H*(n)是當(dāng)前節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的真實(shí)最小代價(jià)。因此，只要保證當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的估價(jià)值不大于真實(shí)最小代價(jià)，且真實(shí)的問(wèn)題域確有可行解，則A*算法就能找到優(yōu)解。

2.2 算法的求解流程

A*算法需要2個(gè)基本的節(jié)點(diǎn)集合：OPEN表和CLOSE表。OPEN表用來(lái)存儲(chǔ)待檢測(cè)的節(jié)點(diǎn)的信息；CLOSE表用來(lái)存儲(chǔ)不需要再次檢查的節(jié)點(diǎn)的信息。A*算法的算法流程見(jiàn)圖1。

圖1 A*算法流程圖Fig.1 Flow chart of A* algorithm

2.3 算法存在的問(wèn)題

使用A*算法進(jìn)行路徑搜索雖然能得到一條最優(yōu)的路徑，但A*算法存在以下幾個(gè)問(wèn)題。

(1)行路徑搜索空間一般都會(huì)存在空間障礙，機(jī)電產(chǎn)品愈加精細(xì)，布線空間中的障礙物外形就愈加復(fù)雜。利用A*算法進(jìn)行搜索時(shí)，算法往往不能迅速識(shí)別障礙物，因此在搜索過(guò)程中，算法會(huì)產(chǎn)生一定程度的繞路和搜索時(shí)間的浪費(fèi)。

(2)應(yīng)用智能算法進(jìn)行路徑搜索時(shí)，算法給出的路徑往往不是實(shí)際的可行路徑，可能會(huì)有較大程度的彎折。這在一般的純路徑規(guī)劃中是可以接受的，但線纜有最小彎曲半徑，實(shí)際應(yīng)用中的彎曲度如果超過(guò)線纜的最小彎曲半徑，可能會(huì)造成線纜絕緣層以及芯線不可逆轉(zhuǎn)的破壞，嚴(yán)重影響線纜性能。

(3)傳統(tǒng)的路徑搜索算法只考慮最短路徑的問(wèn)題，對(duì)真實(shí)場(chǎng)景中的線纜裝配因素考慮得較少，且沒(méi)有考慮布線操作空間的影響，導(dǎo)致部分線纜路徑規(guī)劃的結(jié)果在理論上可行而實(shí)際卻不可行，影響布線路徑在實(shí)際工程布線中的應(yīng)用。

2.4 算法啟發(fā)函數(shù)的選擇

A*算法常用的啟發(fā)式估價(jià)函數(shù)有曼哈頓距離函數(shù)(MHDF)、對(duì)角線距離函數(shù)(DGDF)和歐幾里得距離函數(shù)(ELDF)。MHDF是指兩節(jié)點(diǎn)南北方向距離與東西方向距離之和，其計(jì)算公式為

HMHDF(n)=|xn-xgoal|+|yn-ygoal|

(3)

式中，(xn，yn)為當(dāng)前節(jié)點(diǎn)n的位置；(xgoal，ygoal)為目標(biāo)節(jié)點(diǎn)的位置。

DGDF是指在算法搜索過(guò)程中選取節(jié)點(diǎn)進(jìn)行搜索時(shí)可以沿對(duì)角線方向進(jìn)行，其計(jì)算公式為

HDGDF(n)=max(|xn-xgoal|，|yn-ygoal|)

(4)

ELDF是指在m維空間中兩位置節(jié)點(diǎn)之間的真實(shí)距離，二維平面中ELDF的計(jì)算公式為

(5)

比較三種啟發(fā)函數(shù)可知，HMHDF(n)的值最大，HDGDF(n)次之，HELDF(n)最小。啟發(fā)函數(shù)的選取會(huì)影響算法搜索路徑的整個(gè)過(guò)程，在使用算法進(jìn)行路徑求解[14-15]的過(guò)程中，標(biāo)準(zhǔn)A*算法允許進(jìn)行對(duì)角線節(jié)點(diǎn)搜索，實(shí)現(xiàn)對(duì)當(dāng)前節(jié)點(diǎn)周圍8個(gè)方向節(jié)點(diǎn)的搜索，擴(kuò)大了搜索空間與范圍。對(duì)角線搜索可以形成對(duì)角線路徑，能夠以最短距離完成線纜路徑的搜索與規(guī)劃，但在遇到多障礙復(fù)雜空間搜索時(shí)，容易形成單一的對(duì)角線路徑。線纜布線的工藝約束[11]要求盡量避免在布線位置處存在鈑金或尖銳棱角，而且需要考慮使用過(guò)程中的振動(dòng)。使用對(duì)角線搜索形成的路徑與障礙物的邊角有接觸，線纜布線完成之后，布線環(huán)境發(fā)生振動(dòng)時(shí)，線纜與障礙物棱角發(fā)生摩擦，將會(huì)加速線纜的磨損失效。本文在算法運(yùn)行時(shí)，只允許算法沿4個(gè)方向進(jìn)行節(jié)點(diǎn)的搜索，不沿對(duì)角線搜索，因此啟發(fā)函數(shù)不考慮DGDF。對(duì)MHDF和ELDF使用圖2、圖3所示的矩形陷阱模型和弧形陷阱模型進(jìn)行比較。

圖2 矩形陷阱模型Fig.2 Rectangle trap model

圖3 弧形陷阱模型Fig.3 Arc trap model

更改啟發(fā)函數(shù)的權(quán)重，算法求解路徑中的父節(jié)點(diǎn)數(shù)、搜索節(jié)點(diǎn)數(shù)、重復(fù)搜索節(jié)點(diǎn)數(shù)、拐點(diǎn)數(shù)見(jiàn)表1、表2。

表1 矩形陷阱模型下兩種距離函數(shù)的比較

表2 弧形陷阱模型下兩種距離函數(shù)的比較

由表1、表2可以看出，對(duì)同一種陷阱模型采用不同的啟發(fā)函數(shù)時(shí)，啟發(fā)函數(shù)的權(quán)重越大，路徑搜索中重復(fù)搜索的節(jié)點(diǎn)越少，路徑產(chǎn)生的拐點(diǎn)越少；權(quán)重為1時(shí)，搜索的節(jié)點(diǎn)和重復(fù)搜索的節(jié)點(diǎn)最少，路徑中的拐點(diǎn)最少。

在矩形陷阱模型中，MHDF路徑中的拐點(diǎn)較ELDF更少；在弧形陷阱模型中，MHDF路徑中的拐點(diǎn)不多于ELDF路徑中的拐點(diǎn)；權(quán)重相同時(shí)，MHDF具有更少的搜索點(diǎn)和重復(fù)搜索點(diǎn)。

在算法求解過(guò)程中，減少搜索點(diǎn)和重復(fù)搜索點(diǎn)有利于算法更快得到最優(yōu)的路徑解。改進(jìn)算法針對(duì)的是線纜的布線路徑問(wèn)題，而減少?gòu)澱埸c(diǎn)有利于保證線纜功能不受損壞，因此，本文將MHDF作為啟發(fā)函數(shù)，啟發(fā)函數(shù)的權(quán)重為1，路徑搜索方式為網(wǎng)格地圖搜索方式。

3 改進(jìn)A*算法

A*算法雖可準(zhǔn)確有效地獲得最短路徑，并保證算法的可執(zhí)行性[6]。但在實(shí)際的工程應(yīng)用中，線纜的敷設(shè)不僅要考慮線纜長(zhǎng)度所代表的經(jīng)濟(jì)性，還要考慮線纜敷設(shè)過(guò)程中對(duì)線纜彎曲半徑、線纜裝配完畢后的整體美觀性、線纜裝配操作空間的要求，因此，通過(guò)以下幾個(gè)方面對(duì)A*算法進(jìn)行改進(jìn)，以更加適應(yīng)實(shí)際工程應(yīng)用中的需求。

3.1 估價(jià)函數(shù)的改進(jìn)

A*算法中的估價(jià)函數(shù)F(n)=G(n)+H(n)只考慮從初始點(diǎn)到目標(biāo)點(diǎn)的最短路徑，在單純的尋徑問(wèn)題中能夠找到最短路徑的精確解，但不適用于線纜布線問(wèn)題的尋徑。線纜的路徑規(guī)劃不僅要求路徑較短，還要求美觀性且與其他電器元件不干涉等，因此，一般情況下的最短路徑并不是最優(yōu)路徑，路徑中過(guò)多的彎折會(huì)增加布線工藝的復(fù)雜度，也會(huì)降低線纜的性能。本文在原有估價(jià)函數(shù)的基礎(chǔ)上，添加K(n)和L(n)兩個(gè)估價(jià)指標(biāo)，共同完成路徑搜索過(guò)程中的代價(jià)估計(jì)。

(1)K(n)表示搜索到當(dāng)前節(jié)點(diǎn)時(shí)路徑中的彎折點(diǎn)情況。線纜可以在布線的時(shí)候彎折，但線纜的彎折有最小彎曲半徑的約束，布線的時(shí)候不可以過(guò)分彎折線纜。整個(gè)線纜的布線路徑中，線纜發(fā)生彎折的次數(shù)越少，線纜彎折引起的損壞或功能失效的可能性越小。因此在算法中對(duì)搜索到當(dāng)前節(jié)點(diǎn)時(shí)路徑中的彎折點(diǎn)的情況進(jìn)行統(tǒng)計(jì)，將其算法的估價(jià)函數(shù)對(duì)路徑節(jié)點(diǎn)進(jìn)行評(píng)估。

在算法中進(jìn)行路徑彎折點(diǎn)情況統(tǒng)計(jì)的具體方法如下：①以當(dāng)前節(jié)點(diǎn)n為初始點(diǎn)，回溯目前所有的路徑節(jié)點(diǎn)并導(dǎo)入路徑節(jié)點(diǎn)數(shù)組ST；②讀取路徑節(jié)點(diǎn)數(shù)組ST中節(jié)點(diǎn)的橫坐標(biāo)數(shù)據(jù)；③數(shù)組中第i個(gè)節(jié)點(diǎn)(i=2，3，…,l-1；l表示數(shù)組中節(jié)點(diǎn)的個(gè)數(shù))開(kāi)始，根據(jù)公式判斷路徑是否發(fā)生彎折；④當(dāng)Va=Xi-Xi-1，Vb=Xi+1-Xi中有且僅有一個(gè)為0時(shí)，路徑節(jié)點(diǎn)STi為彎折點(diǎn)，其中，Xi為數(shù)組ST中節(jié)點(diǎn)i的橫坐標(biāo)；Xi-1為數(shù)組ST中節(jié)點(diǎn)i之前一個(gè)節(jié)點(diǎn)的橫坐標(biāo)；Xi+1為數(shù)組ST中節(jié)點(diǎn)i之后一個(gè)節(jié)點(diǎn)的橫坐標(biāo)；⑤累計(jì)求得當(dāng)前路徑中所有的彎折點(diǎn)的個(gè)數(shù)，用K(n)表示。

(2)L(n)表示是否與障礙物及布線空間的邊界發(fā)生干涉。在一定的布線空間內(nèi)布線，需要考慮線纜路徑與障礙物及布線空間邊界的干涉，即線纜的布線路徑不可超越布線空間邊界，也不能與布線空間中已有的障礙物發(fā)生干涉。用L(n)表示搜索節(jié)點(diǎn)與障礙物及邊界的干涉情況，如果當(dāng)前節(jié)點(diǎn)與布線空間的障礙物及布線空間邊界有干涉，則L(n)=1，否則L(n)=0。

由于G(n)和H(n)都表示距離，而K(n)和L(n)為離散的數(shù)字，為統(tǒng)一算法執(zhí)行過(guò)程中的單位，需要將K(n)和L(n)所代表的數(shù)字信息轉(zhuǎn)換為G(n)和H(n)代表的距離信息。將K(n)和L(n)乘以一個(gè)懲罰系數(shù)，從而將彎折點(diǎn)的情況和干涉約束情況轉(zhuǎn)換為算法中統(tǒng)一的距離形式。最終的估價(jià)函數(shù)計(jì)算統(tǒng)一使用距離進(jìn)行比較，通過(guò)估價(jià)函數(shù)F(n)對(duì)路徑點(diǎn)進(jìn)行取舍。改進(jìn)后的A*算法的估價(jià)函數(shù)為

F(n)=G(n)+H(n)+K(n)+L(n)

(6)

3.2 添加附加值因子

搜索時(shí)，OPEN表中可能會(huì)出現(xiàn)2個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)值相同的情況，為選擇更優(yōu)的路徑節(jié)點(diǎn)，在算法中添加一個(gè)附加值因子來(lái)對(duì)估價(jià)函數(shù)值相同的待選節(jié)點(diǎn)進(jìn)行選擇。布線空間一定的情況下，算法在確定下一個(gè)路徑節(jié)點(diǎn)的搜索過(guò)程中會(huì)出現(xiàn)一部分節(jié)點(diǎn)被重復(fù)搜索的情況，重復(fù)搜索的節(jié)點(diǎn)越多，算法在當(dāng)前節(jié)點(diǎn)的搜索范圍越大。一般情況下，算法搜索的范圍越大，該算法具有越大的可能性避免產(chǎn)生局部最優(yōu)解，因此在算法搜索中遇到2個(gè)節(jié)點(diǎn)具有相同的估價(jià)函數(shù)值時(shí)，引入重復(fù)搜索點(diǎn)數(shù)作為算法節(jié)點(diǎn)選擇的附加值因子。

設(shè)n1、n2為算法OPEN表中估價(jià)函數(shù)值相等的2個(gè)節(jié)點(diǎn)，且此時(shí)的估價(jià)函數(shù)值為OPEN表中所有節(jié)點(diǎn)的最小估價(jià)函數(shù)值。設(shè)M1為算法搜索到節(jié)點(diǎn)n1時(shí)重復(fù)搜索的節(jié)點(diǎn)數(shù)，M2為算法搜索到節(jié)點(diǎn)n2時(shí)重復(fù)搜索的節(jié)點(diǎn)數(shù)，則添加附加值因子之后節(jié)點(diǎn)的估價(jià)函數(shù)值為

F*(ni)=F(ni)+A(ni)

(7)

式中，ni為估價(jià)函數(shù)值相等的節(jié)點(diǎn)，i=1，2；A(ni)為節(jié)點(diǎn)的附加值。

節(jié)點(diǎn)n1、n2對(duì)應(yīng)的附加值分別為

(8)

(9)

當(dāng)M1=M2時(shí)，算法跳出附加值因子的評(píng)價(jià)，不對(duì)原估價(jià)函數(shù)添加附加值。

3.3 添加剛性因子

在柵格中對(duì)線纜的路徑進(jìn)行規(guī)劃，線纜最初的布線路徑采用直角彎折的形式。在連續(xù)的2個(gè)彎折處，由于存在線纜最小彎曲半徑的要求，很容易出現(xiàn)1個(gè)彎折角度無(wú)法實(shí)現(xiàn)的情況，導(dǎo)致1個(gè)彎折半徑不滿足線纜最小彎曲半徑的要求。各種線纜的作用和材質(zhì)不同，其所要求的最小彎曲半徑也不相同，為了避免在彎折過(guò)程中出現(xiàn)線纜最小彎曲半徑不滿足的情況，引入剛性因子[16-18]的概念。

剛性因子能夠保證線纜在某段路徑上的最小長(zhǎng)度，限制線纜路徑規(guī)劃過(guò)程中線纜方向的隨意擴(kuò)散，保證線纜在連續(xù)彎折時(shí)的彎折角度滿足線纜最小彎曲半徑的要求。如圖4所示，線纜在2個(gè)障礙物之間的路徑規(guī)劃需要連續(xù)進(jìn)行彎折，其中，R為線纜的最小彎曲半徑。|PQ|<2R時(shí)，PQ段的距離不足以完成線纜的兩次彎折。圖5中，由于加入了剛性因子，因此|PQ|>2R，2個(gè)彎折角都滿足線纜最小彎曲半徑的要求。圖4、圖5的結(jié)果也表明，帶有剛性因子的線纜路徑不一定是最短的路徑，但卻一定是滿足線纜最小彎曲半徑要求的線纜路徑。

圖4 未加入剛性因子的路徑Fig.4 Path before adding rigidity factor

圖5 加入剛性因子后的路徑Fig.5 Path after adding rigidity factor

為保證線纜彎折時(shí)相鄰的2個(gè)彎折角度都滿足最小彎曲半徑的要求，設(shè)定剛性因子：

(10)

式中，i為路徑中從初始節(jié)點(diǎn)開(kāi)始的彎折點(diǎn)的序號(hào)；r為線纜所允許的最小彎曲半徑。

3.4 考慮路徑的位置因素

線纜布線路徑的位置因素主要是布線時(shí)的操作空間大小，以線纜路徑與其周邊的障礙物之間的間距為評(píng)估內(nèi)容。對(duì)于平面布線空間中兩點(diǎn)之間的布線路徑，從初始點(diǎn)到目標(biāo)點(diǎn)的路徑代價(jià)是相同的，但線纜的布線路徑規(guī)劃需要考慮布線操作空間和最小彎曲半徑。圖6所示的布線空間中，3條路徑最終達(dá)到目標(biāo)點(diǎn)的路徑真實(shí)代價(jià)是相同的，但在路徑避障的時(shí)候采取的策略不相同，導(dǎo)致出現(xiàn)了3種可能的線纜路徑規(guī)劃方案。在圖6所示的4個(gè)彎折點(diǎn)處，3條路徑與障礙物的距離不同，導(dǎo)致線纜在避障彎折時(shí)受障礙物邊角的影響不同，使得線纜在真實(shí)布線過(guò)程中的不同彎折點(diǎn)產(chǎn)生不同的彎曲半徑。

圖6 不同布線路徑Fig.6 Different routing paths

圖7 最小彎曲半徑證明Fig.7 Proof of minimum bending radius

3.5 算法的實(shí)現(xiàn)

改進(jìn)A*算法依然存在OPEN表和CLOSE表，它們分別存放已生成但是還未考察過(guò)的點(diǎn)和已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)。改進(jìn)A*算法流程如圖8所示。

對(duì)比圖1、圖8可知，改進(jìn)A*算法在進(jìn)行尋徑時(shí)與A*算法有以下的不同：①A*算法的F值計(jì)算只考慮G(n)和H(n)，改進(jìn)A*算法添加K(n)和L(n)，預(yù)先將干涉因素考慮進(jìn)算法，路徑不需要再經(jīng)過(guò)干涉檢驗(yàn);②在擴(kuò)張當(dāng)前節(jié)點(diǎn)的鄰居節(jié)點(diǎn)時(shí)考慮剛性因子，舍棄不符合剛性因子條件的節(jié)點(diǎn)，減小了算法中節(jié)點(diǎn)的搜索范圍;③2個(gè)節(jié)點(diǎn)的F值相同時(shí)，通過(guò)附加值因子對(duì)節(jié)點(diǎn)進(jìn)行取舍，使路徑中的每個(gè)節(jié)點(diǎn)均為當(dāng)前條件下的最優(yōu)節(jié)點(diǎn)，進(jìn)而保證整個(gè)路徑的最優(yōu)。

4 應(yīng)用實(shí)例

改進(jìn)A*算法的應(yīng)用前提是布線空間得到了一定的處理。布線空間的處理結(jié)果如下：①布線空間內(nèi)的設(shè)備零部件均為固定件，沒(méi)有相對(duì)位移，也不存在相互干涉；②在誤差允許的范圍內(nèi)，線纜路徑規(guī)劃的結(jié)果將會(huì)以線纜中心線的形式在空間中進(jìn)行布線，仿真結(jié)果以線纜設(shè)定的真實(shí)直徑顯示。應(yīng)盡量避免線纜的懸空布置，減少因?yàn)槟p和振動(dòng)造成的線纜功能失效或壽命縮短；考慮到線纜及周邊剛性件的維修便捷性，應(yīng)該盡量減少線纜對(duì)布線空間內(nèi)其他組件的依附，以便在組件故障時(shí)及時(shí)更換?；谝陨系牟季€準(zhǔn)則，線纜必須盡量固定在基板上。

圖8 改進(jìn)A*算法流程圖Fig.8 Flow chart of improved A* algorithm

4.1 算法的仿真結(jié)果

使用柵格法搭建一個(gè)障礙模型，采用改進(jìn)A*算法進(jìn)行線纜路徑規(guī)劃仿真[19]。本文使用直角坐標(biāo)系法和賦值法相結(jié)合的方式進(jìn)行柵格的標(biāo)識(shí)。選取柵格窗口的左下角頂點(diǎn)為坐標(biāo)系原點(diǎn)，定義坐標(biāo)系中水平向右為X軸正方向，豎直向上為Y軸正方向，柵格單元以坐標(biāo)U(x,y)為唯一標(biāo)識(shí)；V(x,y)表示該柵格單元中的障礙物的情況：

(11)

虛擬障礙空間柵格單元中，起始節(jié)點(diǎn)用S表示，目標(biāo)節(jié)點(diǎn)用G表示，將空間障礙信息以上述方法轉(zhuǎn)化為二維數(shù)組，調(diào)用算法進(jìn)行路徑搜索，A*算法的路徑規(guī)劃結(jié)果見(jiàn)圖9，改進(jìn)A*算法求解路徑的結(jié)果見(jiàn)圖10。圖9、圖10所示算法的布線結(jié)果見(jiàn)表3。

圖9 A*算法的路徑規(guī)劃結(jié)果Fig.9 Path planning results of A* algorithm

圖10 改進(jìn)A*算法的路徑規(guī)劃結(jié)果Fig.10 Path planning results of improved A* algorithm

由表3及圖9、圖10可知，改進(jìn)A*算法的父節(jié)點(diǎn)比A*算法的父節(jié)點(diǎn)多，但改進(jìn)A*算法在搜索節(jié)點(diǎn)數(shù)、重復(fù)搜索節(jié)點(diǎn)數(shù)和拐點(diǎn)數(shù)均有優(yōu)勢(shì)。由圖9、圖10可知，改進(jìn)A*算法在連續(xù)彎折處的2個(gè)拐點(diǎn)之間的距離大于A*算法中的距離，在連續(xù)彎折時(shí)滿足線纜最小彎曲半徑的要求，且布線路徑基本處于障礙物中間，有利于實(shí)際布線的操作。

4.2 算法的實(shí)際應(yīng)用

基于改進(jìn)A*算法進(jìn)行路徑搜索，在三維環(huán)境下進(jìn)行線纜路徑規(guī)劃。在三維環(huán)境中創(chuàng)建路徑規(guī)劃空間時(shí)，不考慮自由平面的情況，只考慮在模型平面內(nèi)布線[20-21]。實(shí)際的線纜路徑規(guī)劃中，通常以機(jī)電設(shè)備布線空間的俯視圖視角對(duì)所布線纜的路徑進(jìn)行規(guī)劃。對(duì)布線空間中的障礙物使用最小包圍盒法[22]，將布線空間中的障礙物轉(zhuǎn)換為規(guī)則形狀，選定底面作為布線的參考平面，以俯視圖的形式將障礙物的信息投影到底面，使用前述的柵格法處理空間投影面，將投影平面變換為二維數(shù)組的形式，調(diào)用改進(jìn)A*算法，根據(jù)算法的路徑規(guī)劃結(jié)果在布線參考平面上創(chuàng)建線纜的布線路徑。由于線纜路徑中的所有彎折點(diǎn)均滿足線纜最小彎曲半徑的要求，因此將線纜路徑中的彎折點(diǎn)圓滑為不小于線纜的最小彎曲半徑的圓弧，同時(shí)保證布線的美觀性和整齊性。

(1)在Creo2.0中建立機(jī)柜簡(jiǎn)化模型，通過(guò)改進(jìn)A*算法求得投影平面內(nèi)線纜的最優(yōu)布線路徑；使用Creo2.0的布線功能，將求解出的布線敷設(shè)到模型中。圖11所示為A*算法所敷設(shè)的線纜路徑，圖12所示為改進(jìn)A*算法敷設(shè)的線纜路徑。

圖11 A*算法在機(jī)柜模型中的布線結(jié)果Fig.11 Routing results of A* algorithm in cabinet

圖12 改進(jìn)A*算法在機(jī)柜模型中的布線結(jié)果Fig.12 Routing results of improved A* algorithm in cabinet

根據(jù)圖11、圖12所示的布線結(jié)果，將線纜依次編號(hào)為1～9，在Creo2.0中對(duì)兩種布線路徑進(jìn)行對(duì)比，結(jié)果見(jiàn)表4。

表4 兩種布線結(jié)果

由表4及圖11、圖12可知，改進(jìn)A*算法解決了A*算法不能有效避開(kāi)障礙物的缺點(diǎn)，減少了線纜路徑中的彎折；由于路徑規(guī)劃和實(shí)際的布線不同，改進(jìn)A*算法規(guī)劃的路徑在實(shí)際布線中更短，具有更大的經(jīng)濟(jì)優(yōu)勢(shì)，也避免了A*算法路徑規(guī)劃中線纜緊貼障礙物而帶來(lái)的線纜或障礙物故障時(shí)不便更換的問(wèn)題。對(duì)比圖11、圖12可知，改進(jìn)A*算法規(guī)劃的路徑布線能給予布線人員更大的操作空間，在避開(kāi)障礙物的同時(shí)，也避免了線纜連續(xù)彎折后線纜最小彎曲半徑不滿足的情況。

(2)以某軍工企業(yè)產(chǎn)品的殼體模型內(nèi)部布線為例，分別調(diào)用A*算法和改進(jìn)A*算法進(jìn)行路徑規(guī)劃，規(guī)劃結(jié)果分別見(jiàn)圖13、圖14。根據(jù)圖13、圖14所示的線纜布線結(jié)果，將線纜從左上到右下依次編號(hào)為1～4，利用Creo2.0對(duì)線纜路徑的相關(guān)數(shù)據(jù)進(jìn)行統(tǒng)計(jì)，兩種線纜布線結(jié)果的對(duì)比見(jiàn)表5。

圖13 A*算法在產(chǎn)品模型中的布線結(jié)果Fig.13 Routing results of A* algorithm in product model

圖14 改進(jìn)A*算法在產(chǎn)品模型中的布線結(jié)果Fig.14 Routing results of improved A*algorithm in product model

表5 產(chǎn)品模型中兩種布線路徑結(jié)果

由表5及圖13、圖14可知，改進(jìn)A*算法能有效減少線纜路徑中的彎折點(diǎn)，顯著減少布線過(guò)程中需要確定的位置點(diǎn)；根據(jù)2種布線結(jié)果可知，改進(jìn)A*算法線纜布線整齊美觀，同類型線纜盡量集中在一起，方便在線纜集中段對(duì)線纜進(jìn)行歸類和整理，也為布線提供了足夠的操作空間。但改進(jìn)A*算法部分線纜的總長(zhǎng)度大于A*算法的線纜總長(zhǎng)度，在經(jīng)濟(jì)性上具有一定的局限性。

5 結(jié)論

(1)本文提出了一種基于改進(jìn)A*算法的線纜路徑規(guī)劃設(shè)計(jì)方法，在算法尋徑時(shí)考慮已搜索完成的路徑情況和布線空間環(huán)境情況，避免了與布線空間內(nèi)障礙物和空間邊界的干涉；加入附加值因子，使得算法更加迅速有效地取舍F值相同節(jié)點(diǎn)；算法考慮實(shí)際布線中的剛性因子約束和線纜路徑的位置因素，保證了所求解的線纜路徑有足夠的彎折半徑和操作空間，算法求得的路徑滿足路徑規(guī)劃數(shù)學(xué)模型的要求。

(2)根據(jù)對(duì)A*算法的改進(jìn)，在二維柵格障礙空間中進(jìn)行路徑規(guī)劃仿真，在三維布線空間模型中進(jìn)行布線仿真。實(shí)驗(yàn)的結(jié)果表明，改進(jìn)A*算法能找到一條滿足條件的最優(yōu)路徑。

(3)本文所提方法只涉及單一種類的線纜在復(fù)雜機(jī)電產(chǎn)品中的布線，實(shí)際布線的多種線纜布線和交叉布線未考慮，也未考慮線纜的捆扎和分線，這些內(nèi)容在今后進(jìn)一步研究。