程倩

摘要：

為了實現(xiàn)多約束條件下機(jī)電產(chǎn)品線纜布設(shè)的智能化和自主化，提出了改進(jìn)A*算法的機(jī)電產(chǎn)品線纜布設(shè)方法。分析了機(jī)電產(chǎn)品布設(shè)線纜時的約束條件，對機(jī)電產(chǎn)品建立了三維點云模型；介紹了傳統(tǒng)A*算法原理，為了適用于三維機(jī)電產(chǎn)品模型，將此算法擴(kuò)展到三維空間；劃定工藝約束影響區(qū)域并賦予權(quán)值，節(jié)點權(quán)值大小代表此點作為路徑的工藝優(yōu)劣；將工藝約束權(quán)值引入到代價函數(shù)，使算法能夠兼顧路徑最優(yōu)和工藝約束；仿真實驗表明，改進(jìn)A*算法能夠在考慮多約束條件下，實現(xiàn)線纜布設(shè)的最優(yōu)化，實現(xiàn)了機(jī)電產(chǎn)品線纜布設(shè)的智能化和自主化。

關(guān)鍵詞：機(jī)電產(chǎn)品；線纜布設(shè)；改進(jìn)A*算法；工藝約束權(quán)值

中圖分類號：TP391、TN958.92 文獻(xiàn)標(biāo)志碼：A

文章編號：2095-5383（2018）02-0025-05

Cable Laying of Mechanical and Electrical Products based

on Improved A* Algorithm

CHENG Qian

（Business and Electronic Information Department， Tongcheng Normal College， Tongcheng 231400， China）

Abstract：

In order to realize the intelligence and automation of mechanical and electrical products cable laying under multiple constraints， the cable laying method of mechanical and electrical products based on improved A* algorithm was proposed. The constraints of mechanical and electrical products cable laying were analyzed， and 3dimentional point cloud model of mechanical and electrical products was built. Traditional A* algorithm was introduced， and this algorithm was expanded to 3dimentional space. Influence area of technology constraints was delimited and the weight of point was given. The weight size of point respects technology quantity as path. The weight is introduced to cost function， so that the algorithm can balance the optimal path and technology constraints. By simulation trials， the improved A* algorithm can find the optimal path of cable laying with multiple constraints and realize intelligent and automation of mechanical and electrical products cable laying.

Keywords：

mechanical and electrical products； cable laying； improved A* algorithm； technology constraints weight

隨著技術(shù)的發(fā)展和高新技術(shù)的使用，機(jī)電產(chǎn)品越來越復(fù)雜，線纜作為能量和信號的傳輸媒介，其布設(shè)也越來越復(fù)雜。但是線纜在機(jī)電設(shè)計中呈現(xiàn)“傻大笨粗”形象，說明線纜布設(shè)技術(shù)的發(fā)展沒有受到應(yīng)有的重視，從而使其發(fā)展遠(yuǎn)遠(yuǎn)落后于機(jī)械加工、軟件和硬件的發(fā)展。

線纜布設(shè)問題的研究早期主要集中在理論上，學(xué)者包括Koch等[1]、Mascagni[2]、Abbasi等[3]。近年來的研究重點開始轉(zhuǎn)向?qū)嶋H應(yīng)用，黃訓(xùn)誠等[4-5]將粒子群算法和蟻群算法應(yīng)用在布線設(shè)計上取得了較好效果；付宜利等[6]使用粒子群算法實現(xiàn)了單根管道的自動布設(shè)；陳世明等[7]使用粒子群算法實現(xiàn)了三維有障礙空間的點對點最優(yōu)規(guī)劃。但是這些單一路徑規(guī)劃或布設(shè)問題，無法解決線纜捆扎結(jié)構(gòu)問題，因此本文在考慮線纜布設(shè)時避免懸空、避開熱源和電磁干擾等多約束條件下，對機(jī)電產(chǎn)品線纜布設(shè)進(jìn)行優(yōu)化，將傳統(tǒng)A*算法擴(kuò)展到三維空間，提出引入工藝約束權(quán)值的代價函數(shù)，最終得到了多約束條件下的路徑最優(yōu)規(guī)劃，實現(xiàn)線纜布設(shè)的智能化和自主化。

1 布線環(huán)境空間建模

1.1 布線工藝約束

在機(jī)電產(chǎn)品線纜的實際布設(shè)中，要考慮很多工藝約束問題，并將這些約束條件在環(huán)境建?；蛩惴▽崿F(xiàn)中，從而使線纜布設(shè)方法真正達(dá)到實用要求。典型的工藝約束[8]包括以下6個方面：1）線纜盡量貼近實體壁，盡量避免懸空，便于捆扎；2）線纜的路徑盡量避開熱源、電磁輻射源、避免燒壞和干擾；3）路徑盡量避開鈑金和尖銳角，避免割壞線纜；4）路徑寬度必須大于線纜直徑，才有足夠空間容納線纜；5）線纜束過孔時要加保護(hù)套保護(hù)線纜；6）考慮振動等防止線纜脫落。

不同約束條件針對不同的零件，比如熱源是指電池、加熱絲等發(fā)熱部件，電磁輻射源指電磁計等。本文將這些可能影響線纜布設(shè)問題的部件稱為工藝結(jié)構(gòu)，在環(huán)境建模時，對不同的工藝結(jié)構(gòu)賦予不同屬性值進(jìn)行區(qū)分。

1.2 布線環(huán)境建模

本文使用點云法對線纜布設(shè)的三維空間進(jìn)行建模，將線纜布設(shè)空間離散化。對環(huán)境中的點云分為一般空間點、無工藝障礙點、熱源點、電磁輻射點、銳邊等，其中一般空間點是指空間位置，無工藝障礙點指機(jī)電產(chǎn)品的一般性結(jié)構(gòu)件，熱源點、電磁輻射點、銳邊則是布線時盡量避開的工藝障礙點。為了使算法能夠區(qū)分這些點云，依據(jù)點云位置特點賦不同的屬性值，本文中將一般空間點賦值為0，無工藝障礙點為3，熱源點為4，電磁輻射點為5，銳邊為6。

記機(jī)電產(chǎn)品三維模型的包絡(luò)長寬高分別為lx×ly×lz，X軸上點云數(shù)量為nx，則點云間距為a=lx/nx。在機(jī)電產(chǎn)品三維模型中陣列以a為間距、以φ為直徑的圓球。要求路徑寬度必須大于電纜直徑，因此點云間距a不小于線纜束直徑。然后將整個三維模型按照1：a進(jìn)行縮放，得到圓球之間距離1的三維模型。以圓球球心所在位置為標(biāo)準(zhǔn)進(jìn)行屬性賦值，在此需要強(qiáng)調(diào)的是一個圓球未必只有一個屬性值，若圓球所在位置既是熱源也是電磁輻射源，則需要賦兩個屬性值。

以圖1所示的機(jī)電模型為例，圖中灰色部分表示普通工藝結(jié)構(gòu)，紅色部分為熱源，黃色部分為電磁源。

2 傳統(tǒng)A*算法

A*算法[9-10]是融合了Dijkstra算法和最佳優(yōu)化算法優(yōu)勢的智能算法，它既有Dijkstra算法的貪心性，也具有最佳優(yōu)化算法的啟發(fā)性，也就是說此算法兼顧了搜索時間和搜索空間。

A*算法的原理是在周圍相鄰的點云中，選擇估價函數(shù)最小的節(jié)點作為下一步路徑，若周圍節(jié)點中估價函數(shù)最小值節(jié)點不止一個，則選擇最近一次搜索到的節(jié)點。A*算法的關(guān)鍵在于估價函數(shù)的設(shè)計，傳統(tǒng)A*算法的節(jié)點估價函數(shù)為

f（n）=g（n）+h（n） （1）

式中：g（n）為從起始點S到當(dāng)前節(jié)點n的最小代價；h（n）為從當(dāng)前節(jié)點n到目標(biāo)點T的最佳路徑代價估計； f（n）為對當(dāng)前節(jié)點n的估價值。其中h（n）的設(shè)計對算法性能影響最大，記當(dāng)前節(jié)點n到目標(biāo)點T的真實最小代價為h（n），當(dāng)h（n）≤h（n）時，就能保證算法找到最優(yōu)解；但是為了保證算法求解效率，要求h（n）不能比h（n）小太多，所以h（n）的設(shè)計是A*算法的關(guān)鍵。

在A*算法中用到2個集合，記為Open集合和Close集合，其中Open集合存儲待計算的節(jié)點信息，Close集合用于存儲被選擇的節(jié)點信息。在點云環(huán)境中使用A*算法，首先選擇當(dāng)前節(jié)點的相鄰節(jié)點存入到Open集合中，計算每個節(jié)點的估價值并比較，選擇估價值最小的節(jié)點作為下一步節(jié)點，將此節(jié)點存入到Close集合的同時釋放Open集合，重復(fù)此過程就完成了線纜路線選擇，最后從Close集合中導(dǎo)出線纜路徑。

3 改進(jìn)A*算法的線纜布設(shè)方法

3.1 二維A*算法擴(kuò)展為三維

本文研究的是機(jī)電產(chǎn)品線纜布設(shè)問題，機(jī)電產(chǎn)品模型為三維模型，線纜布設(shè)環(huán)境為三維點云環(huán)境，而傳統(tǒng)的A*算法只適用于二維平面路徑規(guī)劃問題，因此首先將A*算法擴(kuò)展到三維空間。由于環(huán)境空間由二維變?yōu)槿S，所以當(dāng)前節(jié)點的相鄰節(jié)點數(shù)由8個增加為26個，如圖3所示。從圖3可以看出，相鄰節(jié)點距離不同，同軸節(jié)點距離為1.0，平面對角節(jié)點距離為1.4，空間對角節(jié)點距離為1.7。

3.2 代價函數(shù)設(shè)計

本文對機(jī)電產(chǎn)品線纜布設(shè)問題，在滿足工藝約束條件下，以線纜距離最短為優(yōu)化目標(biāo)，因此代價函數(shù)選擇一種距離計算方法。當(dāng)前距離計算方法有曼哈頓距離、對角線距離、歐幾里得距離等。

上文中提到h（n）對算法性能影響很大，h（n）數(shù)值大時會提高算法搜素效率，但是此時算法搜索范圍小，很容易陷入如圖4所示的U型陷阱。因此h（n）的選擇在搜索效率和搜索范圍上是矛盾的。

3種距離算法中，歐幾里得距離最小，可以有效避免U型陷阱，但是算法效率最低；曼哈頓距離最大，但是可以通過改變系數(shù)k的數(shù)值進(jìn)行調(diào)節(jié)。當(dāng)環(huán)境復(fù)雜且時間要求不高時，將系數(shù)k設(shè)置大一些，以犧牲時間來求取最優(yōu)路徑，當(dāng)環(huán)境簡單時將系數(shù)k設(shè)置小一些就可以得到最優(yōu)路徑。因此本文代價函數(shù)采用曼哈頓距離乘以系數(shù)k，依據(jù)環(huán)境復(fù)雜度調(diào)節(jié)系數(shù)k大小，就能夠兼顧算法的搜索空間和搜索效率。

記線纜路徑當(dāng)前節(jié)點為m，周圍待搜索節(jié)點為n個，則代價函數(shù)f（n）設(shè)置為：

式中：g（m）為起點到當(dāng)前節(jié)點m的代價值；（xm，ym，zm）為當(dāng)前節(jié)點三維坐標(biāo)；（xn，yn，zn）為待搜索節(jié)點三維坐標(biāo)；（xgoal，ygoal，zgoal）為目標(biāo)點三維坐標(biāo)，為曼哈頓距離；k為權(quán)系數(shù)。

3.3 引入工藝約束權(quán)值代價函數(shù)

本文引入工藝約束權(quán)值的代價函數(shù)，工藝約束權(quán)值用于表征節(jié)點作為路徑的工藝優(yōu)劣，工藝約束加權(quán)規(guī)則如圖5所示。

圖5中綠色點云為空間點，灰色區(qū)域為普通障礙點，紅色為熱源，黃色為電磁輻射源。首先對所有空間點賦初始權(quán)值value=b，普通障礙點的權(quán)值影響范圍為以物體邊緣為圓心、以r1為半徑的區(qū)域，此區(qū)域空間點權(quán)值在初始權(quán)值上疊加b1，熱源、電磁源權(quán)值范圍與此一致，分別疊加權(quán)值b2、b3，若空間某點在多個權(quán)值影響范圍內(nèi)則將這些權(quán)值相加，即value=b+∑li=1bi，式中l(wèi)為節(jié)點受權(quán)值影響數(shù)量。若節(jié)點的工藝特征適于布線則權(quán)值取為負(fù)數(shù)，若不適于布線則取為正數(shù)，因此節(jié)點越適于布線則其綜合權(quán)值越小。權(quán)值大小可以調(diào)整工藝約束的大小，比如在雷達(dá)等強(qiáng)電磁環(huán)境中，就可以增大電磁源權(quán)值b3，表示主要考慮避開電磁源這一約束。

經(jīng)以上分析，本文引入工藝約束權(quán)值的代價函數(shù)為：

式中；wA為A*算法的公益性約束。通過調(diào)整wA與k值，就可以調(diào)整距離優(yōu)化與工藝約束對算法的影響程度。

4 仿真實驗

4.1 環(huán)境建模

給出如圖6a所示機(jī)電產(chǎn)品三維模型，三維結(jié)構(gòu)包絡(luò)體積為30×30×15，線纜最大直徑為1。建模所用參數(shù)為a=1.5、φ=0.1，得到其點云模型如圖6b所示。建模后起點坐標(biāo)為（10，2，3），終點坐標(biāo)為（10，19，5），縮放后得到20×20×10的三維點云模型。

4.2 算法驗證

本文對算法的改進(jìn)包括兩個方面：一是將算法擴(kuò)展為三維，二是引入了工藝約束權(quán)值value。因此，對算法的驗證就是通過改變value值來驗證不同工藝約束對算法的影響。算法中用到的參數(shù)為k=wA=0.5，初始權(quán)值b=0，貼壁工藝權(quán)值b1=-5、r1=1，熱源工藝權(quán)值b2=3、r2=2，電磁源工藝權(quán)值b3=3、r3=2。

本文共進(jìn)行了4組實驗，分別為：

實驗1：不考慮工藝約束，以線纜路徑最短為優(yōu)化目標(biāo)；

實驗2：只考慮貼壁約束，以線纜路徑最短為優(yōu)化目標(biāo)；

實驗3：考慮貼壁和避開熱源，以線纜路徑最短為目標(biāo)；

實驗4：考慮貼壁、避開熱源和電磁源，以線纜路徑最短為優(yōu)化目標(biāo)。

圖7中，綠色節(jié)點表示貼近實體壁的節(jié)點，是布線工藝性較優(yōu)的點，紅色是考慮熱源和電磁源而權(quán)值較高點。實驗1不考慮任何工藝約束，因此得到的路徑最短，但是從圖7a中可以看出線路懸空部分較多，不利于捆扎，若機(jī)電產(chǎn)品震動大時線纜容易散落；實驗2考慮了貼壁約束，使線纜優(yōu)先選擇實體壁附近的路徑，得到此約束下的最優(yōu)路徑，較實現(xiàn)1犧牲了0.7個單位長度，從圖7b可以看出線纜貼壁較好，利于捆扎和固定；實驗3考慮貼壁和避開熱源約束，得到了一條繞行結(jié)構(gòu)B上表面和結(jié)構(gòu)A內(nèi)壁的路徑，很好的避開了熱源，較實驗2犧牲了0.1個單位距離；實驗4同時考慮貼壁、遠(yuǎn)離熱源和電磁源的約束，能夠完全避開圖7中的紅色點云空間，得到了一條繞行結(jié)構(gòu)A外表面的路徑，具有最優(yōu)工藝性，實現(xiàn)了多約束條件下的路徑最優(yōu)。

5 結(jié)論

通過以上分析可得以下結(jié)論：1）本文將A*算法擴(kuò)展到三維空間，可以實現(xiàn)三維空間的路徑規(guī)劃；2）將工藝約束權(quán)值引入到代價函數(shù)中，得到了多工藝約束下的路徑最優(yōu)規(guī)劃，實現(xiàn)了機(jī)電產(chǎn)品線纜布設(shè)的智能化和自主化。

參考文獻(xiàn)：

[1]KOCH C， POGGIO T. A simple algorithm for solving the cable equation in dendritic trees of arbitrary geometry.[J]. Journal of Neuroscience Methods， 1985， 12（4）：303315.[

2]

MASCAGNI M. A parallelizing algorithm for computing solutions to arbitrarily branched cable neuron models[J]. Journal of Neuroscience Methods， 1991， 36（1）：105114.[

3]

ABBASI V， HEYDARI H， FAGHIHI F. Heuristic mathematical formulations and comprehensive algorithm for optimal decision making for power system cabling[J]. Scientia Iranica， 2012， 19（3）：707720.[

4]

黃訓(xùn)誠， 莊奕琪， 耿阿囡. 基于粒子群優(yōu)化算法的集成電路無網(wǎng)格布線[J]. 西安電子科技大學(xué)學(xué)報（自然科學(xué)版）， 2007， 34（1）：3437.[

5]

黃訓(xùn)誠. 基于蟻群算法的超大規(guī)模集成電路布線研究[D]. 西安：西安電子科技大學(xué)， 2007.[

6]

付宜利， 封海波， 孫建勛，等. 機(jī)電產(chǎn)品管路自動敷設(shè)的粒子群算法[J]. 機(jī)械工程學(xué)報， 2007， 43（11）：194199.[

7]

陳世明， 謝竟， 陳文棟，等. 基于HPSO算法的三維空間路徑規(guī)劃[J]. 華中科技大學(xué)學(xué)報（自然科學(xué)版）， 2013， 41（2）：109113.[

8]

劉瀟. 復(fù)雜產(chǎn)品中的線纜自動布局設(shè)計技術(shù)研究[D]. 北京：北京理工大學(xué)， 2015.[

9]

張前哨. 基于A*算法的地圖尋徑的研究[D]. 武漢：武漢科技大學(xué)， 2005.[10]

秦玉鑫， 王紅旗， 杜翠杰. 基于雙層A*算法的移動機(jī)器人路徑規(guī)劃[J]. 制造業(yè)自動化， 2014（24）：2125.