一種改進(jìn)蟻群算法的移動機(jī)器人路徑規(guī)劃算法

沈葭櫟，李燕，2，季建楠，佘宇

（1.南京信息工程大學(xué)，自動化學(xué)院，南京210044；2.南京信息工程大學(xué)濱江學(xué)院，物聯(lián)網(wǎng)學(xué)院，無錫214105）

0 引言

移動機(jī)器人的路徑規(guī)劃在機(jī)器人技術(shù)中尤為重要。移動機(jī)器人可通過人類的設(shè)計規(guī)劃，替代人類進(jìn)行危險復(fù)雜的工作。移動機(jī)器人路徑規(guī)劃常用的算法有Dijkstra算法［1］、A*算法［2］、人工勢場法［3］等。在較多障礙物的情況下，仿生智能算法能夠幫助移動機(jī)器人尋找到較優(yōu)路徑。近年來一些學(xué)者通過粒子群算法［4］、遺傳算法［5］、DNA計算［6］、蟻群算法等來解決機(jī)器人路徑規(guī)劃問題。

Marco Dorigo于1992年在他的博士論文中提出蟻群算法，是一種啟發(fā)式全局優(yōu)化算法。蟻群算法具有正反饋、并行性，易與其他算法相結(jié)合的優(yōu)點(diǎn)［7］。但傳統(tǒng)蟻群算法存在收斂速度慢，易陷入局部最優(yōu)等問題。近年來一些學(xué)者提出了一些改進(jìn)的蟻群算法。2014年杜鵬楨等人提出一種面向?qū)ο蟮亩嘟巧伻核惴ǎ瑢ο伻航Y(jié)構(gòu)進(jìn)行優(yōu)化分為分工不同地三種蟻群，僅各蟻群最優(yōu)個體進(jìn)行信息素更新，對于大規(guī)模TSP問題有較好的結(jié)果［8］。2020年杜玉紅等人提出了一種粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法，實驗結(jié)果表明改進(jìn)算法可提高移動機(jī)器人到達(dá)目標(biāo)點(diǎn)的速度并降低機(jī)器人運(yùn)動過程中的損耗［9］。2020年官娟等人提出一種基于MIMIC算法和RPCA的混合蟻群算法，通過實驗對比表明在連續(xù)域上尋優(yōu)能力和收斂性方面都有明顯的提高［10］。

研究機(jī)器人路徑規(guī)劃問題可分為兩部分。第一部分是機(jī)器人運(yùn)動環(huán)境的搭建，將機(jī)器人的運(yùn)動空間解析成機(jī)器人能識別的數(shù)學(xué)模型，在機(jī)器人全局路徑規(guī)劃問題中，柵格法是最常用的環(huán)境建模方法。第二部分是路徑規(guī)劃方法的選擇。為解決蟻群算法收斂慢，易陷入局部最優(yōu)解的問題。本文提出一種對蟻群算法中信息素的更新進(jìn)行改進(jìn)的方法，引入了懲罰系數(shù)的概念，使當(dāng)前最優(yōu)路徑上的信息素濃度下降，從而達(dá)到跳出局部最優(yōu)的目的。將信息素濃度設(shè)置為分級動態(tài)變化，隨迭代次數(shù)增加而逐漸衰減，當(dāng)?shù)揭欢ù螖?shù)后，不再衰減，達(dá)到加速收斂的目的。

1 環(huán)境建模

柵格法是將機(jī)器人的工作環(huán)境建立在二維直角坐標(biāo)系上，根據(jù)機(jī)器人運(yùn)動空間的實際情況，將地圖分割成固定大小的柵格。柵格環(huán)境為X行Y列，每個柵格邊長都為1。柵格地圖內(nèi)的可分為三種柵格：第一種是障礙柵格，第二種是可移動?xùn)鸥瘢谌N是起始點(diǎn)柵格。

起點(diǎn)坐標(biāo)為（0，0），終點(diǎn)坐標(biāo)為（19，19）。在本文中螞蟻只能朝上、下、左、右、左上、右上、左下、右下八個方向運(yùn)動。柵格地圖如圖1所示，其中黑色為障礙物。

圖1 柵格地圖

2 傳統(tǒng)蟻群算法（AS）

以旅行商（TSP）問題為例，將m只螞蟻放入有n個城市的環(huán)境中，當(dāng)t時刻，隨機(jī)選取一個城市i，讓第k只螞蟻從該城市出發(fā)，以公式（1）計算得到的概率采取蒙特卡洛算法來選擇這只螞蟻下一個到達(dá)的城市。

每個螞蟻在搜素的過程中，會在已走過的路徑上留下一定濃度的信息素，加大整個系統(tǒng)的正反饋，使算法加速收斂。AS的信息素更新有三種模型：①蟻周模型；②蟻量模型；③蟻密模型。蟻周模型是使用比較多的一種，信息素更新方式見公式（2）。

公式（2）中：ρ是信息素?fù)]發(fā)因子，表示信息素的持久度，該系數(shù)增大會使之前螞蟻在路徑上留下的信息素?fù)]發(fā)變快，導(dǎo)致算法隨機(jī)性加強(qiáng)，收斂速度也降低了；反之，該系數(shù)的減小會使之前遺留在路徑上的信息素?fù)]發(fā)減慢，能夠加速算法的收斂，也會導(dǎo)致算法陷入局部最優(yōu)的情況。Δτij是螞蟻搜索完成后，在路徑上留下的信息素增量，要與之前地圖中的信息素進(jìn)行疊加。在達(dá)到設(shè)定的迭代次數(shù)，或得到期望的解時，結(jié)束整個過程，輸出最優(yōu)解。

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

3.1 優(yōu)化路徑搜索策略

（1）后退策略。螞蟻在路徑搜索的過程中將螞蟻已經(jīng)走過的路徑節(jié)點(diǎn)存入禁忌表，禁忌表中已有節(jié)點(diǎn)在選擇下一個節(jié)點(diǎn)時不會被選取，當(dāng)螞蟻進(jìn)入U型障礙會使螞蟻找不到可選擇的下一節(jié)點(diǎn)，如圖2所示。

圖2 U型障礙

針對U型障礙會使螞蟻找不到可選擇的下一節(jié)點(diǎn)，或其他找不到可選擇的下一節(jié)點(diǎn)的問題，引入后退策略。螞蟻沿著原路徑返回，每后退一個節(jié)點(diǎn)，判斷是否有未走過的節(jié)點(diǎn)，如果找到了就走新的節(jié)點(diǎn)，更新禁忌表中已走過節(jié)點(diǎn)，繼續(xù)算法的進(jìn)行。

（2）修正策略。除了上述無法找到可選擇的下一節(jié)點(diǎn)的問題。在搜索過程中，因為路徑信息素濃度的影響，螞蟻在路徑選擇大概率選擇信息素濃度高的節(jié)點(diǎn)從而出現(xiàn)了繞路，會存在兩種路徑缺陷，如圖3和圖4所示。

圖3 路徑缺陷1

圖4 路徑缺陷2

在每次迭代結(jié)束后，對迭代的最優(yōu)路徑進(jìn)行分析，判斷是否存在路徑缺陷問題，并通過修正策略進(jìn)行修正，修正后的路徑就是此次迭代的最優(yōu)路徑。路徑修正如圖5和圖6所示。

圖5 修正后路徑缺陷1

圖6 修正后路徑缺陷2

3.2 動態(tài)分級信息素濃度

在傳統(tǒng)蟻群算法中，如果使用的是蟻周模型，信息素的更新都取決于上一次迭代中的結(jié)果最好的一次，影響信息素的更新，其中求解質(zhì)量較差的路徑就會影響算法后續(xù)迭代的解的質(zhì)量，導(dǎo)致算法收斂速度變慢。為降低質(zhì)量較差的迭代結(jié)果對算法的負(fù)優(yōu)化，提高質(zhì)量較高的迭代結(jié)果對算法的影響，引入了信息素濃度的分級策略。根據(jù)柵格地圖大小，設(shè)定每個級別的路徑長度界限，將每次迭代的結(jié)果分為：優(yōu)質(zhì)路徑，信息素濃度為Q1；較優(yōu)路徑，信息素濃度Q2；較差路徑，信息素濃度Q3；低質(zhì)路徑，信息素濃度為Q4。

在傳統(tǒng)蟻群算法中，信息素濃度Q和揮發(fā)系數(shù)ρ的值對于整個算法的收斂速度是起決定作用的。Q的值偏大，而揮發(fā)系數(shù)ρ的值偏小時，算法容易陷入局部最優(yōu)。而Q的值偏小，揮發(fā)系數(shù)ρ的值偏大時，算法整體的全局搜索能力變得極低。針對這一問題，提出一種動態(tài)變化信息素濃度Q的方式，隨著迭代次數(shù)的增加，逐漸降低各級信息素濃度，達(dá)到設(shè)定好的迭代次數(shù)時，停止信息素濃度的衰減，此時Q的值固定為常量，后續(xù)的迭代Q的值不再發(fā)生變化。動態(tài)衰減信息素濃度的策略，可以使算法在初期獲得較快收斂速度，逐漸降低的信息素濃度可以保證算法不陷入局部最優(yōu)問題。

結(jié)合以上兩點(diǎn)改進(jìn)的動態(tài)分級信息素濃度Q的設(shè)置如下，見公式（3）。

公式（3）中：Q1、Q2、Q3、Q4分別是各級信息素濃度的初始值；length是每代的最短路徑；iter是迭代的次數(shù)；k1、k2、k3是每次迭代后各級信息素濃度的衰減系數(shù)。當(dāng)?shù)螖?shù)超過50次后，信息素濃度Q就為固定值。

這種方式，達(dá)到了加快收斂速度的目的，也能避免因為信息素濃度突然增加，導(dǎo)致算法容易陷入局部最優(yōu)的情況。

3.3 引入懲罰系數(shù)

當(dāng)算法迭代多次以后，相對優(yōu)秀的路徑上的信息素濃度會遠(yuǎn)高于其他較差的路徑上的濃度，使算法隨機(jī)性大大降低，不利于尋找更優(yōu)的路徑。為解決這一問題，引入了懲罰系數(shù)ε，當(dāng)算法迭代到K代以后，判斷當(dāng)前最優(yōu)路徑L代未發(fā)生變化，下一次更新信息素時，將當(dāng)前最優(yōu)路徑上的信息素濃度衰減。信息素衰減公式，如公式（4）所示。

3.4 蟻群算法相關(guān)參數(shù)

蟻群算法中，參數(shù)的選取影響收斂速度和尋優(yōu)結(jié)果，主要涉及的參數(shù)有螞蟻數(shù)量、信息素?fù)]發(fā)系數(shù)ρ、信息素啟發(fā)因子α與期望啟發(fā)因子β、迭代次數(shù)。具體分析如下：

（1）蟻群大小。蟻群大小直接影響搜索效率，蟻群數(shù)量過小，無法遍歷全地圖獲取全局最優(yōu)路徑。

（2）揮發(fā)系數(shù)。信息素是螞蟻在走過的路徑上留下的信息量之和，影響后面螞蟻的路徑選擇。隨著算法的迭代，路徑上的信息素會揮發(fā)。信息素?fù)]發(fā)系數(shù)對收斂速度和尋優(yōu)能力起主要影響。揮發(fā)系數(shù)變大，算法的收斂速度加快，搜索能力降低；揮發(fā)系數(shù)減小，算法收斂速度減慢，搜索能力提高。

（3）信息素啟發(fā)因子α與期望啟發(fā)因子β。信息素啟發(fā)因子表示信息素濃度對選擇路徑的影響大小；期望啟發(fā)因子表示路徑長度對路徑選擇的影響。α影響蟻群選擇之前走過路徑的概率，β影響算法的搜索效率。

（4）迭代次數(shù)。迭代次數(shù)過小，會導(dǎo)致算法提前結(jié)束，求解結(jié)果不理想。迭代次數(shù)過大會使算法效率降低，影響求解速度。

4 實驗仿真與分析

基于以上分析，在20×20的柵格地圖中進(jìn)行實驗仿真分析。對于本文算法公式中出現(xiàn)的參數(shù)進(jìn)行賦值：每一次迭代螞蟻的數(shù)量M為50只；最大迭代次數(shù)為100次；信息素啟發(fā)因子α為1，期望啟發(fā)因子β為7；信息素?fù)]發(fā)系數(shù)ρ為0.3；動態(tài)分級信息素濃度Q中，Q1、Q2、Q3、Q4分別為2.5、2、1.5、1；啟用懲罰系數(shù)的迭代次數(shù)K為30，最優(yōu)路徑連續(xù)未改變的次數(shù)L為5次，懲罰系數(shù)ε為2。仿真結(jié)果如圖7所示。

圖7 兩種蟻群算法仿真結(jié)果

表1記錄了傳統(tǒng)蟻群算法和本文算法最優(yōu)路徑長度，以及第一次出現(xiàn)最優(yōu)路徑的迭代次數(shù)，來進(jìn)行比較。

表1 算法對比

從仿真結(jié)果來看，兩種蟻群算法都能對路徑進(jìn)行規(guī)劃，但與傳統(tǒng)蟻群算法相比，本文算法具有更強(qiáng)的路徑規(guī)劃能力，在路徑長度上有較強(qiáng)的優(yōu)化效果。

從圖8兩種蟻群算法的收斂曲線來看，與傳統(tǒng)蟻群算法相比，本文算法具有更快的收斂速度，對于迭代次數(shù)也有很好的優(yōu)化能力。

圖8 兩種蟻群算法收斂曲線

5 結(jié)語

本文針對移動機(jī)器人路徑規(guī)劃問題，提出了一種改進(jìn)的蟻群算法。將傳統(tǒng)蟻群算法中固定的信息素濃度，改進(jìn)為動態(tài)分級的信息素濃度，達(dá)到了加速收斂的目的。引入了后退策略來避免螞蟻陷入死鎖導(dǎo)致的算法失效。通過修正策略，對螞蟻搜索路徑過程中存在的一些路徑行為進(jìn)行修正，縮短了路徑距離。通過設(shè)置懲罰函數(shù)，來提高提高算法運(yùn)行到中后期的隨機(jī)性避免陷入局部最優(yōu)，影響算法的搜索結(jié)果。仿真數(shù)據(jù)顯示：本文所提出的改進(jìn)的蟻群算法，在路徑長度的優(yōu)化以及迭代次數(shù)的優(yōu)化方面都具有不錯的效果，具有良好的全局搜索效果。