未知環(huán)境下的蟻群-聚類自適應(yīng)動(dòng)態(tài)路徑規(guī)劃*

劉新宇，譚力銘，楊春曦，翟 持

昆明理工大學(xué) 化學(xué)工程學(xué)院，昆明 650500

1 引言

未知環(huán)境下的機(jī)器人路徑規(guī)劃問題一直是機(jī)器人和人工智能領(lǐng)域研究的一個(gè)熱點(diǎn)課題[1-12]，機(jī)器人的路徑規(guī)劃是指在障礙物已知或未知的環(huán)境中，機(jī)器人按照一定的性能指標(biāo)（如距離、時(shí)間等）規(guī)劃出一條由起始位置到目標(biāo)位置的可通行路徑[2]。

蟻群算法（ant colony algorithm）是一種經(jīng)典的智能優(yōu)化算法[3]，因其在路徑規(guī)劃中的并行性、魯棒性和較易與其他算法相結(jié)合的特點(diǎn)，被廣泛應(yīng)用在環(huán)境全部未知或部分未知的動(dòng)態(tài)路徑規(guī)劃中[4-8]。然而，傳統(tǒng)的蟻群算法在動(dòng)態(tài)路徑規(guī)劃中存在搜索時(shí)間長(zhǎng)、收斂速度慢、易陷入局部最優(yōu)等缺陷；如果在柵格環(huán)境下使用蟻群算法，所規(guī)劃的路徑還存在穿過對(duì)角障礙、轉(zhuǎn)彎次數(shù)多和累計(jì)轉(zhuǎn)折角大等問題。因此，一些學(xué)者提出了一些蟻群改進(jìn)算法來緩解上述問題。文獻(xiàn)[9]通過改進(jìn)距離啟發(fā)因子來增加目標(biāo)節(jié)點(diǎn)對(duì)下一節(jié)點(diǎn)的影響，從而避免陷于局部最優(yōu)解，提高收斂速度。文獻(xiàn)[10]利用遺傳算法的快速全局搜索能力和蟻群算法的并行、全局收斂能力，形成一種快速性和全局收斂性良好的混合算法。文獻(xiàn)[1]認(rèn)為機(jī)器人具有一個(gè)視覺范圍，可以在視覺范圍內(nèi)的一個(gè)子集中自由地選擇步長(zhǎng)，提高搜索效率。文獻(xiàn)[11]采用占空比法來判斷環(huán)境復(fù)雜程度，從而選擇合適的尋優(yōu)半徑，然后調(diào)用改進(jìn)的蟻群算法來完成路徑的動(dòng)態(tài)規(guī)劃。文獻(xiàn)[12]在蟻群算法中加入了平滑因子，平滑蟻群算法能夠在避開障礙物的情況下,有效地降低路徑長(zhǎng)度,增大了轉(zhuǎn)折角度,并且路經(jīng)規(guī)劃結(jié)果優(yōu)于傳統(tǒng)蟻群算法的路徑規(guī)劃結(jié)果。

在上述改進(jìn)的蟻群算法研究中，盡管不同程度地提高了搜索效率和收斂速度，減少了計(jì)算時(shí)間，但是卻沒有綜合考慮在動(dòng)態(tài)環(huán)境下障礙的不確定性、搜索范圍有限和在柵格環(huán)境下規(guī)劃路徑存在轉(zhuǎn)彎次數(shù)多，累計(jì)轉(zhuǎn)折角大等問題。為此，本文提出了一種能在滿足實(shí)時(shí)性要求的前提下，基于聚類算法來準(zhǔn)確判別障礙物分布的復(fù)雜程度，從而進(jìn)行搜索半徑自動(dòng)調(diào)整的自適應(yīng)搜索半徑蟻群動(dòng)態(tài)路徑規(guī)劃算法（self-adjust searching radius based on ant colonyclustering algorithm，SRL-CACA）。首先，通過對(duì)動(dòng)態(tài)柵格障礙環(huán)境的判別，采用虛擬障礙生成法消除穿過對(duì)角障礙的路徑選擇；然后，借鑒滾動(dòng)窗口法[13-14]思想設(shè)計(jì)了一種局部搜索半徑來描述機(jī)器人環(huán)境探索能力有限這一約束，并通過把局部搜索半徑設(shè)計(jì)成為可以根據(jù)環(huán)境復(fù)雜程度進(jìn)行自適應(yīng)調(diào)整的方式，以達(dá)到充分利用機(jī)器人有限的計(jì)算能力的目的；最后，通過在算法中加入平滑機(jī)制，減少轉(zhuǎn)彎次數(shù)和累計(jì)轉(zhuǎn)折角，提高規(guī)劃路徑的質(zhì)量。

仿真實(shí)驗(yàn)表明，本文所提的SRL-CACA算法在路徑距離優(yōu)化、收斂?jī)?yōu)化、轉(zhuǎn)折角和動(dòng)態(tài)復(fù)雜環(huán)境自適應(yīng)能力方面都有較好的綜合性能。

2 環(huán)境建模

2.1 柵格法

對(duì)于機(jī)器人在任意二維地形中，有且存在著有限個(gè)障礙物；由于這些障礙物的坐標(biāo)極易測(cè)繪，因而采用簡(jiǎn)單易處理的柵格法來對(duì)搜索環(huán)境進(jìn)行建模。

記G為機(jī)器人在二維平面上的有限運(yùn)動(dòng)區(qū)域，區(qū)域內(nèi)的柵格編號(hào)如圖1所示，在G中建立直角坐標(biāo)系，以G左下角為坐標(biāo)原點(diǎn)，橫軸為X軸，縱軸為Y軸。設(shè)在相關(guān)區(qū)域內(nèi)存在有限個(gè)障礙柵格，在圖1中用黑色柵格表示，自由柵格則用白色柵格表示。其中每個(gè)柵格為矩形，其邊長(zhǎng)已知。該劃分策略從實(shí)用出發(fā)，使場(chǎng)景描述與實(shí)際環(huán)境嚴(yán)格相符，規(guī)劃出的路徑保證移動(dòng)機(jī)器人暢通無阻。機(jī)器人僅在各個(gè)柵格內(nèi)的中心點(diǎn)行走，則圖1機(jī)器人位置坐標(biāo)的關(guān)系計(jì)算公式如式（1）和式（2）：

在關(guān)系式（1）、（2）中，a為每個(gè)柵格的邊長(zhǎng)，橫（縱）坐標(biāo)的最大柵格數(shù)值為MM，總柵格數(shù)為e=MM×MM，每個(gè)柵格的坐標(biāo)為(xi,yi)，i為每個(gè)小正方形的柵格編號(hào)，mod為求余運(yùn)算，而ceil為舍余取整運(yùn)算。為不失一般性，這里假定機(jī)器人的起始位置和最終目的位置已知，則生成的柵格地圖環(huán)境如圖1所示。

Fig.1 Grid map圖1 柵格地圖

對(duì)于圖1中間的柵格，可以有多條可選擇路徑。這里假設(shè)任選一個(gè)柵格如圖2所示，其周圍沒有障礙物，因此處于該柵格的機(jī)器人下一步可以向鄰接的8個(gè)方位搜索，8個(gè)方位分別為右下、右、右上、上、左上、左、左下、下。按照柵格位置編號(hào)規(guī)律，容易預(yù)知這8個(gè)方位的序號(hào)及其當(dāng)前位置柵格序號(hào)的差值。于是，對(duì)當(dāng)前柵格位置，下一步搜索的方位如圖2表示。

2.2 動(dòng)態(tài)障礙環(huán)境變化設(shè)置

為了便于理解，這里首先給出兩個(gè)定義。

定義1確認(rèn)局部搜索半徑之后，需要進(jìn)行局部路徑搜索，這樣局部搜索路徑規(guī)劃一次為一次規(guī)劃。局部路徑規(guī)劃的次數(shù)即規(guī)劃次數(shù)。

Fig.2 Possible routes圖2 可行路線

定義2步長(zhǎng)為在同一條路徑中，一次規(guī)劃經(jīng)過的柵格數(shù)就是步長(zhǎng)長(zhǎng)度。

為滿足在未知障礙環(huán)境中進(jìn)行動(dòng)態(tài)路徑規(guī)劃時(shí)的特點(diǎn)，本節(jié)設(shè)計(jì)了一種以時(shí)間步長(zhǎng)為指標(biāo)的動(dòng)態(tài)障礙變化規(guī)則，即：以機(jī)器人的規(guī)劃的次數(shù)為指標(biāo)來觸發(fā)障礙環(huán)境分布的變化。這里假設(shè)采用最大搜索半徑進(jìn)行一次局部規(guī)劃所需時(shí)間為T,則障礙環(huán)境變化所需的時(shí)間為t≤nT,n∈Z+。其中n的取值大小與實(shí)時(shí)性有關(guān)，實(shí)時(shí)性要求越高，則n的取值越小。當(dāng)機(jī)器人在時(shí)間t≤nT時(shí)，該子區(qū)域的障礙分布是固定不變的，并且機(jī)器人所在子區(qū)域外的障礙分布與本次路徑規(guī)劃無關(guān)。障礙環(huán)境變化流程如圖3所示。

Fig.3 Flow chart with time-varying obstacle environment圖3 障礙環(huán)境變化流程圖

本文設(shè)置了五種障礙環(huán)境：G1、G2、G3、G4、G5。同時(shí)采用不同的標(biāo)記符號(hào)來辨別機(jī)器人在哪一個(gè)障礙環(huán)境下進(jìn)行路徑規(guī)劃。同一個(gè)標(biāo)記符號(hào)的個(gè)數(shù)代表了機(jī)器人在不同環(huán)境中的規(guī)劃次數(shù)。

3 蟻群算法的改進(jìn)

3.1 對(duì)角障礙

當(dāng)機(jī)器人處于中間柵格時(shí)，假設(shè)其鄰接周圍沒有障礙物，下一步可以向鄰接的8個(gè)方位搜索。由于在規(guī)劃過程中會(huì)遇到障礙，并且障礙的分布是不確定的，當(dāng)遇到圖4所示的對(duì)角障礙時(shí)，所規(guī)劃的路徑會(huì)出現(xiàn)穿過對(duì)角障礙的情況?？紤]到在實(shí)際情況中，這種情況屬于死角，機(jī)器人是無法通過的，因此在規(guī)劃好的路徑中需要避免出現(xiàn)這類情況。

Fig.4 Diagonal obstacle圖4 對(duì)角障礙

在圖4中，令紅點(diǎn)為機(jī)器人的當(dāng)前位置，黑點(diǎn)為機(jī)器人可能選擇的節(jié)點(diǎn)位置。因此這里采用通過虛擬障礙生成法來避免產(chǎn)生這種情況。具體策略如下所示：

其中，MM為橫（縱）坐標(biāo)的最大柵格數(shù)值；障礙柵格節(jié)點(diǎn)編號(hào)的集合為Ob，Ob(i)、Ob(j)分別為障礙柵格節(jié)點(diǎn)i和j的節(jié)點(diǎn)編號(hào)；D(i,j)為障礙柵格節(jié)點(diǎn)i和j的編號(hào)差值；F_Ob為虛擬障礙編號(hào)集合。即當(dāng)兩個(gè)障礙的關(guān)系滿足式（3）時(shí)，這兩個(gè)障礙即為對(duì)角障礙，其虛擬障礙的節(jié)點(diǎn)編號(hào)滿足式（4），虛擬障礙生成如圖5所示。

Fig.5 Virtual obstacle圖5 虛擬障礙

在圖5中，紅色柵格是生成的虛擬障礙，即機(jī)器人在選擇下一步的目標(biāo)點(diǎn)時(shí)，除了黑色柵格節(jié)點(diǎn)，紅色柵格節(jié)點(diǎn)也是不能選擇的。

3.2 基于聚類算法的局部搜索半徑的選擇

為了充分利用機(jī)器人有限的計(jì)算能力，需要根據(jù)環(huán)境的復(fù)雜程度進(jìn)行局部搜索半徑的選擇，確保其計(jì)算能力在每次局部路徑規(guī)劃中均能夠充分利用，最終達(dá)到減少路徑規(guī)劃時(shí)間的目的?？紤]到連接在一起的障礙實(shí)際上可以看成一個(gè)障礙，連接在一起的障礙越多，規(guī)劃的難度越小。而文獻(xiàn)[11]中的占空比法卻無法識(shí)別這類障礙。因此，這里采用聚類算法來進(jìn)行障礙難易程度的準(zhǔn)確識(shí)別。

3.2.1 K-means聚類算法思想

1967年，MacQueen提出了K-means算法。K-means算法是一種基于劃分的經(jīng)典聚類算法。該算法最初隨機(jī)選擇K個(gè)數(shù)據(jù)樣本作為初始聚類中心，在每次的迭代過程中，根據(jù)計(jì)算相似度將每個(gè)數(shù)據(jù)樣本分配到最近的簇中，然后重新計(jì)算簇的中心，也就是每個(gè)簇中所有數(shù)據(jù)的平均值。該算法結(jié)束的條件為聚類準(zhǔn)則函數(shù)達(dá)到最優(yōu)即收斂，從而使生成的每個(gè)聚類內(nèi)緊湊，類間獨(dú)立[15]。

如果把聚集在一起的障礙看成一個(gè)類，則該算法能夠根據(jù)障礙的聚集程度完成對(duì)環(huán)境中障礙類數(shù)的準(zhǔn)確識(shí)別，從而可以根據(jù)搜索半徑中的障礙類數(shù)進(jìn)行環(huán)境復(fù)雜程度的判別。為了區(qū)別于傳統(tǒng)K-means算法中簇類的定義，這里將簇類定義為柵格障礙環(huán)境中的障礙集群。

3.2.2 局部搜索半徑的選擇

在SRL-CACA算法中，為了保證選擇合適的局部搜索半徑，以獲得尋優(yōu)距離、尋優(yōu)時(shí)間和計(jì)算能力三個(gè)指標(biāo)的綜合優(yōu)化效果，所設(shè)計(jì)的局部搜索半徑選擇原則的具體步驟如下：

步驟1確定搜索邊界，本文的邊界確定原則采用文獻(xiàn)[11]中的填充邊界確定原則。因?yàn)槠錈o障礙柵格占所覆蓋范圍總格數(shù)的比例較高，得到的可選節(jié)點(diǎn)更多更全面，全局最優(yōu)路徑效果更優(yōu)。

步驟2確定搜索半徑，這里設(shè)計(jì)了兩種搜索半徑確定原則：簇類最小選擇確定原則和同簇選大選擇確定原則。簇類最小選擇確定原則為：比較在不同搜索半徑所包含的柵格中，選擇聚類算法之后簇類最小的搜索半徑為本次局部路徑規(guī)劃搜索半徑。同簇選大選擇確定原則為：如果存在不同搜索半徑擁有相同的簇類值，則選擇相同簇類值中最大的搜索半徑為本次局部路徑規(guī)劃搜索半徑。簇類最小選擇確定原則可以表示為：

而同簇選大選擇確定原則可以表示為:

其中，f(·)表示對(duì)應(yīng)簇類的搜索半徑函數(shù)；Φ(·)表示簇類相等的不同搜索半徑所對(duì)應(yīng)的子集；g(·)表示對(duì)應(yīng)簇類集合中的搜索半徑函數(shù)；φc表示具有相同簇類Kc的集合；Kc,c=1,2,…,n-1表示具有兩個(gè)以上相同簇類的簇類值。

在圖6中，紅色正方形柵格為機(jī)器人的當(dāng)前位置，由內(nèi)到外的兩個(gè)橙色矩形所包含的區(qū)域分別為兩步搜索半徑和四步搜索半徑所覆蓋的區(qū)域。2步搜索半徑的簇類數(shù)為4，4步為3。按照簇類最小的選擇原則應(yīng)選擇4步搜索半徑。

在圖7中，紅色正方形柵格為機(jī)器人的當(dāng)前位置，由內(nèi)到外的兩個(gè)橙色矩形所包含的區(qū)域分別為2步搜索半徑和4步搜索半徑所覆蓋的區(qū)域。2步搜索半徑的簇類數(shù)為3，4步也為3。按照同簇選大搜索半徑選擇原則應(yīng)選擇4步搜索半徑。

Fig.6 Cluster-based smallest win principle圖6 簇類最小選擇確定原則

Fig.7 Cluster-based biggest win principle from same cluster set圖7 同簇類選大選擇確定原則

在步驟2確定搜索半徑中，基于聚類算法確定簇類的具體步驟為：

步驟1初始化簇類K，即K值為局部搜索半徑內(nèi)障礙柵格總數(shù)。

步驟2計(jì)算樣本集合節(jié)點(diǎn)之間的距離，根據(jù)鄰接矩陣計(jì)算出所有障礙柵格坐標(biāo)，構(gòu)成樣本集合Obstacle_data。從樣本集合Obstacle_data選擇K個(gè)數(shù)據(jù)對(duì)象作為初始聚類中心Cm,m=1,2,…,k；障礙樣本i和j之間的相異度用它們之間的坐標(biāo)距離d(x,y)來表示。距離越小，則樣本i和j越相似；距離越大，兩個(gè)樣本越不相似。歐式距離公式如下：

其中，xi、yi和xj、yj分別為樣本i、j的橫縱坐標(biāo)。

步驟3更新簇類K，根據(jù)d(x,y)=1，計(jì)算出d(x,y)=1的數(shù)p，K=K-p。

步驟4計(jì)算新簇的聚類中心，簇中心指一個(gè)簇中所有對(duì)象組成的幾何中心點(diǎn)，簇的平均值K-means算法中也稱為簇中心，簇中心的公式如下：

其中，Nk是簇k的樣本數(shù)目，Ck是指簇k的中心，Xq是樣本集合Obstacle_data中的每個(gè)數(shù)據(jù)對(duì)象。

步驟5計(jì)算聚類準(zhǔn)則函數(shù)（sum of the squared error，SSE），K-means聚類算法使用聚類準(zhǔn)則函數(shù)來評(píng)價(jià)聚類性能的好壞。聚類準(zhǔn)則函數(shù)公式為：

步驟6給出一個(gè)足夠小的閾值ε＞0，在聚類過程中，如果滿足，則表示算法結(jié)束，否則返回步驟2繼續(xù)執(zhí)行。

3.3 平滑機(jī)制

在柵格環(huán)境下利用蟻群算法規(guī)劃出來的機(jī)器人路徑存在轉(zhuǎn)彎次數(shù)多，累計(jì)轉(zhuǎn)折角大等問題。針對(duì)這些問題，這里提出了中點(diǎn)平滑機(jī)制方法，對(duì)規(guī)劃出的路徑進(jìn)行轉(zhuǎn)角平滑處理，從而使得路徑相對(duì)平滑，縮短起點(diǎn)到終點(diǎn)的距離。

中點(diǎn)平滑機(jī)制方法的基本原則如圖8所示?？紤]規(guī)劃路徑中相鄰的三個(gè)位置z(i-1)、z(i)、z(i+1)，如果夾角∠α≤δ，則對(duì)該折線啟動(dòng)平滑機(jī)制：以位置z(i-1)、z(i+1)為起始位置，產(chǎn)生一條同時(shí)通過兩個(gè)位置的折線來替換原有折線。這里δ為角度閥值。平滑機(jī)制的具體步驟如下：

Fig.8 Smoothing optimization schematic圖8 平滑機(jī)制原理圖

步驟1計(jì)算當(dāng)前節(jié)點(diǎn)與上一個(gè)節(jié)點(diǎn)的斜率k1和當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的斜率k2。

步驟2如果k1=k2，跳過這個(gè)節(jié)點(diǎn)，計(jì)算下個(gè)節(jié)點(diǎn)。

步驟3計(jì)算圖8中的a、b、c值。

步驟4根據(jù)余弦公式cosα=(a2+b2-c2)/2ab，計(jì)算出α值。

步驟5給出一個(gè)閾值δ，判斷α≤δ；如果等式成立，計(jì)算出上一節(jié)點(diǎn)與當(dāng)前點(diǎn)的中點(diǎn)的橫縱坐標(biāo)和當(dāng)前點(diǎn)與下一節(jié)點(diǎn)的中點(diǎn)的橫縱坐標(biāo)；這里給出的δ=155°。

步驟6連接節(jié)點(diǎn)時(shí)，連接生成的新節(jié)點(diǎn)，舍去z(i)節(jié)點(diǎn)，達(dá)到平滑目的。

由圖9可知，加入平滑機(jī)制能顯著提高線路質(zhì)量，有效地降低了機(jī)器人規(guī)劃路徑的長(zhǎng)度和累計(jì)轉(zhuǎn)彎角度。

Fig.9 Smoothing optimization圖9 平滑優(yōu)化

以上三個(gè)改進(jìn)，使得在動(dòng)態(tài)路徑規(guī)劃過程中，對(duì)角障礙識(shí)別能有效避免出現(xiàn)“死角”的情況，保證路徑的成功；聚類算法能在復(fù)雜的障礙環(huán)境下，更準(zhǔn)確地匹配步長(zhǎng)與環(huán)境復(fù)雜度的關(guān)系；平滑優(yōu)化能保證機(jī)器人在行進(jìn)過程中，有效減少轉(zhuǎn)折角的幅度，降低機(jī)器人偏離規(guī)劃路線的機(jī)率。

4 改進(jìn)蟻群-聚類算法的實(shí)現(xiàn)流程

綜上所述，機(jī)器人基于蟻群-聚類算法的自適應(yīng)動(dòng)態(tài)路徑規(guī)劃具體分為以下步驟。蟻群-聚類算法的流程圖如圖10所示。

步驟1首先采用柵格法對(duì)機(jī)器人的工作環(huán)境進(jìn)行建模。

步驟2動(dòng)態(tài)障礙變化設(shè)置。

步驟3初始化蟻群。設(shè)置螞蟻的當(dāng)前位置為起點(diǎn)位置。初始化蟻群禁忌表、路徑表、路徑長(zhǎng)度：禁忌表中存放的數(shù)據(jù)代表所有柵格的禁忌狀況，用來記錄柵格當(dāng)前狀態(tài)；路徑表中存放蟻群經(jīng)過的柵格的編號(hào)，用來記錄蟻群尋找到的路徑。

步驟4對(duì)柵格地圖進(jìn)行識(shí)別對(duì)角障礙，并生成虛擬障礙。

步驟5根據(jù)規(guī)劃實(shí)時(shí)性要求確定本次動(dòng)態(tài)路徑規(guī)劃的搜索半徑上界，即機(jī)器人在一次局部動(dòng)態(tài)路徑規(guī)劃中所允許行走的最大步長(zhǎng)。

步驟6機(jī)器人以當(dāng)前位置為出發(fā)點(diǎn)，采用搜索半徑的選擇規(guī)則確定本次局部動(dòng)態(tài)路徑規(guī)劃的搜索半徑值。

步驟7采用文獻(xiàn)[11]的方法調(diào)用隨機(jī)輪盤賭方法確定本次動(dòng)態(tài)路徑規(guī)劃的最優(yōu)局部目標(biāo)點(diǎn)。

步驟8調(diào)用加入了平滑機(jī)制的可調(diào)用蟻群算法（called ant colony algorithm，C-ACA），規(guī)劃出前往最優(yōu)局部目標(biāo)點(diǎn)路徑。

步驟9通過計(jì)算本次最優(yōu)局部目標(biāo)點(diǎn)與終點(diǎn)的二范數(shù)是否為零來判斷該節(jié)點(diǎn)是否為終點(diǎn)。如果是終點(diǎn)則本次路徑規(guī)劃完成，反之則返回步驟3。

步驟10如果達(dá)到最大迭代次數(shù)，迭代終止。

步驟11篩選出最優(yōu)解，然后輸出最短距離所在的尋優(yōu)路徑。

Fig.10 Flow chart of ant colony-clustering algorithm圖10 蟻群-聚類算法流程圖

通過上述步驟的不斷循環(huán)，即可實(shí)現(xiàn)全局的動(dòng)態(tài)路徑規(guī)劃。

5 仿真與分析

為了驗(yàn)證提出算法的有效性，本文將和以下幾個(gè)典型算法進(jìn)行對(duì)比。

（1）基于精英策略的蟻群算法（elite ant system,EAS）[3]：一種根據(jù)基本的蟻群優(yōu)化算法，精英策略改進(jìn)了信息素的更新方式的算法。

（2）基于柵格法的機(jī)器人路徑規(guī)劃蟻群算法（ant colony algorithm，ACA）[16]：一種靜態(tài)環(huán)境下的機(jī)器人路徑規(guī)劃仿生算法。

（3）基于統(tǒng)計(jì)分析的自適應(yīng)蟻群算法（optimal ant colony based on statistical analysis，ACO）[17]：一種借鑒統(tǒng)計(jì)分析的方法提取了每一代蟻群的三個(gè)特征參數(shù)，進(jìn)而改進(jìn)了局部信息素更新方式的算法。

（4）自適應(yīng)搜索半徑蟻群動(dòng)態(tài)路徑規(guī)劃算法（selfadjust searching radius based on ant colony algorithm，SRL-ACA）[11]：一種能在實(shí)時(shí)性要求內(nèi)，根據(jù)障礙物占空比進(jìn)行搜索半徑自動(dòng)調(diào)整的算法。

所有算法程序均采用Matlab語言進(jìn)行編程，障礙變化規(guī)則為時(shí)間變換規(guī)則，路徑規(guī)劃范圍為20×20的柵格面積，為實(shí)現(xiàn)在同等條件下比較，五種算法的公共參數(shù)初始值設(shè)置如表1所示。

Table 1 Algorithm's public parameter settings表1 算法的公共參數(shù)設(shè)置

5.1 動(dòng)態(tài)性能比較

首先，在同等條件下，圖11對(duì)比了SRL-CACA算法、SRL-CACA+算法（聚類與占空比權(quán)值各占50%的方案）和經(jīng)典ACA算法。圖12對(duì)比了SRL-CACA算法、文獻(xiàn)[17]ACO算法和文獻(xiàn)[3]EAS算法。由圖11、圖12可知，五種算法均很好地適應(yīng)障礙變化，各自規(guī)劃出了一條從起始點(diǎn)到全局目標(biāo)點(diǎn)的優(yōu)化路徑。相比較而言，SRL-CACA算法、SRL-CACA+算法在步長(zhǎng)選擇上更合理、規(guī)劃的次數(shù)更少且路徑更短。

Fig.11 Optimization comparison among SRL-CACA,SRL-CACA+andACA圖11 SRL-CACA、SRL-CACA+與ACA尋優(yōu)對(duì)比圖

Fig.12 Optimization comparison among SRL-CACA,ACO and EAS圖12 SRL-CACA、ACO與EAS尋優(yōu)對(duì)比圖

其次，圖13對(duì)比了SRL-CACA算法、SRL-CACA+算法和文獻(xiàn)[11]的SRL-ACA算法。SRL-CACA算法比文獻(xiàn)[11]的SRL-ACA算法在最優(yōu)路徑上有所提高，并且在步長(zhǎng)選擇上更合理、規(guī)劃的次數(shù)更少。SRL-CACA+算法在SRL-CACA算法上也有所提高，說明聚類法和占空比法在不同的柵格障礙環(huán)境下占有不同的優(yōu)勢(shì)。例如：在柵格障礙圖中，如果障礙聚集比較明顯，那么聚類法比較占優(yōu)勢(shì)；而在障礙聚集不明顯，比較分散的情況下，占空比法比較占優(yōu)勢(shì)。

Fig.13 Optimization comparison among SRL-CACA,SRL-CACA+and SRL-ACA圖13 SRL-CACA、SRL-CACA+與SRL-ACA尋優(yōu)對(duì)比圖

在尋優(yōu)對(duì)比圖11～圖13中，均出現(xiàn)穿越障礙的情況，不是路徑規(guī)劃失敗了，而是因?yàn)檫M(jìn)行路徑規(guī)劃的柵格障礙圖進(jìn)行周期性變化，顯示生成的圖為最后一個(gè)場(chǎng)景障礙圖。

這里以圖11中黑色矩形框標(biāo)記的路徑進(jìn)行說明，標(biāo)記的路徑應(yīng)為第一個(gè)尋優(yōu)路徑環(huán)境下的規(guī)劃路徑，圖14同樣也是第一個(gè)尋優(yōu)路徑環(huán)境下的規(guī)劃路徑，很顯然并沒有穿過障礙圖。

Fig.14 Path planning in the first obstacle environment圖14 第一種障礙環(huán)境下的路徑規(guī)劃

5.2 對(duì)角障礙的準(zhǔn)確性

由圖15可知，圖中紅色柵格為生成的虛擬障礙，綠色實(shí)線為生成虛擬障礙前的路徑規(guī)劃路線，紅色實(shí)線為生成虛擬障礙后的路徑規(guī)劃路線。在進(jìn)行路徑規(guī)劃時(shí)，未生成虛擬障礙的路徑規(guī)劃直接穿過對(duì)角障礙；而生成虛擬障礙的則會(huì)繞過對(duì)角障礙。

Fig.15 Virtual obstacle generation diagram圖15 虛擬障礙生成圖

5.3 搜索半徑選擇規(guī)則對(duì)優(yōu)化參數(shù)的影響

為了測(cè)試所涉及算法對(duì)環(huán)境變化的自適應(yīng)能力，在這里通過設(shè)置相同的算法參數(shù)和環(huán)境參數(shù)，比較了這五種算法在路徑尋優(yōu)關(guān)鍵參數(shù)上的差異。為確保尋優(yōu)關(guān)鍵參數(shù)的有效性，這里的最優(yōu)路徑長(zhǎng)和最短時(shí)間均是50次尋優(yōu)結(jié)果的平均值。

首先，表2分別對(duì)比了五種算法的不同性能，最優(yōu)路徑、尋優(yōu)時(shí)間以及步數(shù)，并分析了算法每次得到結(jié)果的平均值。

Table 2 Performance analysis of different algorithms表2 不同算法的性能分析

由表2知，SRL-CACA算法與ACA算法對(duì)比，在最優(yōu)路徑上提高了22.2%，尋優(yōu)時(shí)間縮短了52.7%，步數(shù)減少了57.1%；與SRL-ACA算法對(duì)比，在最優(yōu)路徑上提高了7.8%，尋優(yōu)時(shí)間縮短了8.3%，步數(shù)減少了14.3%；與ACO算法對(duì)比，在最優(yōu)路徑上提高了10.1%，尋優(yōu)時(shí)間縮短了83.8%，步數(shù)減少了52%；與EAS算法對(duì)比，在最優(yōu)路徑上提高了24.3%，尋優(yōu)時(shí)間縮短了94%，步數(shù)減少了61.3%。

其次，為了進(jìn)一步分析SRL-CACA算法與SRLACA算法在計(jì)算能力和路徑規(guī)劃能力的差異，這里通過一次具體的動(dòng)態(tài)規(guī)劃結(jié)果來說明，如表3所示。

Table 3 Path optimization parameter between SRLCACAand SRL-ACA表3 SRL-CACA和SRL-ACA路徑尋優(yōu)參數(shù)表

由表3知，尋優(yōu)距離方面，本文的總尋優(yōu)距離為30.06，要小于文獻(xiàn)[11]的36.62；尋優(yōu)時(shí)間方面，本文的總尋優(yōu)時(shí)間為4.30，要小于文獻(xiàn)[11]的4.95；計(jì)算能力方面，兩種算法均舍去異常值，文獻(xiàn)[11]中一次局部規(guī)劃所需的最大尋優(yōu)時(shí)間與最小尋優(yōu)時(shí)間的差值為0.027，而本文為0.016，顯然本文的計(jì)算能力分配更合理。并且在第7次規(guī)劃中，本文算法步長(zhǎng)為5，文獻(xiàn)[11]算法步長(zhǎng)為1，但是本文算法所消耗的時(shí)間還少，說明聚類算法對(duì)環(huán)境復(fù)雜程度的判斷是準(zhǔn)確、有效的。

最后，為了比較聚類與占空比權(quán)值各占50%（SRL-CACA+）的方案與本文提出的SRL-CACA算法和文獻(xiàn)[11]的SRL-ACA算法的性能差異，這里分別進(jìn)行了對(duì)比仿真實(shí)驗(yàn)。具體結(jié)果如表4所示。對(duì)應(yīng)的尋優(yōu)對(duì)比圖如圖13。

Table 4 Path optimization parameter among SRL-CACA+,SRL-CACAand SRL-ACA表4 SRL-CACA+、SRL-CACA和SRL-ACA路徑尋優(yōu)參數(shù)表

由表4可知，SRL-CACA+算法比SRL-CACA算法和SRL-ACA算法在最優(yōu)路徑、尋優(yōu)時(shí)間和步數(shù)三個(gè)指標(biāo)上都有所提高，說明加入聚類和占空比權(quán)值分配方案在復(fù)雜未知環(huán)境下的動(dòng)態(tài)路徑規(guī)劃上更具優(yōu)勢(shì)，因此，如何實(shí)現(xiàn)合理的權(quán)值分配具有良好的研究?jī)r(jià)值。

6 結(jié)束語

本文主要在復(fù)雜動(dòng)態(tài)環(huán)境進(jìn)行動(dòng)態(tài)路徑規(guī)劃的過程中，提出了基于蟻群-聚類算法的一種新型的搜索半徑自適應(yīng)蟻群動(dòng)態(tài)路徑規(guī)劃方法。通過自適應(yīng)調(diào)整搜索半徑，使得機(jī)器人的計(jì)算能力始終得到充分的利用，從而進(jìn)一步縮短路徑距離，加快算法收斂速度。通過對(duì)對(duì)角障礙的識(shí)別，生成虛擬障礙，避免了穿過死角的情形。通過對(duì)算法規(guī)劃出的路徑進(jìn)行平滑優(yōu)化，顯著提高了線路質(zhì)量，降低了機(jī)器人規(guī)劃路徑的長(zhǎng)度和累計(jì)轉(zhuǎn)彎次數(shù)。通過仿真實(shí)驗(yàn)驗(yàn)證了文中改進(jìn)算法的有效性。后續(xù)研究中，將針對(duì)聚類與占空比權(quán)值自動(dòng)分配問題，進(jìn)行下一步研究。