徐聯(lián)杰， 劉檢華， 何永熹， 吳宏超， 劉佳順

(北京理工大學(xué)機械與車輛學(xué)院，北京 100081)

一種基于改進(jìn)快速搜索隨機樹算法的管路自動布局方法

徐聯(lián)杰， 劉檢華， 何永熹， 吳宏超， 劉佳順

(北京理工大學(xué)機械與車輛學(xué)院，北京 100081)

針對非正交管路自動布局問題，提出一種基于障礙物碰撞信息的快速搜索隨機樹改進(jìn)算法。該算法主要采用基于碰撞信息的節(jié)點擴(kuò)展策略、快速繞障算法以及基于概率思想的節(jié)點擴(kuò)展策略3種方法進(jìn)行改進(jìn)，能夠在較短的時間內(nèi)搜索出一條沿結(jié)構(gòu)件表面從起點到終點的路徑，在此基礎(chǔ)上采用基于關(guān)鍵節(jié)點的路徑優(yōu)化策略，對求解得到的布局路徑進(jìn)行優(yōu)化后形成最終的管路布局結(jié)果。開發(fā)了原型系統(tǒng)，通過實例驗證了該算法的可行性。

管路；快速擴(kuò)展隨機樹；碰撞檢測；快速繞障；關(guān)鍵節(jié)點

管路是復(fù)雜機械產(chǎn)品重要組成部分，管路布局質(zhì)量可直接影響管路產(chǎn)品的可靠性。隨著CAD技術(shù)的發(fā)展，國內(nèi)外學(xué)者嘗試采用自動布局技術(shù)提高管路布局設(shè)計效率和質(zhì)量。

管路自動布局設(shè)計是在給定的幾何、拓?fù)?、技術(shù)和規(guī)則等約束中求解可行管路布置結(jié)果的過程。從幾何意義上看，是在限定的布置空間中，從指定起點開始尋找出一條與其他物體不發(fā)生干涉，滿足各種約束條件且到指定終點的路徑，該問題與三維空間的機器人路徑尋優(yōu)問題類似，屬于NP-hard組合優(yōu)化問題。

管路自動布局問題經(jīng)歷了從二維空間的簡單避開障礙物發(fā)展到三維空間內(nèi)的滿足多目標(biāo)、多約束[1]路徑求解的過程。國外方面，1975年Rourke[2]首次將迷宮算法用于管路自動布局，并使用矩形框包圍障礙物的屏蔽技術(shù)解決碰撞干涉問題，該算法基于波的連續(xù)擴(kuò)散原理找到一條最短路徑，但是求解所需的存儲空間大、操作速度慢。Ito[3-4]應(yīng)用遺傳算法在二維平面內(nèi)搜索管路的最優(yōu)路徑，取得了突破性的進(jìn)展，但其在處理遺傳算法的編碼方式和遺傳算子上不太理想。2002年P(guān)ark和Storch[5]利用單元生成法解決多約束目標(biāo)的管路敷設(shè)問題，通過假定的敷設(shè)模式來產(chǎn)生管線的單元；當(dāng)空間約束繁雜時，建立基本路徑和改進(jìn)空間路徑并不容易。國內(nèi)方面，北京航空航天大學(xué)的樊江等[6-7]針對航空發(fā)動機三維復(fù)雜管路系統(tǒng)的自動布局問題進(jìn)行了深入地研究，實現(xiàn)了管路敷設(shè)智能化，并進(jìn)行了很多有價值的探索。東北大學(xué)的王成恩等[8]針對航空發(fā)動機中的復(fù)雜管路，基于計算幾何、微分幾何以及智能優(yōu)化的思想提出了一系列管路布局算法，并取得了較好的效果。大連理工大學(xué)的范小寧[9]采用基于蟻群算法和協(xié)作式互利共生類協(xié)同進(jìn)化算法對船舶空間多管路的并行敷設(shè)問題進(jìn)行求解，并在算法的協(xié)作機制中采用了優(yōu)良個體構(gòu)造小環(huán)境的方法，避免了在管路數(shù)目較多時出現(xiàn)組合爆炸現(xiàn)象。上海交通大學(xué)的曲艷峰等[10-11]采用八叉樹模型進(jìn)行環(huán)境建模，并用蟻群算法進(jìn)行路徑搜索，以較高的效率實現(xiàn)了三維管路路徑規(guī)劃問題求解。

雖然目前針對管路自動布局問題已經(jīng)有了一系列的研究成果，但是在路徑搜索算法中一般需要對搜索空間進(jìn)行柵格化建模，在柵格數(shù)量較多時會出現(xiàn)組合爆炸的問題?？焖偎阉麟S機樹(rapidly- exploring random tree，RRT)算法是一種增量的路徑規(guī)劃算法，其不需要進(jìn)行柵格化建模，且改進(jìn)具有很高的靈活性，因此在路徑搜索中具有明顯的優(yōu)勢。到目前為止，RRT算法已經(jīng)有很多經(jīng)典的改進(jìn)方法，其改進(jìn)主要集中在采樣策略、擴(kuò)展策略以及多樹擴(kuò)展 3個方面。其中，采樣策略改進(jìn)的經(jīng)典算法主要有 RRT-GoalBais[12]、RRT-GoalZoom、RRT-Local等；擴(kuò)展策略改進(jìn)的經(jīng)典算法主要有RRT-Con[13]、RRT-blossom[14]等；RRT算法還存在多樹擴(kuò)展[15]的改進(jìn)策略，主要有RRT-ExtExt、RRT-ExtCon、RRT-ConCon等改進(jìn)算法。此外，RRT算法的其他改進(jìn)也在實際中得到了使用，如機器人自動導(dǎo)航[16]、無人機路徑規(guī)劃[17]、機械臂避障抓取運動規(guī)劃[18]等。雖然這些改進(jìn)算法在計算中具有較高的效率，并且有些已經(jīng)進(jìn)入了實際的運用，但是由于管路自動布局問題的復(fù)雜性，RRT算法有時(如需要沿障礙物表面敷設(shè)的管路)不能直接用來進(jìn)行自動布局，還需進(jìn)行進(jìn)一步地改進(jìn)。

本文根據(jù)RRT算法在路徑搜索中的特性，結(jié)合管路自動布局中的約束問題，在現(xiàn)有RRT算法雙樹擴(kuò)展的基礎(chǔ)上，對其進(jìn)行改進(jìn)，提出了一種管路自動布局方法，開發(fā)了管路自動布局設(shè)計原型系統(tǒng)，并通過實例對算法進(jìn)行了測試與驗證。

1　管路自動布局求解問題分析

1.1基于改進(jìn)RRT算法的管路自動布局總體思路

基于改進(jìn) RRT算法的管路自動布局方法的總體解決方案，如圖1所示。

圖1　管路自動布局總體解決方案

在圖1的解決方案中，①獲取三維管路布局結(jié)構(gòu)模型，構(gòu)建三維管路自動布局環(huán)境，在此基礎(chǔ)上開展管路布局路徑求解；②對管路的約束信息進(jìn)行分析，并對部分工程約束進(jìn)行數(shù)學(xué)建模，轉(zhuǎn)化為管路路徑規(guī)劃過程中的約束條件，在RRT算法的初始化和改進(jìn)中集中體現(xiàn)，然后利用該算法在可行空間中找到一條初始路徑；③根據(jù)管路約束對利用RRT算法得到的初始路徑進(jìn)行優(yōu)化，得到最終的管路路徑；④根據(jù)路徑可以直接生成虛擬三維實體管路模型。此外，在進(jìn)行路徑搜索以及路徑優(yōu)化的過程中，需要調(diào)用碰撞模型進(jìn)行碰撞檢測以保證路徑始終處于可行空間中。

1.2管路自動布局問題描述

管路自動布局問題可以看作是一個剛性機器人在布局空間中進(jìn)行運動規(guī)劃，并找到一條從起點到終點的無碰路徑，其數(shù)學(xué)描述如圖2所示。

圖2　管路布局問題描述

管路路徑問題的工作空間用W表示，3W?R，該狀態(tài)空間不僅包含初始產(chǎn)品所有的機械零件、裝配夾具和卡具以及工作臺等，還包括已經(jīng)完成布局的管路及其附件等。其中，作運動規(guī)劃的剛性機器人用 A表示，規(guī)劃空間中的障礙物用 O表示，A、O?W。

一般來說，管路的截面都為恒定的圓形，因此可將進(jìn)行路徑規(guī)劃的剛性機器人設(shè)定為一個球形剛體，其球心的運動軌跡即為管路的中心線，剛體運動掃掠的軌跡即為管路的初始路徑。在管路路徑求解計算過程中，球形剛體變換所產(chǎn)生的流形為三維流形，因此求解該路徑規(guī)劃問題的狀態(tài)空間是三維的，用Cspace表示，Cspace=R3。Cfree是剛性機器人在狀態(tài)空間中所有可行解的集合，該空間稱為自由空間。在Cfree中的任意一個解用x表示，x∈Cfree。

在進(jìn)行管路路徑求解計算之前，先輸入一個起點xinit和一個終點xgoal(xinit，xgoal∈Cfree)，經(jīng)過計算得到一系列離散的路徑節(jié)點，其包含了球形剛體的位姿信息，對這些離散點進(jìn)行優(yōu)化處理即可得到最終的管路路徑。

1.3管路自動布局中考慮的約束

在管路自動布局過程中，通常應(yīng)考慮到工程中的敷管規(guī)則。本文主要考慮了沿結(jié)構(gòu)件表面布局的約束，其針對某些特定的管路，如較長或振動較強的管路，需要利用管卡等進(jìn)行固定以獲得較好的力學(xué)特性，為滿足這一約束對RRT算法進(jìn)行了相關(guān)的改進(jìn)。同時，管路與結(jié)構(gòu)件表面之間及管路之間均需預(yù)留一定的間隙，以滿足管路的可裝配性約束(柔性管可以貼壁敷設(shè)，不需考慮此約束)。此外，在優(yōu)先考慮這兩個約束的基礎(chǔ)上，還需考慮其他管路設(shè)計規(guī)則：

(1) 管路不能與障礙物(零部件、附件、管路)干涉，即路徑可行；

(2) 管路兩端為直管段，直管段的長度不小于管徑的2.5倍，以滿足可裝配性約束；

(3) 管路應(yīng)平直且盡可能短，以減輕重量，減少流體損失；

(4) 管路彎頭數(shù)應(yīng)盡可能的少，以減少壓降；

(5) 管路彎曲角度應(yīng)不小于90°，以滿足可加工性約束。

2　基于障礙物碰撞信息的RRT算法改進(jìn)

本文提出的基于障礙物碰撞信息的 RRT改進(jìn)算法，針對管路需要沿著結(jié)構(gòu)件表面敷設(shè)的約束進(jìn)行相關(guān)的數(shù)據(jù)設(shè)定與算法改進(jìn)，使其在搜索空間中能較快地找到一條沿結(jié)構(gòu)件表面從起點到終點的路徑。算法主要針對節(jié)點的擴(kuò)展、繞開障礙物以及隨機樹的收斂性3個方面進(jìn)行改進(jìn)，包括：基于碰撞信息的節(jié)點擴(kuò)展策略、快速繞障算法以及基于概率思想的節(jié)點擴(kuò)展策略。

2.1基本RRT算法

RRT算法首先由美國伊利諾伊大學(xué) LaValle[19]提出，是一種適用于在高維空間中搜索路徑的方法。該算法的路徑節(jié)點擴(kuò)展過程如圖 3所示，在RRT算法進(jìn)行路徑規(guī)劃之前需設(shè)置基本的相關(guān)參數(shù)，如路徑搜索的起點xinit、終點 xgoal位置，路徑點擴(kuò)展步長ρ、終止循環(huán)數(shù)K等。在設(shè)置好參數(shù)后，算法會先創(chuàng)建一個空的擴(kuò)展樹T，并將起點xinit放入T中作為T的根節(jié)點，并對T進(jìn)行如下循環(huán)擴(kuò)展：

(1) 通過均勻隨機采樣函數(shù)得到一個隨機點xrand；

(2) 在T的所有節(jié)點中找到距離xrand最近的節(jié)點xnear；

(3) 沿xnear指向xrand的方向，在與xnear的距離為步長ρ的位置，得到一個新的路徑點xnew；

(4) 從xnear到xnew進(jìn)行干涉檢測，若發(fā)生干涉，則進(jìn)入下一次循環(huán)；

(5) 若從xnear到xnew不干涉，則將新得到的節(jié)點加入T中，并判斷該節(jié)點是否足夠接近終點，若足夠接近，則直接與終點相連，算法結(jié)束，否則繼續(xù)循環(huán)。

若以上循環(huán)執(zhí)行 K次之后仍然無法找到可行路徑，則說明當(dāng)前參數(shù)設(shè)置不合適，待求解問題無可行解或者陷入局部最優(yōu)解等情況，需要重新設(shè)置算法參數(shù)。

圖3　RRT算法的擴(kuò)展過程

RRT算法的5個主要特點：①能在有限時間內(nèi)返回一個可行解；②在算法中障礙物不需要顯示表達(dá)；③不需要對空間進(jìn)行預(yù)處理建模；④具有概率完備性，當(dāng)采樣基數(shù)無限大時，找到可行解的概率趨近 100%；⑤能夠有效解決高維空間和復(fù)雜約束的運動規(guī)劃問題，求解速度快。

由于RRT算法具有以上的特點，在管路路徑規(guī)劃中具有很大的優(yōu)勢，然而由于該算法具有擴(kuò)展到未探索區(qū)域的趨勢，如果將其直接用于管路自動布局，不僅計算效率低，且不能滿足管路布局中的工程約束，因此基于RRT良好的適應(yīng)性，對其采樣和擴(kuò)展等方面進(jìn)行改進(jìn)以應(yīng)用于管路自動布局設(shè)計。

2.2算法初始化

為滿足管路的相關(guān)約束，在進(jìn)行路徑求解之前，需要對相關(guān)的數(shù)據(jù)進(jìn)行設(shè)定，主要包括球形剛體半徑的確定、算法起始點位置的確定等。

根據(jù)可裝配性約束的要求，管路的兩端設(shè)計為直管段，且直管段的長度不小于管徑的2.5倍。針對該約束，在確定RRT算法的起始點和終止點的位置時，將選定管接口的圓心沿接口平面外法向方向移動距離d(d的值為管路外徑的2.5倍)，將移動后得到的位置點分別設(shè)為起點和終點。

此外，利用三角面片模型對規(guī)劃空間中所有的物體包括剛體小球與障礙進(jìn)行碰撞檢測。碰撞檢測模型在規(guī)劃算法中作為一個黑盒來使用，在每次碰撞檢測中，若檢測到碰撞，則返回本次碰撞相關(guān)的信息。

2.3基于碰撞信息的節(jié)點擴(kuò)展策略

文獻(xiàn)[20]提出了一種基于邊界約束的 RRT算法，該算法能夠利用邊界約束使隨機樹沿障礙物表面擴(kuò)展，采用傳感器檢測障礙物邊界，而在管路自動布局中障礙物邊界需要調(diào)用大量的碰撞檢測來探測，因此并不適用。本文根據(jù)文獻(xiàn)[21]中OBRRT的節(jié)點擴(kuò)展的思想，在路徑搜索時利用剛性機器人與環(huán)境中的障礙物的碰撞信息構(gòu)造邊界約束，這些碰撞信息包括發(fā)生碰撞的碰撞點位置以及障礙物表面的外法向量，在擴(kuò)展過程中基于該信息確定擴(kuò)展方向，并且將障礙物表面的外法向量作為方向?qū)傩蕴砑拥疆?dāng)前節(jié)點中。其中，確定節(jié)點擴(kuò)展方向主要有獲取碰撞信息和計算擴(kuò)展方向兩部分。

(1) 獲取碰撞信息。碰撞信息的獲取主要是剛性機器人在待擴(kuò)展節(jié)點位置沿著某一向量進(jìn)行碰撞檢測，根據(jù)檢測到的碰撞獲得障礙物表面的碰撞位置點xc以及該點所在表面的外法向量n。在該過程中，需要解決的問題是如何構(gòu)造碰撞檢測向量，使待擴(kuò)展節(jié)點在其附近能夠快速地檢測到碰撞。其中向量的長度為定值l，其大小設(shè)為節(jié)點擴(kuò)展步長ρ 的3倍(當(dāng)待擴(kuò)展節(jié)點為根節(jié)點時，l的大小為10 ρ)。

本文針對向量ξ的構(gòu)造，依次采用如圖4所示的3種方法：通過生成的隨機采樣點xrand構(gòu)造從xnear到xrand的向量，如圖4(a)所示；構(gòu)造從xnear到xgoal的向量ξ，如圖4(b)所示；利用父節(jié)點xpar的位置信息，構(gòu)造從xpar到xnear的向量，如圖4(c)所示。當(dāng)任意一步構(gòu)造的向量檢測到碰撞時，即可獲取碰撞信息。

圖4　基于節(jié)點信息構(gòu)造碰撞檢測方向向量ξ

若上述方法無法檢測到碰撞，則構(gòu)造一個循環(huán)，該循環(huán)通過隨機生成一個向量ξ進(jìn)行碰撞檢測，若檢測到碰撞時，即可獲取碰撞信息進(jìn)行下一步擴(kuò)展；若循環(huán)次數(shù)達(dá)到20，結(jié)束循環(huán)，當(dāng)前節(jié)點擴(kuò)展失敗。

(2) 計算擴(kuò)展方向。在隨機樹貼近障礙物表面的擴(kuò)展過程中，不僅要保證節(jié)點能夠快速有效地搜索到一條可行路徑，而且根據(jù)路徑節(jié)點生成管路走向還需要盡量與結(jié)構(gòu)件表面保持平齊，基于該約束，隨機樹中貼近障礙物表面擴(kuò)展的隨機樹既要能夠快速找到一條連通路徑，還要與障礙物之間保持穩(wěn)定的距離，因此確定擴(kuò)展方向是很有必要的。

在確定節(jié)點擴(kuò)展方向的過程中，主要分以下2種情況進(jìn)行處理：

夫妻離婚爭孩子，老婆理直氣壯說：“孩子從我肚子里出來的，當(dāng)然歸我！”老公說：“笑話！簡直是胡說八道！取款機里取出來的錢能歸取款機嗎？還不是誰插卡歸誰！”

①當(dāng)待擴(kuò)展節(jié)點xnear與發(fā)生碰撞的障礙物表面的距離等于d時，其中d為管路半徑的1.3倍，如圖5(a)所示，根據(jù)碰撞得到的障礙物表面法向量n，計算出垂直于n的向量ξn，取沿ξn方向，距離xnear長度為擴(kuò)展步長ρ的坐標(biāo)點為新節(jié)點xnew的位置，若從xnear到xnew之間無碰撞，則將xnew加入到隨機樹T中，擴(kuò)展成功，否則擴(kuò)展失敗；

②若擴(kuò)展節(jié)點xnear與障礙物表面的距離不等于d時，如圖5(b)所示，根據(jù)碰撞得到的碰撞點位置xc和障礙物表面外法向n，可以計算得到垂直于 n的向量ξn，并且在xnear到障礙物表面的垂線上計算出與障礙物距離為d的點xt，取沿ξn方向，距離xt長度為擴(kuò)展步長ρ的坐標(biāo)點為新節(jié)點xnew的位置，若從xnear到xnew之間無碰撞，則將xnew加入到隨機樹T中，擴(kuò)展成功，否則擴(kuò)展失敗。

圖5　xnear與障礙物表面的距離是否等于d時擴(kuò)展方向的計算

在進(jìn)行擴(kuò)展的過程中，根據(jù)得到的碰撞信息，可采用2種方法得到向量ξn，這2種方法能夠引導(dǎo)隨機樹的節(jié)點沿障礙物表面向隨機方向和終點方向擴(kuò)展，2種方向分別以0.5的概率生成，既能保證隨機樹快速向終點方向生長，同時也具有沿障礙物表面探索其他可行路徑的能力。

隨機方向。如圖6(a)所示，根據(jù)得到的障礙物表面法向量n，可以得到垂直于n的一個平面，在該平面內(nèi)的任意一個向量都垂直于向量n，因此令該向量為ξn=(x,y,z)，則n·ξn=0，在區(qū)間(0,1)內(nèi)通過均勻隨機的方法得到x，y的值，進(jìn)而計算出z的大小，通過單位化即可得到一個隨機向量ξn。

終點方向。如圖6(b)所示，利用已有的xnear、xgoal的位置信息，構(gòu)造向量 ξgoal，則可以在經(jīng)過垂直于向量n的平面中計算出一個與ξgoal夾角最小的單位向量ξn，從而使隨機樹向終點方向擴(kuò)展。

圖6　向量ξn的確定

具體計算方法是根據(jù)ξn與向量n、ξgoal之間的幾何關(guān)系，構(gòu)造式(1)所示的方程組：

解式(1)，即可計算出向量ξn的值。沿障礙物表面擴(kuò)展的RRT算法偽代碼如圖7所示。

2.4快速繞障算法

在路徑搜索過程中，由于RRT算法采用基于終點信息擴(kuò)展的策略進(jìn)行節(jié)點的擴(kuò)展，因此當(dāng)該算法在沿著障礙物表面擴(kuò)展時需要繞開其他障礙物，可能會產(chǎn)生搜索節(jié)點過多或搜索路徑沿另一障礙物表面擴(kuò)展的問題，不僅影響算法的搜索效率，而且得到的路徑可能無法滿足管路敷設(shè)的約束要求。因此本文提出一種基于障礙物表面法向量的快速繞障算法，該方法能基于上一節(jié)點的碰撞信息進(jìn)行下一節(jié)點的定向擴(kuò)展，使節(jié)點能夠更加快速地繞過障礙物，具體來說，當(dāng)沿障礙物擴(kuò)展的節(jié)點處于以下2種情況時：①節(jié)點在擴(kuò)展失敗時檢測到碰撞，計算得到其障礙物表面法向量 nc與待擴(kuò)展節(jié)點的方向?qū)傩韵蛄縩的夾角大于45°；②待擴(kuò)展節(jié)點在獲取碰撞信息中得到的碰撞向量與待擴(kuò)展節(jié)點的方向?qū)傩韵蛄縩的夾角大于45°。將向量nc作為當(dāng)前節(jié)點的第二個屬性向量添加到節(jié)點中，如圖8所示。

根據(jù)節(jié)點的兩個屬性向量確定擴(kuò)展方向，進(jìn)行循環(huán)擴(kuò)展過程如下：

圖7　沿障礙物表面擴(kuò)展的RRT算法偽代碼

圖8　具有兩個屬性向量的節(jié)點

(1) 當(dāng)前節(jié)點具有第二個屬性向量時，根據(jù) n 與nc的值，計算出方向向量ξe=±(n×nc)，如圖9(a)所示，該向量垂直于向量n和nc，ξe取與向量ξgoal夾角為銳角的值；

(2) 節(jié)點 xnear沿 ξe方向擴(kuò)展一個步長 ρ得到xnew，此時若 xnear到 xnew方向不發(fā)生碰撞，則擴(kuò)展成功，否則退出循環(huán)；

(3) 在擴(kuò)展得到新的節(jié)點 xnew后，如圖 9(b)所示，將節(jié)點xnew作為待擴(kuò)展節(jié)點，根據(jù)父節(jié)點的方向?qū)傩韵蛄?n和 nc的反方向進(jìn)行碰撞檢測，若 2個方向都發(fā)生碰撞，計算得到節(jié)點xnew的2個方向?qū)傩韵蛄縩和nc，則按照上述1、2循環(huán)進(jìn)行節(jié)點擴(kuò)展，在循環(huán)擴(kuò)展過程中，為避免節(jié)點的擴(kuò)展發(fā)生反向的情況，ξe的方向還應(yīng)該與父節(jié)點到待擴(kuò)展節(jié)點的方向向量的夾角成銳角，否則結(jié)束循環(huán)；

(4) 當(dāng)循環(huán)擴(kuò)展過程中節(jié)點 xnew沒有得到方向向量nc時，如圖9(c)所示，則沿nc方向(或者沿–nc方向，取與ξgoal夾角為銳角的方向)擴(kuò)展一個臨時節(jié)點xnew2，若擴(kuò)展失敗，則退出循環(huán)；若擴(kuò)展成功，則該節(jié)點的屬性向量n與xnew的向量n相同，并在該節(jié)點通過隨機生成至多k個方向進(jìn)行碰撞檢測，若不存在 nc，則刪除節(jié)點 xnew2并結(jié)束循環(huán)，若存在，則按照上述循環(huán)繼續(xù)進(jìn)行節(jié)點擴(kuò)展；

(5) 對于進(jìn)行快速繞障算法擴(kuò)展的節(jié)點，為避免在后續(xù)的節(jié)點擴(kuò)展中重復(fù)利用該方法，利用快速繞障算法擴(kuò)展的節(jié)點以及在這些節(jié)點一定范圍內(nèi)的其他節(jié)點不再調(diào)用該方法進(jìn)行擴(kuò)展，為保證節(jié)點的可擴(kuò)展性，該節(jié)點依然可以利用原來的方法進(jìn)行擴(kuò)展。

快速繞障算法的偽代碼如圖10所示。

圖9　基于障礙物表面法向量的快速繞障算法

2.5基于概率的節(jié)點擴(kuò)展策略

在管路路徑規(guī)劃中，雖然管路是沿著結(jié)構(gòu)件表面敷設(shè)，而在某些無法檢測到碰撞的情況時，如管路接口處于懸臂狀態(tài)、路徑需跨越窄縫等，隨機樹需要在自由空間中進(jìn)行擴(kuò)展。因此針對RRT算法在路徑搜索的過程中，既需要保證隨機樹在沿著結(jié)構(gòu)件表面向目標(biāo)點收斂的同時，還需要保留算法一定的發(fā)散性，并保證隨機樹能向自由空間擴(kuò)展，因此本文采用基于概率的思想進(jìn)行節(jié)點的擴(kuò)展，對每個節(jié)點賦予一個概率值，針對隨機樹中的待擴(kuò)展節(jié)點，通過在區(qū)間［0,1］內(nèi)生成的一個隨機數(shù)與當(dāng)前節(jié)點的概率值進(jìn)行比較，當(dāng)該值小于或等于當(dāng)前節(jié)點的擴(kuò)展概率時，對該節(jié)點進(jìn)行擴(kuò)展，否則不擴(kuò)展。

圖10　快速繞障算法偽代碼

本文針對2種情況對節(jié)點概率進(jìn)行賦值：

(1) 若某個節(jié)點在待擴(kuò)展時檢測到與障礙物發(fā)生碰撞，則認(rèn)為該節(jié)點位于障礙物表面附近，將其擴(kuò)展概率設(shè)為1；

(2) 若某個節(jié)點在待擴(kuò)展時未檢測到碰撞，則認(rèn)為該節(jié)點附近沒有障礙物，將其擴(kuò)展概率設(shè)為p(p∈[0,1])。

在管路自動布局的過程中，p的大小根據(jù)實際情況確定，當(dāng)沿障礙物擴(kuò)展敷設(shè)的要求不嚴(yán)格時，p值較大，反之較小，一般設(shè)置為0.25左右?；诟怕仕枷氲墓?jié)點擴(kuò)展的流程圖如圖11所示。

圖11　基于概率的節(jié)點擴(kuò)展流程

3　基于關(guān)鍵節(jié)點的路徑優(yōu)化

在采用本文算法得到的初始路徑，是通過具有固定步長的樹節(jié)點得到的，因此該路徑對與管路來說具有較多的冗余節(jié)點，并不能直接用來生成管路模型，需要對其進(jìn)行優(yōu)化。在優(yōu)化過程中保證管路沿結(jié)構(gòu)件表面敷設(shè)的前提下，還需要保證管路長度盡量短并且彎頭數(shù)應(yīng)盡可能的少，因此需采用一種基于關(guān)鍵節(jié)點的路徑優(yōu)化方法。

由于在路徑搜索過程中，隨機樹中大部分的節(jié)點都是根據(jù)障礙物表面外法向量進(jìn)行擴(kuò)展的，且節(jié)點中保存有相關(guān)的擴(kuò)展信息，因此在管路布局中路徑優(yōu)化的方法是利用路徑中的節(jié)點信息確定關(guān)鍵節(jié)點，并基于這些關(guān)鍵節(jié)點剔除其他的冗余節(jié)點。關(guān)鍵節(jié)點的判斷依據(jù)包括：

(1) 路徑的起點和終點；

(2) 從路徑起點開始，第一個具有方向?qū)傩缘墓?jié)點；

(3) 快速繞障算法所生成路徑的起點、終點和拐點；

(4) 從具有屬性向量n的關(guān)鍵節(jié)點開始向后搜索，當(dāng)出現(xiàn)屬性向量與該關(guān)鍵節(jié)點的屬性向量夾角大于 30°的節(jié)點時，說明該路徑節(jié)點位置附近的障礙物表面很可能出現(xiàn)了較大凸凹現(xiàn)象，為保證路徑始終處于障礙物附近，將該節(jié)點設(shè)為路徑的關(guān)鍵節(jié)點，如圖12所示的節(jié)點xk2。

根據(jù)關(guān)鍵節(jié)點的定義，需確定、保留路徑中的關(guān)鍵節(jié)點，并剔除路徑中的冗余點，與此同時，引入插值碰撞檢測對路徑進(jìn)行優(yōu)化。其優(yōu)化過程為：從路徑起點開始，將路徑中不屬于關(guān)鍵節(jié)點的路徑點剔除，保留關(guān)鍵節(jié)點，再對每個關(guān)鍵節(jié)點之間進(jìn)行插值碰撞檢測，若兩個節(jié)點之間發(fā)生碰撞，則在原路徑的基礎(chǔ)上對后一關(guān)鍵節(jié)點進(jìn)行回溯碰撞檢測，如圖13所示，節(jié)點1到10為原路徑中的節(jié)點，其中關(guān)鍵節(jié)點為1、10，由于兩個關(guān)鍵節(jié)點之間發(fā)生碰撞，因此先在節(jié)點 1、9之間進(jìn)行插值碰撞檢測，若仍然發(fā)生碰撞，繼續(xù)在 1、8之間進(jìn)行插值碰撞檢測，直到節(jié)點7未發(fā)生碰撞時，將該節(jié)點保存下來，然后以節(jié)點7為起點，繼續(xù)按照上述方法進(jìn)行優(yōu)化。

圖12　拐角位置關(guān)鍵節(jié)點的判斷

在管路布局中，為保證敷設(shè)管路的可加工性，還需要對路徑節(jié)點的彎曲角度進(jìn)行局部優(yōu)化處理，如圖14所示：根據(jù)與控制點1相連的兩個控制點2、3得到兩個單位向量V12、V13，當(dāng)其夾角α小于90°時，則計算出α角平分線的單位向量V1，將控制點1沿V1方向以一定的步長λ逐步平移，直到彎曲角度大于90°。

圖13　引入碰撞檢測的節(jié)點優(yōu)化過程

圖14　彎曲角度的調(diào)整

圖15為路徑節(jié)點優(yōu)化示意圖，圖15(a)所示路徑為根據(jù)改進(jìn)RRT算法得到的初始路徑點，xinit與xgoal分別為路徑的起點和終點，經(jīng)過優(yōu)化后得到的最終路徑如圖15(b)所示。

圖15　路徑節(jié)點優(yōu)化示意圖

4　實例驗證

利用三維造型引擎ACIS和三維顯示交互工具包HOOPS，自主設(shè)計并開發(fā)了管路自動布局系統(tǒng)，該系統(tǒng)在Microsoft Visual Studio2005上利用C++語言開發(fā)，開發(fā)硬件為HP Z400圖形工作站，CPU為2.67 GHz Intel Xeon W3520，內(nèi)存4 G (3.48 G可用)，顯卡為 Nvidia Quadro 5000，操作系統(tǒng)為Windows 7專業(yè)版。

為了驗證算法的計算效率與布局質(zhì)量，對提出改進(jìn)的RRT算法進(jìn)行了測試，測試結(jié)果與雙樹擴(kuò)展中3種經(jīng)典的算法RRT-ExtExt、RRT-ConCon以及RRT-ExtCon進(jìn)行了對比，測試結(jié)果如圖16所示；計算結(jié)果如表1所示。通過綜合對比可以看出，改進(jìn)的RRT算法在保證搜索成功率的同時，能夠在較短的時間內(nèi)搜索出符合管路約束的路徑。

為驗證該算法沿結(jié)構(gòu)件表面敷設(shè)的效果，在如圖 17所示模型(管路接口已隱藏)中的凹形區(qū)域進(jìn)行實例測試，求解得到的雙樹節(jié)點如圖17(a)所示，其中紅色高亮節(jié)點為得到的初始路徑點，生成的實體管路模型如圖17(b)所示。

圖16　測試對比實例

圖17　管路沿結(jié)構(gòu)件表面布局效果

表1　算法測試結(jié)果

運用提出的改進(jìn) RRT算法進(jìn)行管路自動布局設(shè)計，在自主開發(fā)的管路布局系統(tǒng)上對某產(chǎn)品進(jìn)行了驗證，根據(jù)選定的接口位置信息自動求解出管路路徑，并生成實體管路模型，如圖18所示。

圖18　某產(chǎn)品管路自動布局結(jié)果

5　結(jié)論及展望

(1) 本文提出了一種基于障礙物碰撞檢測的RRT算法，其主要針對節(jié)點的擴(kuò)展、繞開障礙物以及隨機樹的生長趨勢3個方面進(jìn)行改進(jìn)，并采用基于關(guān)鍵節(jié)點的路徑優(yōu)化方法對求解到的路徑進(jìn)行了優(yōu)化，在較短的時間內(nèi)搜索出了符合限定約束條件下的管路路徑，有效地解決復(fù)雜結(jié)構(gòu)條件下的沿結(jié)構(gòu)件表面的管路自動布局問題。

(2) 在算法中利用快速繞障算法，避免了障礙物表面生成過多的冗余節(jié)點，提高了算法的搜索效率。

(3) 該算法能夠得到較好的布局方案，但是由于管路布局的復(fù)雜性，并沒有全面考慮工程約束，這些都需要在以后的工作中進(jìn)一步探索。

[1] Sandurkar S, Chen W. GAPRUS—genetic algorithms based pipe routing using tessellated objects [J]. Computers in Industry, 1999, 38(3): 209-223.

[2] Rourke P W. Development of a three-dimensional pipe routing algorithm [D]. Benthlehem: Lehigh University, 1975.

[3] Ito T. A genetic algorithm approach to piping route path planning [J]. Journal of Intelligent Manufacturing, 1999, 10(1): 103-114.

[4] Ito T. Piping layout wizard: basic concepts and its potential for pipe route planning [M]. Methodology and Tools in Knowledge-Based Systems. Springer Berlin Heidelberg, 1998: 438-447.

[5] Park J H, Storch R L. Pipe-routing algorithm development: case study of a ship engine room design [J]. Expert Systems with Applications, 2002, 23(3): 299-309.

[6] 樊江, 馬枚, 楊曉光. 航空發(fā)動機外部管路自動敷設(shè)研究[J]. 機械設(shè)計, 2003, 20(7): 21-23.

[7] 樊江, 馬枚, 楊曉光. 基于協(xié)進(jìn)化的管路系統(tǒng)智能尋徑[J]. 航空動力學(xué)報, 2004, 19(5): 593-597.

[8] 王成恩, 柳強, 白曉蘭, 等. 航空發(fā)動機復(fù)雜約束空間內(nèi)管路敷設(shè)技術(shù)[J]. 計算機集成制造系統(tǒng), 2010, 16(11): 327-332.

[9] 范小寧. 船舶管路布局優(yōu)化方法及應(yīng)用研究[D]. 大連:大連理工大學(xué), 2006.

[10] 曲艷峰, 蔣丹. 基于八叉樹建模和ACA的三維管路路徑規(guī)劃[J]. 計算機工程, 2011, 37(23): 4-7.

[11] Qu Y F, Jiang D, Liu B. A multi-pipe path planning by modified ant colony optimization [J]. Computer Aided Drafting, Design and Manufacturing, 2011, 21(1): 1-7.

[12] LaValle S M, Kuffner J J. Randomized kinodynamic planning [J]. The International Journal of Robotics Research, 2001, 20(5): 378-400.

[13] Kuffner J J, LaValle S M. RRT-connect: an efficient approach to single-query path planning [C]//Robotics and Automation, 2000. Proceedings. ICRA’00. IEEE International Conference on. IEEE, 2000: 995-1001.

[14] Kalisiak M, van de Panne M. RRT-blossom: RRT with a local flood-fill behavior [C]//International Conference on Robotics & Automation. IEEE, 2006: 1237-1242.

[15] Zucker M, Kuffner J, Branicky M. Multipartite RRTs for rapid replanning in dynamic environments [C]//Robotics and Automation, 2007 IEEE International Conference on. IEEE, 2007: 1603-1609.

[16] 賈菁輝. 移動機器人的路徑規(guī)劃與安全導(dǎo)航[D]. 大連:大連理工大學(xué), 2009.

[17] 劉偉, 鄭征, 蔡開元, 等. 快速平滑收斂策略下基于QS-RRT的UAV運動規(guī)劃[J]. 中國科學(xué): 信息科學(xué), 2012, 42(11): 1403-1422.

[18] 楊宇盟, 聶斌, 方紅根, 等. 虛擬人手臂避障抓取運動規(guī)劃[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2014, 26(8): 1362-1373.

[19] LaValle S M. Rapidly-exploring random trees a new tool for path planning [R]. Technical Report No. 98-11. 1998.

[20] 呂偉新, 趙立軍, 王珂, 等. 基于邊界約束RRT的未知環(huán)境探索方法[J]. 華中科技大學(xué)學(xué)報: 自然科學(xué)版, 2011, 39(S2): 366-369.

[21] Rodriguez S, Tang X, Lien J M, et al. An obstacle-based rapidly-exploring random tree [C]//Robotics and Automation, ICRA 2006. Proceedings 2006 IEEE International Conference on. IEEE, 2006: 895-900.

A Method for Pipe Auto Layout Based Improved RRT Algorithm

Xu Lianjie,Liu Jianhua,He Yongxi,Wu Hongchao,Liu Jiashun

(School of Mechanical Engineering, Beijing Institute of Technology, Beijing 100081, China)

An improved rapidly-exploring random tree algorithm is proposed based on collision information for the problem of non-orthogonal pipe automatic routing. This algorithm has three main improved methods: node expansion based collision information, fast bypassing obstacle algorithm and node expansion based on the thinking of node’s probability. It could search out a path to walk along the surface of structure parts in comparably short time. On the basis of the three methods, the optimization strategy based key nodes is used to optimize the obtained path and form the final result of pipe routing layout. A prototype system is developed and the feasibility of the algorithm by instance is verified.

pipe; rapidly-exploring random tree; collision detection; fast bypassing obstacle algorithm; key nodes

TP 391.9

10.11996/JG.j.2095-302X.2016010001

A

2095-302X(2016)01-0001-10

2015-09-24；定稿日期：2015-10-09

國家自然科學(xué)基金項目(51275047)；“十二五”國防基礎(chǔ)科研項目(A2220110008)

徐聯(lián)杰(1990–)，男，湖南常德人，碩士研究生。主要研究方向為管路自動布局技術(shù)。E-mail：xulianjie1234@163.com

劉檢華(1977–)，男，江西萍鄉(xiāng)人，教授，博士，博士生導(dǎo)師。主要研究方向為數(shù)字化裝配與檢測。E-mail：jeffliu@bit.edu.cn