機(jī)器人導(dǎo)航路徑的動態(tài)分級蟻群算法規(guī)劃策略

王槐彬，彭 雪，周詩源，夏小云

（1.廣東交通職業(yè)技術(shù)學(xué)院，廣東 廣州 510650；2.廣東技術(shù)師范大學(xué)，廣東 廣州 510665；3.嘉興學(xué)院，浙江 嘉興 314001）

1 引言

隨著人工智能技術(shù)的迅猛發(fā)展，以移動機(jī)器人為代表的智能生產(chǎn)和智能服務(wù)正加速形成。而機(jī)器人應(yīng)用環(huán)境的多樣性、復(fù)雜性對機(jī)器人路徑規(guī)劃方法提出了更高要求[1]，因此研究機(jī)器人路徑規(guī)劃方法具有指導(dǎo)意義和實用價值。

機(jī)器人路徑規(guī)劃的早期成果主要為靜態(tài)環(huán)境下全局路徑規(guī)劃，常見的方法有柵格法、可視圖法、A*算法等，此類算法原理簡單、規(guī)劃效率低，之后的研究主要是對這幾類方法的改進(jìn)或方法的結(jié)合；當(dāng)靜態(tài)環(huán)境下全局路徑規(guī)劃無法滿足機(jī)器人實際應(yīng)用時，出現(xiàn)了各類仿生算法應(yīng)用于機(jī)器人路徑規(guī)劃，一直延續(xù)至今仍是機(jī)器人路徑規(guī)劃研究的主要方向和熱點。文獻(xiàn)[2]提出了改進(jìn)人工勢場算法，解決了目標(biāo)不可達(dá)、局部極值問題，同時降低了算法計算量并提高了路徑平滑度；文獻(xiàn)[3]提出了變參數(shù)螢火蟲算法，并應(yīng)用于Maklink路徑的二次優(yōu)化，在一定程度上減少了路徑長度；文獻(xiàn)[4]提出了多目標(biāo)遺傳算法，并將其應(yīng)用于對雙焊接機(jī)器人協(xié)調(diào)路徑求解，得到了雙焊接機(jī)器人最佳路徑。以上研究成果對機(jī)器人導(dǎo)航技術(shù)都起到了一定的促進(jìn)作用，隨著算法性能的提高和硬件的發(fā)展，機(jī)器人路徑規(guī)劃技術(shù)仍有較大的研究空間。

研究了靜態(tài)環(huán)境下全局路徑規(guī)劃問題，建立了工作環(huán)境的蜂巢柵格模型，相比于方形柵格的轉(zhuǎn)彎角度和避障路徑比有所減小；提出了動態(tài)分級蟻群算法并應(yīng)用于路徑規(guī)劃中，達(dá)到了提高路徑質(zhì)量和減少算法運行時間的目的。

2 蜂巢柵格模型

2.1 蜂巢環(huán)境模型

蜂巢柵格是參考傳統(tǒng)方形柵格的思想加以改進(jìn)而提出的，如圖1所示。使用邊長為的蜂巢柵格將機(jī)器人工作環(huán)境進(jìn)行分割。對蜂巢柵格內(nèi)的障礙物疊加上機(jī)器人半徑，從而可以將機(jī)器人視為一個質(zhì)點。使用傳統(tǒng)方形柵格的膨化處理方法，未滿一個柵格的障礙物將其膨化到整個蜂巢柵格內(nèi)。障礙物柵格賦屬性值為“1”，不含有障礙物的柵格賦屬性值為“0”。

圖1 蜂巢柵格模型Fig.1 Honeycomb Grid Model

2.2 蜂巢模型與柵格模型對比

從轉(zhuǎn)向角和避障路徑比兩個方面對方形柵格和蜂巢柵格模型進(jìn)行比較。

（1）轉(zhuǎn)向角。機(jī)器人遇到障礙物時，傳統(tǒng)方形柵格轉(zhuǎn)向時的轉(zhuǎn)向角為90°，而蜂巢柵格的轉(zhuǎn)向角為30°，說明使用蜂巢柵格的避障轉(zhuǎn)向角較小，路徑更加平滑，可以提高機(jī)器人運動的安全性，如圖2所示。

圖2 兩種柵格比較Fig.2 Comparation of the Two Kind of Grids

（2）避障路徑比。將避障路徑比定義為：機(jī)器人避開單位長度的障礙物需要繞行的距離。紅色實線為直線行駛時的碰撞路線，黑色實線為避障路線，如圖2所示。則對于方形柵格來講，避障路徑比為，蜂巢柵格的避障路徑比為由此可以看出，傳統(tǒng)方形柵格避開單位長度的障礙物需繞行1.414單位距離，而蜂巢柵格避開單位長度的障礙物只需繞行1.155單位距離，因此從避障路徑比的角度講，蜂巢柵格優(yōu)于方形柵格。

（3）使用 ACS蟻群算法[5]分別在（30×30）的方形柵格地圖和蜂巢柵格地圖上進(jìn)行路徑規(guī)劃，ACS蟻群算法原理在下節(jié)中給出，規(guī)劃出的路徑和路徑長度隨迭代次數(shù)的變化過程，如圖3所示。

圖3 兩種柵格的路徑比較Fig.3 Path Comparation of the Two Kind of Grids

對比圖3中的3幅圖，可以看出，在蜂巢柵格環(huán)境下規(guī)劃出的路徑明顯比方形柵格環(huán)境下更加平滑。由圖3（c）可以看出，蜂巢柵格環(huán)境下的路徑短于方形柵格環(huán)境下的路徑，且收斂時的迭代次數(shù)略少于方形柵格環(huán)境，因此從路徑長度和平滑性角度講，蜂巢柵格模型優(yōu)于方形柵格模型。

3 ACS蟻群算法

3.1 路徑選擇概率

在ACS蟻群算法中，螞蟻由城市i到城市j的選擇方法使用偽隨機(jī)概率進(jìn)行構(gòu)造，即：

式中：S—螞蟻最終選擇的城市；allowedi—城市i的可選城市；τij—城市ij間的信息素濃度；α—信息素因子；ηij—城市ij間的啟發(fā)信息，在旅行商問題中設(shè)置為城市ij間距離的倒數(shù)，在這里設(shè)置為城市j與目標(biāo)點距離；β—啟發(fā)信息因子；q0—（0，1）間的一個常數(shù)；q—（0，1）間的隨機(jī)數(shù)；當(dāng) q≤q0時使用式（1）中的偽隨機(jī)比例公式選擇下一城市j，當(dāng)q>q0時使用輪盤賭[6]選擇下一城市j，即：

3.2 局部與全局信息素更新

信息素更新方法分為局部信息素更新和全局信息素更新兩種。局部信息素更新是螞蟻每完成一次城市選擇就對相應(yīng)的路徑信息素進(jìn)行更新，這種對所有螞蟻走過路徑均進(jìn)行信息素更新的方法可以減小路徑之間的信息素差異，增強(qiáng)算法的多樣性，提高算法全局搜索能力。局部信息素更新方法[7]為：

式中：ρ—信息素?fù)]發(fā)率；τ0—信息素初始值。

全局信息素更新是所有螞蟻完成一次迭代后只對最優(yōu)路徑上的信息素進(jìn)行更新，這種信息素更新方式會逐漸拉大較優(yōu)路徑與較差路徑上的信息素濃度差距，促進(jìn)算法收斂，但是卻容易陷入局部最優(yōu)。全局信息素更新方法[8]為：

式中：Δτij—路徑ij上信息素增量；Lop—最優(yōu)路徑長度。

4 動態(tài)分級蟻群算法

4.1 動態(tài)分級策略

在人工蜂群算法中，根據(jù)蜜蜂的適應(yīng)度將蜂群劃分為引領(lǐng)蜂、跟隨蜂和偵查蜂三個等級[9-10]，參考這種分級思想，將蟻群分為尋優(yōu)蟻和偵查蟻兩個等級，其中適應(yīng)度靠前的螞蟻定義為尋優(yōu)蟻，使用較大的信息素因子α，突出較優(yōu)路徑上信息素對螞蟻的引導(dǎo)作用，促進(jìn)算法收斂；適應(yīng)度靠后的螞蟻定義為偵查蟻，使用較大的啟發(fā)信息因子β，突出啟發(fā)信息對螞蟻的牽引作用，負(fù)責(zé)開發(fā)較優(yōu)路徑之外的路徑，尋找更多優(yōu)質(zhì)解而提高解的質(zhì)量。動態(tài)分級算子設(shè)置為：

式中：Lop—最優(yōu)路徑長度；Lk—螞蟻k的路徑長度；f（Lk）—螞蟻k的適應(yīng)度函數(shù)。

設(shè)置一個偵察蟻與尋優(yōu)蟻的分級閾值M∈（0，1），當(dāng)0

4.2 信息素動態(tài)加權(quán)更新

前文中已經(jīng)分析，局部信息素更新能夠較小路徑間信息素差異，增強(qiáng)算法多樣性，但是收斂性不足；全局信息素更新能夠增大不同路徑間信息素差異，提高算法收斂性，但是易收斂于局部最優(yōu)。為了同時兼顧局部信息素更新和全局信息素更新的優(yōu)勢，提出了信息素動態(tài)加權(quán)更新策略，使尋優(yōu)蟻和偵察蟻執(zhí)行不同權(quán)重的信息素更新策略，為：

式中：Δτij—路徑 ij上的信息素增量；—螞蟻k經(jīng)過路徑ij時產(chǎn)生的信息素增量；N—螞蟻規(guī)模；λ1>λ2>0—加權(quán)系數(shù)。

當(dāng)螞蟻為尋優(yōu)蟻時，使用式（6）中的第二式更新，也即使用較大的權(quán)重λ1更新信息素，同時路徑越優(yōu)則適應(yīng)度函數(shù)f（Lk）也就越大，通過加權(quán)和適應(yīng)度函數(shù)的構(gòu)造方式，使越優(yōu)路徑上的信息素越濃。當(dāng)螞蟻為偵察蟻時，使用式（6）中的第三式更新，通過小權(quán)重和小適應(yīng)度值使較差路徑上信息素濃度較低。由以上分析可知，這種信息素更新方式，即使用了局部信息素更新中的全部螞蟻更新，減小了路徑間信息素的差異，同時也參考了全局信息素更新中的有差異更新思想，保證了較優(yōu)路徑上具有更濃的信息素。加權(quán)系數(shù)λ1、λ2不可相差太大，否則會失去分級加權(quán)的意義。經(jīng)過大量實驗驗證，當(dāng)λ1=4、λ2=2時算法搜索性能最佳。

4.3 蟻群混合與重新分級

在算法的第一次迭代過程中，蟻群按照傳統(tǒng)的ACS算法進(jìn)行。之后每完成一次迭代就將所有螞蟻混合，按照搜索的路徑適應(yīng)度進(jìn)行重新分級，這樣能夠保證“表現(xiàn)進(jìn)步”的偵查蟻升級為尋優(yōu)蟻，而“表現(xiàn)后退”的尋優(yōu)蟻降級為偵查蟻。通過這種方式確保較優(yōu)路徑全部在尋優(yōu)蟻群中，充分發(fā)揮較優(yōu)螞蟻信息素對其他螞蟻的引導(dǎo)作用。

另外，表現(xiàn)較好的偵查蟻將較優(yōu)位置帶入到了尋優(yōu)蟻群中，是對尋優(yōu)蟻群的一種擾動，在尋優(yōu)蟻陷入局部極值的情況下有助于其逃離局部最優(yōu)。

4.4 算法流程

將提出的動態(tài)分級策略、信息素動態(tài)加權(quán)更新方法、混合重新分級方法代入到蟻群算法中，制定動態(tài)分級蟻群算法流程為：

（1）初始化算法參數(shù)，包括蟻群規(guī)模N、位置維度D、算法最大迭代次數(shù)tmax等；

（2）將N只螞蟻全部放置在起始點；

（3）螞蟻按照式（1）和式（2）選擇下一節(jié)點；

（4）當(dāng)所有螞蟻到達(dá)目標(biāo)點，將螞蟻按照適應(yīng)度值進(jìn)行分級，迭代次數(shù)加1；

（5）偵查蟻和尋優(yōu)蟻按照各自的選擇公式進(jìn)行路徑規(guī)劃，當(dāng)完成一次迭代后，按照各自的信息素更新方式進(jìn)行信息素更新；

（6）將所有螞蟻混合，按照規(guī)劃路徑的適應(yīng)度值重新進(jìn)行分級，迭代次數(shù)加1；

（7）判斷是否達(dá)到最大迭代次數(shù)，若是輸出最優(yōu)螞蟻，算法結(jié)束；若否則轉(zhuǎn)至（5）直至算法結(jié)束。

5 仿真分析

在前文中從轉(zhuǎn)彎角、避障路徑比、路徑質(zhì)量等三個角度對比了蜂巢柵格與方形柵格，證明了蜂巢柵格優(yōu)于方形柵格，所以本節(jié)不再對蜂巢柵格進(jìn)行驗證，而對動態(tài)分級蟻群算法從兩個方面進(jìn)行驗證：一是迭代過程中螞蟻的多樣性，二是動態(tài)分級蟻群算法在蜂巢環(huán)境中路徑規(guī)劃性能。

5.1 動態(tài)分級蟻群算法多樣性驗證

為了對比分析動態(tài)分級蟻群算法與蟻群算法在迭代過程中的算法多樣性，以標(biāo)準(zhǔn)TSPILP庫中的KroA100測試集為例進(jìn)行仿真驗證。算法最大迭代次數(shù)設(shè)置為2000，通過設(shè)置程序執(zhí)行斷點，當(dāng)算法執(zhí)行至200、500、1000、1500和2000次時統(tǒng)計螞蟻路徑長度的標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差越大表示蟻群多樣性越好，標(biāo)準(zhǔn)差越小表示蟻群越集中，則蟻群多樣性越差。路徑多樣性隨迭代次數(shù)變化過程，如圖4所示。

圖4 路徑多樣性分析Fig.4 Analysis of Path Diversity

從圖4中可以看出，在（500～1000）代之間，動態(tài)分級蟻群算法的多樣性逐漸下降，這是因為經(jīng)過前期的迭代算法進(jìn)入以尋優(yōu)蟻為主導(dǎo)的收斂階段，使得蟻群向較優(yōu)路徑靠攏，導(dǎo)致蟻群多樣性下降。而在（1000～1500）代，動態(tài)分級蟻群算法的蟻群多樣性逐漸增大，是以偵查蟻為主導(dǎo)的蟻群不斷探索開發(fā)新路徑，導(dǎo)致蟻群多樣性提高。從整體上來講，在整個迭代過程中，動態(tài)分級蟻群算法的蟻群多樣性優(yōu)于蟻群算法，說明在蟻群中設(shè)置偵查蟻來探索新路徑，提高路徑多樣性是可行而有效的。

5.2 路徑規(guī)劃性能驗證

在（40×50）的蜂巢柵格環(huán)境中分別使用動態(tài)分級蟻群算法和蟻群算法進(jìn)行路徑規(guī)劃，設(shè)置算法最大迭代次數(shù)為200，兩種算法各獨立運行10次進(jìn)行路徑規(guī)劃，10次規(guī)劃中最優(yōu)路徑長度隨迭代過程的變化曲線，如圖5所示。

圖5 路徑長度迭代過程Fig.5 Path Length Iteration Process

從圖5中可以看出，動態(tài)分級蟻群算法規(guī)劃的最優(yōu)路徑長度明顯短于蟻群算法，且收斂時的迭代次數(shù)也少于蟻群算法。蟻群算法與動態(tài)分級蟻群算法規(guī)劃的最優(yōu)路徑，如圖6所示。工作環(huán)境中所有障礙物膨脹為圓形，一種柵格為起始柵格，另一種柵格為目標(biāo)柵格。

圖6 最優(yōu)路徑Fig.6 Optimal Path

統(tǒng)計兩種算法10次獨立尋優(yōu)的最優(yōu)值、方差值、平均運行時間和平均收斂次數(shù)，如表1所示。

表1 路徑規(guī)劃統(tǒng)計結(jié)果Tab.1 Path Planning Statistics Result

從圖6和表1可以看出，蟻群算法和動態(tài)分級蟻群算法各自獨立運行10次，蟻群算法搜索的最優(yōu)路徑長度為59.21，動態(tài)分級算法最優(yōu)路徑長度為46.11，路徑長度減少了22.12%；且從10次搜索最優(yōu)路徑長度的標(biāo)準(zhǔn)差看，動態(tài)分級蟻群算法的搜索穩(wěn)定性遠(yuǎn)遠(yuǎn)優(yōu)于蟻群算法。從算法的平均運行時間看，動態(tài)分級蟻群算法比蟻群算法減少了32.33%，平均迭代次數(shù)減少了20.87%。這是因為動態(tài)分級蟻群算法根據(jù)適應(yīng)度排序，自適應(yīng)的將螞蟻分為尋優(yōu)蟻和偵察蟻兩類，尋優(yōu)蟻更加注重較優(yōu)路徑的牽引作用，使算法快速搜索；而偵察蟻注重啟發(fā)信息的引導(dǎo)作用，使算法探索新路徑。在信息素更新時，根據(jù)不同蟻態(tài)和適應(yīng)度構(gòu)造信息素更新方法，使信息素兼顧了差異性和普更性，在算法的收斂速度和尋優(yōu)精度間取得了平衡。

6 結(jié)論

研究了機(jī)器人在靜態(tài)環(huán)境下的全局路徑規(guī)劃問題，從環(huán)境建模和尋優(yōu)算法兩個方面進(jìn)行了改進(jìn)。經(jīng)過驗證可以得到以下結(jié)論：（1）蜂巢柵格環(huán)境下的機(jī)器人轉(zhuǎn)彎角、避障路徑比和路徑質(zhì)量優(yōu)于傳統(tǒng)的方形柵格；（2）動態(tài)分級蟻群算法在迭代過程中的蟻群多樣性優(yōu)于蟻群算法；（3）動態(tài)蟻群算法應(yīng)用于路徑規(guī)劃時，路徑規(guī)劃長度和算法運行時間優(yōu)于蟻群算法。