江 南，吳振輝，吳凌健杰

(1.國網(wǎng)福州供電公司，福建 福州 350000；2.福建杭潤科技有限公司，福建 福州 350000)

1 引言

隨著科技的發(fā)展和進步以及電力系統(tǒng)自動化水平的提高，變電站的數(shù)量急劇增多，對變電站進行巡檢的工作量也越來越大。傳統(tǒng)的巡檢方式還是以人工為主，不僅效率低下，且由于受到巡檢員的素質(zhì)、狀態(tài)、心理等自身因素以及電磁輻射、風雪天氣等外部環(huán)境因素的影響，巡檢任務(wù)中容易發(fā)生事故或?qū)撛诘娘L險無法及時發(fā)現(xiàn)。因此，變電站智能輔助巡檢機器人的意義就顯得十分重大，而智能機器人的路徑規(guī)劃是變電站巡檢機器人導航的重要組成部分。

路徑規(guī)劃是個交叉領(lǐng)域，研究者眾多，與自動化、工業(yè)生產(chǎn)、交通運輸行業(yè)均密切相關(guān)，應(yīng)用在機器人、無人機、USV等無人控制器中。根據(jù)環(huán)境建模方式的不同可以分為基于決策論、物理、數(shù)學的三種建模方法。如模糊控制、狀態(tài)聚類等方法的屬于基于決策論的建模方式，通過在環(huán)境中采取不同的決策來進行路徑規(guī)劃，通過與環(huán)境的不斷交互來訓練被控制目標，主要用的求解方法是神經(jīng)網(wǎng)絡(luò)和強化學習；如線性規(guī)劃、最小樹規(guī)劃、動態(tài)規(guī)劃等方法屬于數(shù)學類的建模方式，通常應(yīng)用在VRP等路線規(guī)劃當中，通過單純形法、分支定界法等傳統(tǒng)算法或者如禁忌搜索、PSO算法等智能算法進行求解；最后一類是物理的建模方式，主要用到的方法有人工勢場法[1]、路線圖法、柵格法[2]、決策樹法等等，這一類方法都是考慮實際的物理空間而不是抽象的運籌建模，通常使用啟發(fā)式算法來進行求解，例如蟻群算法[3]、粒子群算法、模擬退火算法[4]或者多種智能算法融合后的混合啟發(fā)式算法[6]。

鏈接圖法[7](Maklink)是路線圖的一種建模方式，通過將復雜的障礙物空間進行簡化，成為簡單的多邊形體，再通過一系列的步驟以及規(guī)則連接多邊形的頂點或做頂點到邊界的垂線，將自由空間進行劃分。該方法通常將被規(guī)劃目標視為質(zhì)點，并把障礙物區(qū)域進行一定擴展，從而避免規(guī)劃目標與障礙物發(fā)生碰撞。但是，在變電站的巡檢區(qū)域中，會有許多狹窄的通道，對障礙物區(qū)域進行擴展會使得這些通道消失，從而導致巡檢機器人無法到達檢測區(qū)域。

人工勢場法[8]在路徑規(guī)劃中應(yīng)用的也非常廣泛，這是因為其具有簡潔的數(shù)學模型以及較為平滑的規(guī)劃路線。但是，人工勢場法也有其自身的缺陷[9]，盡管計算過程中可以輸入全局的環(huán)境信息，但只有被規(guī)劃目標周圍的力的作用才會對其移動造成影響，這就導致人工勢場法無法使用的全局環(huán)境信息，容易陷入極值點。例如：當終點處在障礙物區(qū)域之中時，斥力的作用可能導致機器人無法到達終點[10]；在狹窄的區(qū)域中斥力和引力的影響，可能導致規(guī)劃路線來回抖動，無法前進。

本文將鏈接圖法與人工勢場法進行結(jié)合，首先通過dijkstra算法在鏈接線上的節(jié)點上規(guī)劃出一條初始路線，并將路線上的節(jié)點作為人工勢場的引力牽引點，障礙物邊界進行離散化處理，將其上的點作為斥力點；然后，通過人工勢場法規(guī)劃出一條平滑的路線；最后，利用遺傳算法對節(jié)點的選擇進行優(yōu)化，不斷的迭代尋優(yōu)，最終可以在有凹多邊形的仿真環(huán)境中得到一條安全性高且較為平滑的可通行路徑。該方法可以解決人工勢場法容易陷入極值點的問題。

2 環(huán)境模型

2.1 改進的Maklink圖路徑規(guī)劃環(huán)境建模方法

Maklink圖是一種簡潔且有效的路徑規(guī)劃環(huán)境建模方法，它最早由Habib于1991年提出，并被廣泛應(yīng)用在機器人路徑規(guī)劃等領(lǐng)域當中。在Maklink圖的傳統(tǒng)應(yīng)用當中，為了避免障礙物與被規(guī)劃目標發(fā)生碰撞，通常是將障礙物的邊界進行一定的緩沖擴大，并且將被規(guī)劃目標視作一個質(zhì)點，不考慮其碰撞體積。該方法在障礙物相對總體空間較小的情況下是可行的，但當總體空間較小，對障礙物的擴張會導致原本可以通行的區(qū)域被覆蓋，尤其像是在變電站這樣過道狹窄的場景下。并且，如果障礙物的頂點較為尖銳，在該點處的擴張會占據(jù)更多的可通行空間，導致路線變長。同時，在尖銳的頂點處的規(guī)劃出來的路線會有急劇的轉(zhuǎn)折，如果通過圓的切線對路線進行平滑處理，可能會導致被規(guī)劃目標與障礙物發(fā)生碰撞，從而產(chǎn)生危險，如圖1(b)所示。如果要避免這種情況發(fā)生，障礙物的擴張至少是半倍的被規(guī)劃目標長度，這樣勢必會占據(jù)更多的原本可通行的空間。

Maklink圖原理是按一定規(guī)則將障礙物區(qū)域的頂點進行連接，從而構(gòu)成全局連通圖，但原初的算法無法解決凹多邊形的問題，存在凹多邊形構(gòu)建的全局連通圖會導致鏈接線穿過障礙物區(qū)域，從而導致無法規(guī)劃出安全的避開障礙物的可通行路線。因此，本文在考慮機器人尺度的前提下，對Maklink圖進行了改進，從而可以解決存在凹多邊形的情況。

首先，在考慮了巡檢機器人尺度之后，Maklink鏈接線所連接的通行區(qū)域可能無法滿足機器人的通行條件，所以應(yīng)當對鏈接線的繪制進行進一步的限制。在Maklink法的中，連接某一頂點與其它某一障礙物的頂點之前，計算該頂點到該障礙物的最短距離，最短距離產(chǎn)生的位置可能在該頂點與定點的連線(如圖2(a))或者與障礙物某一條邊做的垂線(如圖2(b))，當該連線小于巡檢機器人的寬度時，表示不滿足通行要求，從而構(gòu)建連通圖時不在考慮該連接線。

其次，如上所述，原本的Maklink算法無法處理有凹多邊形的情況，會導致規(guī)劃出的路線穿過障礙物區(qū)域。事實上，在巡檢過程中，凹多邊形的情況會大量遇見，尤其是在復雜的變電站與配電房之中。如果要解決凹多邊形，一種可行的方法是對凹多邊形進行劃分，從而形成多個凸多邊形后在進行全局連通圖的構(gòu)建，具體分解凹多邊形的方法如下：

a)依次選取凹多邊形的頂點，將該頂點相鄰的兩個凹多邊形頂點進行連接，如果這條連線沒有從凹多邊形中穿過，則該頂點被記錄為一個凹頂點，不斷重復找出所有的凹頂點。

b)隨機選取一個凹頂點p，將該頂點與該凹多邊形所有與其不相鄰的頂點進行連接，組成集合S。

c)選取集合S中最短的線段，該線段將凹頂點p所在的內(nèi)角切分成兩個內(nèi)角，判斷兩個內(nèi)角是否都小于180°，若是則記錄該連線，進入步驟e；若有一個內(nèi)角大于180°，則將該連線放入備選連接線集合A中

d)備選連接線結(jié)合中的線段將凹頂點p所在的內(nèi)角劃分為多個內(nèi)角，判斷是否每個內(nèi)角都小于180°。若存在大于180°的內(nèi)角，則返回步驟c，若不存在，則進入步驟e。

e)檢查是否將該凹多邊形的頂點都遍歷的一遍，若否，則返回步驟b，若是，則結(jié)束整個流程。

通過如上方法，可以將一個凹多邊形分解為多個凸多邊形，隨后便可繪制鏈接圖。但由于劃分后的凸多邊形的頂點有所重合，因此需要對凸多邊形進行一定的收縮，使凸多邊形的頂點不再重疊。通過對凸多邊形的每條邊進行向內(nèi)移動，距離選取為單位長度的一半。此時凸多邊形之間有著狹窄的通道，但由于對鏈接線區(qū)域的約束，其間巡檢機器人不可通行，于是可以使整片區(qū)域近似為一個不可通行的障礙區(qū)域，如圖2(c)所示。

圖2 改進Maklink示意圖

2.2 改進的人工勢場法的路徑規(guī)劃環(huán)境模型

在傳統(tǒng)的人工勢場法中，障礙物用一個質(zhì)點來表示，障礙物的實際大小由影響距離和斥力系數(shù)的大小來控制。規(guī)劃的目標只被終點的牽引力所吸引，這使得算法很容易進入到極值點或在一定范圍內(nèi)來回抖動。本文提出了一種基于Maklink圖的人工勢場法環(huán)境模型的改進。

在上文改進Maklink建模之后，通過Dijkstra算法在選取鏈接線上的節(jié)點中找到一條起止點的最短路徑來作為人工勢場法的預規(guī)劃路線，將該路線中的節(jié)點依次作為人工勢場法的引力牽引點。對于障礙物區(qū)域的描述，通常人工勢場法中都是簡化成一個質(zhì)點，但該方法精度較低，尤其凹多邊形更無法簡化成一個質(zhì)點的情況，因此本文將障礙物的邊界進行離散化處理，以巡檢機器人寬度的一半作為間隔，在障礙物的每個邊上放置斥力點，將一個障礙物邊界上的所有斥力點的合力來代表一個障礙物的對被規(guī)劃目標的影響，如圖3所示。通過該方法構(gòu)建的路徑規(guī)劃環(huán)境模型，通過人工勢場法進行求解，就可以得到一條安全性高且平滑的路徑，并解決算法原本容易陷入極值點的問題。

圖3 變電站環(huán)境模型

3 考慮巡檢機器人尺度的路徑規(guī)劃算法設(shè)計

3.1 算法流程圖

本文將人工勢場法與Maklink鏈接圖法進行結(jié)合實現(xiàn)了對變電站區(qū)域的路徑規(guī)劃，提高路線安全性的同時也避免了人工勢場法容易陷入極值點等問題。同時，本文又通過遺傳算法對每條鏈接線上節(jié)點的位置進行優(yōu)化，將節(jié)點位置進行遺傳編碼，每一條染色體對應(yīng)所有節(jié)點的位置，再通過Dijkstra算法在節(jié)點中找到一條最短路徑，把該路徑作為人工勢場法的預規(guī)劃路徑，人工勢場法求解之后得到的路徑長度作為染色體的適應(yīng)度值，最后不斷地通過遺傳算法的選擇、交叉、變異進行循環(huán)迭代，最終得到最優(yōu)的規(guī)劃路徑。算法具體流程圖如圖4所示。

圖4 考慮機器人尺度的路徑規(guī)劃算法流程圖

3.2 人工勢場法基本原理及改進

人工勢場法[12]的基本思想仿照電磁場對電荷的作用而構(gòu)建的虛擬力場，被規(guī)劃目標視為正電荷，障礙物同樣為正電荷對其產(chǎn)生斥力，斥力的大小與兩點間距離成反比，目標點為負電荷對被規(guī)劃目標產(chǎn)生引力，引力大小與兩點間距離成正比，最終被規(guī)劃目標在合力的影響下像著目標點前進。傳統(tǒng)人工勢場法路線規(guī)劃示意圖如圖5(a)所示。

圖5 人工勢場法作用原理示意圖

為了方便計算并且提高計算效率，本文對巡檢機器人的形狀進行了簡化，通過多邊形線段集對巡檢機器人的形狀進行表述，以便不會減少機器人的實際尺度以及占用過多的自由空間。如圖5(b)所示，在通過線段集對機器人外形進行描述之后，障礙物對機器人的排斥力不再由原來質(zhì)點間距離進行計算，而是通過點到多邊形的最短距離來進行計算，如前所述，點到多邊形的最短距離只會在點到多邊形的頂點或邊的垂線之間。這樣之后，可以有效地考慮機器人的尺度，從而保證了在狹窄的通道之下也能找到一條安全的可行路徑。

引力場和斥力場函數(shù)公式如下所示

Uatt(X)=0.5αρ2(X，Xg)

(1)

(2)

式中：α、β分別為引力與斥力系數(shù)；X、Xg、XO分別表示巡檢機器人模型的中心點、目標終點引力點、障礙物斥力點的笛卡爾系坐標位置；ρ(X，Xg)、ρ(X′，Xo)分別表示機器人中心點到目標點的距離和機器人邊界到障礙物的最短距離；ρ0為障礙物斥力點的斥力作用范圍。機器人所具有的的勢場勢能隨著距離越近就會越大，距離越遠則會越小，當機器人處在障礙物的最大影響距離之外時，所具有的的勢場勢能則為零。

通過對引力場和斥力場函數(shù)計算負梯度公式，則可以得到機器人受到的作用力：

(3)

(4)

機器人所受的合力為：

(5)

3.3 基于回轉(zhuǎn)半徑的最大轉(zhuǎn)向角控制

(6)

圖6 機器人最大轉(zhuǎn)向角約束

(7)

(8)

l=vn+1*t

(9)

圖7 計算機器人運動示意圖

3.4 切換目標點的判別方法

人工勢場法是通過中間引力點接續(xù)的引力作用指導巡檢機器人到達最終目標點，當中間節(jié)點距離障礙物較遠時，可以在到達該目標點一定距離之內(nèi)切換到下一個中間節(jié)點，直到到達最終點。但當節(jié)點距離障礙物過近的情況下，會導致無法到達目標點的一定范圍之內(nèi)，從而陷入來回徘徊的情形之中，此時需要在合適的時候跳出極值點，選取下一個節(jié)點作為目標點，本文給出的判別方法如下。

圖8 切換目標點的判別方法

4 仿真研究

為了驗證本文算法的有效性，在CPU為Intel Core3的計算機上用MATLAB軟件進行仿真。在200*200的區(qū)域內(nèi)設(shè)置變電站工作區(qū)域，共8個，其中右下角的障礙物區(qū)域為凹多邊形區(qū)域，仿真目標為尋找一條從起點到終點的安全性較高的可通行路線。參數(shù)設(shè)定為：巡航機器人寬度為4、長度為10、引力系數(shù)α的值為5、斥力勢場系數(shù)β的值為10、斥力作用范圍為10，起止點坐標分別為(10，130)、(150，50)。

仿真結(jié)果如圖9所示，圖中的虛線為Maklink圖和遺傳算法求解出的可行路徑，Dijkstra為預規(guī)劃路線，實線為本文算法計算出的結(jié)果?？梢钥闯?，本文算法相較于傳統(tǒng)的Maklink圖計算出的路徑會更為平滑，且與障礙物留有一定的安全距離，從而提高了路線安全性。下面通過相關(guān)指標對兩個路線進行定量分析。

圖9 原算法與改進后的機器人路徑規(guī)劃仿真結(jié)果

本文定義障礙物到機器人邊界的最小距離為最小安全距離，單純Maklink求解路線與本文算法結(jié)果的最小安全距離與機器人方向角的變化曲線圖如圖10所示，可以看出原算法某些時刻的最小安全距離小于零，會發(fā)生碰撞風險。比較航線角的變化情況也可以發(fā)現(xiàn)本文算法得到的路線更為平滑，而原算法會有突然地轉(zhuǎn)角，不符合巡檢機器人的運動規(guī)律。

圖10 規(guī)劃安全距離和路徑方向角曲線圖

5 結(jié)論

本文提出了一種對機器人進行路徑規(guī)劃的新方式，結(jié)合Maklink圖和人工勢場法得到優(yōu)化路徑，再利用遺傳算法迭代尋優(yōu)，最終可以在包含凹多邊形的變電站工作區(qū)域中得到一條平滑且安全性高的最短路徑，并且可以解決人工勢場法本身的局限問題，避免陷入極值點和消除震蕩點。最后利用計算機仿真并與原算法對比，驗證了本文算法的可行性與有效性。