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

徐聯杰， 劉檢華， 何永熹， 吳宏超， 劉佳順

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

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

徐聯杰， 劉檢華， 何永熹， 吳宏超， 劉佳順

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

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

管路；快速擴展隨機樹；碰撞檢測；快速繞障；關鍵節點

管路是復雜機械產品重要組成部分，管路布局質量可直接影響管路產品的可靠性。隨著CAD技術的發展，國內外學者嘗試采用自動布局技術提高管路布局設計效率和質量。

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

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

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

本文根據RRT算法在路徑搜索中的特性，結合管路自動布局中的約束問題，在現有RRT算法雙樹擴展的基礎上，對其進行改進，提出了一種管路自動布局方法，開發了管路自動布局設計原型系統，并通過實例對算法進行了測試與驗證。

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

1.1基于改進RRT算法的管路自動布局總體思路

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

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

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

1.2管路自動布局問題描述

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

圖2　管路布局問題描述

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

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

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

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

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

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

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

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

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

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

2　基于障礙物碰撞信息的RRT算法改進

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

2.1基本RRT算法

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

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

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

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

(4) 從xnear到xnew進行干涉檢測，若發生干涉，則進入下一次循環；

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

若以上循環執行 K次之后仍然無法找到可行路徑，則說明當前參數設置不合適，待求解問題無可行解或者陷入局部最優解等情況，需要重新設置算法參數。

圖3　RRT算法的擴展過程

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

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

2.2算法初始化

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

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

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

2.3基于碰撞信息的節點擴展策略

文獻[20]提出了一種基于邊界約束的 RRT算法，該算法能夠利用邊界約束使隨機樹沿障礙物表面擴展，采用傳感器檢測障礙物邊界，而在管路自動布局中障礙物邊界需要調用大量的碰撞檢測來探測，因此并不適用。本文根據文獻[21]中OBRRT的節點擴展的思想，在路徑搜索時利用剛性機器人與環境中的障礙物的碰撞信息構造邊界約束，這些碰撞信息包括發生碰撞的碰撞點位置以及障礙物表面的外法向量，在擴展過程中基于該信息確定擴展方向，并且將障礙物表面的外法向量作為方向屬性添加到當前節點中。其中，確定節點擴展方向主要有獲取碰撞信息和計算擴展方向兩部分。

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

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

圖4　基于節點信息構造碰撞檢測方向向量ξ

若上述方法無法檢測到碰撞，則構造一個循環，該循環通過隨機生成一個向量ξ進行碰撞檢測，若檢測到碰撞時，即可獲取碰撞信息進行下一步擴展；若循環次數達到20，結束循環，當前節點擴展失敗。

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

在確定節點擴展方向的過程中，主要分以下2種情況進行處理：

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

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

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

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

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

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

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

圖6　向量ξn的確定

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

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

2.4快速繞障算法

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

根據節點的兩個屬性向量確定擴展方向，進行循環擴展過程如下：

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

圖8　具有兩個屬性向量的節點

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

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

(3) 在擴展得到新的節點 xnew后，如圖 9(b)所示，將節點xnew作為待擴展節點，根據父節點的方向屬性向量 n和 nc的反方向進行碰撞檢測，若 2個方向都發生碰撞，計算得到節點xnew的2個方向屬性向量n和nc，則按照上述1、2循環進行節點擴展，在循環擴展過程中，為避免節點的擴展發生反向的情況，ξe的方向還應該與父節點到待擴展節點的方向向量的夾角成銳角，否則結束循環；

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

(5) 對于進行快速繞障算法擴展的節點，為避免在后續的節點擴展中重復利用該方法，利用快速繞障算法擴展的節點以及在這些節點一定范圍內的其他節點不再調用該方法進行擴展，為保證節點的可擴展性，該節點依然可以利用原來的方法進行擴展。

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

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

2.5基于概率的節點擴展策略

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

圖10　快速繞障算法偽代碼

本文針對2種情況對節點概率進行賦值：

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

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

在管路自動布局的過程中，p的大小根據實際情況確定，當沿障礙物擴展敷設的要求不嚴格時，p值較大，反之較小，一般設置為0.25左右。基于概率思想的節點擴展的流程圖如圖11所示。

圖11　基于概率的節點擴展流程

3　基于關鍵節點的路徑優化

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

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

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

(2) 從路徑起點開始，第一個具有方向屬性的節點；

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

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

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

圖12　拐角位置關鍵節點的判斷

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

圖13　引入碰撞檢測的節點優化過程

圖14　彎曲角度的調整

圖15為路徑節點優化示意圖，圖15(a)所示路徑為根據改進RRT算法得到的初始路徑點，xinit與xgoal分別為路徑的起點和終點，經過優化后得到的最終路徑如圖15(b)所示。

圖15　路徑節點優化示意圖

4　實例驗證

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

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

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

圖16　測試對比實例

圖17　管路沿結構件表面布局效果

表1　算法測試結果

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

圖18　某產品管路自動布局結果

5　結論及展望

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

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

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

[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] 樊江, 馬枚, 楊曉光. 航空發動機外部管路自動敷設研究[J]. 機械設計, 2003, 20(7): 21-23.

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

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

[9] 范小寧. 船舶管路布局優化方法及應用研究[D]. 大連:大連理工大學, 2006.

[10] 曲艷峰, 蔣丹. 基于八叉樹建模和ACA的三維管路路徑規劃[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] 賈菁輝. 移動機器人的路徑規劃與安全導航[D]. 大連:大連理工大學, 2009.

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

[18] 楊宇盟, 聶斌, 方紅根, 等. 虛擬人手臂避障抓取運動規劃[J]. 計算機輔助設計與圖形學學報, 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的未知環境探索方法[J]. 華中科技大學學報: 自然科學版, 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

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

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

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