李開(kāi)榮，劉 爽，胡倩倩，唐亦媛

（揚(yáng)州大學(xué)信息工程學(xué)院，江蘇揚(yáng)州 225127）

（*通信作者電子郵箱973279727@qq.com）

0 引言

隨著智能化時(shí)代的到來(lái)，移動(dòng)機(jī)器人越來(lái)越普及，其中一項(xiàng)重要的研究工作即移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題。移動(dòng)機(jī)器人的工作環(huán)境中往往存在著一定數(shù)量的障礙物，需要從初始點(diǎn)準(zhǔn)確且快速地尋找一條能夠避開(kāi)所有障礙物到達(dá)目標(biāo)點(diǎn)的最優(yōu)路徑［1］。傳統(tǒng)的路徑規(guī)劃算法有柵格法、人工勢(shì)場(chǎng)法等［2］。柵格法屬于全局路徑規(guī)劃算法，用于構(gòu)建移動(dòng)環(huán)境，將機(jī)器人的路徑轉(zhuǎn)換為網(wǎng)格之間的連接，算法簡(jiǎn)單易實(shí)現(xiàn)；但是當(dāng)移動(dòng)環(huán)境變大時(shí)，網(wǎng)格數(shù)量急劇增加，數(shù)據(jù)存儲(chǔ)空間大，計(jì)算速度慢。人工勢(shì)場(chǎng)法是一種局部路徑規(guī)劃算法，實(shí)時(shí)性強(qiáng)、計(jì)算量小，對(duì)硬件平臺(tái)的要求低；但是其存在的局部最小點(diǎn)問(wèn)題很容易引起路徑規(guī)劃的失敗。因此，隨著移動(dòng)環(huán)境復(fù)雜度和任務(wù)難度的增加，傳統(tǒng)的路徑規(guī)劃算法無(wú)法達(dá)到預(yù)期的效果。隨著人工智能的發(fā)展，例如遺傳算法［3］、蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［4］、煙花算法［5］、粒子群算法［6］等智能算法也被應(yīng)用到路徑規(guī)劃領(lǐng)域中，并且取得了豐富的成果。

在上述路徑規(guī)劃方法中，蟻群優(yōu)化算法［7］具有較強(qiáng)的魯棒性和搜索能力，作為一種啟發(fā)式算法，對(duì)螞蟻群體的覓食過(guò)程進(jìn)行學(xué)習(xí)模擬，得出螞蟻們共同規(guī)劃的解路徑，具有正反饋、并行計(jì)算以及易融合等特點(diǎn)，但也存在迭代次數(shù)多和易忽略全局最優(yōu)解等問(wèn)題。針對(duì)這些問(wèn)題，許多國(guó)內(nèi)外學(xué)者進(jìn)行了探索與改進(jìn)，文獻(xiàn)［8］針對(duì)傳統(tǒng)蟻群優(yōu)化算法易陷入局部最優(yōu)、初期搜索能力差等問(wèn)題，采用改進(jìn)的頭尾搜索機(jī)制，引入獎(jiǎng)懲因子與信息素最大最小閾值，添加遺傳算法變異因子，使規(guī)劃出來(lái)的路徑得到了進(jìn)一步的優(yōu)化。文獻(xiàn)［9］為避免初期尋優(yōu)的盲目性，在柵格地圖中劃定優(yōu)選區(qū)域，設(shè)置新的初始信息素濃度模型，提高了算法的收斂速度。文獻(xiàn)［10］使用偽隨機(jī)狀態(tài)轉(zhuǎn)移規(guī)則選擇路徑，根據(jù)當(dāng)前最優(yōu)解和迭代次數(shù)計(jì)算狀態(tài)轉(zhuǎn)移概率，自適應(yīng)地調(diào)整確定選擇和隨機(jī)選擇的比例，引入最優(yōu)解和最差解改進(jìn)全局信息素更新方法，仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的蟻群優(yōu)化算法收斂速度更快、全局搜索能力更強(qiáng)。文獻(xiàn)［11］在蟻群優(yōu)化算法中融合免疫算法，大大緩解了抗體種群的“早熟”問(wèn)題。文獻(xiàn)［12］將蟻群優(yōu)化算法生成的路徑進(jìn)行平滑操作，減少了轉(zhuǎn)彎次數(shù)。

以上改進(jìn)蟻群優(yōu)化算法大多致力于優(yōu)化路徑長(zhǎng)度以及提高尋路效率，很少有學(xué)者在尋找下一步移動(dòng)節(jié)點(diǎn)時(shí)就考慮到轉(zhuǎn)彎角度次數(shù)過(guò)多導(dǎo)致機(jī)器人運(yùn)行時(shí)間增長(zhǎng)、能耗增加的問(wèn)題，部分學(xué)者在路徑規(guī)劃出來(lái)后對(duì)其進(jìn)行平滑操作，但這種方式增加了算法的復(fù)雜性，且最終路徑未必就是全局最優(yōu)路徑。鑒于此，本文提出了一種基于轉(zhuǎn)角約束的改進(jìn)蟻群優(yōu)化算法，用于移動(dòng)機(jī)器人路徑規(guī)劃。為降低搜索初期的盲目性，該算法首先增加起始點(diǎn)與終止點(diǎn)之間的初始信息素濃度；并且在啟發(fā)函數(shù)中加入A*算法的估價(jià)函數(shù)和轉(zhuǎn)彎角度因子，使搜索到的路徑是綜合路徑長(zhǎng)度和累計(jì)轉(zhuǎn)角最小的最優(yōu)路徑，有利于減少移動(dòng)機(jī)器人損失的能耗，防止出現(xiàn)局部最優(yōu)的情況；在信息素更新公式中，引進(jìn)狼群算法的獵物分配原則，同時(shí)借鑒最大最小蟻群（Max and Min Ant System，MMAS）算法給路徑上的信息素規(guī)定上限和下限，進(jìn)一步提高收斂速度，便于快速搜索到一條綜合指標(biāo)最優(yōu)的路徑。

1 基本蟻群優(yōu)化算法

蟻群優(yōu)化算法即螞蟻種群從起始點(diǎn)出發(fā)，至目標(biāo)位置獲取食物的過(guò)程，螞蟻的信息素會(huì)被留在其走過(guò)的路徑上，它們利用信息素相互通信，當(dāng)某一條路徑上通過(guò)的螞蟻越來(lái)越多時(shí)，該路徑的信息素濃度就會(huì)越高，其他螞蟻就有更大的概率選擇這條路徑，起到正反饋?zhàn)饔?，然而也容易?dǎo)致局部最優(yōu)或死鎖情況的出現(xiàn)［13］。

通過(guò)對(duì)信息素濃度、啟發(fā)因子、路徑方向等因素進(jìn)行綜合判斷選擇下一步移動(dòng)的柵格，并利用輪盤(pán)賭法計(jì)算當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的概率［14］，如式（1）～（3）所示。

其中：τij是網(wǎng)格i到網(wǎng)格j的信息素值；ηij是網(wǎng)格i到網(wǎng)格j的啟發(fā)式信息；α為信息素激勵(lì)因子，代表信息素值對(duì)路徑選擇的影響程度，α越大則信息素對(duì)于路徑選擇的影響越大，大多數(shù)螞蟻?zhàn)哌^(guò)的路徑將有更大幾率被選中；β是期望啟發(fā)式因子，代表啟發(fā)信息對(duì)螞蟻選擇路徑的影響程度，β與影響程度之間是正相關(guān)關(guān)系；dij代表節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的歐幾里得距離。（xi，y）i和（xj，y）j是網(wǎng)格i與網(wǎng)格j的坐標(biāo)；allowedk中存放網(wǎng)格i中螞蟻此時(shí)能夠選擇的網(wǎng)格集合。

經(jīng)過(guò)t時(shí)刻，當(dāng)每只螞蟻都進(jìn)行了一次路徑規(guī)劃后，計(jì)算所有順利到達(dá)目標(biāo)點(diǎn)的螞蟻?zhàn)哌^(guò)的路徑長(zhǎng)度，從中篩選出最短路徑，并且將每條路徑上的信息素濃度都進(jìn)行更新，一段時(shí)間后，將揮發(fā)一部分信息素，如式（4）所示：

其中：ρ是信息素?fù)]發(fā)系數(shù)。

同時(shí)螞蟻也將在路徑上留下一些信息素，如式（5）所示：

式（6）為蟻群模型的信息素更新策略，其中：Q為信息素的強(qiáng)度，若螞蟻搜索到的路徑長(zhǎng)度dij越小，依據(jù)公式，則將會(huì)有更多的信息素被加到路徑上，之后其他螞蟻選中該路徑的可能性也將更大［15］。

2 環(huán)境建模

常用的環(huán)境建模方法有柵格圖法、可視圖空間法、自由空間法、幾何信息法［16］等。本文選擇柵格圖法對(duì)移動(dòng)機(jī)器人二維運(yùn)動(dòng)空間進(jìn)行建模，假設(shè)每個(gè)柵格的邊長(zhǎng)為1，其中：白色柵格為自由柵格，表示可通行區(qū)域；黑色柵格為障礙物區(qū)域，移動(dòng)機(jī)器人不可通行。如式（7）所示：

移動(dòng)機(jī)器人平行行駛在障礙物邊緣的位置關(guān)系如圖1所示。

圖1 機(jī)器人與障礙物的位置關(guān)系Fig.1 Position relationship between robot and obstacle

假設(shè)移動(dòng)機(jī)器人的直徑為W，從圖1 可以看出，當(dāng)機(jī)器人的中心占據(jù)柵格距離障礙物邊緣的最小距離小于W/2 時(shí)，就會(huì)發(fā)生碰撞［17］，此時(shí)的碰撞概率為100%，即

其中：P（x，y）為柵格（x，y）的碰撞概率；N（x，y）為移動(dòng)機(jī)器人中心所占據(jù)的柵格；｛O｝為障礙物所有邊緣柵格的集合；min（｛O｝，N（x，y））表示移動(dòng)機(jī)器人中心占據(jù)柵格到障礙物所有邊緣柵格距離集的最小值。

為確保移動(dòng)機(jī)器人在運(yùn)動(dòng)中不與障礙物邊緣發(fā)生碰撞，且保證每次轉(zhuǎn)彎的順利進(jìn)行，本文將障礙物尺寸進(jìn)行適當(dāng)膨化后再預(yù)留出一定的安全距離，其中安全距離為移動(dòng)機(jī)器人的半徑，進(jìn)而可將機(jī)器人簡(jiǎn)化為一個(gè)質(zhì)點(diǎn)來(lái)處理，障礙物處理過(guò)程如圖2所示。

圖2 障礙物處理圖Fig.2 Obstacle processing diagram

網(wǎng)格模型被放置在二維坐標(biāo)系中，x為橫軸，y為縱軸，采用序列號(hào)的方法標(biāo)記每個(gè)網(wǎng)格。在N*N的網(wǎng)格圖中，起始節(jié)點(diǎn)以“起始”命名，目標(biāo)節(jié)點(diǎn)以“目標(biāo)”命名，其余柵格分別用編號(hào)i表示，每個(gè)柵格的中心點(diǎn)坐標(biāo)為（xi，y）i，柵格編號(hào)與其坐標(biāo)的對(duì)應(yīng)關(guān)系如式（9）所示：

3 改進(jìn)蟻群優(yōu)化算法

基本的蟻群優(yōu)化算法有以下缺點(diǎn)：每個(gè)柵格的初始信息素值相同且啟發(fā)式值之間也不存在明顯差異，因此往往搜索時(shí)間較長(zhǎng)，難以尋找到全局最優(yōu)解［18］；同時(shí)在柵格地圖中，使用基本蟻群優(yōu)化算法規(guī)劃出來(lái)的路徑可能會(huì)有更多的轉(zhuǎn)彎次數(shù)和較大的累計(jì)轉(zhuǎn)彎角度。為了解決上述問(wèn)題，本文進(jìn)行了以下改進(jìn)。

3.1 初始信息素不均勻分布

在基本蟻群優(yōu)化算法的初始階段，每個(gè)柵格的初始信息素值相同，這就使得螞蟻在初期搜索時(shí)存在不小的盲目性，算法運(yùn)行時(shí)間增加。因此本文將初始信息素的分布進(jìn)行適當(dāng)調(diào)整，使其不均勻分布，并且不會(huì)增加算法的復(fù)雜性。通過(guò)參考其他眾多文獻(xiàn)中的路徑，本文發(fā)現(xiàn)最優(yōu)路徑大部分情況下都存在于起點(diǎn)與終點(diǎn)連線的附近［19］，因此此處取柵格地圖各邊的中點(diǎn)，連接相鄰邊的中點(diǎn)，得到與起點(diǎn)終點(diǎn)連線平行的兩條直線，直線AB與直線CD之間的區(qū)域如圖3 所示，增強(qiáng)該區(qū)域的初始信息素值，如式（10）所示。

圖3 初始信息素增強(qiáng)區(qū)域Fig.3 Initial pheromone enhancement area

其中：τ0為信息素初始值，C為大于τ0的常數(shù)。

3.2 改進(jìn)啟發(fā)式信息

基本蟻群優(yōu)化算法的啟發(fā)函數(shù)中，相鄰網(wǎng)格之間啟發(fā)式值的大小相差無(wú)幾，所以往往需要較長(zhǎng)的搜尋時(shí)間且不易搜索到全局最優(yōu)路徑。為此，本文將A*算法加入到蟻群優(yōu)化算法的啟發(fā)式信息中，以提高算法的收斂速度并獲得更優(yōu)的全局路徑［20］。

A*算法有較快的尋路速度，其啟發(fā)式成本由估價(jià)函數(shù)（fn）表示，通過(guò)（fn）來(lái)指導(dǎo)節(jié)點(diǎn)的擴(kuò)展與搜索，每一次都是搜索從起始點(diǎn)到目標(biāo)點(diǎn)之間使得（fn）最小的路徑，估價(jià)函數(shù)方程為：

其中：g（n）為從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最小路徑成本值；h（n）為從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最小路徑成本估計(jì)值；nx和ny是當(dāng)前節(jié)點(diǎn)n的坐標(biāo)；gx和gy是目標(biāo)節(jié)點(diǎn)g的坐標(biāo)；sx和sy是初始節(jié)點(diǎn)s的坐標(biāo)。

機(jī)器人在經(jīng)過(guò)障礙物群時(shí)，若只是把路徑最短作為主要因素，則會(huì)造成機(jī)器人轉(zhuǎn)彎次數(shù)過(guò)多，時(shí)間和能耗大大增加，也會(huì)導(dǎo)致機(jī)器人壽命的減少。因此，本文將轉(zhuǎn)彎角度因子也加入到蟻群優(yōu)化算法的啟發(fā)信息中，使移動(dòng)機(jī)器人盡可能選擇一條轉(zhuǎn)彎角度更小的路徑，若一條路徑中節(jié)點(diǎn)之間的轉(zhuǎn)彎角度過(guò)大，則啟發(fā)函數(shù)值將降低，路徑中節(jié)點(diǎn)之間的轉(zhuǎn)彎角度示意圖如圖4所示。

圖4 轉(zhuǎn)彎角度示意圖Fig.4 Schematic diagram of turning angle

圖4中統(tǒng)一按照順時(shí)針的方向進(jìn)行角度測(cè)量，（A，B）節(jié)點(diǎn)之間的路徑相對(duì)于（O，A）節(jié)點(diǎn)之間轉(zhuǎn)彎角度是45°，而（C，D）節(jié)點(diǎn)之間的路徑相對(duì)于（B，C）節(jié)點(diǎn)之間的轉(zhuǎn)彎角度是90°，轉(zhuǎn)彎角度值的計(jì)算公式如下：

其中：R是轉(zhuǎn)彎角度因子；γ是轉(zhuǎn)彎角度（單位：rad）；c是轉(zhuǎn)彎角度權(quán)重系數(shù)。

綜上，在蟻群優(yōu)化算法中，將A*算法的估計(jì)函數(shù)用作啟發(fā)式信息，以便于搜索全局最優(yōu)路徑、提高收斂速度；同時(shí)，將轉(zhuǎn)彎角度因子也添加到蟻群優(yōu)化算法的啟發(fā)式值中，以減少轉(zhuǎn)彎次數(shù)和累計(jì)轉(zhuǎn)向角度，促使機(jī)器人按照路徑長(zhǎng)度和轉(zhuǎn)彎角度雙重因素進(jìn)行最優(yōu)選擇。改進(jìn)后的啟發(fā)函數(shù)公式如下：

其中：Q1是大于1的常數(shù)。

3.3 改進(jìn)信息素更新

蟻群算法模擬自然界中的蟻群覓食機(jī)制，采用分布式正反饋并行計(jì)算機(jī)制，傳統(tǒng)蟻群算法是各個(gè)螞蟻單獨(dú)行動(dòng)且每只螞蟻都執(zhí)行相同的操作，螞蟻之間的協(xié)作不足，可能會(huì)導(dǎo)致滯后、算法陷入局部最優(yōu)、收斂速度慢等問(wèn)題。在搜索路徑時(shí)，存在一部分螞蟻找到的路徑是最差路徑，它們所釋放的信息素將對(duì)之后的螞蟻尋路造成負(fù)面影響，從而容易使搜索陷入局部最優(yōu)，還可能出現(xiàn)死鎖情況導(dǎo)致有效螞蟻數(shù)量損失；而另一些螞蟻尋得最優(yōu)路徑，它們所釋放的信息素將對(duì)其余螞蟻尋找最優(yōu)路徑起到促進(jìn)作用。為了提升收斂速度、獲得最優(yōu)路徑，此處融合狼群算法，在蟻群算法的信息素更新公式中加入獵物分配原則［21］。

狼群算法是一種智能優(yōu)化算法，模擬狼群的社會(huì)分工和捕食行為，其分配規(guī)則為“強(qiáng)者生存”的狼群更新機(jī)制，狼群中存在貢獻(xiàn)能力弱的狼，即身體瘦弱的狼，它們獵得食物的數(shù)量和可能性都遠(yuǎn)小于身體強(qiáng)壯的狼，就如蟻群中存在尋得路徑差的螞蟻，這些螞蟻尋得的路徑要差于尋路能力強(qiáng)的螞蟻。

因此，狼群算法中按照狼“由強(qiáng)到弱”的順序進(jìn)行獵物分配，身體強(qiáng)壯且善于捕獵的狼會(huì)優(yōu)先獲得食物，反之身體瘦弱的狼則只能分得很少的食物。隨著每次分配的進(jìn)行，部分身體弱小的狼將越來(lái)越難以生存下去，直至餓死；而先前本就強(qiáng)壯的狼將越發(fā)強(qiáng)壯，在下一次捕獵時(shí)獵得食物的可能性將進(jìn)一步增大，經(jīng)過(guò)迭代，狼群的生存能力被逐漸提高。

在蟻群算法中融合狼群算法中獵物分配原則的動(dòng)機(jī)是借鑒該分配原則來(lái)解決傳統(tǒng)蟻群算法在信息素更新時(shí)存在的問(wèn)題，即尋得最差路徑的螞蟻釋放的信息素將會(huì)對(duì)隨后的螞蟻尋路造成一定的誤導(dǎo)作用，容易使路徑陷入局部最優(yōu)，并且尋得最優(yōu)路徑的螞蟻釋放的信息素不能很好地傳遞給之后的螞蟻。這一融合過(guò)程可以理解為，加強(qiáng)蟻群算法中優(yōu)質(zhì)路徑上的信息素濃度，較弱個(gè)體的經(jīng)驗(yàn)由于參考價(jià)值少，不應(yīng)被著重考慮，便于更多的螞蟻吸收優(yōu)質(zhì)個(gè)體的經(jīng)驗(yàn)，提高收斂速度。

采用狼群算法中“強(qiáng)者生存”的更新機(jī)制有效傳承了整個(gè)螞蟻種群在搜索路徑時(shí)形成的“智慧”、提高全局搜索能力、避免陷入局部最優(yōu)解，符合自然界種群繁衍進(jìn)化的特點(diǎn)，不斷更新的信息素代表著蟻群在整個(gè)路徑搜索過(guò)程中形成的尋路智慧，有利于該智能優(yōu)化算法對(duì)解空間進(jìn)行更好的學(xué)習(xí)。

借鑒這種思想，本文算法在每次迭代中，計(jì)算各個(gè)螞蟻的運(yùn)動(dòng)軌跡長(zhǎng)度，將到達(dá)目標(biāo)點(diǎn)路徑最短的螞蟻所留下的信息素增強(qiáng)，路徑最長(zhǎng)的螞蟻所留下的信息素減弱，突出不同路徑之間信息素的差別化。對(duì)信息素更新公式作如下改進(jìn)：

其中：Δ*τij和Δ**τij分別代表每次迭代中最優(yōu)和最差路徑經(jīng)過(guò)節(jié)點(diǎn)i、j的信息素大??；L*和L**分別代表每次蟻群到達(dá)目標(biāo)點(diǎn)的最短運(yùn)動(dòng)軌跡和最長(zhǎng)運(yùn)動(dòng)軌跡；δ和ω分別表示每次搜索時(shí)找到最短路徑和最長(zhǎng)路徑的螞蟻數(shù)量；Q2為增強(qiáng)因子，此處將其設(shè)為1；R1為減弱因子，將其值設(shè)為0.5。

經(jīng)過(guò)多次迭代后，某條路徑上的信息素值可能遠(yuǎn)大于或遠(yuǎn)小于其他路徑，使得搜索不能繼續(xù)進(jìn)行下去、過(guò)早收斂，為防止這種極端情況產(chǎn)生，借鑒MMAS算法［22］，將信息素的取值范圍限定在τmin到τmax，如式（19）所示：

4 改進(jìn)算法的步驟

綜上所述，本文對(duì)基本蟻群算法改進(jìn)后，移動(dòng)機(jī)器人路徑規(guī)劃的步驟如下：

步驟1 通過(guò)柵格法對(duì)工作環(huán)境進(jìn)行建模，為移動(dòng)機(jī)器人設(shè)定好運(yùn)動(dòng)的起始點(diǎn)和目標(biāo)點(diǎn)。

步驟2 初始化參數(shù)：螞蟻數(shù)量m，信息素重要程度因子α，啟發(fā)函數(shù)重要程度因子β，信息素?fù)]發(fā)系數(shù)ρ，信息素強(qiáng)度系數(shù)Q、迭代次數(shù)N等，其中初始信息素濃度按式（10）設(shè)置。

步驟3 更新禁忌表。將螞蟻k（k=1，2，…，n）放在當(dāng)前節(jié)點(diǎn)上，將當(dāng)前節(jié)點(diǎn)添加到禁忌表中。

步驟4 選擇下一步的網(wǎng)格。根據(jù)式（15）計(jì)算加入A*估價(jià)函數(shù)和轉(zhuǎn)角約束的啟發(fā)式函數(shù)值，然后依據(jù)式（1）～（3）求出狀態(tài)轉(zhuǎn)移概率值。再借鑒輪盤(pán)賭法選出下一步將要到達(dá)的柵格，若螞蟻抵達(dá)目標(biāo)位置，則轉(zhuǎn)到步驟5；反之轉(zhuǎn)到步驟3。

步驟5 如果螞蟻到達(dá)目標(biāo)位置，重復(fù)步驟3，直到每個(gè)螞蟻在其迭代過(guò)程中完成整個(gè)搜索過(guò)程，之后轉(zhuǎn)到步驟6。

步驟6 更新信息素。每次迭代完成，如果此時(shí)迭代次數(shù)小于最大迭代次數(shù)，將按照狼群算法的獵物分配原則即式（16）～（18）計(jì)算路徑上的信息素濃度，同時(shí)要保證其滿足式（19），若滿足收斂條件，則退出；若不滿足，轉(zhuǎn)到步驟3。反之迭代次數(shù)大于最大迭代次數(shù)時(shí)，則停止計(jì)數(shù)，輸出最終結(jié)果。

本文算法整體流程如圖5所示。

圖5 本文算法流程Fig.5 Flowchart of proposed algorithm

5 仿真分析

為了驗(yàn)證本文改進(jìn)蟻群算法的可靠性，使用Matlab 軟件進(jìn)行仿真。分別使用4 種不同規(guī)模的柵格地圖，每次在同樣大小的柵格地圖中，采用相同的實(shí)驗(yàn)條件對(duì)8 種不同的算法進(jìn)行對(duì)比分析。

5.1 參數(shù)取值

關(guān)于蟻群算法主要參數(shù)值的確定，目前沒(méi)有特別詳盡的理論方法，因此本文根據(jù)經(jīng)驗(yàn)反復(fù)實(shí)驗(yàn)而定，設(shè)置不同的參數(shù)組合進(jìn)行仿真，分析實(shí)驗(yàn)結(jié)果，選擇最佳參數(shù)組合。

對(duì)每一個(gè)參數(shù)設(shè)置一組值，以圖3 的柵格地圖為本次實(shí)驗(yàn)環(huán)境，起始點(diǎn)和目標(biāo)點(diǎn)分別用點(diǎn)S和點(diǎn)T在圖中表示，在每次測(cè)試中僅改變一個(gè)參數(shù)的取值，其他參數(shù)為常量，分別計(jì)算最佳路徑長(zhǎng)度和迭代次數(shù)。由于對(duì)規(guī)劃結(jié)果影響較大的參數(shù)是螞蟻數(shù)量m、信息素啟發(fā)因子α和期望啟發(fā)式因子β，因此本文僅介紹這三個(gè)參數(shù)的取值過(guò)程。其余參數(shù)根據(jù)經(jīng)驗(yàn)及實(shí)驗(yàn)仿真對(duì)比，初始化參數(shù)值如表1所示。

表1 初始化參數(shù)值Tab.1 Initialized parameter values

5.1.1 螞蟻數(shù)量m

在蟻群算法中，當(dāng)螞蟻數(shù)目過(guò)多時(shí)，信息素的作用將被削弱，導(dǎo)致蟻群算法的收斂速度變慢；當(dāng)螞蟻數(shù)目過(guò)少時(shí)，可能存在路徑未被選擇的情況，無(wú)法有效搜索到全局最優(yōu)解。因此，選擇合適的螞蟻數(shù)量至關(guān)重要，本文對(duì)除螞蟻數(shù)目m之外的其他參數(shù)取值分別為：α=1，β=7，ρ=0.3，取螞蟻數(shù)量m=10，20，30，40，50，60，70，80，90，100。為防止偶然因素，對(duì)每組數(shù)據(jù)運(yùn)行10次，得到螞蟻數(shù)量m對(duì)計(jì)算結(jié)果的影響如圖6所示。

圖6 螞蟻數(shù)量m對(duì)ACO算法的影響Fig.6 Influence of the number of ants m on ACO algorithm

由圖6 可知，隨著螞蟻數(shù)量從10 變化到40，最短路徑的長(zhǎng)度急劇下降，之后變化幅度減小至不再變化；迭代次數(shù)呈現(xiàn)升降升的趨勢(shì)，在螞蟻數(shù)量為50 時(shí)，迭代次數(shù)達(dá)到最小?？偨Y(jié)發(fā)現(xiàn)，當(dāng)螞蟻數(shù)量約為自由柵格數(shù)的1/6 時(shí)，算法的收斂速度和路徑長(zhǎng)度達(dá)到最優(yōu)。

5.1.2 信息素啟發(fā)因子α和期望啟發(fā)式因子β

α表示當(dāng)前螞蟻受前代蟻群搜索結(jié)果的啟發(fā)程度，β反映的是當(dāng)前環(huán)境相關(guān)信息對(duì)螞蟻的影響程度。α越大，β越小，則螞蟻越依賴(lài)信息素的指導(dǎo)，傾向于選擇之前走過(guò)的路徑；反之，α越小，β越大，則螞蟻更傾向依據(jù)當(dāng)下的環(huán)境選擇較短的路徑抵達(dá)目標(biāo)點(diǎn)。兩者是相互關(guān)聯(lián)的，因此此處選擇將β/α設(shè)為自變量，路徑長(zhǎng)度和迭代次數(shù)作為因變量。設(shè)α=1，β/α取1～10，m=50，ρ=0.3，其余參數(shù)取值如表1。對(duì)計(jì)算結(jié)果的影響如圖7所示。

圖7 β/α對(duì)ACO算法的影響Fig.7 Influence of β/α on ACO algorithm

由圖7 可知，隨著β/α值的遞增，最短路徑長(zhǎng)度逐漸減小直至穩(wěn)定，迭代次數(shù)先減小后增加，在β/α=7 時(shí)取最小值。因此，當(dāng)α=1，β=7時(shí)，蟻群算法各方面具有較優(yōu)的性能。

5.2 小規(guī)模柵格環(huán)境

首先將基本蟻群算法、文獻(xiàn)［12］、文獻(xiàn)［23］、文獻(xiàn)［24］改進(jìn)的蟻群算法及本文算法在20×20、30×30規(guī)模的柵格地圖上進(jìn)行對(duì)比實(shí)驗(yàn)。此處實(shí)驗(yàn)各相關(guān)參數(shù)取值為：m=50，α=1，β=7，其余按表1取值。

5.2.1 20×20柵格環(huán)境

在20×20 規(guī)模的柵格環(huán)境中，5 種算法仿真結(jié)果如圖8 所示。由圖8可知，基本蟻群算法規(guī)劃出的路徑長(zhǎng)度為31.4，文獻(xiàn)［23］算法的路徑長(zhǎng)度為31.4，文獻(xiàn)［24］算法的路徑規(guī)劃長(zhǎng)度為29.8，文獻(xiàn)［12］規(guī)劃出的路徑長(zhǎng)度為28.82，本文算法的最優(yōu)路徑長(zhǎng)度為28.63。

圖8 在20×20地圖上5種算法規(guī)劃的路徑Fig.8 Paths planned by five algorithms on 20×20 map

五種算法的路徑長(zhǎng)度和迭代次數(shù)如圖9 所示。由圖9 可知，本文算法和文獻(xiàn)［23］算法的迭代穩(wěn)定次數(shù)相差不大，比基本蟻群算法和文獻(xiàn)［12］算法減少50%的迭代穩(wěn)定次數(shù)，比文獻(xiàn)［24］的迭代穩(wěn)定次數(shù)也更優(yōu)，具體指標(biāo)比較如表2 所示。由表2 可知，在路徑長(zhǎng)度上，本文改進(jìn)之后的算法運(yùn)行出的最優(yōu)路徑長(zhǎng)度為28.63，較基本蟻群算法和文獻(xiàn)［23］算法縮短8.8%，較文獻(xiàn)［24］算法也縮短了3.9%；在轉(zhuǎn)彎次數(shù)上，本文算法轉(zhuǎn)彎次數(shù)為4，分別較基本蟻群算法和文獻(xiàn)［23］算法減少了75%和50%，大幅減少了轉(zhuǎn)彎次數(shù)；在累計(jì)轉(zhuǎn)彎角度上，較基本蟻群算法、文獻(xiàn)［23］和文獻(xiàn)［24］算法分別減少了720°、270°和180°，規(guī)劃出的路徑更加平滑，避免了移動(dòng)機(jī)器人過(guò)多的能耗損失，延長(zhǎng)了壽命，縮短了轉(zhuǎn)彎時(shí)間。

圖9 在20×20地圖上的路徑長(zhǎng)度迭代圖Fig.9 Path length iteration graph on 20×20 map

文獻(xiàn)［12］算法的主要思想是將蟻群算法生成的全局最優(yōu)路徑再進(jìn)行平滑處理，將路徑中兩個(gè)不在同一直線上的節(jié)點(diǎn)連線，若連線中間不穿過(guò)障礙物則此連線就是新的路徑，以此法來(lái)進(jìn)行路徑平滑處理。由表2 中可以看出，文獻(xiàn)［12］算法能夠有效縮短路徑長(zhǎng)度和累計(jì)轉(zhuǎn)彎角度，但是該算法仍存在明顯不足：在迭代次數(shù)上，該算法需要26 次迭代才能達(dá)到穩(wěn)定，而本文算法僅需4 次即可；在程序運(yùn)行時(shí)間上，文獻(xiàn)［12］算法需要10.632 s，本文算法在6.921 s 內(nèi)即可完成。綜合多種指標(biāo)來(lái)看，在此處柵格環(huán)境下本文算法都要優(yōu)于文獻(xiàn)［12］算法。

表2 在20×20地圖上的仿真結(jié)果Tab.2 Simulation results on 20×20 map

綜上，本文算法生成的路徑綜合指標(biāo)最優(yōu)，改進(jìn)之后的算法優(yōu)勢(shì)明顯。

5.2.2 30×30柵格環(huán)境

為了進(jìn)一步驗(yàn)證本文算法的可靠性，將柵格地圖擴(kuò)大為30×30，障礙物增多，再次進(jìn)行仿真。基本蟻群算法、文獻(xiàn)［12］算法、文獻(xiàn)［23］算法、文獻(xiàn)［24］算法以及本文算法的路徑規(guī)劃如圖10所示。

圖10 在30×30地圖上五種算法規(guī)劃的路徑Fig.10 Paths planned by five algorithms on 30×30 map

由圖10 可以看出，當(dāng)柵格地圖規(guī)模擴(kuò)大并且障礙物增多時(shí)，基本蟻群算法、文獻(xiàn)［12］算法、文獻(xiàn)［23］算法、文獻(xiàn)［24］算法無(wú)法很好地適應(yīng)該類(lèi)較為復(fù)雜環(huán)境的全局路徑規(guī)劃，其規(guī)劃出的最優(yōu)路徑長(zhǎng)度分別為50.2、45.8、47.2和47.5，而本文算法仍然可以很好地執(zhí)行，尋得的最優(yōu)路徑長(zhǎng)度為43.3，較其他算法有效縮短了路徑長(zhǎng)度，路徑長(zhǎng)度與迭代次數(shù)的關(guān)系如圖11所示。

圖11 在30×30地圖上的路徑長(zhǎng)度迭代圖Fig.11 Path length iteration graph on 30×30 map

圖11為五種算法在30×30柵格規(guī)模下的收斂曲線變化趨勢(shì)，可以看出當(dāng)環(huán)境復(fù)雜化后，本文算法及文獻(xiàn)［23］算法在迭代穩(wěn)定次數(shù)上比其余三種算法更優(yōu)，文獻(xiàn)［23］算法的收斂速度比文本算法稍快一些，具體指標(biāo)比較如表3所示。

表3 在30×30地圖上的仿真結(jié)果Tab.3 Simulation results on 30×30 map

由表3 可知，本文的改進(jìn)蟻群算法在路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)以及累計(jì)轉(zhuǎn)彎角度等指標(biāo)上都明顯優(yōu)于基本蟻群算法、文獻(xiàn)［23］及文獻(xiàn)［24］的算法，這三種算法在障礙物增多的環(huán)境中都無(wú)法很好地適應(yīng)，其中本文算法在路徑長(zhǎng)度上較基本蟻群算法縮短了13.7%、較文獻(xiàn)［23］算法和文獻(xiàn)［24］算法縮短了8.3%和8.8%；轉(zhuǎn)彎次數(shù)也是其中最少的，尤其是較基本蟻群算法減少了64.3%；在累計(jì)轉(zhuǎn)彎角度指標(biāo)上，本文算法占明顯優(yōu)勢(shì)，較迭代穩(wěn)定次數(shù)表現(xiàn)較優(yōu)的文獻(xiàn)［23］算法減少了41.2%。另外，可以看出文獻(xiàn)［12］算法、文獻(xiàn)［23］算法和文獻(xiàn)［24］算法在復(fù)雜環(huán)境下出現(xiàn)多次直角轉(zhuǎn)彎，而移動(dòng)機(jī)器人面臨直角轉(zhuǎn)彎時(shí)比45°轉(zhuǎn)彎會(huì)消耗更多的能量，本文算法規(guī)劃的路徑中不存在直角轉(zhuǎn)彎的情況。同時(shí)在實(shí)際運(yùn)動(dòng)中，直角轉(zhuǎn)彎所需要的時(shí)間也更多，將大大增加機(jī)器人從起始點(diǎn)到目標(biāo)點(diǎn)的運(yùn)行時(shí)間，而本文算法不僅累計(jì)轉(zhuǎn)彎角度最小，也有效避免了直角轉(zhuǎn)彎的出現(xiàn)。

目前針對(duì)移動(dòng)機(jī)器人轉(zhuǎn)角減小的研究中，文獻(xiàn)［12］中的平滑方法較為普遍，但該方法存在一定的局限性。由表3 可以看出，在路徑長(zhǎng)度上，文獻(xiàn)［12］算法較其他三種算法更優(yōu)，但本文算法規(guī)劃出的路徑長(zhǎng)度是43.3，比其更短；在轉(zhuǎn)彎次數(shù)上，兩者相同；但在累計(jì)轉(zhuǎn)彎角度上，本文算法比文獻(xiàn)［12］算法減少了20.4%；除此之外，本文算法在迭代穩(wěn)定次數(shù)和程序運(yùn)行時(shí)間上分別比文獻(xiàn)［12］算法減少了50.0%和21.1%。綜合來(lái)看，本文算法在30×30 的柵格地圖中具有更好的計(jì)算結(jié)果，各方面性能更優(yōu)，克服了傳統(tǒng)路徑平滑方法的不足。

由兩次不同規(guī)模的柵格實(shí)驗(yàn)可以看出，環(huán)境變復(fù)雜時(shí)，本文算法仍有良好的適應(yīng)性并且優(yōu)勢(shì)更加明顯，可以尋得一條綜合性能更優(yōu)的路徑。

5.3 大規(guī)模柵格環(huán)境

5.3.1 100×100柵格環(huán)境

為了進(jìn)一步驗(yàn)證本文改進(jìn)算法在規(guī)模較大的柵格地圖中的適應(yīng)性，首先建立100×100 規(guī)模的柵格地圖，將文獻(xiàn)［25］的改進(jìn)A*算法、文獻(xiàn)［26］的改進(jìn)RRT（Rapidly-exploring Random Tree）算法以及本文算法在該規(guī)模的地圖中進(jìn)行仿真，此處實(shí)驗(yàn)各相關(guān)參數(shù)取值為：m=100，α=1，β=7，其余按表1 取值。三種算法的路徑規(guī)劃如圖12所示。

圖12 在100×100地圖上三種算法規(guī)劃的路徑Fig.12 Paths planned by three algorithms on 100×100 map

由圖12可以直觀地看出，相較于改進(jìn)的A*算法以及RRT算法，本文算法生成的路徑擁有更少的轉(zhuǎn)彎次數(shù)，三種算法的具體仿真結(jié)果如表4所示

表4 在100×100地圖上的仿真結(jié)果Tab.4 Simulation results on 100×100 map

由表4 可以看出，改進(jìn)A*算法和改進(jìn)RRT 算法在路徑長(zhǎng)度上相差很小，本文算法規(guī)劃的路徑長(zhǎng)度上更優(yōu)；同時(shí)，在轉(zhuǎn)彎次數(shù)上，本文算法表現(xiàn)更好，規(guī)劃出的路徑最為平滑；本文規(guī)劃路徑的累計(jì)轉(zhuǎn)彎角度較前兩種算法分別減少了19.9%和37.6%；但在程序運(yùn)行時(shí)間上，表現(xiàn)得不如改進(jìn)A*算法優(yōu)異。綜合來(lái)看，本文算法在100×100 規(guī)模的柵格地圖中仍具有良好的適應(yīng)性，規(guī)劃路徑的長(zhǎng)度和轉(zhuǎn)角次數(shù)是最優(yōu)的。

5.3.2 200×200柵格環(huán)境

將柵格規(guī)模再次擴(kuò)大為200×200，此處將文獻(xiàn)［27］的改進(jìn)蟻群算法作為本文算法的對(duì)比算法。將兩者在柵格地圖中進(jìn)行仿真分析，兩種算法的路徑規(guī)劃如圖13所示。

圖13 在200×200地圖上兩種算法規(guī)劃的路徑Fig.13 Paths planned by two algorithms on 200×200 map

由圖13 可知，兩種算法在大規(guī)模的復(fù)雜環(huán)境中均能從起點(diǎn)順利抵達(dá)終點(diǎn)，與文獻(xiàn)［27］算法相比，本文算法規(guī)劃出的路徑更加平滑，轉(zhuǎn)彎次數(shù)更少，具體實(shí)驗(yàn)結(jié)果如表5所示。

表5 在200×200地圖上的仿真結(jié)果Tab.5 Simulation results on 200×200 map

由表5 可知，本文算法在運(yùn)行時(shí)間上稍遜于文獻(xiàn)［27］算法，但在路徑長(zhǎng)度、轉(zhuǎn)彎次數(shù)以及累計(jì)轉(zhuǎn)彎角度上都更占優(yōu)勢(shì)，分別較文獻(xiàn)［27］算法降低了6.7%、55.6%和65.8%。

由以上實(shí)驗(yàn)結(jié)果，驗(yàn)證了本文改進(jìn)蟻群算法在復(fù)雜地形環(huán)境中進(jìn)行路徑規(guī)劃的可行性和有效性。

6 結(jié)語(yǔ)

本文針對(duì)基本蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃應(yīng)用上存在的缺陷，提出了基于轉(zhuǎn)彎角度約束的改進(jìn)蟻群算法。規(guī)劃不同柵格的初始信息素值，在啟發(fā)函數(shù)中有效融合了A*算法的尋路能力，以路徑長(zhǎng)度和轉(zhuǎn)彎角度兩因素為下一步柵格的選擇指標(biāo)，使路徑更加平滑，并且在信息素更新中引入了狼群算法的分配原則，同時(shí)限制最大最小信息素的值。本文改進(jìn)之后的算法使螞蟻能在更短的時(shí)間內(nèi)尋得一條綜合路徑長(zhǎng)度和轉(zhuǎn)角次數(shù)的最優(yōu)路徑，降低了移動(dòng)機(jī)器人的能耗損失，延長(zhǎng)壽命，使其能高效、安全地移動(dòng)到目標(biāo)點(diǎn)，驗(yàn)證了本文算法在復(fù)雜環(huán)境中的有效性和適應(yīng)性。

在今后的研究中，將進(jìn)一步研究蟻群算法參數(shù)的取值問(wèn)題，利用神經(jīng)網(wǎng)絡(luò)計(jì)算出使路徑更優(yōu)的參數(shù)取值，將大大節(jié)約調(diào)試時(shí)間，使算法更加智能化。