基于IACO-ABC 算法的變電站巡檢機器人路徑規劃

薛 陽，俞志程，吳海東，張 寧

（上海電力大學 自動化工程學院，上海 200090）

0 引言

隨著我國科學技術不斷發展，自動化水平不斷提高，變電站無人值守模式逐漸成為變電站監控和保護的主流趨勢。變電站巡檢主要是對變電站內部設備包括儀器儀表等進行巡檢，通過定期檢查確保設備能夠穩定運行。采用機器人進行自動化巡檢，既能夠保證安全性和高效性，又能夠克服傳統人工變電站巡檢所存在的一些問題和缺陷，而巡檢機器人的路徑規劃則是機器人導航的關鍵技術之一[1]。

路徑規劃問題是指在存在障礙物的情況下，按照規定的要求，找到一條歷時盡可能短、路徑盡可能平滑的從起點到終點的無碰撞軌跡[2]。在上述問題中，首先需要考慮的是要找到實現不碰撞障礙物的軌跡，然后通過智能算法來判斷篩選滿足指標的最優軌跡[3]。變電站的監測點即檢查點是固定點，也就是說機器人要到達指定的位置完成檢查工作，可見變電站巡檢機器人的路徑規劃為全局路徑規劃[4]。

研究者們提出了不同算法來解決各種環境下的路徑規劃問題。機器人路徑規劃應用較普遍的算法是人工勢場法，如文獻[5]利用柵格法建立工作環境并且對傳統的ACO（蟻群優化）算法進行改進，通過仿真表明該算法收斂速度快且優化性能良好，但是算法所用迭代次數相對較高，優勢不夠明顯。RRT（快速擴展隨機樹）算法是另外一種常用的機器人路徑規劃算法，該算法可高效地搜索高維空間來獲得解，其搜索效率得到了研究者們的青睞，文獻[6]提出改進的RRT 算法以提高路徑規劃的質量，縮短機器人到達目標點運動時間，但由于隨機性較高，導致了算法的不確定性。近年來學者提出了多種仿生智能優化算法，并在機器人路徑規劃領域得到了發展，如：文獻[7]將改進的Dijkstra 算法與模擬退火算法相結合，應用到變電站智能巡檢機器人的全局路徑規劃中，可實現可靠運行，但面對復雜環境時仍然無法高效地完成規劃任務；文獻[8]為了提高傳統ACO算法在實現路徑規劃時的收斂速度和效率，并且解決傳統算法易陷入局部最優的問題，提出蟻群-粒子群組合優化算法，雖然能成功避免算法陷入局部最優的情況，但由于計算量較大導致收斂速度較慢。

本文根據機器人路徑規劃的特征，以ACO算法為基礎，針對其全局尋優能力差和搜索性能弱等缺點，結合ABC（人工蜂群）算法，提出IACO-ABC（改進蟻群-蜂群融合）算法，并將其應用到變電站機器人路徑規劃中，以提高系統的魯棒性以及在復雜工作環境下的路徑規劃能力，并通過仿真實驗進行了驗證。

1 ACO 算法與ABC 算法原理

1.1 ACO 算法的改進

ACO 算法模擬螞蟻在大自然中覓食時發現路徑的行為，是一種用來尋找優化路徑的概率性算法[9]。在該算法中，螞蟻會在蟻穴和食物之間往返的過程中留下一種稱為信息素的關鍵信息，螞蟻們會優先尋找并且往返于最短的路徑，因此越優的路徑中留下的信息素就越多，進而吸引蟻群中的大多數螞蟻聚集來此路徑[10]。當螞蟻遇到障礙物時，會首先尋找周圍信息素濃的地方，若周圍沒有信息素存在，那么螞蟻會隨機選擇路徑，避開障礙物[11]。

為了解決ACO 算法易陷入局部最優的問題并擴大搜索空間，提高搜索結果的多樣性，許多專家學者針對不同應用場景提出了多種改進的ACO 算法，如文獻[12]的相遇ACO 算法、文獻[13]的獎懲ACO 算法等。本文在此基礎上提出一種IACO（改進的蟻群優化）算法，其基本思想為：在初始位置初始化一群螞蟻，螞蟻們按照狀態轉移概率對下一節點進行選擇和移動，朝著最后的目的地出發[14]。整個蟻群系統采取確定性選擇與隨機性選擇相結合的選擇策略以避免出現停滯現象，且狀態轉移概率會在蟻群搜索最優路徑的過程中動態地變化。當位于地點i 的螞蟻隨機數q≤q0（q0為算法參數）時，按照式（1）前往下一個地點j；當q＞q0時，按照狀態轉移概率，利用輪盤賭法確定螞蟻下一個要去的地點。

式中：i 為可行柵格以及周圍8 個方向上相鄰柵格的節點；為信息素，α 為信息啟發式因子；為啟發值，β 為期望啟發式因子；J 為式（2）所計算出的概率；pij為方格i 到下一個方格j 的概率；τij為路徑（i，j）上的信息素濃度；ηij為方格i 轉移到方格j 的期望程度；A 為此時螞蟻k 下一步允許選擇的方格集合。

信息素只針對每次循環中找到最優路徑的螞蟻進行更新，更新規則如下：

式中：ρ 為信息素揮發系數；Q 為信息量增加強度；Lk（t）為第k 只螞蟻在本次循環中所走路徑的總長度。

當滿足迭代次數，螞蟻構建的當前最優路徑輸出為最終所得的解。

1.2 ABC 算法的改進

ABC 算法是受蜜蜂采蜜行為的啟發而提出的一種新型群智能優化算法，該算法被廣泛應用于許多領域來解決最優化問題[15]。ABC 算法將工作蜂群分為雇傭蜂與未雇傭蜂，而未雇傭蜂又分為觀察蜂和偵察蜂，每個族群分工不同，各司其職。雇傭蜂開發對應的蜜源并傳遞相應的信息給觀察蜂，每個蜜源的位置代表問題的一個可能解，蜜源的花蜜量對應于相應的解的適應度[16]。偵察蜂負責尋找更好的蜜源，而觀察蜂根據從雇傭蜂得到的信息，選擇自己認為好的蜜源并進行開采，若觀察蜂發現蜜源質量并不理想，放棄當前蜜源，轉為偵察蜂，繼續尋找更好的蜜源[17]。

通過分工合作，蜜蜂們能夠很快發現最好的蜜源，當偵察蜂觀察到陷入局部最優時，可隨機搜索其他可能的蜜源[18-19]。該算法具有強大的探索能力，并具有一定的解決算法陷入局部最優的處理方法，且蜜蜂在找尋最優蜜源的這個過程與機器人在路徑規劃上有很大的相似度，所以應用ABC 算法解決巡檢機器人的路徑規劃問題有著比較好的效果。

標準ABC 算法中，與第j 個蜜源相對應的雇傭蜂依據式（5）尋找新的蜜源：

式中：j=1，2，…，K，雇傭蜂與觀察蜂的個數均為K；d=1，2，…，D，D 為維數；為新蜜源位置；xjd為當前位置；φjd為區間[－1，1]上的隨機數；q≠j。

受到差分進化算法的啟發，文獻[20]提出改進雇傭蜂尋找新蜜源的公式來提高算法的局部搜索能力，本文在此基礎上提出自適應位置更新公式，雇傭蜂隨機選擇兩個不同個體以及當前最佳個體來尋找新的蜜源，充分利用種群個體信息來提高種群搜索過程中的多樣性，即：

式中：xgbest為當前最優解；xr1d與xr2d為隨機選擇的不同個體。等式右邊第1 項為當前位置；第2項為隨機位置差值所得，代表了蜜蜂的全局搜索能力；第3 項為當前最優對當前位置的影響；φ由個體之間的適應度值來確定。

式中：F 為[0，1]之間的隨機數；fr1，fr2，fb分別為xr1d，xr2d，xgbest對應的適應度值。

每個觀察蜂依據概率選擇一個蜜源，概率公式為：

式中：fj為可能解Xj的適應度值。

對于被選擇的蜜源，觀察蜂根據式（8）搜尋新的可能解。當所有的雇傭蜂和觀察蜂都搜索完整個搜索空間時，如果一個蜜源的適應度值在給定的步驟內（定義為控制參數“llimit”）沒有被提高，則丟棄該蜜源，而與該蜜源相對應的雇傭蜂變成偵察蜂，偵察蜂通過式（9）搜索新的可能解。

2 IACO-ABC 算法

基于兩種算法各自優勢，為了平衡算法的探索能力與收斂性能[21]，同時能夠提高算法的魯棒性和解決算法陷入局部最優的問題，提出IACOABC 算法。

IACO-ABC 算法的基本思想為：生成一個群體，將其分為兩個部分，Part1 為蜂群，Part2 為蟻群。通過比較兩者的當前最優解，學習對方種群有用的信息，取長補短。仿真實驗表明該交互融合算法具有較好的尋優能力以及魯棒性，并且在復雜工作環境下也能出色地完成任務。

IACO-ABC 算法流程如圖1 所示，具體步驟如下：

Step1：參數初始化；對融合算法的各個參數進行初始賦值，包括螞蟻數K、信息素矩陣τ、信息啟發式因子、期望啟發式因子、信息素總量Q、螞蟻迭代次數N、維數D、蜂群總數K、蜂群迭代次數G、限度llimit。

Step2：隨機生成初始解N，并將種群分為兩部分，Part1 的規模為n1，Part2 的規模為n2。

Step3：Part1 子群根據IACO 算法進行進化，得到全局最優解為gbest1；Part2 子群根據ABC 算法進行進化，得到全局最優解為gbest2。

Step4：比較gbest1與gbest2，若gbest1優于gbest2，將gbest1作為Part2 蜂群當前最優解再次進行迭代更新；若gbest2優于gbest1，則將gbest2作為最優解輸出。

Step5：比較當前最優解是否滿足終止條件輸出最優解，否則返回Step1。

圖1 IACO-ABC 算法流程

3 仿真結果

3.1 仿真環境建模

在機器人路徑規劃中柵格法非常實用，因此首先采用柵格法構建機器人的工作環境。如圖2所示，將變電站巡檢機器人規劃地圖分解為一系列小柵格，使用大小相同的柵格劃分環境空間，并用20×20 二值化柵格數組來表示環境。其中：黑格代表障礙物，在柵格數組中標為1；白格代表自由空間，在柵格數組中標為0；同時還存在陷阱，例如被黑格包圍著的白格同樣是不能經過的。最優路徑要求是在所有不能碰到黑色障礙物的路徑中的一條最短路徑。Start，End 分別表示機器人的起始和終止位置。

圖2 機器人工作環境柵格法建模

3.2 實驗結果與分析

將IACO-ABC 算法應用于實驗工作環境下巡檢機器人的路徑規劃，本文算法實現的軟件平臺為MATLAB 2017a，采用計算機配置為Intel Core i5-4570 CPU，8.00 GB RAM。為了體現改進融合算法的性能，IACO-ABC 算法中的蟻群參數與ABC 算法參數一致，并將仿真結果與ABC 算法結果進行分析對比，算法初始化參數對比見表1、表2。

表1 ACO 算法初始化參數

表2 改進算法蜂群初始化參數

仿真結果對比如圖3、圖4 所示。

圖3 ACO 算法仿真結果

圖4 IACO-ABC 算法仿真結果

為了更好地驗證融合算法的有效性與優勢，通過改變障礙物的分布情況以及擴大地圖的大小來進行進一步的仿真實驗。將原先的20×20 二值化柵格數組尺寸改為25×25，30×30 與35×35。隨著地圖尺寸的增加，障礙物的規模增大，尋優的難度系數增大，可以充分衡量算法對于不同尺度地圖的規劃能力，測試其魯棒性和泛化能力。

算法優化結果對比見表3。可以看出：當工作環境簡單時，融合算法的優勢并沒有體現出來，搜索時間反而相對較長；當面對復雜情況時，融合算法體現了其快速性與穩定性，在參數不變的前提下，IACO-ABC 算法有效地加快機器人全局尋優速度，減少了搜索時間，改善了算法執行效率。

表3 算法優化結果對比

4 結語

針對變電站巡檢機器人的路徑規劃，本文提出了IACO-ABC 算法。為了避免算法出現停滯現象，將融合算法的ACO 算法部分在全局信息已知的情況下進行改進，并提出一種蜂群自適應位置更新公式，提高了ABC 算法部分的局部搜索能力。對柵格地圖的仿真實驗結果表明，本文算法在復雜環境下的規劃能力和魯棒性能較好，并提高了路徑質量以及算法效率。