萬逸飛， 彭 力

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

0 引 言

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

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

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

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

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

圖1 障礙物柵格描述

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

圖2 10×10的柵格地圖

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

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

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

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

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

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

(1)

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

A*算法中有OPEN與CLOSED列表。其中OPEN中保存有待考查的可行相鄰節(jié)點。CLOSED保存已考查過的節(jié)點。A*算法在尋路時，從起始節(jié)點開始，不斷向外擴展，每次找OPEN列表中f(n)最小的節(jié)點，直到找到目標(biāo)點。最終從目標(biāo)點開始，沿著每一個柵格的父節(jié)點移動，直到回到起始點。本文將這條路徑的初始信息素設(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é)策略的運用要隨著問題、目標(biāo)、內(nèi)容和教學(xué)對象的不同而改變。

(2)

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

2.2 蟻群算法主體部分

(3)

(4)

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

(5)

(6)

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

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

(7)

(8)

(9)

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

2.3 簡化算子

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

圖3 原始路徑圖

將起始點，拐點以及終點依次標(biāo)上序號：P1,P2,…,Pn，此圖中n=7。接下來進行循環(huán)簡化，第一次循環(huán)時，s=1。將點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 改進的A*蟻群算法步驟

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

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

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

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

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

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

4 仿真對比分析

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

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

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

表1 三種算法比較

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

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

圖6 IGA與IACO路徑對比

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

圖7 AACO與IACO路徑對比

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

圖8 ACO-PDG與IACO路徑對比

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

表2 ACO-PDG與IACO對比

5 結(jié) 論

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