運用人工勢場法與RRT 算法對比智能化路徑規(guī)劃

毛悅慈

（天津仁泓電力科技有限公司，天津 300385）

1 研究背景及意義

路徑規(guī)劃技術(shù)是目前很多技術(shù)領(lǐng)域研究的熱點，具有廣闊的應(yīng)用前景和科研價值，而路徑規(guī)劃算法的研究是其中的核心內(nèi)容。在特高壓線路鋪設(shè)領(lǐng)域也得到廣泛的應(yīng)用，如何將電路鋪設(shè)地高效化、合理化，并考慮成本是擺在電力設(shè)計人員面前的新課題[1]。隨著人工智能技術(shù)快速發(fā)展，比較實用的一種辦法就是可以考慮將其用于路徑規(guī)劃。實現(xiàn)電路鋪設(shè)智能化，從而也促使現(xiàn)有輸電線路三維數(shù)字化設(shè)計平臺的逐步升級完善[2]。因此，如何在新時代把人工智能技術(shù)加入已經(jīng)比較完善的路徑規(guī)劃中，以實現(xiàn)流程化及規(guī)范化，是新時代擺在廣大科研工作者面前的新挑戰(zhàn)。從上面的在線路中加入人工智能的相關(guān)功能進(jìn)行輔助的優(yōu)點不難看出，電網(wǎng)設(shè)計領(lǐng)域的智能化發(fā)展趨勢不容小覷。從研究的環(huán)境來看，路徑規(guī)劃可分為全局或局部規(guī)劃。根據(jù)對路徑規(guī)劃分類的研究，為了全面解決環(huán)境的規(guī)劃問題，需要使用全局規(guī)劃，部分路徑問題更實用的就是局部路徑規(guī)劃。所以要利用兩種方式的優(yōu)缺點結(jié)合來滿足人們的生產(chǎn)需要[3]。顧名思義，全局規(guī)劃全局性好，適用于大范圍，局部規(guī)劃在部分環(huán)境下會很實用。這兩種方法各有各的優(yōu)缺點，結(jié)合起來就十分完美了[4]。

本次課題主要使用了人工勢場法和RRT 算法兩種算法進(jìn)行路徑規(guī)劃，對企業(yè)要求的輸電線路路徑規(guī)劃，根據(jù)實際情況，選擇了進(jìn)行仿真實驗，在GIS 系統(tǒng)中選擇了部分有代表性的地理信息要素構(gòu)成的地圖，使用PyCharm Community Edition 2022.1 先進(jìn)行算法演示的實驗，隨后對已經(jīng)獲取的地圖進(jìn)行路徑規(guī)劃算法的使用，并對比兩種方式的優(yōu)缺點，同時對算法和結(jié)果加以改進(jìn)，使之更加符合企業(yè)的實際環(huán)境要求。

2 兩種算法的python 實現(xiàn)

2.1 人工勢場算法

作為一種局部的最優(yōu)化路線規(guī)劃算法[5]，人工勢場算法構(gòu)造簡便，設(shè)計工作量較小，實時性好，規(guī)劃出的道路均勻平滑而安全，并具備了相應(yīng)的魯棒性，在路線規(guī)劃中獲得了廣泛的運用。路徑規(guī)劃的過程中，本研究主要分了三步進(jìn)行。首先，通過從GIS 系統(tǒng)中獲取的地圖信息來對地理信息進(jìn)行建模，障礙點、可行點、加權(quán)重以及相應(yīng)的地圖數(shù)據(jù)參數(shù)都需要被保存為可以被計算機識別的數(shù)據(jù)信息流。其次，選取適當(dāng)?shù)乃惴ú⒓右匝芯?，針對所要進(jìn)行的簡單任務(wù)，對計算過程加以實際優(yōu)化，提升路線規(guī)劃效率。最后，通過經(jīng)過改進(jìn)的路徑規(guī)劃算法找到一個從當(dāng)前地址到目標(biāo)點位置的無碰撞最優(yōu)路線，再按照路徑信息和設(shè)置的物理參數(shù)進(jìn)行。然后是使用PyCharm 對人工勢場法進(jìn)行模擬運行。在進(jìn)行了多次仿真，并對結(jié)果進(jìn)行分析篩選后，出現(xiàn)了比較滿意的兩次結(jié)果。本研究設(shè)置四個機器人進(jìn)行尋路，將引力參數(shù)設(shè)置為，將斥力參數(shù)設(shè)置200，最小斥力距離設(shè)為2，地圖大小500*500，在地圖中設(shè)置三個靜態(tài)障礙，標(biāo)識為長方形，再設(shè)置動態(tài)障礙，將動態(tài)障礙設(shè)置成橫縱坐標(biāo)的變化率在0 到0.03 范圍內(nèi)，并規(guī)定隨機變化的區(qū)域，設(shè)置8 個動態(tài)障礙。三次實驗都取得了成功的結(jié)果，但是因為人工勢場法固有的缺陷，程序運行初期調(diào)試時出現(xiàn)了震蕩的情況，好在多次實驗可以避免失敗，還可以修改參數(shù)，增大斥力場的相關(guān)參數(shù)，改變受力也能避免這種情況。

圖1 人工勢場法模擬地圖規(guī)劃

2.2 RRT 算法

在RRT 算法python 語言實現(xiàn)方面，本研究選擇使用PyCharm 對人工勢場法進(jìn)行模擬運行。算法的運行相比于原來的RRT 算法有明顯的快慢之分，但是多次的迭代換來的是路徑的優(yōu)化，有利必有弊。這樣要是想繼續(xù)優(yōu)化，就需要 informed-方法，因為在生成父節(jié)點時使用的是在圓內(nèi)進(jìn)行尋找，而改進(jìn)后的方法使用了橢圓的方式，以起點和終點作為橢圓的兩個節(jié)點，而不用再使用圓內(nèi)等距采樣的方式，這樣可以節(jié)省算法的工作量，從而提高運算效率。本研究的實驗結(jié)果中改進(jìn)后能節(jié)省30%左右的時間。

3 實驗

進(jìn)行實驗部分，本研究抽取了一張地圖進(jìn)行部分截取，利用python 語言對地圖中的障礙，主要包括對建筑進(jìn)行了構(gòu)造，使用幾何圖形模擬障礙，并運用兩種算法分別進(jìn)行規(guī)劃，得到了兩種算法的規(guī)劃結(jié)果。在實驗中發(fā)現(xiàn)，雖然人工勢場法的程序相對簡單，對于計算機進(jìn)行大量計算并不是很困難的事情，但是實際效果上來講，使用RRT 算法較為合適。人工勢場法模擬了勢場，帶來的代價是需要大量的運算。而RRT法相對來講設(shè)置好步長，讓目標(biāo)自動尋路，需要的只是反復(fù)的尋徑，在一定程度上優(yōu)化了計算量。而且RRT 算法在近些年的發(fā)展十分迅速，也是領(lǐng)域內(nèi)相對前沿的發(fā)展方式，這種算法的未來潛力相對于發(fā)展比較完善的人工勢場法更加巨大，適合于進(jìn)行研究使用。第一次抽象實驗的結(jié)果表明，兩種方法都能成功規(guī)劃最優(yōu)路徑，但是速度有快有慢，同時結(jié)果也有相對優(yōu)劣之分。

這是使用人工勢場法的規(guī)劃結(jié)果，本研究采用了從地圖中截取部分的方法，再使用改進(jìn)了的人工勢場法進(jìn)行規(guī)劃。為了避免陷入局部最優(yōu)，采用的方法是構(gòu)造了拉普拉斯勢場。滿足拉普拉斯方程的實函數(shù)在實空間內(nèi)沒有局部最小點，而且最值只能在邊界上取到，這樣就有效地避免了陷入局部最優(yōu)。拉普拉斯方程的解，就是所要求的調(diào)和函數(shù)，而且因為二階可導(dǎo)性，導(dǎo)出的勢場函數(shù)還是光滑的。

實現(xiàn)人工勢場后，本研究使用同一張圖片再次使用RRT 算法進(jìn)行路徑規(guī)劃，得到了上面的結(jié)果。比較兩種方法，人工勢場法及其改進(jìn)需要大量的數(shù)學(xué)計算，而RRT 產(chǎn)生隨機樹后進(jìn)行判斷尋找距離最近的節(jié)點即可，節(jié)省了工作量。最后，使用matlab 軟件對一張地圖采用直接黑白化的方式進(jìn)行直接的規(guī)劃。在RRT 的matlab 實驗中，設(shè)計思路是先將彩色地圖設(shè)置成只有黑白的圖像，初始化地圖，設(shè)置起點和終點，設(shè)置步長，根據(jù)RRT 算法的原理對空間內(nèi)進(jìn)行搜索，先查找域內(nèi)所有滿足距離要求的節(jié)點，再將它們存放在一個集合內(nèi)，使用迭代比較距離父節(jié)點的大小，逐個進(jìn)行選擇直至找到距離最小的節(jié)點，作為下一個父節(jié)點進(jìn)行尋路。這樣一個節(jié)點一個節(jié)點地尋找，就可以找到一條由起點到達(dá)終點的路徑。再使用不同顏色將這條路徑進(jìn)行標(biāo)注，顯示在黑白圖和原圖上，就可以在原圖里表示出最終的規(guī)劃結(jié)果了。彩圖處理成黑白圖像，本研究的方法是設(shè)定三通道的像素值均大于某一值則為1，否則為0，就能將彩圖轉(zhuǎn)為黑白。轉(zhuǎn)為黑白后，再用隨機樹尋路找到結(jié)果路徑，最后用原圖表示一下路徑即可。這樣，就成功完成了相關(guān)算法在實際地圖中的規(guī)劃，而且結(jié)果也比較合適。

圖2 RRT 法模擬地圖規(guī)劃

4 結(jié)論

根據(jù)企業(yè)的要求，本論文選擇了兩種合適的路徑規(guī)劃算法，并將其分別運用于解決企業(yè)所給出的實際問題，得到結(jié)果后進(jìn)行比對，驗證了兩種方式分別的優(yōu)缺點。同時，對利用人工智能技術(shù)來規(guī)劃輸電線路進(jìn)行了深入探討，因此對一些用于路徑規(guī)劃的方法進(jìn)行了人工智能實驗。根據(jù)兩次成功的實驗，驗證了兩種算法的優(yōu)缺點。

人工勢場法，由于其優(yōu)越的數(shù)學(xué)分析和簡單性，常用于移動機器人的實時避碰和平滑路徑，但其固有缺陷很明顯。

首先，無法到達(dá)障礙物附近的目標(biāo)。當(dāng)目標(biāo)點在障礙物影響范圍內(nèi)時，障礙物斥力增加，重力迅速減小。

其次，存在局部極小問題。機器人在行進(jìn)過程中，合力方向與規(guī)劃路徑的運動方向在同一直線上，機器人無法有效避障，只能在一定范圍內(nèi)來回振動。

針對這兩種問題，改進(jìn)方法就是修改對應(yīng)的函數(shù)獲得最終結(jié)果。而RRT 算法從程序上來說，實際上編程要比人工勢場法更加復(fù)雜一些，對編程工作者的能力要求會更高一些。RRT 法相對來講確實方便了許多，運行速度也可以有很多方式改善，而且作為一門相對新穎的技術(shù)，網(wǎng)上也有許多相關(guān)的研究文獻(xiàn)，采用和人工智能結(jié)合或者數(shù)學(xué)改進(jìn)的方式使得算法更加優(yōu)化，所以如果對企業(yè)進(jìn)行推薦的話，可使用RRT 算法為核心，引入人工勢場的概念，對RRT 算法進(jìn)行改進(jìn)，以符合企業(yè)的實際要求。