基于改進(jìn)ACS 算法的移動(dòng)機(jī)器人路徑規(guī)劃研究

馬小陸，梅宏，龔瑞，王兵，吳紫恒

（1.安徽工業(yè)大學(xué) 電氣與信息工程學(xué)院，安徽 馬鞍山 243032；2.特種重載機(jī)器人安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 馬鞍山 243032）

路徑規(guī)劃問(wèn)題是移動(dòng)機(jī)器人研究的重點(diǎn)對(duì)象之一，是指移動(dòng)機(jī)器人依據(jù)現(xiàn)有信息規(guī)劃出一條從起始位置安全到達(dá)目標(biāo)位置，且滿足各項(xiàng)性能指標(biāo)的完整路徑[1].近年來(lái)，國(guó)內(nèi)外學(xué)者對(duì)路徑規(guī)劃問(wèn)題進(jìn)行了大量的研究，并取得了一定的成果.傳統(tǒng)路徑規(guī)劃算法有Dijkstra 算法[2]、A*算法[3]、人工勢(shì)場(chǎng)法[4]等，隨著移動(dòng)機(jī)器人工作空間復(fù)雜度的提升，逐漸涌現(xiàn)出一系列的智能仿生算法，如遺傳算法[5]、粒子群算法[6]、人工蜂群算法[7]等.

螞蟻系統(tǒng)（Ant System，AS）是由Dorigo 等[8]提出的一種模擬自然界中螞蟻覓食行為的仿生算法.雖然AS 算法已經(jīng)能夠有效解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，但是依舊存在收斂速度慢、易陷入局部最優(yōu)等問(wèn)題，因此，Dorigo 等[9]于1997 年提出了蟻群系統(tǒng)（Ant Colony System，ACS）.ACS 算法具有并行性、強(qiáng)魯棒、易實(shí)現(xiàn)等優(yōu)點(diǎn)，可以有效解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，但是ACS 算法仍存在尋路速度慢、易陷入局部最優(yōu)、路徑不平滑等問(wèn)題.針對(duì)上述問(wèn)題，國(guó)內(nèi)外學(xué)者提出了多種優(yōu)化方法.文獻(xiàn)[10]引入了蟻周模型更新信息素，提高了蟻群搜索效率，降低局部最優(yōu)概率；文獻(xiàn)[11]提出了一種A*算法和ACS 算法的融合算法，加快了算法的收斂速度，提高了最優(yōu)路徑的質(zhì)量；文獻(xiàn)[12]引入了信息素閾值，提高了算法的全局搜索能力，增加了最優(yōu)路徑的多樣性；文獻(xiàn)[13]提出了一種自適應(yīng)啟發(fā)函數(shù)，提高了蟻群的尋路效率，加快了算法的收斂速度.

針對(duì)ACS 算法收斂速度慢、易陷入局部最優(yōu)和路徑轉(zhuǎn)折點(diǎn)數(shù)量過(guò)多等問(wèn)題，本文在ACS 算法的基礎(chǔ)上提出了一種引力蟻群系統(tǒng)（Gravitational Search Ant Colony System，GSACS）算法.首先，引入了簡(jiǎn)化的ACS 算法，對(duì)初始信息素濃度進(jìn)行更新，降低了算法初期蟻群尋路的盲目性；同時(shí)，引入了萬(wàn)有引力搜索策略，提升了算法路徑尋優(yōu)的收斂速度，有效克服了局部最優(yōu)問(wèn)題；最后，提出了路徑優(yōu)化方法，減少了路徑轉(zhuǎn)折點(diǎn)數(shù)量，提升了移動(dòng)機(jī)器人的導(dǎo)航效率.仿真和實(shí)驗(yàn)結(jié)果證明，GSACS 算法所規(guī)劃出的路徑是有效且可行的，并且相比于ACS 算法，尋路效率更高.

1 蟻群系統(tǒng)算法

自然界中，螞蟻在覓食時(shí)會(huì)不斷向周?chē)h(huán)境中釋放一種名為信息素的物質(zhì)，當(dāng)某條路徑上的信息素濃度逐漸增多，則越來(lái)越多的螞蟻都會(huì)選擇該路徑行走[14].在ACS 算法中，若螞蟻k 當(dāng)前位置為節(jié)點(diǎn)i，將根據(jù)偽隨機(jī)比率規(guī)則計(jì)算出后續(xù)行走的節(jié)點(diǎn)j，其公式如式（1）所示.

式中：q0（q0∈[0，1]）為常數(shù)；q（q∈[0，1]）為隨機(jī)數(shù).若q≤q0，則按照上述公式篩選后續(xù)行走節(jié)點(diǎn)；若q＞q0，則按照（t）選擇后續(xù)行走節(jié)點(diǎn).（t）如式（2）所示.

式中：α 為信息啟發(fā)因子；β 為距離啟發(fā)因子；Ak為螞蟻k 可以行走鄰節(jié)點(diǎn)的集合；為節(jié)點(diǎn)i 到節(jié)點(diǎn)j的啟發(fā)信息，其公式如式（3）所示.

當(dāng)螞蟻由節(jié)點(diǎn)i 移動(dòng)到節(jié)點(diǎn)j 時(shí)，更新路徑〈i，j〉上的局部信息素濃度，其公式如式（4）所示.

式中：ζ 為局部信息素濃度揮發(fā)系數(shù)；τ0為路徑〈i，j〉上的初始信息素濃度值.

當(dāng)所有螞蟻完成一次迭代尋路時(shí)，則會(huì)更新當(dāng)前最優(yōu)路徑上的全局信息素濃度[15]，其公式如式（5）（6）所示.

2 萬(wàn)有引力算法

2.1 基本原理

萬(wàn)有引力算法（Gravitational Search Algorithm，GSA）[16]是Rashedi 等于2009 年提出的一種新的啟發(fā)式智能優(yōu)化算法.根據(jù)牛頓的萬(wàn)有引力定律可知，空間中兩個(gè)物體間的相互作用力F 與慣性質(zhì)量成正比，與距離的平方成反比，引力F 如式（7）所示.

式中：G 為引力常數(shù)；m1和m2分別為兩個(gè)物體的質(zhì)量；r 為兩物體之間的距離.

GSA 算法通過(guò)種群的粒子位置移動(dòng)來(lái)尋找最優(yōu)解，隨著算法的不斷迭代，粒子依靠相互作用力在空間中不停的搜索運(yùn)動(dòng)，直至搜索到最優(yōu)解.由于GSA存在收斂速度過(guò)快、全局搜索能力較差、局部最優(yōu)問(wèn)題較為嚴(yán)重等問(wèn)題，導(dǎo)致該算法并沒(méi)有被廣泛應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃任務(wù)中.

2.2 數(shù)學(xué)模型

假設(shè)一個(gè)d 維空間內(nèi)有N 個(gè)粒子，定義第i 個(gè)粒子的位置如式（8）所示.

在t 時(shí)刻，粒子i 在第d 維空間上受到粒子j 的引力大小為（t），其公式如式（9）所示.

式中：Mi（t）和Mj（t）分別表示t 時(shí)刻粒子i 和粒子j的質(zhì)量；ε 為一個(gè)很小的常數(shù)；Rij（t）為t 時(shí)刻粒子i與j 之間的歐幾里得距離，其公式如式（10）所示；G（t）為t 時(shí)刻下的引力系數(shù)，其公式如式（11）所示.

式中：G0為初始時(shí)引力常數(shù)；α 為一個(gè)常量；T 為最大迭代次數(shù).

為了增強(qiáng)隨機(jī)可能性，定義在t 時(shí)刻，粒子X(jué)i在k 維空間中所受引力合力（t）等于周邊所有粒子對(duì)其引力之和（t）如式（12）所示.

式中：rj（rj∈[0，1]）為隨機(jī)數(shù).在t 時(shí)刻，粒子i 在k 維空間上的加速度（t）如式（13）所示.

式中：Mi（t）為粒子i 的慣性質(zhì)量，其公式如式（14）（15）所示.

式中：Si（t）為粒子i 在t 時(shí)刻的適應(yīng)度值；B（t）為粒子i 在t 時(shí)刻最優(yōu)適應(yīng)度值；W（t）為粒子i 在t 時(shí)刻最差適應(yīng)度函數(shù).B（t）和W（t）分為最小化和最大化問(wèn)題進(jìn)行定義.

1）最小化問(wèn)題：

2）最大化問(wèn)題：

在每迭代一次中，粒子i 的速度和位置分別按式（20）（21）進(jìn)行更新：

3 改進(jìn)的ACS 算法

ACS 算法是目前應(yīng)用較為廣泛的一種路徑規(guī)劃算法，但依舊存在收斂速度慢、易陷入局部最優(yōu)、路徑不平滑等問(wèn)題.針對(duì)以上問(wèn)題，本文提出了引力蟻群系統(tǒng)算法，首先引入一種簡(jiǎn)化ACS 算法，對(duì)初始信息素濃度進(jìn)行更新；其次引入GSA 搜索策略，提升算法的收斂速度；最后提出了一種路徑優(yōu)化方法，提升了路徑的平滑性.

3.1 改進(jìn)的初始信息素分配規(guī)則

在傳統(tǒng)ACS 算法中，柵格地圖各節(jié)點(diǎn)上的初始信息素濃度均為τ0，從而導(dǎo)致蟻群在算法初期的收斂性較差、尋路時(shí)間較長(zhǎng).針對(duì)上述問(wèn)題，本文對(duì)初始信息素分配規(guī)則進(jìn)行了改進(jìn)，引入了簡(jiǎn)化ACS 算法，對(duì)初始信息素濃度重新分配，在算法尋路初期加入環(huán)境的先驗(yàn)知識(shí)，提高了算法前期的收斂速度.

簡(jiǎn)化ACS 算法的種群數(shù)量為1，即只派出一只螞蟻進(jìn)行路徑搜索.由零點(diǎn)定理可知，最優(yōu)路徑一般存在于起始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)為頂點(diǎn)的矩形區(qū)域內(nèi).定義該螞蟻在尋路時(shí)，只在鄰節(jié)點(diǎn)中篩選最大信息素和距離的節(jié)點(diǎn)，同時(shí)簡(jiǎn)化ACS 算法，不進(jìn)行局部信息素濃度更新，其轉(zhuǎn)移公式如式（22）所示.

由于初始信息素濃度為均值，由式（22）可知，螞蟻在行走時(shí)，傾向于選擇朝向目標(biāo)節(jié)點(diǎn)的方向行走，由于缺少地圖的先驗(yàn)知識(shí)，螞蟻易陷入“死鎖”狀態(tài)，即無(wú)后續(xù)可行走節(jié)點(diǎn).針對(duì)上述問(wèn)題，本文采用回溯法重新計(jì)算其父節(jié)點(diǎn)的后續(xù)可移動(dòng)節(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)放入禁忌表中.重復(fù)上述過(guò)程，直至螞蟻搜索到目標(biāo)節(jié)點(diǎn)，此時(shí)簡(jiǎn)化的ACS 算法完成了一條完整路徑的規(guī)則.

簡(jiǎn)化ACS 算法完成路徑搜索后，將會(huì)更新此路徑上的全局信息素濃度，其余節(jié)點(diǎn)上的濃度不變.信息素更新公式如式（23）所示.

式中：ω 為初始信息素濃度增加系數(shù).

如圖1 所示，黑色折線為簡(jiǎn)化ACS 算法搜索到的一條完整路徑，此時(shí)更新灰色節(jié)點(diǎn)上的初始信息素濃度，其他節(jié)點(diǎn)上的初始信息素濃度不變.由蟻群的狀態(tài)轉(zhuǎn)移概率可知，蟻群更傾向于選擇信息素濃度更高的節(jié)點(diǎn)行走，因此初始信息素濃度的不均勻分配將有效降低蟻群尋路的盲目性，提升算法的收斂速度.

圖1 初始信息素分配Fig.1 Initial pheromone allocation

3.2 改進(jìn)的啟發(fā)信息函數(shù)

傳統(tǒng)ACS 算法路徑尋優(yōu)時(shí)，螞蟻k 從當(dāng)前節(jié)點(diǎn)i 搜索后續(xù)的行走節(jié)點(diǎn)j 時(shí)，只受到信息素濃度和距離這兩個(gè)因素的影響.迭代次數(shù)越多，最優(yōu)路徑上的信息素濃度越高，最終所有螞蟻都將聚集到這條路徑上，但是由于ACS 算法的全局搜索能力較強(qiáng)，蟻群尋路盲目性較大，從而導(dǎo)致算法的收斂速度受到很大影響.針對(duì)上述問(wèn)題，本文引入了GSA 搜索策略，提升了算法尋路時(shí)的收斂速度.

3.2.1 引力蟻群規(guī)則

在GSACS 算法中，將螞蟻視為粒子，螞蟻k 對(duì)其他螞蟻產(chǎn)生引力，同時(shí)螞蟻k 也受到其他螞蟻引力的影響，目標(biāo)點(diǎn)也對(duì)所有螞蟻產(chǎn)生引力.目標(biāo)節(jié)點(diǎn)的慣性質(zhì)量Mgoal（t）=1.

慣性質(zhì)量由蟻群的適應(yīng)度函數(shù)值決定，本文定義螞蟻k 的適應(yīng)度函數(shù)值fk（t）為當(dāng)前位置距離目標(biāo)節(jié)點(diǎn)的歐幾里得距離.其公式如式（24）所示.

式中：（xk，yk）和（xg，yg）分別為螞蟻k 當(dāng)前位置節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的坐標(biāo).

螞蟻k 受到的引力Fk（t）為所有螞蟻和目標(biāo)節(jié)點(diǎn)對(duì)螞蟻k 的引力合力，其公式如式（25）所示.

式中：Fkj（t）為螞蟻k 受到螞蟻j 的引力；Fkgoal（t）為螞蟻k 受到目標(biāo)節(jié)點(diǎn)的引力；rgoal（rgoal∈[0，1]）為隨機(jī)數(shù).

螞蟻k 的加速度ak（t）如式（26）所示.

式中：Mk（t）為螞蟻k 的慣性質(zhì)量.

如圖2 所示，F(xiàn)kj為螞蟻k 受螞蟻j 的引力，F(xiàn)kgoal為螞蟻k 受目標(biāo)點(diǎn)的引力，矢量合力Fk為螞蟻k 向目標(biāo)節(jié)點(diǎn)G 行走的加速力，由于合力Fk的大小是由蟻群和目標(biāo)節(jié)點(diǎn)共同決定的，從而可以有效避免蟻群陷入局部最優(yōu).

圖2 移動(dòng)機(jī)器人受力方向示意圖Fig.2 Schematic diagram of force direction of mobile robot

3.2.2 改進(jìn)的啟發(fā)信息函數(shù)

在GSACS 算法中，螞蟻k 搜索后續(xù)節(jié)點(diǎn)的啟發(fā)信息由引力啟發(fā)信息和距離啟發(fā)信息組成.引力啟發(fā)信息為螞蟻k 在柵格地圖中所受到引力的合力，其公式如式（27）所示.

式中：γ 為常數(shù)；ak為螞蟻k 受到引力的合力而獲得的加速度；θ 為螞蟻可移動(dòng)節(jié)點(diǎn)和加速度ak方向的夾角.

由式（27）可知，引力啟發(fā)信息在加速度和方向夾角的共同作用下，使螞蟻k 更傾向于選擇加速度更大的節(jié)點(diǎn)行走.引力啟發(fā)信息使蟻群逐漸聚集到一條路徑上，雖然收斂速度更快，但是全局搜索能力較弱，且易出現(xiàn)局部最優(yōu)解.GSACS 算法在啟發(fā)信息中引入加速度系數(shù)ξ，其公式如式（28）所示.

式中：N 為當(dāng)前迭代次數(shù)；Nmax為最大迭代次數(shù).

算法尋路初期，在加速度系數(shù)ξ 的影響下，螞蟻k 的加速度為0，引力啟發(fā)信息為1，此時(shí)蟻群尋路完全由距離啟發(fā)信息發(fā)揮作用；隨著迭代次數(shù)增多，引力啟發(fā)信息隨之增大，加速度逐漸對(duì)蟻群尋路產(chǎn)生影響.

由距離啟發(fā)信息和引力啟發(fā)信息可知，改進(jìn)算法的啟發(fā)信息ηij（t）如式（29）所示.

螞蟻k 在柵格環(huán)境行走時(shí)，分別受到蟻群和目標(biāo)節(jié)點(diǎn)對(duì)其的引力作用，本文定義移動(dòng)機(jī)器人在工作空間內(nèi)可向周?chē)? 個(gè)方向移動(dòng).如圖3 所示，假設(shè)機(jī)器人當(dāng)前兩條可行路徑分別為①和②，矢量合力Fk與兩條可行路徑的夾角θ1＜θ2，且由式（1）（2）和式（29）可知，合力Fk與可行路徑夾角越小，啟發(fā)信息ηij（t）值越大，則該路徑的轉(zhuǎn)移概率越大，從而螞蟻k選擇路徑①行走的概率也越大.

圖3 移動(dòng)機(jī)器人受力分析圖Fig.3 Force analysis diagram of mobile robot

3.3 路徑平滑性處理

GSACS 算法是基于柵格地圖進(jìn)行路徑規(guī)劃，由于算法只選擇長(zhǎng)度最短的路徑作為最終路徑，并不對(duì)路徑轉(zhuǎn)折點(diǎn)數(shù)量進(jìn)行判斷.蟻群在搜索后續(xù)節(jié)點(diǎn)時(shí)，僅由信息素濃度和啟發(fā)信息決定，蟻群更優(yōu)于選擇信息素更大、距離目標(biāo)節(jié)點(diǎn)更近的節(jié)點(diǎn)作為后續(xù)節(jié)點(diǎn)，從而導(dǎo)致算法規(guī)劃出的路徑轉(zhuǎn)折點(diǎn)數(shù)量過(guò)多.

本文在當(dāng)前路徑的基礎(chǔ)上，進(jìn)行路徑平滑性處理，提升了ACS 算法規(guī)劃路徑的平滑性，使得移動(dòng)機(jī)器人行走更加平滑，減少運(yùn)行時(shí)間、提升工作效率.如圖4 所示，實(shí)線和虛線分別為兩條長(zhǎng)度相等的路徑，其中實(shí)線為算法規(guī)劃出的路徑，虛線為平滑處理后的路徑，由圖可以看出，虛線只存在一個(gè)轉(zhuǎn)折點(diǎn)，路徑更加平滑，從而更適合移動(dòng)機(jī)器人的行走.

圖4 最短路徑示意圖Fig.4 Shortest path diagram

路徑平滑性處理方法如下：

設(shè)優(yōu)化ACS 算法當(dāng)前獲取到的最短路徑為P={S，x1，…，xi，…，xp，G}，其中S 為起始節(jié)點(diǎn)；G 為目標(biāo)節(jié)點(diǎn)；xi為完整路徑的中間節(jié)點(diǎn).首先定義起始節(jié)點(diǎn)S 為當(dāng)前優(yōu)化節(jié)點(diǎn)，并依據(jù)起始節(jié)點(diǎn)S 和目標(biāo)節(jié)點(diǎn)G獲取過(guò)渡節(jié)點(diǎn)T，若路徑〈S，T，G〉不與障礙物發(fā)生碰撞，則稱該路徑為合理路徑；反之則稱該路徑為不合理路徑，同時(shí)開(kāi)始計(jì)算起始節(jié)點(diǎn)S 和后續(xù)節(jié)點(diǎn)xp的過(guò)渡節(jié)點(diǎn)T1，并判斷路徑〈S，T，xp，G〉是否為合理路徑，若該路徑為合理路徑，則結(jié)束起始節(jié)點(diǎn)S 的路徑平滑，選取節(jié)點(diǎn)x1和目標(biāo)節(jié)點(diǎn)G 開(kāi)始計(jì)算過(guò)渡節(jié)點(diǎn)，不斷重復(fù)上述過(guò)程，直至選取的節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)重合，此時(shí)已經(jīng)完成了路徑平滑性處理.過(guò)渡節(jié)點(diǎn)的公式如式（30）（31）所示.

式中：dx和dy分別為當(dāng)前計(jì)算兩個(gè)節(jié)點(diǎn)的橫、縱坐標(biāo)之差，公式如式（32）（33）所示.

式中：（x1，y1）和（x2，y2）分別為當(dāng)前計(jì)算的兩個(gè)節(jié)點(diǎn)的坐標(biāo).

路徑平滑處理過(guò)程如圖5 所示，其中S 為起始節(jié)點(diǎn)，G 為目標(biāo)節(jié)點(diǎn).蟻群迭代N 次獲取當(dāng)前最優(yōu)路徑后，首先依據(jù)節(jié)點(diǎn)S 和節(jié)點(diǎn)G 獲取過(guò)渡節(jié)點(diǎn)T，判斷路徑〈S，T，G〉是否為合理路徑，如圖5（a）所示.由于路徑〈S，T，G〉為不合理路徑，此時(shí)將依據(jù)節(jié)點(diǎn)S 和節(jié)點(diǎn)x 獲取過(guò)渡節(jié)點(diǎn)T 并判斷路徑〈S，T，x〉是否合理，如果路徑合理，則利用路徑〈S，T，x，G〉替代原路徑〈S，x，G〉，如圖5（b）所示.若發(fā)現(xiàn)了一條優(yōu)化路徑，則結(jié)束節(jié)點(diǎn)S 的路徑優(yōu)化，并選取后續(xù)節(jié)點(diǎn)x1作為當(dāng)前優(yōu)化節(jié)點(diǎn)，如圖5（c）所示.依據(jù)節(jié)點(diǎn)x1和節(jié)點(diǎn)G 獲取過(guò)渡節(jié)點(diǎn)T，并判斷路徑〈x1，T，G〉是否合理，若路徑合理，則利用路徑〈S，x1，T，G〉替代原路徑，反之則繼續(xù)進(jìn)行后續(xù)節(jié)點(diǎn)的路徑優(yōu)化，如圖5（d）所示.直至當(dāng)前判斷節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)G 重合時(shí)，則結(jié)束路徑優(yōu)化，并利用優(yōu)化路徑替換原路徑.

圖5 路徑優(yōu)化過(guò)程示意圖Fig.5 Schematic diagram of path optimization process

由上述路徑優(yōu)化過(guò)程可知，平滑處理后路徑的轉(zhuǎn)折點(diǎn)數(shù)量更少、路徑更加平滑，從而可以減少移動(dòng)機(jī)器人導(dǎo)航時(shí)的轉(zhuǎn)彎次數(shù)，使得移動(dòng)機(jī)器人在工作環(huán)境中行使更加靈活，降低移動(dòng)機(jī)器人運(yùn)行時(shí)間及能耗的損失，提高工作效率.

4 仿真及實(shí)驗(yàn)驗(yàn)證

4.1 仿真驗(yàn)證

為了驗(yàn)證GSACS 算法的有效性，利用不同規(guī)格的柵格地圖進(jìn)行仿真試驗(yàn).仿真用的計(jì)算機(jī)性能參數(shù)為：主頻為2.80 GHz 的英特爾酷睿i7-7700 處理器，內(nèi)存大小為12 G，運(yùn)行的系統(tǒng)為Windows10，利用Visual Studio 2017 軟件分別對(duì)ACS 算法和GSACS 算法進(jìn)行仿真試驗(yàn).試驗(yàn)中2 種算法參數(shù)設(shè)置如表1 所示.

表1 算法參數(shù)設(shè)置Tab.1 Experiment parameters

30×30 的柵格仿真環(huán)境如圖6 所示，其中起始節(jié)點(diǎn)坐標(biāo)為（1，1），目標(biāo)節(jié)點(diǎn)坐標(biāo)為（30，30），黑色柵格為障礙物，黑色折線為兩種算法規(guī)劃出的最優(yōu)路徑.由圖6 可以得出，GSACS 算法較ACS 算法而言，路徑轉(zhuǎn)折點(diǎn)數(shù)量更少，從而規(guī)劃出的路徑平滑性更高，且有效克服了局部最優(yōu)問(wèn)題.

圖6 相同環(huán)境下2 種算法路徑規(guī)劃結(jié)果Fig.6 Path planning results of two algorithms in the same environment

圖7 為ACS 算法和GSACS 算法在30×30 柵格中的最短路徑收斂圖.由圖7 可以得出，ACS 算法和GSACS 算法的收斂迭代次數(shù)分別為47 次和34 次，GSACS 算法的收斂速度要明顯優(yōu)于ACS 算法，獲取的最優(yōu)路徑長(zhǎng)度也要優(yōu)于ACS 算法.

圖7 最短路徑長(zhǎng)度變化圖Fig.7 Shortest path length variation graph

為了驗(yàn)證GSACS 算法在不同柵格地圖環(huán)境下的有效性和實(shí)用性，分別采用另外幾組環(huán)境模型進(jìn)行路徑尋優(yōu)試驗(yàn)，試驗(yàn)結(jié)果如表2 所示.由表2 可以得出，GSACS 算法在不同柵格地圖環(huán)境下路徑尋優(yōu)的收斂速度、路徑長(zhǎng)度、收斂時(shí)間、轉(zhuǎn)折點(diǎn)數(shù)量等，均要優(yōu)于ACS 算法，且隨著環(huán)境復(fù)雜度的提升，GSACS算法的優(yōu)越性越明顯.

表2 不同地圖環(huán)境下2 種算法仿真數(shù)據(jù)對(duì)比Tab.2 Comparison of simulation data of two algorithms under different map environments

4.2 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證算法的有效性和可行性，將ACS 算法和GSACS 算法分別應(yīng)用到實(shí)際的基于ROS（Robot Operating System）的移動(dòng)機(jī)器人導(dǎo)航實(shí)驗(yàn)中.本文所使用的移動(dòng)機(jī)器人底盤(pán)是四輪行走結(jié)構(gòu)的輪式機(jī)器人，其中前輪為被動(dòng)輪，后輪為驅(qū)動(dòng)輪，移動(dòng)機(jī)器人實(shí)物如圖8 所示.

圖8 實(shí)驗(yàn)所用移動(dòng)機(jī)器人Fig.8 The mobile robot used in the experiment

移動(dòng)機(jī)器人底座控制平臺(tái)主要有激光雷達(dá)、STM32 控制板、光電編碼器、驅(qū)動(dòng)器、直流無(wú)刷電機(jī)、蓄電池、前后輪和多種接口等組成.STM32 作為平臺(tái)控制的核心，將編碼器數(shù)據(jù)發(fā)送給上位機(jī)，上位機(jī)會(huì)根據(jù)編碼器信息和激光雷達(dá)數(shù)據(jù)計(jì)算角速度和線速度發(fā)送給STM32，STM32 將速度分解成機(jī)器人左右輪的速度，之后通過(guò)中斷引腳給電機(jī)驅(qū)動(dòng)器輸送高低電平，并由驅(qū)動(dòng)器根據(jù)接收到的PWM 脈沖信號(hào)控制電機(jī)轉(zhuǎn)動(dòng)，從而實(shí)現(xiàn)移動(dòng)機(jī)器人的自主導(dǎo)航.

由于ACS 算法中的信息啟發(fā)因子α 和距離啟發(fā)因子β 在實(shí)際應(yīng)用中非常重要，目前參數(shù)的設(shè)置基本依靠實(shí)驗(yàn)統(tǒng)計(jì)數(shù)據(jù)和經(jīng)驗(yàn)值來(lái)確定.本文為了確定α 和β 的取值，選取不同環(huán)境進(jìn)行移動(dòng)機(jī)器人導(dǎo)航實(shí)驗(yàn)，在參數(shù)變化范圍內(nèi)設(shè)置不同的參數(shù)組合，每次實(shí)驗(yàn)只改變一個(gè)參數(shù)的值，獲取ACS 算法尋路時(shí)間和柵格地圖中路徑長(zhǎng)度的實(shí)驗(yàn)數(shù)據(jù)，從而確定最優(yōu)參數(shù)的組合.測(cè)試參數(shù)為：α∈{1，2，…，7，8}、β∈{1，2，…，7，8}，參數(shù)默認(rèn)設(shè)為α=1、β=7，柵格地圖分辨率R=0.05.實(shí)驗(yàn)結(jié)果如圖9 和圖10 所示.

由圖9 可以看出，當(dāng)β 不變，信息啟發(fā)因子α 不斷增大時(shí)，算法很難搜索到最優(yōu)路徑，且尋路時(shí)間不斷增加；由圖10 可以看出，當(dāng)α 不變，距離啟發(fā)因子β 不斷增大時(shí)，尋路時(shí)間和最優(yōu)路徑長(zhǎng)度逐漸減小.

圖9 信息啟發(fā)因子對(duì)算法性能的影響曲線Fig.9 The influence curve of information heuristic factor on algorithm performance

圖10 距離啟發(fā)因子對(duì)算法性能的影響曲線Fig.10 The influence curve of distance heuristic factor on algorithm performance

由上述分析可知，α 和β 的作用是相互耦合的，且α 和β 的組合設(shè)置對(duì)算法的性能有很大影響，初始信息素τ0對(duì)算法的結(jié)果影響不大，因此本文選取最優(yōu)組合為α=1、β=7、τ0=0.000 3.

導(dǎo)航實(shí)驗(yàn)中，在相同環(huán)境下，選擇相同的起點(diǎn)和目標(biāo)點(diǎn)分別進(jìn)行2 組對(duì)比實(shí)驗(yàn)，2 種算法生成的最終路徑分別如圖11 和圖12 中標(biāo)注路徑的折線所示.

由圖11 和圖12 可以得出，ACS 算法規(guī)劃出的路徑存在轉(zhuǎn)折點(diǎn)數(shù)量過(guò)多、局部最優(yōu)等問(wèn)題，上述問(wèn)題可能會(huì)導(dǎo)致移動(dòng)機(jī)器人行走時(shí)頻繁轉(zhuǎn)向，降低導(dǎo)航效率，甚至減少移動(dòng)機(jī)器人的使用壽命.GSACS 算法規(guī)劃出的路徑更加平滑，有效克服了局部最優(yōu)問(wèn)題，從而GSACS 算法規(guī)劃出的路徑質(zhì)量更優(yōu).2 種算法路徑尋優(yōu)的試驗(yàn)數(shù)據(jù)如表3 所示.

圖11 目標(biāo)點(diǎn)1 下2 種算法的路徑規(guī)劃結(jié)果Fig.11 The path planning results of the two algorithms at target point 1

圖12 目標(biāo)點(diǎn)2 下2 種算法的路徑規(guī)劃結(jié)果Fig.12 The path planning results of the two algorithms at target point 2

表3 2 種算法尋路數(shù)據(jù)對(duì)比Tab.3 Comparison of path finding data of the two algorithms

由表3 可知，目標(biāo)點(diǎn)1 下ACS 算法和GSACS 算法尋路時(shí)間分別為484.8 ms 和340.6 ms，GSACS 算法的尋路效率提升了約29.7%.目標(biāo)點(diǎn)2 下ACS 算法和GSACS 算法的尋路時(shí)間分別為703.4 ms 和532.1 ms，GSACS 算法尋路效率提升了約24.3%.由上述分析可知，GSACS 算法相比于ACS 算法，尋路效率更高、路徑質(zhì)量更優(yōu).

5 結(jié)論

本文針對(duì)ACS 算法在路徑規(guī)劃時(shí)存在收斂速度慢、易陷入局部最優(yōu)、路徑轉(zhuǎn)折點(diǎn)數(shù)量多等缺點(diǎn)，提出了一種基于GSA 搜索策略的改進(jìn)ACS 算法.該算法首先引入了一種簡(jiǎn)化的ACS 算法，對(duì)初始信息素濃度進(jìn)行更新，減少了蟻群尋路時(shí)的盲目性、提高了算法前期的收斂速度；其次引入了GSA 搜索策略，對(duì)螞蟻尋找后續(xù)行走節(jié)點(diǎn)的策略進(jìn)行了改進(jìn)，提高了算法的收斂速度；最后提出了路徑優(yōu)化方法，減少了規(guī)劃路徑的轉(zhuǎn)折點(diǎn)數(shù)量，提升了路徑的光滑度.仿真試驗(yàn)結(jié)果表明，改進(jìn)算法相比于ACS 算法，收斂速度更快、路徑質(zhì)量更優(yōu)化、尋路效率更高.導(dǎo)航實(shí)驗(yàn)結(jié)果得出，改進(jìn)后的GSACS 算法能夠有效解決路徑規(guī)劃任務(wù)，且機(jī)器人導(dǎo)航效率要優(yōu)于ACS 算法.