改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃上的應(yīng)用

周敬東， 楊 磊， 高偉周， 汪 宇

(1 湖北工業(yè)大學(xué)機(jī)械工程學(xué)院， 湖北 武漢 430068；2 湖北省農(nóng)業(yè)機(jī)械工程研究設(shè)計(jì)院， 湖北 武漢 430068)

作為機(jī)器人實(shí)現(xiàn)智能自主規(guī)劃的關(guān)鍵技術(shù)，根據(jù)可支配的外界環(huán)境有效信息的程度，路徑規(guī)劃[1-2]可分為靜態(tài)路徑規(guī)劃和動(dòng)態(tài)路徑規(guī)劃[3]。相較于模糊算法、人工勢(shì)場(chǎng)法[4]以及D*算法[5]等，蟻群算法擁有強(qiáng)魯棒性、隱含并行點(diǎn)而被廣泛地應(yīng)用到動(dòng)態(tài)路徑規(guī)劃中。但是，傳統(tǒng)蟻群算法規(guī)劃路徑時(shí)存在搜索精度不高、容易早斂、搜索時(shí)間較長(zhǎng)且收斂速度慢等問(wèn)題[6-7]。為解決上述不足，本文對(duì)蟻群算法中存在的具體問(wèn)題進(jìn)行局部改進(jìn)。仿真分析的結(jié)果表明，改進(jìn)后的蟻群算法求解速度更加迅速，路徑更優(yōu)且不會(huì)陷入U(xiǎn)形陷阱，驗(yàn)證了改進(jìn)算法的可行性。

1 蟻群算法原理

作為個(gè)體，螞蟻只有有限的視覺(jué)和嗅覺(jué)，但它們以群體形式存在的時(shí)候，卻能非常高效、有組織地完成筑巢、覓食、搬運(yùn)等大型活動(dòng)。Dorigo等通過(guò)研究螞蟻群體尋找食物的行為，結(jié)合螞蟻之間團(tuán)隊(duì)協(xié)作覓食的特點(diǎn)提出了蟻群算法[8]，其原理：螞蟻在尋找食物的過(guò)程中會(huì)沿途釋放信息素，信息素不會(huì)立即揮發(fā)而是會(huì)逐漸累積，而信息素累計(jì)的濃度會(huì)影響下一個(gè)螞蟻選擇該路徑的概率，即濃度越大，選擇概率也會(huì)越大。圖1上方的路徑長(zhǎng)度會(huì)比下方的短，而路徑的長(zhǎng)度和信息素累積的濃度隨著時(shí)間呈反比關(guān)系，所以上方的信息素累計(jì)會(huì)相對(duì)多一些。最終螞蟻會(huì)全部走上方的路徑。

圖 1 蟻群覓食

由于蟻群算法和機(jī)器人路徑規(guī)劃的目標(biāo)都是尋找從起點(diǎn)到終點(diǎn)的一條最短路徑，故非常合適將蟻群算法運(yùn)用到路徑規(guī)劃中。具體執(zhí)行流程見(jiàn)圖2。

圖 2 蟻群算法路徑規(guī)劃流程

蟻群算法用于機(jī)器人路徑規(guī)劃時(shí)，主要由初始化、解構(gòu)建和信息素更新三部分組成。

1)初始化。主要設(shè)置信息素、啟發(fā)信息、種群規(guī)模、信息素?fù)]發(fā)率、迭代次數(shù)等參數(shù)的初始值。

2)解構(gòu)建。解構(gòu)建是蟻群算法用來(lái)實(shí)施迭代最關(guān)鍵的步驟，主要內(nèi)容是依據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選擇下一路徑點(diǎn)，最終形成完整路徑。

3)信息素更新。信息素更新對(duì)螞蟻搜索路徑起到無(wú)比關(guān)鍵的影響。在其所經(jīng)過(guò)的路徑上釋放信息素，將加強(qiáng)對(duì)螞蟻未來(lái)選擇該路徑的影響，增強(qiáng)算法的開(kāi)發(fā)能力。每次迭代后降低路徑上的信息素，將減小正反饋效果，從而增強(qiáng)算法的探索能力。

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

2.1 非均勻分布初始信息素

由于蟻群算法前期初始信息素值相同，螞蟻在搜索路徑時(shí)會(huì)以最短距離為標(biāo)準(zhǔn)來(lái)選擇下一個(gè)節(jié)點(diǎn)，而忽視了全局信息。這種方式使得螞蟻會(huì)往返搜索，導(dǎo)致規(guī)劃出來(lái)的路徑存在回路。這種情況的產(chǎn)生會(huì)使搜索效率降低且增加路徑長(zhǎng)度。

為解決這個(gè)問(wèn)題，本文以起點(diǎn)和終點(diǎn)為對(duì)角頂點(diǎn)劃定一個(gè)矩形區(qū)域，并且增加該區(qū)域信息素初始值。這樣做能夠使得機(jī)器人在早期的移動(dòng)過(guò)程中具有向目標(biāo)點(diǎn)的方向前行的啟發(fā)性，有利于減少螞蟻盲目搜索，大大提高了收斂速度。

2.2 基于A*算法的啟發(fā)式信息

傳統(tǒng)蟻群算法依據(jù)相鄰柵格之間的距離進(jìn)行啟發(fā)式搜索，這種搜索方式造成柵格之間數(shù)值差別不明顯。針對(duì)此問(wèn)題，本文采用A*算法作為路徑搜索的啟發(fā)式信息，使其移動(dòng)的總體方向偏向于目標(biāo)點(diǎn)，從而獲得較好的路徑。

A*算法[9]同時(shí)具備Dijkstra算法和貪心搜索算法的優(yōu)勢(shì)，能夠在啟發(fā)函數(shù)指引下快速靠近目標(biāo)點(diǎn)的同時(shí)，確保規(guī)劃路徑最優(yōu)。A*算法的評(píng)價(jià)函數(shù)

f(n)=g(n)+h(n)

(1)

式中：f(n)代表由出發(fā)點(diǎn)途經(jīng)當(dāng)前點(diǎn)并到達(dá)目標(biāo)點(diǎn)的總代價(jià)值；g(n)代表f(n)總代價(jià)的前一部分代價(jià)，即當(dāng)前點(diǎn)到出發(fā)點(diǎn)的代價(jià)；h(n)代表f(n)總代價(jià)的后一部分代價(jià)，即當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的代價(jià)。改進(jìn)后啟發(fā)式為

(2)

這里Q2是大于1的常量。

2.3 改進(jìn)轉(zhuǎn)移概率

信息素分布差異越大則正反饋效果越明顯，算法能夠更快地收斂。而蟻群算法由于早期天然存在各節(jié)點(diǎn)信息素分布差異不明顯的特點(diǎn)，算法規(guī)劃的路徑容易出現(xiàn)大量的交叉路徑。與此同時(shí)，螞蟻在尋路時(shí)會(huì)將之前走過(guò)的路徑點(diǎn)加入到禁忌表中，這種單向行走不能往返的方式使得螞蟻在交叉路徑中會(huì)進(jìn)入死鎖階段，最終迷失方向。為了解決這個(gè)問(wèn)題，可以加入避障策略[10]到前期的搜索流程中：

(3)

式中：Oj記錄節(jié)點(diǎn)j鄰域里存在障礙物的柵格總數(shù)；Lj記錄節(jié)點(diǎn)j鄰域里被禁忌表限制不能通過(guò)的柵格總數(shù)；Aj記錄節(jié)點(diǎn)j相鄰柵格總數(shù)；ε為避障系數(shù)。算法引入避障策略后，螞蟻死鎖的概率極大降低。

2.4 螞蟻回退策略

螞蟻在面對(duì)U型障礙物時(shí)會(huì)落入“陷阱”中，此時(shí)螞蟻四周無(wú)路可走且走過(guò)的路徑已經(jīng)加入到禁忌表中，這將導(dǎo)致螞蟻無(wú)法走出陷阱。這種現(xiàn)象的發(fā)生會(huì)使螞蟻處于死亡狀態(tài)，最終導(dǎo)致算法進(jìn)入死鎖。顯然這種情況是不利于路徑規(guī)劃的。如圖3所示一共有3處陷阱，分別為N12-N14,N11-N14-N17,N13-N16-N18。陷阱一類是障礙物之間形成的，一類是障礙物與環(huán)境邊界形成的。為了增強(qiáng)算法的健壯性以及對(duì)環(huán)境的適應(yīng)性，可以采用螞蟻回退策略來(lái)應(yīng)對(duì)。

當(dāng)螞蟻k處于N15時(shí),螞蟻k進(jìn)入陷阱。此時(shí)螞蟻k需要回退到父節(jié)點(diǎn)N12，接著從tabuk中刪除N15，然后在可行解集合中選取柵格。假如螞蟻發(fā)現(xiàn)依舊無(wú)路可走，則繼續(xù)回退，圖3中螞蟻k仍需從tabuk中刪除N12，回退到N8,直到脫離陷阱為止。

通過(guò)引入螞蟻回退策略,解決了“死鎖”問(wèn)題，確保每一只螞蟻能夠逃離陷阱。螞蟻在搜索過(guò)程中不發(fā)生“死亡”，每個(gè)螞蟻的作用被充分發(fā)揮，增強(qiáng)了算法的魯棒性。

圖 3 具有U形障礙物的柵格圖

3 仿真實(shí)驗(yàn)分析

為驗(yàn)證改進(jìn)算法的可行性和適用性，在MATLABR2017b建立的柵格環(huán)境下進(jìn)行仿真。算法開(kāi)始運(yùn)行前需要對(duì)一些參數(shù)的值進(jìn)行初始化，m=50，α=1，β=9，ρ=0.9，Q=1，epochs=100，分別代表螞蟻個(gè)數(shù)、信息素因子、啟發(fā)因子、信息素蒸發(fā)系數(shù)、信息素增長(zhǎng)強(qiáng)度系數(shù)以及迭代次數(shù)。接著在兩種不同的實(shí)驗(yàn)環(huán)境中對(duì)兩種算法進(jìn)行仿真對(duì)比，實(shí)驗(yàn)結(jié)果如圖4-7所示。

傳統(tǒng)算法和改進(jìn)算法在兩種不同仿真環(huán)境下路徑長(zhǎng)度和迭代次數(shù)的兩項(xiàng)指標(biāo)分別如表1和表2所示。由表1-2可知：相較于傳統(tǒng)算法，本文改進(jìn)蟻群算法顯著降低了迭代次數(shù)，縮短了路徑長(zhǎng)度，路徑規(guī)劃更高效。

(a)蟻群算法

(b)改進(jìn)蟻群算法圖 4 蟻群算法規(guī)劃路徑實(shí)例(環(huán)境1)

(a)蟻群算法

(b)改進(jìn)蟻群算法圖 5 蟻群算法迭代(環(huán)境1)

(a)蟻群算法

(b)改進(jìn)蟻群算法圖 6 蟻群算法規(guī)劃路徑實(shí)例(環(huán)境2)

(a)蟻群算法

為驗(yàn)證改進(jìn)算法的通用性和可靠性，本文在不同的仿真環(huán)境中進(jìn)行5組實(shí)驗(yàn)，得到的數(shù)據(jù)如表3和表4所示。其中g(shù)oal_distance代表起點(diǎn)到終點(diǎn)的直線路徑，path_cost代表機(jī)器人路徑規(guī)劃的真實(shí)路徑。在表3中，改進(jìn)蟻群算法通過(guò)加入A*算法的啟發(fā)式函數(shù)搜索函數(shù)，使算法移動(dòng)的總體方向偏向于目標(biāo)點(diǎn)，從而獲得較好的路徑，相較于傳統(tǒng)的蟻群算法，規(guī)劃出的路徑更短。在表4中，改進(jìn)蟻群算法對(duì)初始信息素采取非均勻式分配，避免螞蟻進(jìn)行無(wú)用的搜索行為。改進(jìn)算法利用改進(jìn)轉(zhuǎn)移概率解決了死鎖現(xiàn)象并采用螞蟻回退策略處理U型陷阱。局部改進(jìn)方案使傳統(tǒng)蟻群算法的迭代次數(shù)和搜索時(shí)間明顯降低。

表3 蟻群算法與改進(jìn)蟻群算法路徑長(zhǎng)度對(duì)比

表4 蟻群算法與改進(jìn)蟻群算法迭代次數(shù)和搜索時(shí)間對(duì)比

通過(guò)對(duì)具體數(shù)據(jù)的對(duì)比分析發(fā)現(xiàn)，改進(jìn)蟻群算法相比于傳統(tǒng)蟻群算法規(guī)劃出來(lái)的路徑更短，尋路效率更高效。5組實(shí)驗(yàn)結(jié)果顯示，改進(jìn)蟻群算法的迭代次數(shù)平均減少了34%，搜索時(shí)間平均降低了60%，規(guī)劃出的路徑平均縮短了7%。

4 結(jié)論

本文在算法早期利用非均勻分布初始信息素的方式減少了螞蟻盲目搜索路徑，提高了收斂速度。引入A*算法的啟發(fā)信息來(lái)改進(jìn)蟻群算法的啟發(fā)函數(shù)，從而加快搜索速度。改進(jìn)轉(zhuǎn)移概率解決了死鎖現(xiàn)象。最后采用螞蟻回退策略較好地處理了U型陷阱。通過(guò)在MATLAB仿真平臺(tái)上對(duì)改進(jìn)前后的蟻群算法進(jìn)行仿真對(duì)比分析，由仿真結(jié)果可知，本文算法在路徑長(zhǎng)度和搜索效率均有所提高且可以應(yīng)對(duì)U形障礙物環(huán)境。