程倩

摘要：

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

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

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

文章編號(hào)：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ù)雜，線纜作為能量和信號(hào)的傳輸媒介，其布設(shè)也越來越復(fù)雜。但是線纜在機(jī)電設(shè)計(jì)中呈現(xiàn)“傻大笨粗”形象，說明線纜布設(shè)技術(shù)的發(fā)展沒有受到應(yīng)有的重視，從而使其發(fā)展遠(yuǎn)遠(yuǎn)落后于機(jī)械加工、軟件和硬件的發(fā)展。

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

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

1.1 布線工藝約束

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 代價(jià)函數(shù)設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 環(huán)境建模

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

4.2 算法驗(yàn)證

本文對(duì)算法的改進(jìn)包括兩個(gè)方面：一是將算法擴(kuò)展為三維，二是引入了工藝約束權(quán)值value。因此，對(duì)算法的驗(yàn)證就是通過改變value值來驗(yàn)證不同工藝約束對(duì)算法的影響。算法中用到的參數(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組實(shí)驗(yàn)，分別為：

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

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

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

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

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

5 結(jié)論

通過以上分析可得以下結(jié)論：1）本文將A*算法擴(kuò)展到三維空間，可以實(shí)現(xiàn)三維空間的路徑規(guī)劃；2）將工藝約束權(quán)值引入到代價(jià)函數(shù)中，得到了多工藝約束下的路徑最優(yōu)規(guī)劃，實(shí)現(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)誠(chéng)， 莊奕琪， 耿阿囡. 基于粒子群優(yōu)化算法的集成電路無(wú)網(wǎng)格布線[J]. 西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2007， 34（1）：3437.[

5]

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

6]

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

7]

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

8]

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

9]

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

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