褚凱軒 常天慶 王全東 閆曉東

(1.陸軍裝甲兵學(xué)院兵器與控制系， 北京 100072； 2.軍事科學(xué)院評估論證研究中心， 北京 100091)

0 引言

路徑規(guī)劃是移動機(jī)器人在具有障礙物的環(huán)境約束下，根據(jù)給定的起點(diǎn)和終點(diǎn)，應(yīng)用算法準(zhǔn)則，找到一條最優(yōu)或接近最優(yōu)的、安全、無障礙路徑[1-2]。路徑規(guī)劃主要包括環(huán)境建模和路徑規(guī)劃算法兩部分。

柵格圖法是環(huán)境建模的經(jīng)典方法[3]，柵格圖將地圖切割成相同大小且相互連接的柵格，每個(gè)柵格對應(yīng)相應(yīng)位置信息，能在考慮全局優(yōu)化的基礎(chǔ)上兼顧較小的計(jì)算量, 對特定感知系統(tǒng)的假設(shè)參數(shù)不敏感，具有較強(qiáng)的魯棒性[4]，目前被廣泛運(yùn)用于機(jī)器人、自動駕駛的運(yùn)載器等領(lǐng)域[5-7]。柵格圖下，傳統(tǒng)的路徑搜索方式主要有4鄰域4方向搜索方式和8鄰域8方向搜索方式。徐菱等[8]提出一種24鄰域16方向的搜索方式，使路徑搜索具有更廣的搜索范圍和更多的方向選擇。但是有限方向有限鄰域使機(jī)器人每次只能在相鄰柵格間轉(zhuǎn)移，增大了搜索次數(shù)和步數(shù)。曾明如等[9]提出了一種搜索范圍不局限于相鄰柵格的多步長柵格圖法，能搜索出一條轉(zhuǎn)移步數(shù)更少的路徑,該方法在面臨較大規(guī)模地圖時(shí)計(jì)算量巨大。文獻(xiàn)[10-11]提出直接將信息素存放于柵格中而不是存放于路徑上，這種信息素存儲方式可以降低算法的復(fù)雜度，但是由于失去了方向性，在大規(guī)模柵格路徑規(guī)劃中易發(fā)生閉鎖和折回的現(xiàn)象。

路徑規(guī)劃算法主要有局部避障算法、基于幾何模型算法和智能搜索算法。局部避障算法包括人工勢場法[12]和動態(tài)窗口法[13]。人工勢場法通過模擬障礙物產(chǎn)生的斥力場和終點(diǎn)產(chǎn)生的引力場，推動機(jī)器人避障并向終點(diǎn)移動。動態(tài)窗口法是在速度空間中采樣多組數(shù)據(jù)，并模擬移動機(jī)器人以這些速度在下一時(shí)間段內(nèi)的軌跡并對軌跡進(jìn)行評價(jià)，選取最優(yōu)軌跡對應(yīng)的速度來驅(qū)動機(jī)器人運(yùn)動?；趲缀文Ｐ退惴ㄖ饕蠨ijkstra算法[14]和A*算法[15]，Dijkstra算法計(jì)算起始點(diǎn)到其他所有點(diǎn)的最短路徑長度，是廣度優(yōu)先搜索，具有較高的空間復(fù)雜度和時(shí)間復(fù)雜度，而A*算法是一種啟發(fā)式算法，是一種深度優(yōu)先的算法。智能搜索算法有蟻群算法[16-19]、遺傳算法[20]、粒子群算法[21]、人工蜂群算法[22]等，是利用群體智能的快速收斂特性尋找最優(yōu)解。路徑規(guī)劃屬于NP-hard問題,因此很多學(xué)者采用啟發(fā)式群智能算法進(jìn)行求解。蟻群算法模擬自然界螞蟻尋找最短覓食路徑，每只螞蟻在覓食時(shí)都會在路徑上留信息素，并且路徑越短，信息素濃度越高。螞蟻更傾向于沿著信息素濃度較高的路徑行走，并繼續(xù)在路徑上留下新的信息素。通過上述正反饋效應(yīng)，最終蟻群路線收斂到信息素濃度最高的最短路徑上。蟻群算法具有魯棒性好、全局搜索能力強(qiáng)、環(huán)境約束表達(dá)方便等優(yōu)勢，被廣泛應(yīng)用于路徑規(guī)劃問題中。傳統(tǒng)的蟻群算法存在迭代次數(shù)多、搜索效率低等缺點(diǎn)。為了解決這些問題，LEE[16]提出了一種基于異構(gòu)蟻群的路徑規(guī)劃方法，該方法改進(jìn)了蟻群的轉(zhuǎn)移概率函數(shù)和信息素更新規(guī)則，在不需要后續(xù)平滑處理的情況下可以直接找到節(jié)點(diǎn)數(shù)較少的最優(yōu)路徑；ZHANG等[17]提出了一種智能蟻群路徑規(guī)劃算法，該方法通過消除蟻群算法中禁忌表的約束，引入臨時(shí)權(quán)值矩陣，避免了小權(quán)值路徑的重復(fù)選擇，提高了算法的效率；LEE等[18]改變了蟻群算法生成初始種群的方式，縮短了尋找最優(yōu)解的時(shí)間，加快了算法的收斂速度；SAIDI-MEHRABAD等[19]將蟻群算法分為兩個(gè)階段進(jìn)行路徑搜索，有效縮短了路徑規(guī)劃的完成時(shí)間。劉可等[23]采用參數(shù)遷移的方法對蟻群算法進(jìn)行參數(shù)優(yōu)化，利用先驗(yàn)知識有效解決蟻群算法路徑規(guī)劃時(shí)的參數(shù)選擇問題。張強(qiáng)等[24]在蟻群算法中構(gòu)建負(fù)反饋通道，使全局信息素和局部信息素的更新速率跟隨收斂次數(shù)的變化自適應(yīng)調(diào)節(jié)，使收斂速度與全局搜索精度協(xié)調(diào)統(tǒng)一。

本文在柵格地圖中提出有效拐點(diǎn)，使路徑規(guī)劃能夠以任何方向、任何距離的柵格作為下一步的目標(biāo)柵格的方法，以提高搜索效率并降低轉(zhuǎn)彎頻率。提出最短最小路徑并給出計(jì)算方法，將最短最小距離作為蟻群算法的啟發(fā)值，作為閾值來指導(dǎo)信息素更新，以期提高引導(dǎo)效率和算法前期的收斂速度，并提高信息素更新的質(zhì)量。

1 基于拐點(diǎn)的柵格圖

柵格圖將地圖切割成相同尺寸且相互連接的柵格，每個(gè)柵格對應(yīng)相應(yīng)位置信息。3種典型柵格圖搜索方式如圖1所示。

本文提出一種能夠以任何方向、任何距離的柵格作為下一步目標(biāo)柵格的搜索方式，大大提高了搜索效率并降低轉(zhuǎn)彎頻率。如圖2所示，在某一無障礙的環(huán)境中，采用4種搜索方式搜索機(jī)器人運(yùn)動軌跡，考慮到地圖設(shè)定簡單，采用常規(guī)蟻群算法[8]進(jìn)行路徑搜索，蟻群算法關(guān)鍵參數(shù)有：迭代次數(shù)K=10，螞蟻數(shù)量m=20，信息素啟因子α=2；啟發(fā)函數(shù)因子β=3，信息素蒸發(fā)系數(shù)ρ=0.3。由圖2可以看出，4鄰域4方向搜索方式只能走直線拐直角，從起點(diǎn)到終點(diǎn)最短路徑長度為14，步數(shù)為14；8鄰域8方向搜索方式可以走45°，從起點(diǎn)到終點(diǎn)的最短路徑長度為9.1，步數(shù)為7；24鄰域16方向搜索方式從起點(diǎn)到終點(diǎn)的最短路徑為8.7，步數(shù)為5；本文的搜索方式可以取捷徑直達(dá)終點(diǎn)，路徑長度為8.6，步數(shù)為1。

鄰域數(shù)量的增多，意味著單步搜索空間增大，為了降低單步搜索的計(jì)算量，本文提出柵格拐點(diǎn)?？紤]最短路徑一定會繞過障礙柵格，因此搜索過程中僅需考慮障礙物的鄰域柵格，即拐點(diǎn)一定是障礙物的鄰域柵格。采用滑動窗口的方法尋找拐點(diǎn)，設(shè)定2×2滑動窗，遍歷整個(gè)地圖，當(dāng)窗內(nèi)僅有1個(gè)障礙物柵格時(shí)，將窗內(nèi)其他3個(gè)柵格均設(shè)定為拐點(diǎn)；當(dāng)窗內(nèi)有2個(gè)障礙物柵格，且位置處于對角，則將另外一對對角的2個(gè)柵格設(shè)定為拐點(diǎn)。幾種典型拐點(diǎn)如圖3所示，其中黑色表示障礙物柵格，白色表示可通行柵格，紅色表示拐點(diǎn)。路徑搜索時(shí)，只需要搜索拐點(diǎn)。通過設(shè)定拐點(diǎn)，可以大大減少單步搜索的工作量。

2 最短最小路徑

能夠快速、準(zhǔn)確地估計(jì)各搜索節(jié)點(diǎn)到終點(diǎn)的距離對于全局的路徑規(guī)劃具有重要意義。如在A*算法中，當(dāng)前節(jié)點(diǎn)i的代價(jià)函數(shù)為f(i)=g(i)+h(i)，式中g(shù)(i)是移動機(jī)器人從起點(diǎn)到當(dāng)前節(jié)點(diǎn)i走過的實(shí)際距離，h(i)是從當(dāng)前節(jié)點(diǎn)i到終點(diǎn)的估計(jì)值。g(i)是準(zhǔn)確值，而h(i)是估計(jì)值，正確選擇h(i)函數(shù)可以提高A*算法中搜索和選擇的科學(xué)性。傳統(tǒng)方法采用歐氏距離[3]表示h(i)。

啟發(fā)式算法中，需要用搜索節(jié)點(diǎn)的啟發(fā)值計(jì)算選擇概率，而啟發(fā)值由搜索節(jié)點(diǎn)到終點(diǎn)的距離估計(jì)值決定。例如在蟻群算法中，選擇概率由信息素濃度和啟發(fā)值共同決定，在迭代初期，路徑信息素濃度差別不大，主要依靠啟發(fā)信息選擇節(jié)點(diǎn)，因此準(zhǔn)確的啟發(fā)值有利于快速收斂。常見的蟻群算法[11，25]、蜂群算法[26]也多采用歐氏距離函數(shù)表示搜索節(jié)點(diǎn)到終點(diǎn)的距離估計(jì)值。

采用歐氏距離，即認(rèn)為搜索節(jié)點(diǎn)可取捷徑到達(dá)終點(diǎn)，使得距離終點(diǎn)直線距離更近的點(diǎn)更容易被選擇，但是當(dāng)捷徑路線上存在障礙物時(shí)，這種選擇傾向可能是錯(cuò)誤的。如圖4所示，起點(diǎn)為S，終點(diǎn)為E,考慮A、B兩點(diǎn)，點(diǎn)A距離終點(diǎn)E的直線距離明顯小于點(diǎn)B距離終點(diǎn)E的直線距離，但是由于AE之間存在障礙物，無法通行，因此更近的路徑是S-B-E。如果能夠在搜索節(jié)點(diǎn)到終點(diǎn)的距離估計(jì)中，發(fā)現(xiàn)B到E的距離比A到E的距離更近，可大大提高節(jié)點(diǎn)搜索和選擇的科學(xué)性。

本文提出最短最小路徑，并用最短最小距離代替歐氏距離，用于算法前期搜索節(jié)點(diǎn)的啟發(fā)值。當(dāng)起點(diǎn)、終點(diǎn)和拐點(diǎn)確定后，根據(jù)柵格點(diǎn)之間是否可直達(dá)，構(gòu)造從起點(diǎn)到終點(diǎn)的貫通樹。具體操作為：

增枝操作步驟如下：①將終點(diǎn)E置于最底層L0。②將所有與上一層Ln-1可通的點(diǎn)置于當(dāng)前層Ln。③判斷起點(diǎn)S是否在當(dāng)前層，如果S∈Ln，則算法結(jié)束，否則轉(zhuǎn)步驟②。

增枝操作得到貫通樹T1。增枝操作依據(jù)各點(diǎn)到達(dá)終點(diǎn)的步數(shù)，對有效柵格進(jìn)行分層。最底層為終點(diǎn)柵格；第2層為所有與終點(diǎn)柵格可通的點(diǎn)；第3層為所有與第2層任一點(diǎn)可通的點(diǎn)；以此類推，最上層為起點(diǎn)柵格和所有與起點(diǎn)柵格處于同一層的點(diǎn)。

剪枝操作步驟如下：①最上層僅保留起點(diǎn)柵格，其它柵格從最上層中刪除。②保留當(dāng)前層Ln中與上一層Ln+1可通的點(diǎn)，其它點(diǎn)從當(dāng)前層刪除。③如果檢索到L0，則算法結(jié)束，否則轉(zhuǎn)步驟②。

剪枝操作得到貫通樹T2。

設(shè)從起點(diǎn)到終點(diǎn)的某條路徑Rout=[a1(S),a2,a3,…,a(E)],令ci表示點(diǎn)ai所在的層數(shù)，如果Rout為最短路徑，必滿足ci≥ci+1,即下一個(gè)點(diǎn)必須在當(dāng)前點(diǎn)所在層或距離終點(diǎn)更近的層，不可能是遠(yuǎn)離終點(diǎn)的一層?；谶@一條規(guī)律，在啟發(fā)式路徑搜索中，只需要搜索與當(dāng)前節(jié)點(diǎn)處在同一層的點(diǎn)和當(dāng)前節(jié)點(diǎn)的下一層點(diǎn)，而不需要搜索所有與當(dāng)前點(diǎn)可直達(dá)的拐點(diǎn)，可以大大減小搜索壓力。

設(shè)從起點(diǎn)到終點(diǎn)的某條路徑Rout=[a1(S),a2,a3,…,a(E)]，當(dāng)對于任意i，均滿足ci>ci+1時(shí)，Rout為最小步數(shù)路徑。所有最小步數(shù)路徑中的最短路徑稱為最短最小路徑。本文用最短最小路徑的長度作為蟻群算法前期的啟發(fā)值。

3 蟻群算法求解最短路徑

為了配合前文的拐點(diǎn)柵格和最短最小路徑，本節(jié)對蟻群算法進(jìn)行特定的設(shè)計(jì)和改進(jìn)。蟻群算法路徑規(guī)劃流程見圖5。

3.1 有效拐點(diǎn)和最短最小路徑

首先刪減地圖中的無效拐點(diǎn)，并計(jì)算有效拐點(diǎn)到終點(diǎn)的最短最小距離，步驟如下：

(1)構(gòu)造柵格地圖，并用兩種滑動窗循掃整幅地圖，找到所有拐點(diǎn)。

(2)采用增枝操作，得到貫通起點(diǎn)到終點(diǎn)的貫通樹T1，采用剪枝操作，得到貫通樹T2，保留貫通樹T1最上層的拐點(diǎn)和貫通樹T2中所有的拐點(diǎn)為有效拐點(diǎn)，其余拐點(diǎn)均視為無效拐點(diǎn)。

(3)初始化信息素矩陣，如果節(jié)點(diǎn)i、j滿足：Li≥Lj或柵格點(diǎn)i與柵格點(diǎn)j不可直達(dá)，則將從節(jié)點(diǎn)i到節(jié)點(diǎn)j的路徑上的信息素強(qiáng)制置零。

(4)計(jì)算所有有效拐點(diǎn)到終點(diǎn)的最短最小距離，存放于距離期望矩陣中。

3.2 轉(zhuǎn)移概率

螞蟻從當(dāng)前柵格i到下一處柵格j的轉(zhuǎn)移概率為

(1)

(2)

式中α——信息素啟發(fā)因子

β——啟發(fā)函數(shù)因子

allowed——可選擇的柵格點(diǎn)集合

τij——點(diǎn)i到點(diǎn)j的信息素濃度

ηij——螞蟻從點(diǎn)i到點(diǎn)j的啟發(fā)信息

τis——點(diǎn)i到點(diǎn)s的信息素濃度

ηis——螞蟻從點(diǎn)i到點(diǎn)s的啟發(fā)信息

dij——點(diǎn)i到點(diǎn)j的距離

dj→end——點(diǎn)j到終點(diǎn)的距離期望

3.3 距離期望

初始時(shí)，用點(diǎn)j到終點(diǎn)的最短最小轉(zhuǎn)彎路徑長度作為距離期望。迭代過程中，實(shí)時(shí)更新距離期望矩陣，當(dāng)螞蟻搜索到一條從起點(diǎn)到終點(diǎn)的可行路徑Rout=[a1(S),a2,a3,…,a(E)]，比較中間節(jié)點(diǎn)ai沿該條可行路徑到終點(diǎn)E的實(shí)際距離與節(jié)點(diǎn)ai到終點(diǎn)的當(dāng)前距離期望，如果實(shí)際距離小于距離期望，則用該距離代替距離期望。

3.4 信息素更新

算法每次迭代中,讓所有螞蟻各自完成一次路徑搜索,并在每只到達(dá)終點(diǎn)或出現(xiàn)死鎖時(shí)停止搜索，每次迭代結(jié)束后,根據(jù)各螞蟻搜索到的路徑，各柵格的信息素濃度為

(3)

式中m——蟻群數(shù)量

此處改進(jìn)在于，由于已經(jīng)有了最短最小轉(zhuǎn)彎路徑作為參考，本文認(rèn)為只有螞蟻成功搜索到終點(diǎn)，且長度小于等于最短最小轉(zhuǎn)彎路徑的長度才算對群體有貢獻(xiàn)，因此信息素濃度增量取

(4)

式中Q——常數(shù)

dk——螞蟻k從起點(diǎn)到終點(diǎn)走過路徑的距離

dm——起點(diǎn)到終點(diǎn)的最短最小距離

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

為了驗(yàn)證本文算法的有效性和可行性,通過仿真實(shí)驗(yàn)對算法的相關(guān)性能進(jìn)行驗(yàn)證，并與文獻(xiàn)[8]中提出的方法進(jìn)行對比。仿真實(shí)驗(yàn)運(yùn)行環(huán)境:操作系統(tǒng)Windows 7(64位),處理器Inter(R) Core(TM) i5-4590U, CPU3.30 GHz,內(nèi)存8 GB,仿真平臺Matlab R2016a。

4.1 最短最小距離和歐氏距離統(tǒng)計(jì)實(shí)驗(yàn)

為了驗(yàn)證本文提出的用最短最小距離作為啟發(fā)值的方法的科學(xué)性，進(jìn)行最短最小距離和歐氏距離統(tǒng)計(jì)實(shí)驗(yàn)。隨機(jī)生成100幅規(guī)模為30×30、障礙比例為0.2～0.4的柵格地圖并從中隨機(jī)選取起點(diǎn)和終點(diǎn)(每幅地圖可取多組起點(diǎn)和終點(diǎn))，求取起點(diǎn)和終點(diǎn)間的最短最小路徑和歐氏距離，同時(shí)用本文的蟻群算法計(jì)算起點(diǎn)到終點(diǎn)的最近路徑，蟻群算法關(guān)鍵參數(shù)：迭代次數(shù)K=50，螞蟻數(shù)量m=50，信息素啟因子α=3；啟發(fā)函數(shù)因子β=6，信息素蒸發(fā)系數(shù)ρ=0.3。路徑距離見表1，其中R表示最短最小距離(歐氏距離)與用本文蟻群算法求得的最短距離的比值。

表1 路徑距離Tab.1 Path distance

由表1可以看出，即使拐點(diǎn)層數(shù)達(dá)到12，最短最小距離和最短距離的比值仍小于1.08，說明最短最小距離可以很大程度上體現(xiàn)起點(diǎn)到終點(diǎn)的距離；而歐氏距離與最短距離的比值隨著層數(shù)的增多，比值減小到0.354，說明二者差距逐漸加大。由此可以看出，用最短最小距離作為搜索節(jié)點(diǎn)的啟發(fā)值更準(zhǔn)確可靠。

4.2 有效拐點(diǎn)數(shù)量和單步搜索空間統(tǒng)計(jì)實(shí)驗(yàn)

螞蟻在選擇下一步節(jié)點(diǎn)時(shí),長遠(yuǎn)的視野范圍可以幫助螞蟻更好地規(guī)劃路徑，但是也造成了單步搜索空間巨大而不利于快速收斂。為解決這個(gè)問題，本文基于最短路徑和障礙柵格的關(guān)系，提出拐點(diǎn)柵格，并通過增枝操作進(jìn)一步刪減掉無效拐點(diǎn)；同時(shí)，基于增枝貫通樹中柵格點(diǎn)的層級關(guān)系，進(jìn)一步減小了螞蟻單步移動需要搜索的柵格數(shù)量。

為了便于直觀地理解增枝操作在減少有效拐點(diǎn)數(shù)量和減小單步搜索空間方面的作用，仿真算例如圖6所示。圖6a為原始柵格地圖，白色表示可通行，黑色表示障礙物，左上角為起點(diǎn)，右下角為終點(diǎn)。圖6b為拐點(diǎn)地圖，紅色柵格為拐點(diǎn)。圖6c為經(jīng)過增枝操作生成的分層地圖，圖中紫色柵格為L0層的點(diǎn)，也就是終點(diǎn)，綠色柵格為L1層的點(diǎn)，也就是所有與L0層的點(diǎn)可直達(dá)的點(diǎn)，同理深藍(lán)色為L3層的點(diǎn)，淺藍(lán)色為L4層的點(diǎn)，起點(diǎn)位于L4層中，而圖6c中的紅色點(diǎn)即為淘汰的無效拐點(diǎn)?？梢钥闯?，通過增枝操作減小了有效拐點(diǎn)的數(shù)量。由于在最短路徑中，下一步到達(dá)的點(diǎn)必須是當(dāng)前點(diǎn)所在層的點(diǎn)或距離終點(diǎn)更近的層中的點(diǎn)，而不可能是遠(yuǎn)離終點(diǎn)的一層中的點(diǎn)，由此可以明顯減少單步搜索空間，以起點(diǎn)為例，當(dāng)前單步搜索只需要搜索L4層的點(diǎn)(淺藍(lán)色)和L3層的點(diǎn)(深藍(lán)色)，而不需要搜索其他的有效拐點(diǎn)。同時(shí)通過節(jié)點(diǎn)間是否可直達(dá)的限制，進(jìn)一步刪減一部分待搜索的拐點(diǎn)，可以明顯減少單步搜索的壓力。

為了進(jìn)一步驗(yàn)證本文方法在減少有效拐點(diǎn)數(shù)量和減小單步搜索空間方面的作用，設(shè)定地圖規(guī)模為15×15、30×30、60×60，障礙柵格比例為0.2、0.3、0.4、0.5，共計(jì)12種地圖下，重復(fù)實(shí)驗(yàn)20次，統(tǒng)計(jì)有效拐點(diǎn)數(shù)量和單步搜索空間的平均值。平均有效拐點(diǎn)數(shù)量見圖7，平均單步搜索空間見圖8。

由圖7、8可以看出，雖然本文采取了無限鄰域的搜索方式，但是由于有效拐點(diǎn)概念的提出刪減了大量無效柵格點(diǎn)，使得每幅地圖的平均有效拐點(diǎn)數(shù)和平均單步搜索空間都在可接受的范圍內(nèi)。對比常規(guī)的有限鄰域有限方向搜索方式，可通行柵格數(shù)和平均單步搜索空間見表2，本文搜索方式的有效拐點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)小于常規(guī)搜索方式的可通行柵格數(shù)，平均單步搜索空間略高于常規(guī)搜索方式的平均單步搜索空間。

表2 常規(guī)搜索方式可通行柵格數(shù)和平均單步搜索空間Tab.2 Number of passable grids and average single step search domain of conventional search methods

4.3 對比實(shí)驗(yàn)

文獻(xiàn)[8]采用16方向24鄰域的螞蟻搜索方式,并結(jié)合向量夾角的思想設(shè)計(jì)2種啟發(fā)信息的計(jì)算方法，并在轉(zhuǎn)移選擇時(shí)采用δ-貪婪策略。首先采用文獻(xiàn)中的地圖進(jìn)行對比實(shí)驗(yàn)。對比方法和本文方法搜索到最優(yōu)路徑如圖9所示。

文獻(xiàn)[8]方法和本文方法搜索到最優(yōu)路徑的長度和步數(shù)比較見表3。經(jīng)人工分析，圖9a、9b、9d、9e中的路徑都是相應(yīng)搜索規(guī)則下的最短路徑，可以看出，本文方法得到的最短路徑，在路徑長度和步數(shù)上均優(yōu)于文獻(xiàn)[8]方法的最優(yōu)路徑。

為了進(jìn)一步驗(yàn)證本文算法的優(yōu)越性，設(shè)定地圖規(guī)模為15×15、30×30、60×60，障礙柵格比例0.2、0.4，隨機(jī)生成6幅地圖。為了便于讀者復(fù)現(xiàn)和驗(yàn)證，采用rand(‘state’,0)鎖定隨機(jī)地圖。如生成規(guī)模為15×15、障礙比例為0.2的地圖，代碼為

表3 最優(yōu)路徑比較Tab.3 Comparison of optimal path

rand(‘state’,0);

G=rand(15);

Map=double(G<0.2)；

分別用本文算法和文獻(xiàn)[8]方法求解每幅地圖的最短路徑，每幅地圖重復(fù)實(shí)驗(yàn)10次。蟻群算法關(guān)鍵參數(shù)：迭代次數(shù)K=50，螞蟻數(shù)量m=50，信息素啟因子α=3；啟發(fā)函數(shù)因子β=6，信息素蒸發(fā)系數(shù)ρ=0.3，文獻(xiàn)[8]算法采用method 1作為啟發(fā)信息計(jì)算方式，貪婪選擇概率δ=0.8。本文算法和文獻(xiàn)[8]算法最優(yōu)路徑對比見表4。

可以看出，本文方法在路徑長度、步數(shù)、迭代次數(shù)方面均優(yōu)于文獻(xiàn)[8]方法。由于本文提出的搜索方式不受距離限制，隨著地圖規(guī)模增大，所需步數(shù)的增加速度較慢，而對比算法的步數(shù)隨地圖規(guī)模的增大快速增多,因此隨著地圖規(guī)模增大，本文算法相對于對比算法，步數(shù)這一指標(biāo)的提升愈加明顯，更短的步數(shù)意味著更少的出錯(cuò)概率和更高的可靠性，利于快速收斂。文獻(xiàn)[8]算法在貪婪選擇中增加了參數(shù)δ，有一定概率隨機(jī)選擇柵格，有利于跳出局部最優(yōu)解但減緩了收斂速度。因此本文算法比文獻(xiàn)[8]算法需要更少的迭代次數(shù)。本文方法求得的路徑距離更短的原因有：①由于搜索方式的改進(jìn)，對于遠(yuǎn)距離的可直達(dá)柵格點(diǎn)，機(jī)器人可以直接取捷徑通過，避免不必要的彎折。②本文方法步數(shù)少而帶來的低錯(cuò)誤率和高收斂精度優(yōu)勢。

表4 本文方法和文獻(xiàn)[8]方法最優(yōu)路徑對比Tab.4 Comparison of optimal path of proposed method and Literature[8] method

5 結(jié)論

(1)針對柵格圖環(huán)境下的路徑規(guī)劃問題，提出了一種基于有效拐點(diǎn)和最短最小路徑的蟻群路徑規(guī)劃方法。在柵格地圖中采取無限鄰域的搜索方式，使機(jī)器人可取捷徑直達(dá)任何可直通的柵格點(diǎn)，同時(shí)為了減小搜索量，提出有效拐點(diǎn)的概念，大大減小了搜索空間。提出最短最小路徑的概念，并用其取代歐氏距離作為啟發(fā)值，提高了啟發(fā)值的準(zhǔn)確度和可靠性，同時(shí)用起點(diǎn)到終點(diǎn)的最短最小距離，指導(dǎo)信息素更新，提高了蟻群算法迭代的質(zhì)量。

(2)不同規(guī)模和復(fù)雜度環(huán)境的仿真實(shí)驗(yàn)表明,本文方法與常規(guī)柵格搜索方式下的蟻群路徑規(guī)劃方法相比有較大的提升，有效減少了路徑長度和步數(shù),加快了算法的迭代收斂速度。