基于RRT*的母線布線路徑規劃算法

劉 沖,周 馳

(華南理工大學 機械與汽車工程學院，廣州 510641)

0 引言

近年來，隨著電子電力及其相關產品的改進與發展，母線在一些高層建筑、軌道交通、環保、石化、智能型大廈和房地產項目，以及各種城市工業園的輸配電系統中得到了快速發展和廣泛應用[1]。母線布局設計是母線設計的核心環節，除了滿足電氣連接的基本需求之外，還需要綜合考慮與相鄰風火水電系統的干涉情況、制造和安裝成本、以及工作使用的要求。母線布局路徑的規劃，本質上就是在三維空間中設計一條連接起止端，并滿足上述約束的路徑。目前母線設計主要依靠人工方式，費時費力，且難以尋獲最優路徑，設計出一種自動化的母線路徑規劃算法對工程中的母線布局設計具有重大意義。

為了解決路徑規劃問題，國內外學者在大量研究與不斷探索的基礎上，提出了很多路徑規劃的算法。常用的路徑規劃算法有A*,蟻群算法，遺傳算法，粒子群算法，人工勢場法等[2-6]，這些算法在解決傳統的二維平面上的路徑規劃問題時，由于解空間較小并且問題簡單，可以取得不錯的效果。但是到了三維空間中，復雜的環境和高一維的空間容易引發維度災難，使得這些算法的計算復雜度會劇烈增加，導致問題求解困難，收斂時間變長。近年來，基于抽樣的路徑規劃算法被引入用來解決三維空間的路徑規劃問題，例如快速探索隨機樹(RRT)[7]，通過隨機抽取一些采樣點來進行搜索，由于該算法避免構建顯式的任務空間，進而大大降低了算法的計算復雜度，同時該算法具有概率完備性，這些特性使得該算法在解決路徑規劃相關問題中被廣泛應用。然而，RRT算法仍有一些缺點：由于其采用的是隨機的采樣策略，導致其生成的路徑不穩定，規劃出的解一般都不是最優的，同時RRT算法求解出的路徑具有很多的冗余點，不僅增加了路徑長度，同時導致路徑存在較多不規則的彎折。而在母線的布線的過程中，僅支持90度彎折。為了解決RRT算法存在非概率最優解問題，2010年 S.Karaman 和E.Frazzoli 提出了RRT*算法，該算法在迭代過程中對生成的路徑進行局部的重新布線，使得路徑長度減小，確保算法可以收斂到最優解，并且與傳統RRT算法計算的時間消耗只在一個常數比例內[8-9]。

母線布線的路徑規劃與普通線纜布線有顯著區別。首先，母線是由銅排構成的，因此不能像線纜一樣自由地改變走向，也就是不能自由的彎曲。母線只能通過90度的彎頭連接來改變走向，因此要求前后兩段母線走向互相垂直。其次，母線的布局設計應該盡可能的少使用彎頭，彎頭數目的增多不僅增加制造成本，還會削弱母線的穩定性、安全性以及可維護性。最后，受到現場空間和插接箱取電位置的限制，在母線路徑規劃時還必須考慮母線的朝向，這在普通線纜布線中是不需要考慮的。

由上述分析可知，直接使用標準的RRT*算法進行求解無法滿足母線布線設計的約束條件。但由于該算法具有良好的適應性，本文在RRT*算法的基礎上，設計了一個母線的三維空間路徑規劃算法，該算法拋棄了原始RRT*算法擴展過程中直接將采樣點和擴展樹相連的方式，而是通過選用corner點將擴展樹和采樣點間接相連，在此基礎上引入貪心的優化策略進一步滿足工程中母線的相關約束。最后通過多組實例計算驗證了該算法的有效性和穩定性。

1 RRT* 算法

快速隨機搜索樹(RRT)算法是一種基于采樣的啟發式路徑搜索算法，其核心步驟開始開始建立以起點為根的擴展樹，在全圖中隨機采樣生成一個隨機點，之后在從擴展樹中找到離這個隨機點最近的節點，接著嘗試從這個最近的節點向隨機點擴展一個步長，如果擴展后沒有發生碰撞，則把這個擴展的新節點加入樹中，否則重新采樣。重復上述過程，直到擴展的節點離終點的距離小于一定值即可認為路徑生成成功。最后通過路徑回溯的方式在擴展樹返回一條連接起點到終點的路徑[10-12]。與其他智能搜索算法在路徑搜索不同的是：該算法雖然沒有實現完整性，但是其具有概率完備性，即該規劃算法計算出解的概率會隨著采樣數量增加快速趨近于1。因此，其在高維度空間中且復雜約束的條件下具有更高的求解效率。

相較于RRT算法，RRT* 算法主要在每次擴展成功后對新增節點的周圍的節點嘗試進行重新布線來獲得漸進收斂到最優路徑的特性[13]。RRT* 算法的偽代碼如算法1所示：其中V表示擴展樹的節點，E表示擴展樹中的邊，T表示擴展樹由V和E組合而成。RRT* 算法在完成這些數據的初始化過程之后通過隨機抽樣開始其迭代過程：首先從給定的配置空間中選取一個隨機點xrand，并從擴展樹中找到距離xrand最近的節點xnearest(3～4行)。之后從xnearest向xrand方向擴展出一個給點步長的新節點xnew。再從擴展樹中找到一組在以xnew為中心的球形區域內的點集合Xnear(5～6行)。接著對Xnear中的每個點按照從xinit到該點的成本和從該點到xnew的成本的和從小到大排序(7行)，獲得列表Ls。之后在Ls中取得可以連接xinit到xnew作為xnew的最佳父節點返回(8行)，如果找到了這個父節點xmin，則將xnew作為該節點的子節點加入擴展樹中，如圖1(a)所示。并進行重新布線(10～11行)，重新布線過程為檢查Ls中每個節點x，如果從xinit到xnew到x的成本小于原來從xinit到x的成本，并且可以將xnew和x相連，那么就斷開x和原來父節點的連接，將xnew作為x的父節點連接到樹中[14-16]。重新布線過程如圖1(b,c,d)所示。RRT* 算法通過引入重新布線的過程保證了漸進最優性。

圖1 RRT*迭代過程

2 母線布線路徑規劃算法

2.1 母線布線設計的約束與優化目標

在實際的母線布線設計中，建筑的內部結構復雜緊湊，布線空間狹窄且不規則。另外建筑內部除母線外，還存在大量的其他機電設備，如風管，水管，電纜橋架等。這些復雜凌亂的環境使得母線布線的難度大大增加。本文所考慮的工程約束主要有以下三條。

1)空間干涉約束：母線的路徑應保證不與建筑中的承重墻、柱以及其他機電設備發生干涉，否則無法完成安裝。

2)母線走向約束：不同于傳統的線纜布線設計，在母線的布線設計中，相鄰的兩段母線應保證相互垂直，且每段母線的起點終點坐標只允許有一個分量不同，也就是說每段母線所在的直線必須與所建立的空間坐標軸平行。

3)母線朝向約束：需要保證母線的起止點朝向相對應，同時母線的路徑中的特定位置也需要滿足朝向的需求。

優化目標主要考慮以下兩條：

1)長度最短：一條母線的長度應該盡可能的短，降低成本，減小空間的占用。

2)彎頭數目最少：每個彎頭都會影響母線的安全性和穩定性，同時增加維護成本。

原始的RRT*迭代過程可以保證空間干涉約束和長度最短的優化目標，本文通過改變RRT*算法的的擴展方式來滿足母線走向約束，并在迭代過程中引入路徑優化過程滿足母線朝向約束的彎頭數目最少的優化目標。

2.2 母線走向約束的處理

在原始的RRT* 算法中，找到xmin直接與xnew相連，此時生成的路徑不符合相鄰母線段相互垂直的要求，如圖1(a)所示。本文在找到xmin后，先尋找xmin與xnew之間的xcorners，通過xcorners把xmin與xnew間接相連，來保證生成的路徑符合母線的布線要求。如圖2所示。重新布線過程也采用這種擴展方式。

圖2 新的擴展方式

2.3 corner點的選擇

在三維環境中，兩個點的坐標關系可以分成三種情況：

1)兩個點的三個坐標分量只有一個不同，說明這兩個點在平行于坐標軸的同一條直線上，此時不需要corner點直接相連即可滿足母線的走向需求。

2)兩個點的三個坐標分量有兩個不同，說明這兩個點在平行于坐標平面的同一平面內,需要一個corner點來連接xmin與xnew，此時有兩個備用的corner點供選擇。如圖2(a)所示。

3)兩個點的三個坐標分量都不同，需要兩個(一對)corner點來連接xmin與xnew，此時有六對corner點對可供選擇。

本文以第二種情況來說明corner點選擇，其他兩種情況類似。如圖3所示，corner點的選取時主要考慮下述三種情形：

1)當某個備選的corner點位于障礙物中時，此時違反了空間干涉約束，所以不應該選擇，如圖3(a)所示。

2)當某個備選的corner點位于xmin到其父節點xmin-parent的連線上時，并且此時xmin到corner點的方向與xmin-parent到xmin方向相反時，即造成了方向沖突，此時生成的路徑會產生對折的情況。這種路徑不符合現實情況，所以這種corner點不應該被選擇，如圖3(b)所示。

3)當某個備選的corner已經在擴展樹中，并且該corner點的父節點不是xmin，此時若選用該corner點會破壞原來的樹結構，從而形成環，后續無法通過回溯取得路徑，所以這種corner點不應該被選擇，如圖3(c)所示。

除開上述三種情形之外，其他情況的corner點均可以被選擇加入擴展樹中，如果有多個或者多對corner點可供選擇，那么選擇構建過程中第一個或者第一對corner點。

圖3 corner點選擇

2.4 路徑優化策略

由RRT*算法生成的路徑存在很多的冗余點，這些冗余點造成了路徑過多的彎折。為使得生成的路徑長度進一步減小和彎頭的使用數量最少，在搜索過程中每次完成擴展后和每次重新布線后都加入以下優化步驟：

取出從起點到剛剛加入擴展樹的節點路徑，取出該路徑最后的5個點，記作a，b，c，d，e。此時考察點a和點e的之間的corner點，如果找到了滿足的corner點，那么就通過這些corner點將點a和點e相連。由前文的分析可知，如果找到了滿足的corner點，那么最多的情況只有兩個，所以原來的5個點至少減少為4個，這樣就完成了一次優化過程，并且這次優化過后這條被優化路徑的長度必定小于等于優化前的長度。之后再取出優化后路徑的最后的五個點，重復上述過程。直到某次優化前后路徑的節點數目不變，說明路徑已經達到了需要最少彎頭的情況。

不同于傳統的線纜，母線由起點引出時就有一個固定的N面，而不同的走向會造成N面朝向的不同。相同的母線由于走向的不同導致終點的N面朝向不同，而在終點或者路徑中安裝插接箱的位置也有N面朝向的要求。所以在算法迭代的過程中(在引入新節點后和每一次優化路徑后)還需要實時計算并記錄擴展樹中的每一段路徑的N面朝向，在每次嘗試獲取連接終點解時需要考慮N面朝向是否符合要求。

改進后的算法偽代碼如算法2所示。主要改進在第8行，第10行和第11行。在第8行，我們不僅需要得到xmin，同時還需要獲得將xmin和xnew相連的corner點,這一步如算法3所示。在算法3中，我們遍歷已經排好序的列表Ls，依次對Ls每個點嘗試獲取到xnew的corner點，一旦獲取到就返回。嘗試獲取corner點這一步如算法4所示。算法2中第10行為將corner點和xnew一并加入樹中，第11行為按照本文新的擴展方式對xnew周圍節點的重新布線過程，這兩步每次擴展成功后均加入2.3中的優化策略。

3 仿真結果及分析

在實驗中，規劃區域為邊長100的正方形，起點為(30,20)，終點為(60,82)。RRT* 算法采用的代價函數為歐式距離，本文算法采用的是曼哈頓距離。圖4和圖5分別為RRT* 算法和本文算法不同階段的情況。由圖4可以看出，原始的RRT* 算法雖然可以收斂到理論最優解，但是由于擴展方式的原因導致生成的路徑不符合母線的走向要求，彎折角度沒有規律。由圖5可以看出，本文改進的擴展方式可以很好的生成滿足母線走向要求的路徑，同時也保留了原始RRT* 算法的漸進最優特性，如圖6所示(本環境的理論最優值為202)，隨著迭代次數的增加，算法取得的路徑長度趨近于理論最優值。但是此時算法迭代過程中并沒有加入對路徑的優化策略，所形成的的路徑折彎過多。加入2.3中描述的路徑優化策略后，算法的迭代過程如圖7所示。可以看出，相較于未加入路徑策略時，此時擴展樹中的節點到起始點的路徑都經過優化大大減少了折彎的次數。

圖4 RRT* 算法

圖5 改進算法(未加入路徑優化)

圖6 路徑長度

圖7 改進算法(加入路徑優化)

最后，為驗證本文算法在三維環境下的效果，根據某公司配電站項目建立簡化三維環境的仿真環境如圖8所示。該配電站一共有三層，其中一條母線需要從一樓的配電柜引出，經過二樓，三樓樓板預留的墻洞引入到三樓配電柜。本文算法在兩種不同需求情況下分別給出了兩條路徑。其中左邊的路徑在一樓到三樓的上升段沒有朝向的要求，而右邊的路徑在該段需要掛接插接箱造成對該段的朝向有要求。從圖中可以看出，兩條路徑長度相同且均滿足在各自需求下的約束。比較左右兩條路徑發現，左邊路徑彎折了8次，右邊路徑彎折了10次，為了滿足上升段的朝向要求，右邊的路徑比左邊多出了兩個折彎，整條母線需要多引入兩個彎頭。

圖8 三維環境下生成的路徑

4 結論

傳統的路徑規劃算法沒有考慮到母線布局設計中的約束，將導致生成的路徑無法指導母線的布局設計，本文在總結出母線布局設計約束與優化目標基礎上，提出了一種新的RRT*的自動布線算法。通過引入corner點的概念，改進原始算法的擴展方式由原來的向隨機方向擴展變為垂直方向擴展，滿足母線布局設計的走向約束。同時將貪心的路徑優化引入算法的迭代過程中獲得更短的路徑長度，最少折彎次數，滿足朝向約束的路徑。最后，通過改進的算法和原始算法進行反復的仿真試驗。結果表明，本文算法生成的路徑可以很好的滿足母線布局設計的需求，為實際工程中的母線布局設計起到了指導意義。