改進(jìn)A*蟻群算法求解機(jī)器人路徑規(guī)劃問題*

萬逸飛， 彭 力

(江南大學(xué) 物聯(lián)網(wǎng)應(yīng)用技術(shù)教育部工程中心，江蘇 無錫 214122)

0 引 言

機(jī)器人的路徑規(guī)劃問題是指在有障礙物的環(huán)境中，尋找出一條從設(shè)定的起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞路徑，并且此路徑要求最短，路徑搜索過程要求最快。機(jī)器人路徑規(guī)劃問題是導(dǎo)航與控制的基礎(chǔ)，也一直是人工智能的熱點(diǎn)問題。目前機(jī)器人路徑規(guī)劃的常用方法有：柵格法[1]，人工勢場法[2]，A*算法[3]，神經(jīng)網(wǎng)絡(luò)[4]，遺傳算法[5，6]，粒子群算法[7]等。其中神經(jīng)網(wǎng)絡(luò)算法需要頻繁的調(diào)整網(wǎng)絡(luò)權(quán)重，并且需要大量的訓(xùn)練樣本；遺傳算法計(jì)算量大，收斂太慢；粒子群算法簡單，但是太容易早熟于局部最優(yōu)；人工勢場法[8]雖便于底層實(shí)時(shí)控制，但容易出現(xiàn)死鎖、停滯以及陷入局部最優(yōu)，并且障礙物較多時(shí)還會出現(xiàn)計(jì)算量過大等問題。雖然也有很多學(xué)者對它們的不足做出改進(jìn)，但一直沒有一個完美高效的結(jié)果。比如：朱毅等人[9]用“奔向目標(biāo)”，“沿墻行走”等行為對人工勢場法進(jìn)行改進(jìn)，避免了死鎖、停滯等現(xiàn)象，但明顯沒有解決局部最優(yōu)的問題。

雖然蟻群優(yōu)化(ant colony optimization,ACO)算法也有一定的缺陷，但由于其具有正反饋、較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算等優(yōu)點(diǎn)，一直受廣大學(xué)者關(guān)注。文獻(xiàn)[10]將蟻群單向搜索目標(biāo)方式變?yōu)殡p向并行搜索，加快算法的尋優(yōu)速度。但是判斷螞蟻相遇的過程會消耗一定的時(shí)間，而且對于算法的尋優(yōu)能力提高不大；文獻(xiàn)[11]改變螞蟻的搜索步長，由定步長搜索改為變步長搜索，加快蟻群算法收斂速度。但是蟻群算法前期效率低、耗時(shí)長的問題并沒有解決；文獻(xiàn)[12]將人工勢場法與蟻群算法結(jié)合，并加入幾何優(yōu)化，從而提高算法的收斂速度與全局尋優(yōu)能力。而且蟻群算法的生物機(jī)理就是螞蟻在巢穴與食物之間找一條最短的可行路徑。

本文也是基于蟻群算法進(jìn)行移動機(jī)器人的路徑規(guī)劃。不過本文的蟻群算法結(jié)合了A*算法，加入了簡化算子，并且對蟻群算法的啟發(fā)函數(shù)以及信息素更新公式做出改進(jìn)，從而加快了蟻群算法的收斂速度，大大提高了蟻群算法尋優(yōu)能力。

1 柵格環(huán)境建模以及地圖預(yù)處理

柵格法是目前環(huán)境建模方面應(yīng)用最廣泛的方法之一。該方法用黑白柵格分別表示不可行與可行區(qū)域。如圖1所示，為了簡化實(shí)際問題，確保運(yùn)動的安全性，對每個障礙物進(jìn)行膨脹，膨脹的寬度為機(jī)器人的半徑[10]，這樣機(jī)器人在仿真時(shí)就可以視為質(zhì)點(diǎn)。

圖1 障礙物柵格描述

此時(shí)路徑規(guī)劃問題就是從柵格地圖的可行柵格中規(guī)劃出一條從起點(diǎn)到目標(biāo)點(diǎn)的最短路徑。圖2為10×10的柵格地圖，假設(shè)柵格1是起始點(diǎn)，柵格100是目標(biāo)點(diǎn)，對于圖中的凹型障礙物，如若用人工勢場法，很可能出現(xiàn)“死鎖”現(xiàn)象。而用蟻群算法，部分螞蟻也會出現(xiàn)“死鎖”現(xiàn)象，或者在“死角”區(qū)域浪費(fèi)較長時(shí)間。為了提高螞蟻的效率，降低螞蟻“死鎖”的概率，本文路徑規(guī)劃前先對柵格地圖進(jìn)行處理。

圖2 10×10的柵格地圖

對于每個可行柵格進(jìn)行判斷，如果地圖四邊的柵格“活躍度”小于等于2，即周邊的可行柵格數(shù)小于等于2，并且其周圍的障礙柵格按順時(shí)針方向，連續(xù)超過3個時(shí)，將此可行“死角”柵格視為障礙物。例如柵格71，其“活躍度”為1，并且其周圍的4個障礙物按順時(shí)針連續(xù)排列，故柵格71視為“死角”；如果中間的可行柵格“活躍度”小于等于3(最大為8)，并且周圍的障礙物柵格按順時(shí)針方向，連續(xù)超過5個時(shí)，視其為死角。例如：柵格35，5，9，都為“死角”，柵格65不是。對于“死角”柵格，如果它們不是起始點(diǎn)與目標(biāo)點(diǎn)，在地圖預(yù)處理時(shí)，直接將其變?yōu)檎系K物柵格。

2 改進(jìn)蟻群算法設(shè)計(jì)

2.1 A*算法產(chǎn)生初始信息素

傳統(tǒng)的蟻群算法在初次搜索時(shí)，由于對地圖信息匱乏，一般將信息素均勻分布，即每個可行柵格上的信息素都是常量，這導(dǎo)致蟻群初期進(jìn)行“盲目”搜索。針對這一問題，本文利用A*算法決定初始信息素，從而加快算法初期的收斂速度，減少迭代次數(shù)。

A*算法為啟發(fā)式路徑搜索算法[13]，路徑搜索主要根據(jù)一個路徑評價(jià)

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

(1)

這里g(n)為從起點(diǎn)s,沿著產(chǎn)生的路徑，到方格n的移動消耗；h(n)為從方格n到終點(diǎn)g的預(yù)估移動消耗。

A*算法中有OPEN與CLOSED列表。其中OPEN中保存有待考查的可行相鄰節(jié)點(diǎn)。CLOSED保存已考查過的節(jié)點(diǎn)。A*算法在尋路時(shí)，從起始節(jié)點(diǎn)開始，不斷向外擴(kuò)展，每次找OPEN列表中f(n)最小的節(jié)點(diǎn)，直到找到目標(biāo)點(diǎn)。最終從目標(biāo)點(diǎn)開始，沿著每一個柵格的父節(jié)點(diǎn)移動，直到回到起始點(diǎn)。本文將這條路徑的初始信息素設(shè)為

τij(initial)=kc,k>1

3.設(shè)置的問題要有靈活性。同一教學(xué)方法可以解決不同的教學(xué)內(nèi)容，不同的教學(xué)方法也可以解決相同的教學(xué)內(nèi)容；同一教學(xué)方法面對不同的教學(xué)對象會產(chǎn)生不同的教學(xué)效果，不同的教學(xué)方法面對相同的教學(xué)對象也會產(chǎn)生不同的教學(xué)效果。因此，教學(xué)策略的運(yùn)用要隨著問題、目標(biāo)、內(nèi)容和教學(xué)對象的不同而改變。

(2)

其中k為初始信息素放大倍數(shù)，其余柵格上的信息素仍然保持常數(shù)c。

2.2 蟻群算法主體部分

(3)

(4)

式中dij為柵格i到下個一個可行柵格j的距離。傳統(tǒng)的啟發(fā)函數(shù)必將導(dǎo)致螞蟻在選擇下一格柵格時(shí)，更傾向于選擇正方向的可行柵格。這里面并沒有考慮終點(diǎn)柵格的位置，因此該啟發(fā)信息函數(shù)還過于片面。本文對公式(5)改進(jìn)

(5)

(6)

蟻群算法為了避免留下的信息素累積過多而淹沒啟發(fā)信息，每迭代一次，都會對信息素進(jìn)行更新。但是傳統(tǒng)信息素更新公式，對于優(yōu)秀螞蟻與劣質(zhì)螞蟻留下的信息素進(jìn)行的是相同處理。這樣不能充分顯示出每代最優(yōu)解的指導(dǎo)作用，同時(shí)劣質(zhì)螞蟻的信息素也相當(dāng)于是一種干擾，這將降低蟻群的效率。本文為了提高螞蟻的效率，對優(yōu)秀螞蟻與劣質(zhì)螞蟻產(chǎn)生的信息素進(jìn)行不平等處理

τij(t+1)=(1-ρ)τij(t)+Δτij(t,t+1)

(7)

(8)

(9)

式中ρ為信息揮發(fā)系數(shù)，取值范圍為[0,1]；Lk為第k只螞蟻在本次循環(huán)中所走的路徑總長度；Q是信息素強(qiáng)度。此處引入變量kLk，當(dāng)Lk除inf外，在同一代螞蟻中最大時(shí)，即劣質(zhì)螞蟻產(chǎn)生的路徑，其值取0；當(dāng)Lk大于同一代螞蟻產(chǎn)生的路徑中位值時(shí)，kLk取ka∈[0.5,0.9]；當(dāng)小于中位值時(shí)，kLk取kb∈[1,1.2]；當(dāng)Lk最小時(shí)，即最優(yōu)螞蟻產(chǎn)生的路徑，其值取1.3。這樣進(jìn)行不平等的處理，便可拉大劣質(zhì)螞蟻與優(yōu)秀螞蟻產(chǎn)生的影響度，在保證路徑信息素多樣性的前提下，提高下一代螞蟻尋優(yōu)的效率。

2.3 簡化算子

利用簡化算子是為了去除冗余的拐點(diǎn)[14]。假設(shè)某規(guī)劃路徑如圖3所示。

圖3 原始路徑圖

將起始點(diǎn)，拐點(diǎn)以及終點(diǎn)依次標(biāo)上序號：P1,P2,…,Pn，此圖中n=7。接下來進(jìn)行循環(huán)簡化，第一次循環(huán)時(shí)，s=1。將點(diǎn)Ps與Pk(k=s+2,s+3,…,n)依次相連，看是否有連線不經(jīng)過障礙物，即生成了新的可行路徑。若存在這樣的連線，則選擇其中最大的k值，連接Ps與Pk，s更新為k-1；如無這樣的連線，s更新為s+1。直至s為n-1,循環(huán)結(jié)束，即簡化過程結(jié)束。圖4是用簡化算子，簡化后的路徑圖。

圖4 簡化路徑圖

3 改進(jìn)的A*蟻群算法步驟

1)初始化本文算法的參數(shù)；

2)根據(jù)初始化中的終起點(diǎn)位置，建立指定大小的柵格地圖，并用本文中的方法對地圖進(jìn)行處理，去除死角；

3)用A*算法確定蟻群的初始信息素分布；

4)每只螞蟻找到可行并且自己沒有走過的柵格，用式(3)、式(5)、式(6)計(jì)算出去每個可選柵格的概率，并用輪盤賭法做最終選擇。不斷循環(huán)此操作，直至每只螞蟻到達(dá)終點(diǎn)或者陷入“死胡同”，循環(huán)結(jié)束；

5)用改進(jìn)的更新式(7)～式(9)更新上一代螞蟻留下的信息素；

6)循環(huán)步驟(4)與步驟(5)，直至到達(dá)最大迭代次數(shù)。找出最優(yōu)路徑并用簡化算子簡化。

4 仿真對比分析

本文針對傳統(tǒng)蟻群算法在路徑規(guī)劃方面應(yīng)用的不足，做出了一些改進(jìn)。下面在CPU為奔騰G2020的電腦上，用軟件MATLAB2014b進(jìn)行4組仿真驗(yàn)證。

首先與經(jīng)典蟻群算法對比，選取20*20的地圖，其障礙物覆蓋率為21 %。初始化時(shí)，螞蟻數(shù)量m=30，最大迭代次數(shù)K=200，α=1，β=16，ρ=0.15。圖5(a)為基本蟻群算法(ACO)的路徑規(guī)劃圖；圖5(b)是應(yīng)用本文3.1與3.2節(jié)改進(jìn)的蟻群算法(improve ant colony optimization-main,IACO-M)的路徑規(guī)劃圖，其中用A*算法形成的初始信息素放大倍數(shù)k=4；圖5(c)是在圖5(b)算法的基礎(chǔ)上，加了地圖預(yù)處理以及簡化算子，即本文最終的IACO的路徑規(guī)劃圖。圖5(c)的地圖看似與其他兩個有所區(qū)別，實(shí)則是一樣的，只不過經(jīng)過地圖預(yù)處理，將“死角”直接轉(zhuǎn)化為了障礙柵格。它們路徑總長度分別為33.7990，28.6274，27.6340。

圖5 對比路徑規(guī)劃

表1 三種算法比較

為了進(jìn)一步分析，將每個圖對應(yīng)的算法運(yùn)行10次，取平均值，繪制表1，其中X為到達(dá)收斂的迭代次數(shù)。e為螞蟻效率，隨迭代次數(shù)增加，不斷抖動上升的值。此處用第一次迭代能到達(dá)終點(diǎn)的螞蟻數(shù)量進(jìn)行衡量。由表1可證明本文算法改進(jìn)的每個環(huán)節(jié)都起到了優(yōu)化作用。相同參數(shù)的情況下，改進(jìn)的蟻群算法，其螞蟻搜索效率有所提高，收斂速度加快，路徑長度更是大幅度縮短。

將本文算法與其他三個文獻(xiàn)中改進(jìn)的算法進(jìn)行對比。文獻(xiàn)[15]應(yīng)用改進(jìn)的遺傳算法(簡稱IGA)進(jìn)行路徑規(guī)劃。圖6(a)是文獻(xiàn)中最復(fù)雜地圖的最優(yōu)路徑規(guī)劃圖，圖6(b)是基于本文算法的路徑規(guī)劃圖，它們的路徑長度分別是30.384 8，29.460 1。達(dá)到收斂的迭代次數(shù)分別為20，14。

圖6 IGA與IACO路徑對比

文獻(xiàn)[16]是A*算法與蟻群算法結(jié)合，并作出改進(jìn)，這里簡稱AACO。圖7(a)是文獻(xiàn)[16]中的一張路徑規(guī)劃圖，圖7(b)是IACO基于相同地圖的路徑規(guī)劃圖。它們的路徑長度分別28.627 5，28.006 0。達(dá)到收斂所耗費(fèi)的迭代次數(shù)分別為15，22。

圖7 AACO與IACO路徑對比

文獻(xiàn)[12]中算法是將人工勢場法，幾何優(yōu)化與蟻群算法結(jié)合并改進(jìn)，稱為ACO-PDG。圖8(a)是文獻(xiàn)中的路徑規(guī)劃圖，構(gòu)建與文獻(xiàn)中相同的柵格地圖，應(yīng)用本文IACO規(guī)劃出來的路徑如圖8(b)所示。因?yàn)榕c文獻(xiàn)方法不同，所以不能取一樣的參數(shù)值進(jìn)行對比，但可以基于相同的地圖進(jìn)行對比，此處參數(shù)初始化同之前的測試。圖8(a)與圖8(b)中地圖有差別是因?yàn)楸疚乃惴▽ⅰ八澜恰鞭D(zhuǎn)化為障礙物，所以實(shí)則兩地圖是一樣的。

圖8 ACO-PDG與IACO路徑對比

經(jīng)對比，可以明顯的看出本文的算法在路徑長度方面是遠(yuǎn)遠(yuǎn)優(yōu)于ACO-PDG的。為進(jìn)一步驗(yàn)證算法的效果，實(shí)驗(yàn)10次，取平均值進(jìn)行對比。其中表2中X為到達(dá)收斂的迭代次數(shù)，ACO-PDG的10次實(shí)驗(yàn)數(shù)據(jù)來自文獻(xiàn)[12]。由表2可見，雖然本文算法的收斂速度沒有文獻(xiàn)[12]中的快，但路徑平均長度比它短很多。而計(jì)算機(jī)的運(yùn)行速度肯定比移動機(jī)器人的運(yùn)動速度快很多，所以平均迭代次數(shù)多6.4所消耗的時(shí)間肯定比2.686 1的路徑所消耗的時(shí)間少得多。而且本文算法規(guī)劃的路徑拐點(diǎn)更少，更方便機(jī)器人運(yùn)動。

表2 ACO-PDG與IACO對比

5 結(jié) 論

仿真結(jié)果表明：本文算法相對于經(jīng)典蟻群算法以及部分改進(jìn)算法收斂速度加快。雖然相對于一些改進(jìn)的比較好的蟻群算法，收斂速度還略慢，但是本文改進(jìn)的蟻群算法全局尋優(yōu)能力最強(qiáng)，即最終規(guī)劃的路徑其他算法短。