柵格環(huán)境下機(jī)器人路徑的復(fù)合啟發(fā)蟻群規(guī)劃

龍珊珊，高 倩，高曼曼

（石家莊理工職業(yè)學(xué)院，河北 石家莊 050000）

1 引言

機(jī)器人可以輔助或者代替人類完成重復(fù)性強(qiáng)、危險(xiǎn)性高的活動(dòng)，但是移動(dòng)機(jī)器人的工作環(huán)境一般較為復(fù)雜，對(duì)機(jī)器人行走路線的最優(yōu)化和安全性提出了較高要求。行走路徑的優(yōu)劣決定了機(jī)器人的行駛安全性和工作效率的高低[1]，因此研究機(jī)器人路徑規(guī)劃問題具有重要意義。

路徑規(guī)劃是指在含有不同障礙物的環(huán)境中，按照一定的評(píng)價(jià)準(zhǔn)則（長(zhǎng)度最短、安全性最高、平滑性最好等），規(guī)劃出一條從起點(diǎn)到終點(diǎn)的最優(yōu)無碰路徑[2]。機(jī)器人路徑規(guī)劃可以分為環(huán)境建模和路徑搜索兩個(gè)方面的內(nèi)容。環(huán)境建模是指將機(jī)器人實(shí)際的工作場(chǎng)景抽樣為機(jī)器人可以識(shí)別的數(shù)學(xué)模型，常見方法包括柵格法、連通圖法、拓?fù)鋱D法等[3]。路徑搜索可以分為傳統(tǒng)路徑搜索算法和仿生搜索算法兩類，其中傳統(tǒng)路徑搜索算法包括人工勢(shì)場(chǎng)法、模擬退火法、模糊邏輯法等，仿生搜索算法包括蟻群算法、遺傳算法、粒子群算法等。人工勢(shì)場(chǎng)法根據(jù)障礙物斥力和目標(biāo)引力規(guī)劃出路徑，路徑的平滑性較好，但是當(dāng)障礙物較多時(shí)容易出現(xiàn)“死點(diǎn)”[4]。模擬退火法可以解決大規(guī)模組合優(yōu)化問題，但是卻需要較長(zhǎng)的退火時(shí)間，使算法收斂速度慢。模糊邏輯針對(duì)駕駛員的駕駛行為形成專家系統(tǒng)，根據(jù)路徑查表獲得駕駛路徑，此方法在環(huán)境突變時(shí)可能失效，因此靈活性較差[5]。仿生搜索算法是對(duì)生物優(yōu)化的某個(gè)過程進(jìn)行模擬，實(shí)現(xiàn)算法的智能化，是當(dāng)前機(jī)器人路徑規(guī)劃的研究熱點(diǎn)，。文獻(xiàn)[6]使用人工勢(shì)場(chǎng)法對(duì)蟻群算法的啟發(fā)信息進(jìn)行改進(jìn)，此方法提高了算法的收斂速度，并減小了路徑的轉(zhuǎn)彎次數(shù)。文獻(xiàn)[7]在遺傳算法中引入新的遺傳因子，提出了協(xié)同進(jìn)化遺傳算法，該方法加快了算法的收斂速度，并改善了解的質(zhì)量。文獻(xiàn)[8]可以根據(jù)地圖的不同情況自適應(yīng)地調(diào)節(jié)蟻群算法參數(shù)，在保證解的質(zhì)量同時(shí)提高了優(yōu)化效率。仿生搜索算法存在的共性問題是算法優(yōu)化能力的深化，當(dāng)前關(guān)于仿生搜索算法的研究均集中在這一問題上。

針對(duì)機(jī)器人在柵格環(huán)境下的路徑規(guī)劃問題，提出了復(fù)合啟發(fā)信息蟻群算法的路徑規(guī)劃策略。該方法以蟻群算法為基礎(chǔ)，融入了兩種啟發(fā)信息，給出了基于改進(jìn)蟻群算法的規(guī)劃策略，實(shí)現(xiàn)了減小路徑長(zhǎng)度、提高規(guī)劃效率的目的。

2 問題描述與建模

2.1 問題描述

這里研究的問題為柵格環(huán)境下機(jī)器人的路徑規(guī)劃問題，包括3個(gè)方面的內(nèi)容：（1）柵格環(huán)境模型的建立；（2）規(guī)劃目標(biāo)的設(shè)定；（3）規(guī)劃算法，其中規(guī)劃算法是核心內(nèi)容。柵格模型的建立是指使用一定尺寸的方形柵格對(duì)工作環(huán)境進(jìn)行分割，機(jī)器人行駛時(shí)以柵格為基本單元。柵格尺寸的設(shè)定需參考機(jī)器人直徑、環(huán)境中障礙物尺寸及復(fù)雜程度，一般來講，機(jī)器人尺寸較大、障礙物尺寸較大、障礙物分布較簡(jiǎn)單時(shí)，柵格尺寸設(shè)置值較大。

為了保證行駛路徑的絕對(duì)安全，對(duì)障礙物一般使用膨化處理方法，即當(dāng)某柵格中存在障礙物時(shí)，則讓障礙物充滿該柵格[9]，如圖1所示。

圖1 障礙物膨化Fig.1 Obstacles Expansion

另外，機(jī)器人對(duì)實(shí)際的工作環(huán)境是無法識(shí)別的，為了將實(shí)際工作環(huán)境轉(zhuǎn)化為機(jī)器人可以識(shí)別的模式，根據(jù)柵格特性為其賦不同的屬性值，當(dāng)柵格中存在障礙物時(shí)為其賦值為1，當(dāng)柵格中不存在障礙物時(shí)為其賦值為0。按照以上規(guī)則，圖1的工作環(huán)境可以轉(zhuǎn)化為0-1矩陣，為：

對(duì)于屬性為0的可自由行駛柵格，為了對(duì)走過的自由柵格和未走過的自由柵格進(jìn)行區(qū)分，將走過的自由柵格賦值為-1，未走過的自由柵格屬性不變。則機(jī)器人可明確區(qū)分障礙物柵格、已走過的自由柵格和未走過的自由柵格。

在柵格環(huán)境下，路徑規(guī)劃的目標(biāo)為機(jī)器人從起始柵格到達(dá)目標(biāo)柵格的路徑最短，即目標(biāo)函數(shù)為：

式中：LSG—起始柵格S與目標(biāo)柵格G之間的路徑長(zhǎng)度。

2.2 傳統(tǒng)蟻群算法與分析

傳統(tǒng)蟻群算法中，螞蟻對(duì)柵格的選擇包括8方向搜索和4方向搜索兩種，因8方向搜索的路徑平滑性更好、搜索效率更高，這里使用8方向搜索法。螞蟻對(duì)柵格的選擇是在啟發(fā)信息和信息素的雙重引導(dǎo)下實(shí)現(xiàn)的。啟發(fā)信息由目標(biāo)柵格對(duì)螞蟻的啟發(fā)作用而設(shè)定，信息素是模擬蟻群協(xié)作時(shí)的交流介質(zhì)而給出的。螞蟻對(duì)鄰域內(nèi)自由柵格的選擇概率為[10]：

式中：i—螞蟻所在的當(dāng)前柵格；j—鄰域內(nèi)的待選自由柵格；k—螞蟻編號(hào)；t—迭代次數(shù)—螞蟻k由柵格i選擇柵格j的概率；τij(t)—螞蟻擇柵格j的啟發(fā)信息，τij(t)=，LjG—柵格j與目標(biāo)柵格G的距離；α—啟發(fā)因子；ηij(t)—路徑ij間的信息素濃度；β—信息素因子；allowedi—柵格i鄰域的自由柵格。

在傳統(tǒng)蟻群算法中規(guī)定，每完成一次算法迭代，則進(jìn)行一次信息素更新。信息素更新包括信息素?fù)]發(fā)和信息素殘留兩個(gè)方面，即：

式中：ρ—揮發(fā)系數(shù)；Δτij(t)—螞蟻在路徑ij上殘留的信息素；M—螞蟻數(shù)量—螞蟻k在路徑ij上殘留的信息素；Lk—螞蟻k的路徑長(zhǎng)度。

蟻群算法存在路徑多樣性與路徑收斂的矛盾，當(dāng)路徑多樣性較好時(shí)，說明螞蟻搜索的范圍較大，但同時(shí)也說明螞蟻搜索的隨機(jī)性較大，路徑的收斂性較差。當(dāng)路徑收斂性較好時(shí)，說明螞蟻搜索的方向性較好，但是同時(shí)說明螞蟻容易陷入某一局部最優(yōu)路徑，螞蟻的探索能力較差。上述問題是傳統(tǒng)蟻群算法存在的共識(shí)問題。

3 復(fù)合啟發(fā)信息蟻群算法

3.1 復(fù)合啟發(fā)信息

為了平衡蟻群算法的路徑多樣性與收斂性，基于目標(biāo)柵格的引導(dǎo)作用提出了兩種啟發(fā)信息。在傳統(tǒng)蟻群算法中，一般將待選柵格j與目標(biāo)柵格G的距離倒數(shù)作為啟發(fā)信息，也就是說將待選柵格與目標(biāo)柵格的遠(yuǎn)近作為一種啟發(fā)。但是，直觀地講，螞蟻由當(dāng)前柵格沿直線到達(dá)目標(biāo)柵格是最佳路徑，因此將目標(biāo)柵格與當(dāng)前柵格的連線方向作為啟發(fā)信息，其啟發(fā)性必然強(qiáng)于距離信息的啟發(fā)性。按照這一思路，使用待選柵格j與目標(biāo)柵格G間的向量夾角θ構(gòu)造啟發(fā)信息。夾角示意圖，如圖2所示。

圖2 待選柵格向量與目標(biāo)柵格向量夾角Fig.2 Angle Between Selected Grid Vector and Target Grid Vector

在圖2 中，當(dāng)前柵格坐標(biāo)記為(xi，yi)，待選柵格坐標(biāo)記為(xj，yj)，目標(biāo)柵格坐標(biāo)記為(xG，yG)。由直觀理解可知，螞蟻搜索的最佳方向?yàn)镈→iG=(xG-xi，yG-yi)，實(shí)際搜索方 向?yàn)镈→ij=(xj-xi，yj-yi)，在此將兩個(gè)向量的夾角定義為兩者之間的真角，因此取值范圍為θ∈[0，π]。以?shī)A角θ為基礎(chǔ)，構(gòu)造兩種啟發(fā)信息。啟發(fā)信息1為：

啟發(fā)信息2為：

對(duì)于啟發(fā)信息1 和啟發(fā)信息2，當(dāng)θ∈[0，π]范圍內(nèi)，ηij1和ηij2均為單調(diào)遞減函數(shù)，這意味著夾角θ越?。ù藭r(shí)待選柵格越靠近最優(yōu)方向），對(duì)應(yīng)柵格對(duì)螞蟻的啟發(fā)能力越強(qiáng)，螞蟻更容易選擇這一柵格；夾角θ越大（此時(shí)待選柵格越遠(yuǎn)離最優(yōu)方向），對(duì)應(yīng)柵格對(duì)螞蟻的啟發(fā)能力越弱，螞蟻越不容易選擇這一柵格。以上分析表明，2種啟發(fā)信息的構(gòu)造方法是合理的。啟發(fā)信息1和啟發(fā)信息2的ηij值隨夾角θ的變化趨勢(shì)，如圖3所示。

圖3 啟發(fā)信息變化趨勢(shì)Fig.3 Changing Tendency of Inspiration Information

經(jīng)計(jì)算圖3中的交點(diǎn)A橫坐標(biāo)為148.1°，這意味著幾乎在整個(gè)θ的取值范圍內(nèi)，當(dāng)ηij值相同時(shí)，相應(yīng)的有θ1>θ2。也就是說，在相同啟發(fā)信息范圍的情況下，夾角θ1的變化范圍大于夾角θ1的變化范圍，說明啟發(fā)信息1可以指導(dǎo)螞蟻進(jìn)行更大角度范圍的搜索，而啟發(fā)信息2的方向性較強(qiáng)，可以指導(dǎo)螞蟻沿著最佳方向進(jìn)行搜索。為了對(duì)上述分析進(jìn)行更加直觀的解釋，設(shè)置ηij1=ηij2>0.5，則夾角θ1∈(0，90°)，θ2∈(0，39.7°)，如圖4所示。由圖4可直觀看出，啟發(fā)信息1的搜索范圍更廣，而啟發(fā)信息2的搜索方向性更強(qiáng)。

圖4 啟發(fā)信息1和啟發(fā)信息2對(duì)比Fig.4 Comparison of Inspiration Information 1 and Inspiration Information 2

3.2 復(fù)合啟發(fā)信息蟻群算法

根據(jù)蟻群算法的路徑規(guī)劃需求，算法前期需要較大的搜索范圍，以便對(duì)工作區(qū)域的最優(yōu)路徑進(jìn)行廣泛搜索；算法后期需要較強(qiáng)的方向性搜索，以便算法收斂于最優(yōu)路徑附近，并進(jìn)行最優(yōu)路徑附近的細(xì)致搜索。按照算法上述的需求分析，提出的改進(jìn)蟻群算法思想為：前期設(shè)置較大數(shù)量的啟發(fā)信息1螞蟻，以便進(jìn)行大范圍搜索；后期設(shè)置較大數(shù)量的啟發(fā)信息2螞蟻，以便進(jìn)行方向性強(qiáng)的小范圍細(xì)致搜索。

根據(jù)算法的需求分析，算法前期蟻群中設(shè)置更多的啟發(fā)信息1類的螞蟻，隨著算法的迭代，啟發(fā)信息1類的螞蟻數(shù)量逐漸減少，而增加啟發(fā)信息2類的螞蟻。這種設(shè)置方法兼顧了前期大范圍搜索需求和后期方向性較強(qiáng)的搜索需求。蟻群規(guī)模記為N，算法的最大迭代次數(shù)記為tmax，啟發(fā)信息1類的螞蟻數(shù)量記為N1，啟發(fā)信息2類的螞蟻數(shù)量記為N2，則兩類螞蟻的數(shù)量設(shè)置為：

式中：t—當(dāng)前迭代次數(shù)。

分析式（6）可知，隨著算法的迭代，啟發(fā)信息1類的螞蟻逐漸減少，啟發(fā)信息2類的螞蟻逐漸增多，滿足前文的構(gòu)造需求。

兩類螞蟻之間的交流通過信息素實(shí)現(xiàn)，即通過路徑上殘留的信息素濃度可以實(shí)現(xiàn)螞蟻之間的交流與協(xié)作。

3.3 基于復(fù)合啟發(fā)信息蟻群算法的路徑規(guī)劃步驟

根據(jù)復(fù)合啟發(fā)信息蟻群算法的原理，結(jié)合柵格環(huán)節(jié)下機(jī)器人路徑規(guī)劃的特點(diǎn)，設(shè)置基于復(fù)合啟發(fā)信息蟻群算法的機(jī)器人路徑規(guī)劃步驟為：

（1）設(shè)置柵格環(huán)境規(guī)模、起點(diǎn)柵格、終點(diǎn)柵格；設(shè)置算法參數(shù)，包括螞蟻數(shù)量、信息素因子、啟發(fā)因子、信息素?fù)]發(fā)系數(shù)、算法最大迭代次數(shù)等；（2）將螞蟻放置在起始柵格，開始路徑規(guī)劃；（3）兩類螞蟻按照各自的啟發(fā)信息進(jìn)行柵格選擇，得到各自規(guī)劃出的路徑；（4）判斷是否所有螞蟻完成了一次迭代，若否則等待；若是則迭代i次數(shù)＋1；（5）判斷是否達(dá)到最大迭代次數(shù)，若否則轉(zhuǎn)至（2）；若是則輸出最優(yōu)路徑，算法結(jié)束。

4 仿真驗(yàn)證

4.1 啟發(fā)信息效果驗(yàn)證

首先在（30×30）規(guī)模的柵格環(huán)境下驗(yàn)證路徑規(guī)劃效果，工作環(huán)境中障礙物柵格的比例設(shè)置為10%和20%兩種情況，起始柵格設(shè)定為左上角柵格，目標(biāo)柵格設(shè)置為右下角柵格。算法的參數(shù)設(shè)置為：螞蟻規(guī)模為50，信息素因子為1.5，啟發(fā)因子為4.0，信息素?fù)]發(fā)系數(shù)為0.4，算法的最大迭代次數(shù)為100，計(jì)算環(huán)境為Win?dowsl0、i5CPU、內(nèi)存8GB，仿真軟件為Matlab2017。

在障礙物柵格占比為10%和20%兩種情況下，分別使用啟發(fā)信息1蟻群算法和啟發(fā)信息2蟻群算法進(jìn)行10次路徑規(guī)劃，障礙物占比為10%的最優(yōu)路徑，如圖5所示。障礙物占比為20%的最優(yōu)路徑，如圖6 所示。在一些實(shí)驗(yàn)中得到的最優(yōu)路徑是重合的，因此圖中給出的最優(yōu)路徑數(shù)量小于10。

圖5 障礙物占比10%的規(guī)劃結(jié)果Fig.5 Planning Result of 10% Barrier Environment

圖6 障礙物占比20%的規(guī)劃結(jié)果Fig.6 Planning Result of 20% Barrier Environment

對(duì)比圖5和圖6中兩種啟發(fā)信息蟻群算法的規(guī)劃結(jié)果可以看出，10次規(guī)劃得到的路徑中，啟發(fā)信息1蟻群算法規(guī)劃的路徑范圍更加廣泛，這意味著啟發(fā)信息1 蟻群算法的搜索全局性更好；而啟發(fā)信息2蟻群算法規(guī)劃的路徑范圍相對(duì)較小，這意味著啟發(fā)信息2蟻群算法搜索的路徑方向性更好。該實(shí)驗(yàn)現(xiàn)象與3.1節(jié)的設(shè)計(jì)原理完全一致，驗(yàn)證了兩種啟發(fā)信息設(shè)置的合理性。

4.2 與傳統(tǒng)蟻群算法比較

為了進(jìn)一步驗(yàn)證復(fù)合啟發(fā)信息蟻群算法在柵格環(huán)境中路徑規(guī)劃的可行性，設(shè)置（30×30）規(guī)模的柵格工作環(huán)境，分別使用復(fù)合啟發(fā)信息蟻群算法和傳統(tǒng)蟻群算法進(jìn)行10次路徑規(guī)劃，統(tǒng)計(jì)10次最優(yōu)路徑的最短距離、標(biāo)準(zhǔn)差、迭代次數(shù)，如表1所示。復(fù)合啟發(fā)信息蟻群算法和傳統(tǒng)蟻群算法搜索的最短路徑，如圖7所示。

表1 傳統(tǒng)蟻群與復(fù)合啟發(fā)蟻群對(duì)比Tab.1 Comparison of Compound Inspiration Ant Colony and Traditional Ant Colony

圖7 復(fù)合啟發(fā)蟻群與傳統(tǒng)蟻群規(guī)劃結(jié)果Fig.7 Planning Result of Compound Inspiration Ant Colony and Traditional Ant Colony

結(jié)合表1和圖7可以看出，10次規(guī)劃的最優(yōu)路徑中，傳統(tǒng)蟻群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度為68.021，路徑的標(biāo)準(zhǔn)差為4.251，復(fù)合啟發(fā)信息蟻群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度為52.545，路徑標(biāo)準(zhǔn)差為2.211，這說明復(fù)合啟發(fā)信息蟻群算法規(guī)劃的最優(yōu)路徑比傳統(tǒng)蟻群算法規(guī)劃結(jié)果更優(yōu)，且路徑規(guī)劃的穩(wěn)定性更強(qiáng)，這是因?yàn)閺?fù)合啟發(fā)信息蟻群算法中引入了兩種啟發(fā)信息，啟發(fā)信息1搜索的全局性好，而啟發(fā)信息2搜索的方向性好，這樣兼顧了算法的優(yōu)化能力和穩(wěn)定性，因此復(fù)合啟發(fā)信息蟻群算法的規(guī)劃結(jié)果優(yōu)于傳統(tǒng)蟻群算法。

4.3 與其余改進(jìn)蟻群算法比較

為了進(jìn)一步對(duì)比規(guī)劃策略與其余規(guī)劃策略的路徑優(yōu)劣，選擇文獻(xiàn)[11]的改進(jìn)蟻群算法進(jìn)行比較。在（30×30）規(guī)模的柵格環(huán)境中，分別使用復(fù)合啟發(fā)信息蟻群算法和文獻(xiàn)[11]蟻群算法進(jìn)行10次路徑規(guī)劃，得到的最短路徑，如圖8所示。

圖8 復(fù)合啟發(fā)蟻群與文獻(xiàn)蟻群規(guī)劃結(jié)果Fig.8 Planning Result of Compound Inspiration Ant Colony and Ant Colony in Essay

經(jīng)統(tǒng)計(jì)，復(fù)合啟發(fā)蟻群算法規(guī)劃的最短路徑長(zhǎng)度為43.355，規(guī)劃出最優(yōu)路徑的迭代次數(shù)為41；文獻(xiàn)[11]參數(shù)優(yōu)化蟻群算法規(guī)劃的最短路徑長(zhǎng)度為46.113，規(guī)劃出最短路徑的迭代次數(shù)為57。以上數(shù)據(jù)表明，復(fù)合啟發(fā)信息蟻群算法規(guī)劃的路徑更短，且規(guī)劃效率更高。這是因?yàn)槲墨I(xiàn)[11]只是使用粒子群算法對(duì)蟻群算法的參數(shù)進(jìn)行了優(yōu)化，并未從原理上解決多樣性和收斂性之間的矛盾。而這里提出的復(fù)合啟發(fā)信息蟻群算法在算法中引入了兩種啟發(fā)信息，一個(gè)啟發(fā)信息具有更大的搜索范圍，另一個(gè)啟發(fā)信息具有更好的搜索方向性，因此兼顧了算法的多樣性和收斂性，從根本上改善了算法性能。綜合以上分析，本文提出的復(fù)合啟發(fā)信息蟻群算法在柵格環(huán)境路徑規(guī)劃中是有效的，可以得到更短路徑，且規(guī)劃效率較高。

5 結(jié)論

研究了機(jī)器人在柵格環(huán)境下的路徑規(guī)劃方法，提出了兩種啟發(fā)信息，將兩種啟發(fā)信息融入到蟻群算法中，得到了兼顧多樣性和收斂性的蟻群算法。將復(fù)合啟發(fā)信息蟻群算法應(yīng)用于路徑規(guī)劃中，得到以下結(jié)論：

（1）提出的兩種啟發(fā)信息中，啟發(fā)信息1具有較大的搜索范圍，啟發(fā)信息2具有更強(qiáng)的搜索方向性；

（2）復(fù)合啟發(fā)信息蟻群算法規(guī)劃的路徑優(yōu)于傳統(tǒng)蟻群算法，且規(guī)劃效率更高。