基于ACO算法的變電站運載機器人路徑優化方法研究

嚴 宇,潘舒妍,黃文杰,江 維,樊紹勝

(1. 國網湖南省電力有限公司超高壓變電公司, 湖南 長沙 410004;2. 變電智能運檢國網湖南省電力有限公司實驗室, 湖南 長沙 410004;3. 長沙理工大學電氣與信息工程學院, 湖南 長沙 410114;4. 武漢紡織大學機械工程與自動化學院, 湖北 武漢 430073)

變電站運載機器人作為一種新型運輸機器人,其主要工作任務是按照既定的路徑規劃或者自主規劃的路徑進行變電站工具、貨物、作業人員的運輸[1-4].由于機器人在運輸時從起始點到達目標點會有多條行進路徑,而且要求機器人能夠自主避障,因此,在眾多行進路徑中按照一定的性能準則選取最優路徑,即對機器人的路徑進行最優規劃是提升機器人智能行為能力的關鍵.當前,在工業機器人領域路徑規劃已有較多的研究成果,總體可分為傳統路徑規劃算法[5]和智能路徑規劃算法[6]兩大類.傳統路徑規劃算法根據環境的不同可分為全局規劃和局部規劃,全局規劃為已知環境信息基本不變,而局部規劃是在未知環境中進行規劃,需要借助傳感器對局部環境進行信息感知才能實現機器人的自主尋跡和避障;智能路徑規劃算法包括遺傳算法、蟻群算法、粒子群算法等群體智能算法[7-11],已取得了一些實際應用成果.變電站運載機器人屬特種機器人行業,其工作于極端電力環境下,因此,變電檢修運載機器人對于路徑規劃的實時性和精確性要求高,亟需尋找一種實時性好、規劃精度高的算法.目前已有基于激光導航并結合蟻群算法的最優路徑規劃方法[12]、改進蟻群優化IACO算法[13]、模擬退火法[14]等,并在實際變電站進行了路徑規劃,提升了系統魯棒性和復雜環境下的規劃能力.機器人路徑規劃性能與算法本身及算法參數有關,特別是算法的參數對算法收斂性及收斂精度具有較大影響,會直接影響到機器人路徑規劃的實時性和路徑的精確性,因此,各類改進算法在機器人路徑規劃領域的應用層出不窮.

本文提出一種基于蟻群算法(ant colony algorithm,ACO)的變電站運載機器人最優路徑規劃算法.首先介紹ACO算法的基本原理和搜索過程,對變電站檢修運載機器人建立路徑規劃地圖;通過ACO算法與A*算法的仿真對比驗證ACO算法在處理復雜路徑問題上的優勢;采用不同參數對ACO算法路徑規劃性能進行仿真得到最優算法參數;通過機器人物理樣機在現場變電站中的測試與應用驗證了本文所提出算法的工程實用性.

1 ACO算法基本原理與參數分析

1.1 ACO算法原理

蟻群算法是模仿自然界中蟻群的覓食方式而提出的,即蟻群在存在障礙物的情況下能夠找到一條較短的路徑到達食物源或者洞穴.從生物學角度出發,單只螞蟻在行進過程中會釋放一種信息素物質,用于與其它螞蟻進行信息交流.信息素在自然環境中會以一定的速率揮發在空氣中,表現為濃度的降低,而蟻群則趨向于向信息素濃度高的方向行動.當系統開始工作時,首先需要設置各個邊上的信息素量,在此基礎上通過比較判斷是否符合最短路徑的要求,如果不滿足隨機分配變電站內工作點,并以此開始遍歷計數,如果計數次數小于工作點數目,則根據啟發式信息和信息素濃度信息開始訪問下一工作點,直到遍歷所有工作點為止,最終選擇所有完整路徑中最短路徑作為路徑的最優解,從而實現最優路徑的選擇.

1.2 ACO算法參數分析

1.2.1 概率轉移函數

ACO算法的概率轉移函數計算式為:

(1)

式中:τij為信息素殘留量;ηij為啟發式因子;α為信息素重要程度;β為啟發式因子重要程度.

信息素重要程度α值越大,信息素高濃度對個體的吸引力越大,個體越趨向于該條路線,搜索路徑的隨機性越弱,系統陷入局部最優解的可能性越大.啟發式因子重要程度β表示個體對于局部最優解的趨向性,β越大選擇局部最短路徑可能性越大,可以有效地降低系統的收斂速度,但易陷入局部最優解的困境.為了避免上述情況,通常會根據經驗要求α、β∈[0,5].

1.2.2 啟發式因子與信息素濃度

為了高效區分個體自身對于路徑的選擇,定義路徑距離的倒數為選擇該路徑的概率:

ηij=1/dij

(2)

通常ηij為一個介于0和1之間的小數.當群體完成了一次完整的迭代后,各個位置上的信息素濃度計算式為:

τij(t+n)=(1-ρ)τij(t)+Δτij

(3)

2 路徑規劃地圖建模

變電站地圖建模是路徑規劃的基礎,首先對實際環境柵格化,選擇合適的比例尺,要求能夠比較合理地得到障礙物與機器人之間的大小相對關系;然后人為設定禁行區域,該區域包含無法通過的障礙物區域、可能發生碰撞的區域和保證電力設備運行安全的安全區域,同時應考慮到變電站環境處于動態環境下的復雜情況;最后比對上述禁行區域和柵格化處理的最小單位,根據碰撞概率確定處理結果,得到如圖1所示的變電站二維點陣圖.

圖1 變電站二維點陣圖

3 仿真試驗與現場測試

3.1 不同算法路徑規劃比較分析

采用規格為20×20的二維柵格障礙圖,仿真比較A*算法和ACO算法.采用A*算法而不是Dijkstra算法是因為Dijkstra算法需要遍歷所有柵格,雖然相對來說更穩定可靠,但是每次增加一個新的節點都要進行大量計算,對于其中大部分偏遠節點來說,無疑是冗余的算力和大量的計算時間.仿真試驗采用路徑優先原則,對平滑程度要求不高.圖2為A*算法和ACO算法在簡單環境下分別擬合出的路徑情況,兩者路線規劃相似,且距離相同,A*算法耗時約10 s,ACO算法耗時約8 s.

(a) A*算法

在如圖3所示的復雜環境下,當起點和終點之間的路徑需要進行大量迂回才能到達時,A*算法和ACO算法都能搜索到相同最短路徑,但A*算法耗時約168 s,ACO算法耗時約9 s.

(a) A*算法

為了更好地探索算法路徑規劃效果,對A*算法在簡單和復雜環境下的搜索深度進行比較(見圖4).由圖4(a)可見,對簡單環境的起點和終點距離進行路徑擬合時,A*算法獲取結果較快、搜索范圍相對較少;由圖4(b)可見,在路徑需要偏轉一個稍大角度進行迂回時的復雜環境下,隨著搜索柵格數目的增多,每次增加的柵格都需要與上一次探索的所有節點進行一次更新,而搜索時沒有一個終點作為參考,數據的更新相對來說比較盲目,再次增加了運算量,最終搜索速度越來越慢.如果擴大地圖范圍,會由于同樣的原因造成整體搜索進度緩慢.

(a) 簡單環境

ACO算法中個體的初始位置雖然是隨機的,但是可以根據地圖規模適當調整種群數量,覆蓋地圖獲取更多信息的可能性也越大;ACO算法采取分布式控制方法,對運算要求不高,即使種群數量增長較多,但總時長并沒有增加太多;ACO算法獲取信息后決策形成最終路徑的速度也比較快.綜上所述,ACO算法在應對動態復雜環境時比A*算法表現更為優異.

3.2 ACO算法參數對檢修機器人路徑規劃的影響分析

為了增加路徑搜索難度,采用圖3的復雜環境以更好地模擬變電站實際環境,在控制單一變量的條件下進行仿真試驗.

3.2.1 種群規模的影響

以10次完整的路徑規劃為一個樣本容量,研究種群數量對于最優路徑規劃的影響,結果如表1和圖5所示.

表1 種群數量N對路徑迭代的影響

圖5 種群數量N對路徑迭代的影響

由表1和圖5可見:N=25時,由于收斂速度過慢,最短路徑誤差為5%;隨著種群數量的增加,獲得可接受較優路徑所耗費的迭代次數逐漸減少.種群數量越大,對應的覆蓋規劃區域面積也相對更廣,迭代出更優路徑的速度也更快.種群數量大意味著離群者的基數越大,當有離群者偏離航道,就有更多尋找潛在最優解的可能性.當N超過一定范圍后,對于提高尋找較優解效率的影響就比較小.另外,在N增加的過程中,每次迭代種群數量激增,會造成額外的算力消耗,經過迭代后會使用大量資源,所以通過不斷增加種群數量以達到最優路徑的目的不可取,需要尋找適合于變電站路徑規劃規模的種群數量.根據種群數量-平均迭代次數的迭代曲線,選取拐點所對應的種群數量作為算法最優參數,本文選取N=200.

3.2.2 信息素和啟發因子的影響

對照組路徑規劃效果和收斂曲線如圖6所示.

(a) 路徑規劃效果

當調整α時,靜態障礙物路徑規劃和路線距離沒有發生明顯變化,規劃路徑長度隨時間的變化如圖7所示.由圖7可見:隨著α的增加,路線的路徑長度趨于穩定,最終的實際規劃距離和實際最優解的結果相差不大,在可接受范圍內;α的增大提升了信息素在概率轉移中的權重,加快了機器人路徑搜索收斂速度,達到一個相對最短路徑速度也就越快;α并不是越大越好,在α較大時整個路徑雖然趨于收斂,但是和實際最短距離仍有差別,而且這個差別隨著α的增大而增大,逐漸偏離目標;反觀α=1時,雖然前期收斂速度較慢,但中后期保證了較好的收斂速率,最終獲得一個目前最優路線.這里推測為:雖然增加離群者路徑的采納概率,但是離群者中更優策略畢竟是少數,種群有被誤導的可能性;另外,由于是指數權重,會占用大量的計算資源,造成用時過長等問題,所以α也不宜過大.

圖7 信息素重要程度α對規劃路徑長度的影響

如圖8所示,隨著啟發因子重要程度β增加,迭代曲線收斂明顯.β直接體現了群體對于最短路徑的趨向性,β的增加可以有效提高路徑規劃效率,但存在算力占用問題,所以β設定值也不宜過大.

圖8 啟發因子重要程度β對規劃路徑長度的影響

綜上所述,信息素重要程度α與路徑收斂呈反相關,而啟發因子重要程度β與路徑收斂呈正相關,兩個參數共同影響變電站運載機器人路徑規劃的收斂速度,但是兩者都存在邊緣效應,當到達一定范圍后需要投入更多的資源,與收益增量不成比例.通過多輪試驗,結合實際情況,確定α=1、β=7作為一個比較折中的參數,既能保證一定的收斂速度又不至于占用過多資源.

3.2.3 信息素蒸發系數ρ的影響

ρ為信息素自然蒸發下的殘留量,在一定程度上決定了群體決策過程中采納現有規劃的趨向性.分別采用5組信息素蒸發系數進行比較,結果如圖9所示.

圖9 信息素蒸發系數ρ對規劃路徑長度的影響

由圖9可見:當ρ較小時,路徑距離有明顯的收斂趨勢,且隨著ρ的增大收斂趨勢加強;當ρ超過某一限定值時,隨著迭代次數的增加,路徑逐漸固定,不再出現距離減小趨勢,甚至當ρ到達0.9時,終值和理想最優路徑相差較遠.由式(3)可知:ρ越小,信息素殘留越多,在同重要程度因子的限制下,路徑決策會傾向于既往路徑,殘留信息素過多導致大量資源耗費在無效路徑的搜索上,會極大程度地影響算法的收斂速率;而ρ越大,殘留信息素越少,雖然可以減少無效路徑的搜索,但是對應的信息素能起到的作用會很小,有效路徑的搜索也可能被摒棄,最終形成的路線趨向于快速穩定而并非最短路徑.信息素蒸發系數最好控制在一定范圍內,在保證收斂速度的同時,還要兼顧終值誤差,防止出現負優化的情況.因此,在面對復雜的變電站環境時,ACO算法能夠針對變電站運載機器人路徑規劃工作進行最優路徑搜索,滿足不同任務的需求,且能根據環境要求適當調節各項重要參數以符合不同特點的實際環境,完成資源的最優配置,可保證搜索性能優于其他算法.

由仿真試驗結果可知,將地圖柵格單位長度定為1 m,在改變機器人體型時,仿真結果沒有多大改變;將地圖柵格單位長度定為1.5、2.0 m時,算法搜索速度明顯加快.由此可知,影響算法搜索速度的因素為地圖建模時柵格單位長度,而柵格寬度代表實際環境中道路寬度.因此,結合實際環境,對ACO算法進行合理的參數設置,能夠加快算法搜索的時間、提高搜索效率,進一步提高運載機器人的運載水平和智能性.

3.3 現場測試

為驗證本文提出機器人路徑規劃方法的可行性和工程實用性,通過系統集成開發了變電站運載機器人物理樣機系統,并在國網湖南省電力有限公司所轄的變電站區域內進行現場應用.圖10(a)為機器人在工區充電樁上充電;圖10(b)為機器人搭載重物;圖10(c)為操控人員通過人機交互系統設置目標點;圖10(d)為機器人根據集成的路徑規劃控制算法在變電站自主運行.人工設置變電站內01#充電樁為起始點,08#變壓器為終止點進行檢修工具運輸,起始點至終止點直線距離為324 m,取仿真試驗中的最優算法參數,通過A*算法和ACO算法進行路徑規劃對比測試,結果如表2所示.由表2可見,整個運載過程中兩種算法機器人能夠實現在變電站內無碰避障、選取最優路徑將所載工具準確運送至目標點,但ACO算法規劃路徑和耗時較短,說明基于ACO算法的機器人自主路徑規劃具有較強的工程實用性.

表2 兩種算法現場測試試驗性能對比

(a) 起始點充電

4 結語

針對變電站運載機器人的作業需求,本文提出一種基于ACO算法的變電站運載機器人最優路徑規劃方法.該算法能夠針對變電站運載機器人運載任務所需要的路徑規劃需求進行最優路徑搜索.通過建立機器人在變電站內的運載運動地圖,對ACO算法的優化性能進行了仿真試驗.變電站運載機器人在現場進行運行測試,與A*算法相比,ACO算法收斂速度更快、規劃路徑更短,更好地滿足了機器人在變電站內進行檢修工具自主運輸的需求,進一步提升了運載機器人的智能化和實用性水平.