基于改進A*算法的管路自動敷設(shè)研究

陳 巖,李 濤,印明昂

(1.中國兵器科學(xué)研究院, 北京 100089; 2.東北大學(xué) 機械工程與自動化學(xué)院, 沈陽 110819)

在裝甲車輛發(fā)動機設(shè)計中存在大量的管路敷設(shè)設(shè)計問題，管路自動敷設(shè)是提高裝甲車輛發(fā)動機管路敷設(shè)水平、降低敷設(shè)成本的重要途徑，對提高產(chǎn)品設(shè)計質(zhì)量、縮短制造周期有著重要的意義[1-3]。

A*算法具有可納性、最優(yōu)性、應(yīng)用簡便、快捷等優(yōu)點，廣泛應(yīng)用在電腦游戲、機器人路徑規(guī)劃、無人機航跡規(guī)劃等領(lǐng)域。管路自動布局設(shè)計的本質(zhì)是路徑規(guī)劃問題，路徑規(guī)劃不僅要求路徑可行，還應(yīng)滿足該領(lǐng)域的多項工程約束(如可制造性規(guī)則、可裝配性規(guī)則等)以尋求路徑的最優(yōu)化[4-5]。由于A*算法起源于二維平面，且以估價距離作為啟發(fā)式信息，針對三維環(huán)境下管路自動布局設(shè)計這一具體問題，應(yīng)考慮長度較短、彎曲加工的代價較少、安裝方便和安全性等因素，因此需要對算法進行改進。管路一般采用基于控制點的表示方法，通過A*算法得到的路徑由一系列分布在不同折線段上的點構(gòu)成。路徑點數(shù)目多，難以滿足管路的制造要求，因此需要進一步優(yōu)化[6-10]。盡管國內(nèi)外學(xué)者提出了一系列管路自動布局算法[11-14]，并取得了一些成果，但工程實際中，管路布局還需要考慮整體布局的可行性和最優(yōu)性，特別是在裝甲車輛發(fā)動機中存在的布局空間狹小、零部件眾多的條件下，管路與管路之間的交叉性、耦合性使得管路布局的先后順序?qū)Σ季纸Y(jié)果影響較大，如何使整個管路系統(tǒng)的布局達到最優(yōu)是目前工程中亟待解決的問題。

1 基本A*算法

A*算法以估價函數(shù)獲得各節(jié)點的擴展代價，并從中選擇最小代價點進行擴展。節(jié)點的估價函數(shù)為：

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

(1)

式(1)中，g(n)表示從初始節(jié)點S到節(jié)點n的最小代價的估計；h(n)表示從節(jié)點n到目標節(jié)點T的最佳路徑的估計代價。A*算法執(zhí)行過程中也用到Open表和Closed表，其中Open表用于存放剛生成的節(jié)點，Closed表用于存放將要擴展或者已經(jīng)擴展的節(jié)點。算法執(zhí)行步驟為：

步驟1 開始，將起點添加至Open表中。

步驟2 判斷Open表是否為空，若不為空，則轉(zhuǎn)步驟3；否則路徑搜索失敗。

步驟3 考察Open表中具有最小f值的節(jié)點n，判斷n是否為目標節(jié)點，若是則路徑搜索成功；否則，轉(zhuǎn)步驟4。

步驟4 生成當前節(jié)點n的相鄰可行節(jié)點n′。若n′為新，則加入Open表中，并設(shè)其父節(jié)點為n，轉(zhuǎn)步驟2；若n′已在Closed表中，不作任何操作，也轉(zhuǎn)步驟2。若n′已在Open表中，則轉(zhuǎn)步驟5。

2 管路自動布局中的改進A*算法

2.1 管路布局空間柵格化模型

裝甲車輛發(fā)動機由于管路種類繁多、形狀尺寸多樣，使得空間不規(guī)則，給管路的布局設(shè)計帶來了限制。本文采用柵格法進行建模，柵格法的實質(zhì)是將整個布局空間劃分為一個三維點陣，它能對布局空間進行精確的表示。為了節(jié)約計算機資源，提高算法效率，對于確定的起始點S和終止點T，將管路路徑的求解空間圍繞起終點進行構(gòu)造，避免對全空間進行柵格劃分。本文采用了正方體幾何模型對求解空間進行表達。具體步驟為：

1) 獲取以S(xs,ys,zs)和T(xt,yt,zt)為對角頂點的正方體ABCD-EFGH的幾何中心O，并計算O到S或S的距離L；

2) 擴展S和S得到H′和B′，其坐標為(xs-λL,ys-λL,zs-λL)，(xt+λL,yt+λL,zt+λL),λ≥1)；

3) 新的正方體求解空間為A′B′C′D′-E′F′G′H′，H′和B′為其對角頂點，如圖1(a)所示，顯然，新構(gòu)建的正方體邊長為λL。為滿足管路與設(shè)備間的最小間距dmin要求，設(shè)管路的直徑為D，則柵格的粒度2a≥D+2dmin，管路布局空間可以劃分為[λL/a]×[λL/a]×[λL/a]多個大小相同的正方體，[ ]表示取不大于方括號內(nèi)的最大整數(shù)，如圖1(b)所示。λ是為了限定算法的求解空間，減少無用節(jié)點的擴展，當該空間內(nèi)無法找到路徑時，可以考慮擴大求解空間，如含障礙陷阱的路徑求解，λ可取1.5～3.0。

在完成了管路的路徑搜索空間的柵格化模型后，記錄柵格節(jié)點的信息，主要包含幾何信息、歸屬信息及代價信息這三類，如表1所示。最后采用A*算法完成管路的路徑搜索。

2.2 基于方向引導(dǎo)的啟發(fā)式函數(shù)

管路的布局設(shè)計不僅要求長度盡量短，還應(yīng)減少彎頭數(shù)目。為了能優(yōu)先選擇最優(yōu)路徑上的節(jié)點，本文采用結(jié)合距離代價、折彎代價和方向引導(dǎo)的啟發(fā)式函數(shù)，如式(2)所示。

(2)

式(2)中，ln為節(jié)點n到終點T的距離；N為起點S到節(jié)點n的折彎數(shù)目；θn為父節(jié)點n-1和節(jié)點n(n>1)的連線與節(jié)點n和終點T連線的夾角；c為單個柵格長度代價，與柵格粒度a相同；W1為折彎與長度代價的轉(zhuǎn)換比；W2為角度與長度代價的轉(zhuǎn)換比，由實驗確定。W1與W2決定了搜索的速度與質(zhì)量，W1取值越大，搜索范圍也越大，相應(yīng)的計算時間也就越長。W2取值越大，搜索范圍就越集中。

表1 節(jié)點信息組成

2.3 多約束條件下的改進方法

管路布局過程中存在各類約束，其中，安全性約束和貼壁約束是常見的約束形式。基本A*算法并不能直接對該類約束識別，也無法根據(jù)約束自動調(diào)整路徑的搜索。為滿足多約束條件下管路自動布局，本文將對算法作針對性改進。

1) 安全性約束下障礙物繞行方法

管路常常要避開濾油器、高溫油管等障礙物，這是為了保證布局過程的安全性和導(dǎo)管工作的可靠性。本文在確定危險障礙物前提下，提出建立障礙物的“危險區(qū)”，對障礙物建立最小包圍盒，并對包圍盒進行擴展得到“危險區(qū)”，并建立虛擬實體。在進行節(jié)點擴展時，處于“危險區(qū)”內(nèi)的節(jié)點將是不可行節(jié)點，如圖2所示。

2) 貼壁約束下節(jié)點“吸引”策略

輔助固定是為了便于安裝、減小振動等，特別是針對長管路，有必要添加輔助固定平臺。添加平臺有兩種方式：一種是選擇平面；另一種是選擇障礙物實體。若選擇某平面作為固定，如圖3所示，定義平面的吸引半徑為ρ，算法先獲取當前平面的外法向量n，隨后將節(jié)點沿該向量反向平移ρ個單位，若不發(fā)生碰撞，不作任何處理；否則，將當前節(jié)點吸引到該障礙物附近(距離為d，d<ρ)得到點Ei，進入子路徑的搜索，此時搜索過程變?yōu)槎S平面，搜索區(qū)域是以當前節(jié)點為中心，半徑為L2的圓(L2是控制點間最小間距)。建立與平面相齊的局部坐標系Ei-UVN，EiT在平面Π的投影直線EiH與圓相交于點Eo，將Eo作為子路徑搜索終點，若Eo不可達時，則在小鄰域范圍內(nèi)隨機選擇可行節(jié)點作為終點。

對于障礙物實體，如圖4所示，為了使路徑能夠向固定平臺靠近，構(gòu)建輔助固定平臺的最小包圍盒Ω1:abcd-efgh，將Ω1向外擴展2～3個管徑得到擴展包圍盒Ω2:ABCD-EFGH，定義ΩA:Ω1≤ΩA≤Ω2為“吸引區(qū)”。當擴展的節(jié)點進入該吸引區(qū)域時，與上類似地進入子路徑的構(gòu)造。子路徑構(gòu)造過程中，子節(jié)點的選擇范圍將限制在該ΩA，當擴展的節(jié)點到達距離終點最近的包圍盒頂點，子路徑搜索完成。子路徑是主路徑不可缺少的一部分，在獲得子路徑后，以子路徑終點為起點，完成剩余路徑的搜索。最后生成的路徑由三部分組成，分別是前路徑、子路徑、后路徑，將這些路徑順次連接，即可構(gòu)成一條可行且滿足貼壁約束的管路路徑。

3 路徑優(yōu)化方法

3.1 路徑節(jié)點的篩選

在路徑回溯時，不僅存儲了路徑節(jié)點列表，還存儲了在各個直線段間的連接點，采用二分法原理篩選路徑關(guān)鍵點。二分法的數(shù)學(xué)原型為：設(shè)x1,x2,x3為不在同一直線上的三個點，若x1與x2連線不與障礙物發(fā)生碰撞，而x1與x3連線與障礙物發(fā)生碰撞，則存在x0∈[x2,x3]使得x1與x0的連線恰好不與障礙物發(fā)生碰撞，在給定的精度ε要求下，通過不斷對區(qū)間二分的方法，最終能找到x0。

管路路徑節(jié)點的篩選如圖5所示。具體執(zhí)行步驟如下：

步驟1 以1為起點，連接1-4、1-5、1-7均未發(fā)生碰撞，連接1-12發(fā)生碰撞，取7與12的中位數(shù)9；

步驟2 連接1-9，發(fā)生碰撞，取7與9的中位數(shù)8；

步驟3 連接1-8，不發(fā)生碰撞，顯然，8是不可缺少的路徑關(guān)鍵點，保存8。

步驟4 由于8為“吸引區(qū)”的“入口”，12為“吸引區(qū)”的“出口”，以8為起點，12為終點，采取相同方法對8-12間的節(jié)點進行篩選。

步驟5 在完成“吸引區(qū)”內(nèi)的路徑篩選后，返回到主路徑的節(jié)點篩選過程。取12為起點，連接12-13、12-15、12-16均不碰撞，保存16。從而得到路徑的關(guān)鍵點坐標為1-8-12-16，并將這些點將作為管路的初始控制點。

3.2 面向可制造約束的路徑優(yōu)化

在路徑優(yōu)化階段，本文重點考慮控制點間最小間距約束及相鄰直段間的夾角約束。文中根據(jù)導(dǎo)管段及導(dǎo)管段之間的相互關(guān)系判斷約束的滿足性，并建立約束違反后的兩種處理機制：長度處理機制和角度處理機制。

1) 長度處理機制

2) 角度處理機制

當相鄰直段夾角θ1小于90°時，采取添加控制點進行過渡，如圖7(b)所示。直段Pi-1Pi與PiPi+1構(gòu)成平面，過Pi作長度為L2(控制點間距)的垂線PiQi，若不發(fā)生碰撞且線段PiQi與QiPi+1構(gòu)成的夾角θ2滿足θ2≥π/2,則添加控制點Qi；否則隨機給定Pi-1Pi的垂直向量n，沿n進行擴展得到滿足θ2≥π/2的控制點Qi，并添加到控制點列表中，記其為Qi(Pi)，括號內(nèi)表示新增節(jié)點Qi的歸屬節(jié)點為Pi。

在優(yōu)化過程中，不僅控制點位置發(fā)生變化，控制點列表也是動態(tài)變化的。這體現(xiàn)在控制點的位置更新或新增控制點時，本文采用“可視圖法”刪除冗余的控制點，這樣既能簡化優(yōu)化過程還能減少折彎數(shù)目。此外，針對需要在特定位置固定的導(dǎo)管，可將整個導(dǎo)管在輔助固定導(dǎo)管段的始端和末端進行分割處理，保證每一部分可采用以上機制完成導(dǎo)管的優(yōu)化過程。為獲取較優(yōu)管路路徑，分別采用正向優(yōu)化和逆向優(yōu)化相結(jié)合的方法。以管長、折彎數(shù)和約束違反程度作為評判標準，從中選擇一條較為合理的路徑作為管路路徑。

該優(yōu)化算法主要包含約束檢查和約束處理兩大模塊，整個優(yōu)化過程是一個約束檢查與約束求解的過程。算法優(yōu)化的準則是：當前控制點只對未進行約束檢查的控制點位置產(chǎn)生影響，而不會對已經(jīng)優(yōu)化處理過的點作二次處理。對于不同形式的約束沖突，算法指定了相應(yīng)的約束處理機制，當該約束不能被求解時，算法將對相應(yīng)的控制點和導(dǎo)管段進行高亮顯示，并提示設(shè)計人員進行手動調(diào)整。值得注意的是，經(jīng)過優(yōu)化后的路徑不一定是最短路徑，但一定是滿足工程約束規(guī)則的合理路徑。整個系統(tǒng)優(yōu)化流程如圖8所示。

4 應(yīng)用驗證

節(jié)選模型發(fā)動機的主水管路作為研究對象，管路周圍的障礙物如圖9所示。管路直徑為55 mm，管路與障礙物之間最短距離為6 mm，取柵格粒度為30 mm，對障礙物進行劃分，結(jié)果如圖10所示。

經(jīng)優(yōu)化結(jié)果如圖11所示。其中，管路①為主水管優(yōu)化后的管路，長度為1 730.89 mm，其附近的黑色陰影管路為原管路，長度為1 835.26 mm。管路②為機油箱管路優(yōu)化后的管路，長度為700.48 mm，其附近的黑色陰影管路為原管路，長度為693.28 mm。優(yōu)化后的管路三維模型如圖12所示。

5 結(jié)論

合理的管路敷設(shè)是提高管路敷設(shè)效率、降低敷設(shè)成本、提高管路系統(tǒng)可靠性的重要途徑。現(xiàn)代武器裝備多要求在全天候、多地域環(huán)境下作戰(zhàn)，工作環(huán)境越來越惡劣，對裝備的功能、性能指標要求越來越高，并要求能夠耐受嚴酷的使用環(huán)境。本文研究的基于改進A*算法的裝甲車輛發(fā)動機管路自動布局敷設(shè)技術(shù)，解決了裝甲車輛型號研制管路系統(tǒng)經(jīng)驗設(shè)計中的突出問題，節(jié)省了管路布局時間，逐步形成具有指導(dǎo)意義的裝甲車輛管路系統(tǒng)自動布局規(guī)范，對管路布局優(yōu)化設(shè)計具有一定的軍事意義和經(jīng)濟意義。