基于改進(jìn)A*算法的管路自動(dòng)敷設(shè)研究

陳 巖,李 濤,印明昂

(1.中國(guó)兵器科學(xué)研究院, 北京 100089; 2.東北大學(xué) 機(jī)械工程與自動(dòng)化學(xué)院, 沈陽(yáng) 110819)

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

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

1 基本A*算法

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

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

(1)

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

步驟1 開始，將起點(diǎn)添加至Open表中。

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

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

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

2 管路自動(dòng)布局中的改進(jìn)A*算法

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

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

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

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

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

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

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

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

(2)

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

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

2.3 多約束條件下的改進(jìn)方法

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

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

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

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

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

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

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

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

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

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

步驟1 以1為起點(diǎn)，連接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)鍵點(diǎn)，保存8。

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

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

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

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

1) 長(zhǎng)度處理機(jī)制

2) 角度處理機(jī)制

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

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

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

4 應(yīng)用驗(yàn)證

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

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

5 結(jié)論

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