基于RRT*的母線布線路徑規(guī)劃算法

劉 沖,周 馳

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

0 引言

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

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

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

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

1 RRT* 算法

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

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

圖1 RRT*迭代過程

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

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

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

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

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

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

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

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

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

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

2.2 母線走向約束的處理

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

圖2 新的擴(kuò)展方式

2.3 corner點(diǎn)的選擇

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

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

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

3)兩個(gè)點(diǎn)的三個(gè)坐標(biāo)分量都不同，需要兩個(gè)(一對)corner點(diǎn)來連接xmin與xnew，此時(shí)有六對corner點(diǎn)對可供選擇。

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

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

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

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

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

圖3 corner點(diǎn)選擇

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

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

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

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

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

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

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

圖4 RRT* 算法

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

圖6 路徑長度

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

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

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

4 結(jié)論

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