基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人路徑規(guī)劃①

陳勁峰 黃衛(wèi)華 王 肖 章 政

(武漢科技大學(xué)信息科學(xué)與工程學(xué)院 武漢 430081) (智能信息處理與實(shí)時(shí)工業(yè)系統(tǒng)湖北省重點(diǎn)實(shí)驗(yàn)室 武漢 430081)

0 引 言

移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人研究領(lǐng)域中的一個(gè)重要分支和研究熱點(diǎn)，它指的是按照一定參考指標(biāo)，機(jī)器人在具有障礙物的環(huán)境中尋找一條從起點(diǎn)到目標(biāo)點(diǎn)最優(yōu)或次優(yōu)的無(wú)碰撞路徑[1]。傳統(tǒng)的路徑規(guī)劃方法有柵格法[2]、人工勢(shì)場(chǎng)法[3]、可視圖法[4]、快速探索隨機(jī)樹(shù)法[5]等。然而對(duì)于一些復(fù)雜環(huán)境，如震后救援、野外運(yùn)輸?shù)龋阉鲄^(qū)域空間大，且障礙物的分布不規(guī)則，傳統(tǒng)路徑規(guī)劃算法存在尋優(yōu)效率低等問(wèn)題。近年來(lái)，一些具有啟發(fā)性智能算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃中，其中蟻群算法[6]已得到較為廣泛的應(yīng)用。

蟻群算法是一種自組織算法，具有較強(qiáng)的魯棒性，優(yōu)良的并行分布式計(jì)算能力、易于與其他算法結(jié)合等優(yōu)點(diǎn)。然而，蟻群算法存在初期信息素匱乏、收斂速度慢、易陷入局部最優(yōu)解等問(wèn)題[7]，眾多學(xué)者展開(kāi)了一系列的改進(jìn)工作。文獻(xiàn)[8]提出了將信息素與啟發(fā)信息兩者的權(quán)重參數(shù)互鎖，改進(jìn)啟發(fā)信息，提高了搜索速度，避免算法陷入局部最優(yōu)。文獻(xiàn)[9]和文獻(xiàn)[10]主要提出了螞蟻雙向搜索策略，并輔之信息素更新等方法，提高了避障能力且加快了算法收斂速度。文獻(xiàn)[11]將貪婪交叉算子應(yīng)用于每次迭代結(jié)束時(shí)的輪盤賭中，以實(shí)現(xiàn)交叉操作，加快了求解最優(yōu)解的速度。文獻(xiàn)[12]使用刺激概率與無(wú)限步長(zhǎng)的啟發(fā)信息，改進(jìn)信息素?fù)]發(fā)率，加快了算法的收斂速度。文獻(xiàn)[13]通過(guò)設(shè)置初始信息素，以及信息素?fù)]發(fā)機(jī)制，調(diào)整自適應(yīng)路徑長(zhǎng)度等策略提高了算法找最優(yōu)解的收斂速度。文獻(xiàn)[14]改進(jìn)信息素更新機(jī)制和信息素平滑機(jī)制，豐富了解的多樣性且提高了收斂速度。

上述算法，通過(guò)改進(jìn)信息權(quán)重參數(shù)，信息素?fù)]發(fā)與更新機(jī)制以及搜索模式有效地提高了全局搜索的收斂速度，但存在一些問(wèn)題有待于進(jìn)一步研究，如：(1)當(dāng)?shù)貓D中存在多達(dá)7個(gè)方向的鄰節(jié)點(diǎn)時(shí)，路徑判斷過(guò)程復(fù)雜會(huì)導(dǎo)致降低算法運(yùn)算速度，同時(shí)引起步數(shù)冗余；(2)啟發(fā)信息缺乏緊密地對(duì)螞蟻的引導(dǎo)性與對(duì)環(huán)境的適應(yīng)性；(3)給予初始信息素總量恒定容易導(dǎo)致路徑信息素過(guò)度積累，使機(jī)器人尋優(yōu)陷入局部最優(yōu)。

鑒于此，本文設(shè)計(jì)了一種改進(jìn)的蟻群算法，并用于解決復(fù)雜環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題。首先，通過(guò)精簡(jiǎn)可選孫節(jié)點(diǎn)策略，縮小傳統(tǒng)蟻群算搜索節(jié)點(diǎn)的范圍，同時(shí)實(shí)現(xiàn)減小算法復(fù)雜度；其次，將環(huán)境規(guī)模尺寸與目標(biāo)點(diǎn)引入到啟發(fā)函數(shù)，使得螞蟻搜索具有明確的方向性，并且適應(yīng)不同環(huán)境規(guī)模；然后，設(shè)置每代信息素總量按高斯函數(shù)下降趨勢(shì)自適應(yīng)給予機(jī)制。最后，建立了移動(dòng)機(jī)器人路徑規(guī)劃的復(fù)雜環(huán)境模型，將本文設(shè)計(jì)的改進(jìn)蟻群算法應(yīng)用于路徑規(guī)劃中，仿真結(jié)果證明了本文算法的有效性。

1 問(wèn)題描述及環(huán)境建模

本文中機(jī)器人工作環(huán)境為復(fù)雜的靜態(tài)2維空間，在全局路徑規(guī)劃中，設(shè)工作環(huán)境為n×n的柵格環(huán)境，黑色柵格用1表示障礙物，白色柵格用0表示自由可行區(qū)，不滿一個(gè)柵格的障礙物仍按照一個(gè)柵格處理。柵格序號(hào)按自上向下、從左到右的順序編為1，2，3，…，N。以柵格圖左下角為坐標(biāo)原點(diǎn)，橫軸以從左至右為x軸正方向，縱軸以自下向上為y軸正方向，每個(gè)柵格長(zhǎng)度取為單位長(zhǎng)度，每一個(gè)柵格記為一個(gè)節(jié)點(diǎn)，建立的環(huán)境模型如圖1所示。

圖1 柵格環(huán)境模型

設(shè)柵格序號(hào)為Dx，n為每行每列的柵格數(shù)，則柵格序號(hào)與直角坐標(biāo)的轉(zhuǎn)換關(guān)系為

(1)

式(1)中，MOD(Dx,n)表示Dx/n的取余函數(shù)；CEIL(Dx/n)表示求取大于或者等于Dx/n的最小整數(shù)函數(shù)。提取柵格環(huán)境二值信息(0或1)得到對(duì)應(yīng)矩陣G(n,n)，設(shè)mr表示矩陣的行，mc表示矩陣的列，則柵格序號(hào)與矩陣坐標(biāo)轉(zhuǎn)換關(guān)系為

(2)

2 基于改進(jìn)蟻群算法的路徑規(guī)劃

本文改進(jìn)的蟻群算法主要分為3個(gè)部分：(1)根據(jù)螞蟻已走的兩步節(jié)點(diǎn)，確定性分析出將運(yùn)動(dòng)下一節(jié)點(diǎn)最小的選擇區(qū)域；(2)采用既符合環(huán)境規(guī)模大小又具有目標(biāo)點(diǎn)的指引性的啟發(fā)函數(shù)對(duì)螞蟻進(jìn)行引導(dǎo)；(3)將初始給定信息素總量Q隨迭代次數(shù)的增加，按照高斯函數(shù)下降部分依次遞減分配。

2.1 路徑精簡(jiǎn)策略的選擇

一般而言，在傳統(tǒng)蟻群算法的鄰節(jié)點(diǎn)選擇中，當(dāng)前節(jié)點(diǎn)在鄰節(jié)點(diǎn)不含有障礙物前提下，除去已走過(guò)的上一節(jié)點(diǎn)外，對(duì)于將選擇的下一節(jié)點(diǎn)有7個(gè)方向需要判斷，很大程度上降低了螞蟻搜索效率，導(dǎo)致步數(shù)冗余，造成搜索路徑加長(zhǎng)。鑒于此，提出一種精簡(jiǎn)螞蟻下一步可行區(qū)域的策略。以圖2所示的孫節(jié)點(diǎn)選擇方向?yàn)槔f(shuō)明路徑精簡(jiǎn)策略，策略如下。

針對(duì)一條路徑中順序相連的節(jié)點(diǎn)D、F和節(jié)點(diǎn)G，按照螞蟻經(jīng)過(guò)節(jié)點(diǎn)D、F和G的順序，若先經(jīng)過(guò)節(jié)點(diǎn)D，其次經(jīng)過(guò)節(jié)點(diǎn)F，再經(jīng)過(guò)節(jié)點(diǎn)G，則將D記為父節(jié)點(diǎn)，F(xiàn)記為子節(jié)點(diǎn)，G記為孫節(jié)點(diǎn)，同時(shí)規(guī)定節(jié)點(diǎn)G不屬于節(jié)點(diǎn)D的鄰接點(diǎn)。其示意如圖2所示。

針對(duì)柵格模型中，螞蟻單步運(yùn)動(dòng)行走方式：直線和斜線，分別由圖2(a)與圖2(b)的路徑“父→子”所示。針對(duì)圖2(a)所示可選的3個(gè)孫節(jié)點(diǎn)，由移動(dòng)機(jī)器人路徑規(guī)劃定義有，假定每一只螞蟻由父節(jié)點(diǎn)到子節(jié)點(diǎn)這一搜索路徑是并且就是所尋找的最優(yōu)路徑，也即當(dāng)前子節(jié)點(diǎn)為父節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的必經(jīng)節(jié)點(diǎn)，即子節(jié)點(diǎn)已定，那么由父節(jié)點(diǎn)到當(dāng)前子節(jié)點(diǎn)，有5條可選路徑，如圖3(a)所示，分別為：①父→a→子；②父→b→子；③父→子；④父→c→子；⑤父→d→子。

圖2 孫節(jié)點(diǎn)選擇方向

圖3 父子節(jié)點(diǎn)走向圖

分析如下，經(jīng)比較，從起點(diǎn)到目標(biāo)點(diǎn)，③父→子這一路徑長(zhǎng)度最短，且無(wú)拐角，故路徑中如果出現(xiàn)了路徑③，那么路徑①②④⑤則不會(huì)出現(xiàn)在該次搜索路徑中，否則搜索路徑將會(huì)冗余曲折，不符合最短路徑要求。基于上述分析，路徑精簡(jiǎn)策略是除了將父節(jié)點(diǎn)加入禁忌表中，同時(shí)如圖3(a)將父節(jié)點(diǎn)的相鄰節(jié)點(diǎn)a、b、c和d不納入孫節(jié)點(diǎn)可選范圍，進(jìn)行屏蔽處理。因此根據(jù)父節(jié)點(diǎn)到子節(jié)點(diǎn)這一既定直線運(yùn)動(dòng)趨勢(shì)，可選孫節(jié)點(diǎn)有3個(gè)，如圖2(a)所示孫1、孫2和孫3。同理針對(duì)螞蟻?zhàn)咝本€的情形，可得到有效孫節(jié)點(diǎn)范圍如圖2(b)所示，孫1、孫2、孫3、孫4和孫5共5個(gè)節(jié)點(diǎn)。

由上述分析可知，通過(guò)使用對(duì)下一可選節(jié)點(diǎn)的精簡(jiǎn)策略相對(duì)原始搜索需要判斷鄰近多達(dá)7個(gè)節(jié)點(diǎn)的模式，變?yōu)楫?dāng)父與子節(jié)點(diǎn)路徑呈直線時(shí)，孫節(jié)點(diǎn)的可走路徑如圖2(a)有①子→孫1、②子→孫2、③子→孫3，只需判斷處理3個(gè)節(jié)點(diǎn)；呈斜線時(shí)孫節(jié)點(diǎn)的可走路徑如圖2(b)有①子→孫1、②子→孫2、③子→孫3、④子→孫4、⑤子→孫5，只需判斷處理5個(gè)節(jié)點(diǎn)。走直線和斜線處理的共同點(diǎn)是當(dāng)父節(jié)點(diǎn)和子節(jié)點(diǎn)已定，孫節(jié)點(diǎn)的選擇區(qū)域是在子節(jié)點(diǎn)的鄰節(jié)點(diǎn)中，除去父節(jié)點(diǎn)與子節(jié)點(diǎn)共有鄰節(jié)點(diǎn)而余下的節(jié)點(diǎn)。2種運(yùn)動(dòng)方式中的節(jié)點(diǎn)處理數(shù)均小于7個(gè)，有利于提高搜索效率，降低搜索盲目性，同時(shí)降低計(jì)算代價(jià)。

邊界特殊孫節(jié)點(diǎn)的處理。針對(duì)上述精簡(jiǎn)下一節(jié)點(diǎn)的策略，為避免螞蟻因根據(jù)圖2(a)中尋找孫節(jié)點(diǎn)的搜索模式運(yùn)動(dòng)到環(huán)境邊界節(jié)點(diǎn)，出現(xiàn)如圖4(a)中所示的困境，也即當(dāng)父→子節(jié)點(diǎn)已定，子節(jié)點(diǎn)的上下鄰節(jié)點(diǎn)被屏蔽而其右邊無(wú)孫節(jié)點(diǎn)可選，導(dǎo)致出現(xiàn)此螞蟻由于路徑精簡(jiǎn)策略的局限性而鎖死，提出取消搜索局部屏蔽機(jī)制，提高螞蟻的存活率，處理方式為開(kāi)放其偽孫節(jié)點(diǎn)，如圖4(b)所示，取消算法對(duì)子節(jié)點(diǎn)的上下鄰節(jié)點(diǎn)的屏蔽；同理，針對(duì)當(dāng)螞蟻若走斜線到達(dá)環(huán)境角落如圖4(c)無(wú)孫節(jié)點(diǎn)可選的情形時(shí)，同樣對(duì)其開(kāi)放偽孫節(jié)點(diǎn)，如圖4(d)所示。

圖4 邊界孫節(jié)點(diǎn)

2.2 啟發(fā)函數(shù)與概率函數(shù)選擇

基本蟻群算法在搜索過(guò)程中具有搜索時(shí)間長(zhǎng)，存在搜索指向不明確的缺陷。蟻群算法作為啟發(fā)型算法中的一種，啟發(fā)函數(shù)質(zhì)量的優(yōu)劣，對(duì)算法的應(yīng)用效果具有較大影響，但是傳統(tǒng)蟻群算法的啟發(fā)函數(shù)1/dij，其中dij表示相鄰節(jié)點(diǎn)之間的距離，對(duì)環(huán)境的能見(jiàn)度較低，且不具有目標(biāo)點(diǎn)的引導(dǎo)作用，導(dǎo)致搜索盲目性。針對(duì)此問(wèn)題，提出一種不受環(huán)境規(guī)模大小影響的具有引導(dǎo)機(jī)制性啟發(fā)函數(shù)，如式(3)所示：

(3)

式(3)中，Jk表示螞蟻k在一條路徑上鄰近可選下一節(jié)點(diǎn)的集合，n為環(huán)境柵格的行列數(shù)；DijE表示節(jié)點(diǎn)i、j以及目標(biāo)點(diǎn)依次連接的距離之和。當(dāng)子節(jié)點(diǎn)到孫節(jié)點(diǎn)以及目標(biāo)點(diǎn)的距離越短，其引導(dǎo)性越強(qiáng)。

以螞蟻第一步出發(fā)并無(wú)既定的父子節(jié)點(diǎn)位置關(guān)系作為指引，本文設(shè)計(jì)了聯(lián)合概率函數(shù)，如式(4)和式(5)所示：

(4)

式(4)中，τij(t)為t時(shí)刻在邊ij上的信息素積累，?為信息素權(quán)重參數(shù)，?越大表明螞蟻越傾向選擇過(guò)往螞蟻?zhàn)哌^(guò)的路徑；ηij(t)表示t時(shí)刻從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的啟發(fā)信息，β為啟發(fā)信息權(quán)重參數(shù)，其值越大，表明螞蟻越傾向走距離目標(biāo)點(diǎn)更近的節(jié)點(diǎn)。

(5)

式(5)中，Ns表示起始點(diǎn)的相鄰有效節(jié)點(diǎn)個(gè)數(shù)，step表示螞蟻k在一條路徑上累計(jì)搜索的節(jié)點(diǎn)個(gè)數(shù)；當(dāng)step=1時(shí)，使用等概率搜索，一方面有利于從起點(diǎn)擴(kuò)大全局搜索范圍，同時(shí)可解決螞蟻第一步出發(fā)無(wú)既定的父子節(jié)點(diǎn)位置關(guān)系作為指引的限制。

2.3 自適應(yīng)信息素總量給予機(jī)制

在基本蟻群算法中，信息素總量是一個(gè)定值，極大可能性存在隨著迭代次數(shù)的增加，后期路徑上的信息素濃度易積累過(guò)高導(dǎo)致螞蟻一定程度上失去搜索優(yōu)質(zhì)解能力而陷入局部最優(yōu)解，針對(duì)此問(wèn)題，提出將信息素的總量根據(jù)迭代次數(shù)遞增而按照高斯函數(shù)模型下降部分逐步降低的給予機(jī)制。

在一次迭代完成后，針對(duì)到達(dá)目標(biāo)點(diǎn)的螞蟻，將路徑上的信息素進(jìn)行更新，可得：

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

(6)

式(6)中，ρ為信息素?fù)]發(fā)系數(shù)，其中0<ρ<1，Δτij(t,t+1)表示t+1時(shí)刻所有經(jīng)過(guò)邊ij之間的螞蟻殘留信息素增量，可得：

(7)

Δτij表示第k只螞蟻經(jīng)過(guò)邊ij殘留的信息素，可得：

(8)

式(8)中，Q為信息素常量，Lk為螞蟻k在本次搜索中的路徑長(zhǎng)度。其中信息素總量Q的給予機(jī)制設(shè)計(jì)為

(9)

式(9)中，G為算法的迭代次數(shù)，設(shè)定μ=0對(duì)應(yīng)信息素總量Q的峰值，保證從第一代直至最后一代Q(G)呈下降趨勢(shì)；取σ=35，使得信息素總量符合正態(tài)分布的3σ法則，也即保證最后一代給予的總信息素量近乎為最低值。

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

將所設(shè)計(jì)的改進(jìn)蟻群算法用于路徑規(guī)劃中，算法流程如下。

步驟1參數(shù)初始化。將具有多個(gè)障礙物的地圖柵格化，并計(jì)算任意兩節(jié)點(diǎn)之間距離，取障礙柵格到其他柵格距離為無(wú)窮大，表示不可達(dá)；設(shè)定節(jié)點(diǎn)之間初始信息素，迭代次數(shù)K，螞蟻種群個(gè)數(shù)M，起始點(diǎn)S，目標(biāo)點(diǎn)E，信息素權(quán)重系數(shù)α，啟發(fā)信息權(quán)重系數(shù)β和揮發(fā)系數(shù)ρ，以及信息素總量Q。

步驟2路徑選擇。利用式(5)計(jì)算螞蟻下一節(jié)點(diǎn)的選擇概率，然后采用輪盤賭選出下一節(jié)點(diǎn)，判斷是否滿足到達(dá)目標(biāo)點(diǎn)或可選孫節(jié)點(diǎn)數(shù)小于1的條件，不滿足則轉(zhuǎn)至步驟3，滿足轉(zhuǎn)至步驟4。

步驟3狀態(tài)更新。將步驟2選出的子節(jié)點(diǎn)同時(shí)加入路徑列表和禁忌表，計(jì)算當(dāng)前路徑總距離，并根據(jù)父節(jié)點(diǎn)和子節(jié)點(diǎn)的位置關(guān)系，推導(dǎo)出可選孫節(jié)點(diǎn)范圍，返回步驟2。

步驟4螞蟻序號(hào)更新。針對(duì)沒(méi)到達(dá)目標(biāo)點(diǎn)且可選孫節(jié)點(diǎn)個(gè)數(shù)小于1的螞蟻路徑長(zhǎng)度記為無(wú)窮大；m=m+1，計(jì)算下一只螞蟻的搜索路徑，返回步驟2；當(dāng)前螞蟻序號(hào)m等于種群總數(shù)M時(shí)，轉(zhuǎn)至步驟5。

步驟5信息素更新。將完成一次迭代的所有螞蟻按式(6)的信息素更新函數(shù)進(jìn)行路徑上的信息素更新。

步驟6螞蟻迭代次數(shù)更新。迭代次數(shù)k=k+1，返回步驟2；當(dāng)?shù)螖?shù)滿足設(shè)定迭代次數(shù)時(shí)，結(jié)束算法。記錄歷史最優(yōu)路徑，繪制出每代平均距離曲線與算法收斂曲線。

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

在不同規(guī)模的復(fù)雜環(huán)境下，驗(yàn)證本文設(shè)計(jì)的改進(jìn)蟻群算法并用于移動(dòng)機(jī)器人的路徑規(guī)劃，基于柵格法建立如圖5(a)和圖6(a)所示的環(huán)境地圖，環(huán)境1和環(huán)境2分別為20×20與30×30的柵格地圖。地圖中，一部分障礙物呈現(xiàn)凹陷狀，另一部分障礙物設(shè)置成無(wú)次序且無(wú)規(guī)則的近似隨機(jī)分布狀態(tài)，設(shè)置機(jī)器人起始點(diǎn)為柵格模型的左上角，目標(biāo)點(diǎn)為右下角。

4.1 環(huán)境1實(shí)驗(yàn)結(jié)果分析

在20×20的柵格環(huán)境1中，傳統(tǒng)蟻群算法與本文改進(jìn)蟻群算法最短路徑如圖5(a)所示，每代最小路徑與平均路徑距離分別如圖5(b)和圖5(c)所示。對(duì)比搜索路徑，傳統(tǒng)蟻群算法在搜索時(shí)缺乏目標(biāo)點(diǎn)的引導(dǎo)作用，導(dǎo)致搜索盲目，同時(shí)算法后期路徑上信息素積累過(guò)高，螞蟻更多地選擇已走路徑，從而出現(xiàn)圖5(a)虛線所示路徑上的第4個(gè)不必要的拐點(diǎn)；而本文算法在使用精簡(jiǎn)下一節(jié)點(diǎn)的可選范圍策略上，首先就避免了路徑直角折點(diǎn)的出現(xiàn)，在實(shí)際情形下實(shí)現(xiàn)降低移動(dòng)機(jī)器人消耗的能量，其次引入具有啟發(fā)性的啟發(fā)函數(shù)，自適應(yīng)遞減信息素總量，因此路徑無(wú)多余曲折的拐點(diǎn)。

對(duì)比收斂曲線，如圖5(b)所示，在傳統(tǒng)蟻群算法中由于沒(méi)有目標(biāo)點(diǎn)的引導(dǎo)作用，在前60代搜索中只有4代搜索到了最短路徑，直至接近第90代平均路徑與最短路徑才最終匯合，歸結(jié)于傳統(tǒng)蟻群算法的初期信息素匱乏，導(dǎo)致收斂速度慢；而本文算法中螞蟻搜索存在目標(biāo)點(diǎn)的引導(dǎo)作用，以高斯函數(shù)下降部分按迭代次數(shù)遞減信息素總量避免信息素積累的基礎(chǔ)上，不僅在第13代就能找到最短路徑，而且在圖5(c)可以看出平均路徑距離開(kāi)始逐步降低且趨于穩(wěn)定，由于信息素的自適應(yīng)給予機(jī)制使得全體螞蟻搜索路徑收斂很快。

(a) 傳統(tǒng)蟻群算法與本文算法最優(yōu)路徑圖

(b) 傳統(tǒng)蟻群算法與本文算法路徑最小曲線

(c) 傳統(tǒng)蟻群算法與本文算法路徑平均距離曲線圖5 環(huán)境1中實(shí)驗(yàn)結(jié)果比較

4.2 環(huán)境2實(shí)驗(yàn)結(jié)果分析

在環(huán)境2中，傳統(tǒng)蟻群算法與本文算法最短路徑實(shí)驗(yàn)結(jié)果如圖6(a)所示，最小路徑距離和平均距離曲線圖分別如圖6(b)和圖6(c)所示。柵格環(huán)境中設(shè)置了更多凹陷區(qū)，對(duì)于基本蟻群算法結(jié)果而言，其路徑由于沒(méi)有目標(biāo)點(diǎn)的引導(dǎo)作用，同時(shí)由于路徑信息素的積累作用，導(dǎo)致后期信息素過(guò)高，后期螞蟻選擇前期螞蟻?zhàn)哌^(guò)的路徑，出現(xiàn)了3個(gè)多余的拐點(diǎn)，如圖6(a)曲線直角所示，在實(shí)際搜索中增加了能量損耗，而本文算法由于設(shè)置了自適應(yīng)信息素總量給予機(jī)制，避免了路徑上的信息素過(guò)度積累，在以找到最短路徑為目標(biāo)時(shí)，只出現(xiàn)了不可避免最少的拐點(diǎn)數(shù)。

(a) 傳統(tǒng)蟻群算法與本文算法最優(yōu)路徑圖

(b) 傳統(tǒng)蟻群算法與本文算法路徑最小曲線

(c) 傳統(tǒng)蟻群算法與本文算法路徑平均距離曲線圖6 環(huán)境2中實(shí)驗(yàn)結(jié)果比較

在最小路徑圖6(b)中，與環(huán)境1類似，由于具有目標(biāo)點(diǎn)對(duì)螞蟻的緊密引導(dǎo)作用，本文算法在找到最短路徑的代數(shù)遠(yuǎn)遠(yuǎn)早于傳統(tǒng)蟻群算法找到最短路徑的代數(shù)；鑒于采用了精簡(jiǎn)可選節(jié)點(diǎn)策略，實(shí)現(xiàn)降低搜索范圍，使得螞蟻搜索路徑集中，本文算法平均路徑不僅下降速度比傳統(tǒng)蟻群算法快，而且距離更短。

本文實(shí)驗(yàn)參數(shù)設(shè)置如表1所示，針對(duì)實(shí)驗(yàn)參數(shù)的取值，本文在計(jì)算下一節(jié)點(diǎn)概率函數(shù)中取消信息素項(xiàng)，然后依舊以輪盤賭的方式選擇下一節(jié)點(diǎn)做測(cè)試。結(jié)果顯示，平均曲線與最小曲線均呈現(xiàn)雜亂無(wú)序狀況，即表明假使缺失信息素項(xiàng)的作用，算法將失效，表明了信息素項(xiàng)在所取該值的情況下，發(fā)揮了其在蟻群算法中使蟻群相互協(xié)作的作用，同時(shí)表明了所取值的合理性。

表1 本文實(shí)驗(yàn)參數(shù)設(shè)置

本文算法與傳統(tǒng)蟻群算法在環(huán)境1與環(huán)境2的實(shí)驗(yàn)結(jié)果分別如表2和表3所示。

表2 環(huán)境1實(shí)驗(yàn)結(jié)果

表3 環(huán)境2實(shí)驗(yàn)結(jié)果

由表2以及表3知，采用相同的螞蟻群體個(gè)數(shù)和迭代次數(shù)，本文算法與傳統(tǒng)蟻群算法在2種環(huán)境的路徑規(guī)劃比較中，本文算法獲得路徑距離更短，收斂代數(shù)更早，拐點(diǎn)數(shù)目更少，最優(yōu)路徑上總的拐角度數(shù)之和更小，即路徑更為平滑，對(duì)于實(shí)際機(jī)器人有利于降低能量與時(shí)間消耗。綜合而言，改進(jìn)算法比傳統(tǒng)蟻群算法在復(fù)雜環(huán)境中更加體現(xiàn)出其優(yōu)越性，具有更快的搜索速度及路徑平滑度。

5 結(jié) 論

本文針對(duì)傳統(tǒng)蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃時(shí)出現(xiàn)初期信息素缺乏、易陷入局部最優(yōu)、收斂速度慢等問(wèn)題，對(duì)可選轉(zhuǎn)移節(jié)點(diǎn)進(jìn)一步優(yōu)化，使用精簡(jiǎn)可選節(jié)點(diǎn)策略，實(shí)現(xiàn)降低了盲目搜索性，降低了計(jì)算代價(jià)；在此基礎(chǔ)上，設(shè)計(jì)符合環(huán)境變化的啟發(fā)函數(shù)，將目標(biāo)點(diǎn)引入其中，增強(qiáng)對(duì)螞蟻搜索的引導(dǎo)作用；最后，為了加強(qiáng)后期螞蟻受前期螞蟻在路徑上殘留信息素的影響，同時(shí)為了避免搜索后期信息素過(guò)度積累，引入符合高斯函數(shù)模型隨迭代次數(shù)而遞減的自適應(yīng)總信息素給予機(jī)制。仿真實(shí)驗(yàn)表明，與傳統(tǒng)蟻群算法相比，在獲得路徑質(zhì)量更優(yōu)的前提下，本文算法所規(guī)劃的路徑更短、更平滑，具有更快的收斂速度，證實(shí)了本文算法在不同復(fù)雜環(huán)境中作為移動(dòng)機(jī)器人路徑規(guī)劃算法的有效性與優(yōu)越性。