劉 沖,周 馳

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

0 引言

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

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

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

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

1 RRT* 算法

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

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

圖1 RRT*迭代過程

2 母線布線路徑規(guī)劃算法

2.1 母線布線設(shè)計的約束與優(yōu)化目標

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

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

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

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

優(yōu)化目標主要考慮以下兩條：

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

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

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

2.2 母線走向約束的處理

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

圖2 新的擴展方式

2.3 corner點的選擇

在三維環(huán)境中，兩個點的坐標關(guān)系可以分成三種情況：

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

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

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

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

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

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

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

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

圖3 corner點選擇

2.4 路徑優(yōu)化策略

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

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

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

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

3 仿真結(jié)果及分析

在實驗中，規(guī)劃區(qū)域為邊長100的正方形，起點為(30,20)，終點為(60,82)。RRT* 算法采用的代價函數(shù)為歐式距離，本文算法采用的是曼哈頓距離。圖4和圖5分別為RRT* 算法和本文算法不同階段的情況。由圖4可以看出，原始的RRT* 算法雖然可以收斂到理論最優(yōu)解，但是由于擴展方式的原因?qū)е律傻穆窂讲环夏妇€的走向要求，彎折角度沒有規(guī)律。由圖5可以看出，本文改進的擴展方式可以很好的生成滿足母線走向要求的路徑，同時也保留了原始RRT* 算法的漸進最優(yōu)特性，如圖6所示(本環(huán)境的理論最優(yōu)值為202)，隨著迭代次數(shù)的增加，算法取得的路徑長度趨近于理論最優(yōu)值。但是此時算法迭代過程中并沒有加入對路徑的優(yōu)化策略，所形成的的路徑折彎過多。加入2.3中描述的路徑優(yōu)化策略后，算法的迭代過程如圖7所示?？梢钥闯觯噍^于未加入路徑策略時，此時擴展樹中的節(jié)點到起始點的路徑都經(jīng)過優(yōu)化大大減少了折彎的次數(shù)。

圖4 RRT* 算法

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

圖6 路徑長度

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

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

圖8 三維環(huán)境下生成的路徑

4 結(jié)論

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