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

薛 陽(yáng)，俞志程，吳海東，張 寧

（上海電力大學(xué) 自動(dòng)化工程學(xué)院，上海 200090）

0 引言

隨著我國(guó)科學(xué)技術(shù)不斷發(fā)展，自動(dòng)化水平不斷提高，變電站無(wú)人值守模式逐漸成為變電站監(jiān)控和保護(hù)的主流趨勢(shì)。變電站巡檢主要是對(duì)變電站內(nèi)部設(shè)備包括儀器儀表等進(jìn)行巡檢，通過(guò)定期檢查確保設(shè)備能夠穩(wěn)定運(yùn)行。采用機(jī)器人進(jìn)行自動(dòng)化巡檢，既能夠保證安全性和高效性，又能夠克服傳統(tǒng)人工變電站巡檢所存在的一些問(wèn)題和缺陷，而巡檢機(jī)器人的路徑規(guī)劃則是機(jī)器人導(dǎo)航的關(guān)鍵技術(shù)之一[1]。

路徑規(guī)劃問(wèn)題是指在存在障礙物的情況下，按照規(guī)定的要求，找到一條歷時(shí)盡可能短、路徑盡可能平滑的從起點(diǎn)到終點(diǎn)的無(wú)碰撞軌跡[2]。在上述問(wèn)題中，首先需要考慮的是要找到實(shí)現(xiàn)不碰撞障礙物的軌跡，然后通過(guò)智能算法來(lái)判斷篩選滿足指標(biāo)的最優(yōu)軌跡[3]。變電站的監(jiān)測(cè)點(diǎn)即檢查點(diǎn)是固定點(diǎn)，也就是說(shuō)機(jī)器人要到達(dá)指定的位置完成檢查工作，可見(jiàn)變電站巡檢機(jī)器人的路徑規(guī)劃為全局路徑規(guī)劃[4]。

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

本文根據(jù)機(jī)器人路徑規(guī)劃的特征，以ACO算法為基礎(chǔ)，針對(duì)其全局尋優(yōu)能力差和搜索性能弱等缺點(diǎn)，結(jié)合ABC（人工蜂群）算法，提出IACO-ABC（改進(jìn)蟻群-蜂群融合）算法，并將其應(yīng)用到變電站機(jī)器人路徑規(guī)劃中，以提高系統(tǒng)的魯棒性以及在復(fù)雜工作環(huán)境下的路徑規(guī)劃能力，并通過(guò)仿真實(shí)驗(yàn)進(jìn)行了驗(yàn)證。

1 ACO 算法與ABC 算法原理

1.1 ACO 算法的改進(jìn)

ACO 算法模擬螞蟻在大自然中覓食時(shí)發(fā)現(xiàn)路徑的行為，是一種用來(lái)尋找優(yōu)化路徑的概率性算法[9]。在該算法中，螞蟻會(huì)在蟻穴和食物之間往返的過(guò)程中留下一種稱為信息素的關(guān)鍵信息，螞蟻們會(huì)優(yōu)先尋找并且往返于最短的路徑，因此越優(yōu)的路徑中留下的信息素就越多，進(jìn)而吸引蟻群中的大多數(shù)螞蟻聚集來(lái)此路徑[10]。當(dāng)螞蟻遇到障礙物時(shí)，會(huì)首先尋找周圍信息素濃的地方，若周圍沒(méi)有信息素存在，那么螞蟻會(huì)隨機(jī)選擇路徑，避開(kāi)障礙物[11]。

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

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

信息素只針對(duì)每次循環(huán)中找到最優(yōu)路徑的螞蟻進(jìn)行更新，更新規(guī)則如下：

式中：ρ 為信息素?fù)]發(fā)系數(shù)；Q 為信息量增加強(qiáng)度；Lk（t）為第k 只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。

當(dāng)滿足迭代次數(shù)，螞蟻構(gòu)建的當(dāng)前最優(yōu)路徑輸出為最終所得的解。

1.2 ABC 算法的改進(jìn)

ABC 算法是受蜜蜂采蜜行為的啟發(fā)而提出的一種新型群智能優(yōu)化算法，該算法被廣泛應(yīng)用于許多領(lǐng)域來(lái)解決最優(yōu)化問(wèn)題[15]。ABC 算法將工作蜂群分為雇傭蜂與未雇傭蜂，而未雇傭蜂又分為觀察蜂和偵察蜂，每個(gè)族群分工不同，各司其職。雇傭蜂開(kāi)發(fā)對(duì)應(yīng)的蜜源并傳遞相應(yīng)的信息給觀察蜂，每個(gè)蜜源的位置代表問(wèn)題的一個(gè)可能解，蜜源的花蜜量對(duì)應(yīng)于相應(yīng)的解的適應(yīng)度[16]。偵察蜂負(fù)責(zé)尋找更好的蜜源，而觀察蜂根據(jù)從雇傭蜂得到的信息，選擇自己認(rèn)為好的蜜源并進(jìn)行開(kāi)采，若觀察蜂發(fā)現(xiàn)蜜源質(zhì)量并不理想，放棄當(dāng)前蜜源，轉(zhuǎn)為偵察蜂，繼續(xù)尋找更好的蜜源[17]。

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

標(biāo)準(zhǔn)ABC 算法中，與第j 個(gè)蜜源相對(duì)應(yīng)的雇傭蜂依據(jù)式（5）尋找新的蜜源：

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

受到差分進(jìn)化算法的啟發(fā)，文獻(xiàn)[20]提出改進(jìn)雇傭蜂尋找新蜜源的公式來(lái)提高算法的局部搜索能力，本文在此基礎(chǔ)上提出自適應(yīng)位置更新公式，雇傭蜂隨機(jī)選擇兩個(gè)不同個(gè)體以及當(dāng)前最佳個(gè)體來(lái)尋找新的蜜源，充分利用種群個(gè)體信息來(lái)提高種群搜索過(guò)程中的多樣性，即：

式中：xgbest為當(dāng)前最優(yōu)解；xr1d與xr2d為隨機(jī)選擇的不同個(gè)體。等式右邊第1 項(xiàng)為當(dāng)前位置；第2項(xiàng)為隨機(jī)位置差值所得，代表了蜜蜂的全局搜索能力；第3 項(xiàng)為當(dāng)前最優(yōu)對(duì)當(dāng)前位置的影響；φ由個(gè)體之間的適應(yīng)度值來(lái)確定。

式中：F 為[0，1]之間的隨機(jī)數(shù)；fr1，fr2，fb分別為xr1d，xr2d，xgbest對(duì)應(yīng)的適應(yīng)度值。

每個(gè)觀察蜂依據(jù)概率選擇一個(gè)蜜源，概率公式為：

式中：fj為可能解Xj的適應(yīng)度值。

對(duì)于被選擇的蜜源，觀察蜂根據(jù)式（8）搜尋新的可能解。當(dāng)所有的雇傭蜂和觀察蜂都搜索完整個(gè)搜索空間時(shí)，如果一個(gè)蜜源的適應(yīng)度值在給定的步驟內(nèi)（定義為控制參數(shù)“l(fā)limit”）沒(méi)有被提高，則丟棄該蜜源，而與該蜜源相對(duì)應(yīng)的雇傭蜂變成偵察蜂，偵察蜂通過(guò)式（9）搜索新的可能解。

2 IACO-ABC 算法

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

IACO-ABC 算法的基本思想為：生成一個(gè)群體，將其分為兩個(gè)部分，Part1 為蜂群，Part2 為蟻群。通過(guò)比較兩者的當(dāng)前最優(yōu)解，學(xué)習(xí)對(duì)方種群有用的信息，取長(zhǎng)補(bǔ)短。仿真實(shí)驗(yàn)表明該交互融合算法具有較好的尋優(yōu)能力以及魯棒性，并且在復(fù)雜工作環(huán)境下也能出色地完成任務(wù)。

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

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

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

Step3：Part1 子群根據(jù)IACO 算法進(jìn)行進(jìn)化，得到全局最優(yōu)解為gbest1；Part2 子群根據(jù)ABC 算法進(jìn)行進(jìn)化，得到全局最優(yōu)解為gbest2。

Step4：比較gbest1與gbest2，若gbest1優(yōu)于gbest2，將gbest1作為Part2 蜂群當(dāng)前最優(yōu)解再次進(jìn)行迭代更新；若gbest2優(yōu)于gbest1，則將gbest2作為最優(yōu)解輸出。

Step5：比較當(dāng)前最優(yōu)解是否滿足終止條件輸出最優(yōu)解，否則返回Step1。

圖1 IACO-ABC 算法流程

3 仿真結(jié)果

3.1 仿真環(huán)境建模

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

圖2 機(jī)器人工作環(huán)境柵格法建模

3.2 實(shí)驗(yàn)結(jié)果與分析

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

表1 ACO 算法初始化參數(shù)

表2 改進(jìn)算法蜂群初始化參數(shù)

仿真結(jié)果對(duì)比如圖3、圖4 所示。

圖3 ACO 算法仿真結(jié)果

圖4 IACO-ABC 算法仿真結(jié)果

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

算法優(yōu)化結(jié)果對(duì)比見(jiàn)表3?？梢钥闯觯寒?dāng)工作環(huán)境簡(jiǎn)單時(shí)，融合算法的優(yōu)勢(shì)并沒(méi)有體現(xiàn)出來(lái)，搜索時(shí)間反而相對(duì)較長(zhǎng)；當(dāng)面對(duì)復(fù)雜情況時(shí)，融合算法體現(xiàn)了其快速性與穩(wěn)定性，在參數(shù)不變的前提下，IACO-ABC 算法有效地加快機(jī)器人全局尋優(yōu)速度，減少了搜索時(shí)間，改善了算法執(zhí)行效率。

表3 算法優(yōu)化結(jié)果對(duì)比

4 結(jié)語(yǔ)

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