徐勁力，柳 佳，司馬立萱

(武漢理工大學(xué)機(jī)電工程學(xué)院，武漢 430070)

0 引言

移動(dòng)機(jī)器人的路徑規(guī)劃技術(shù)是決定其智能與否的關(guān)鍵技術(shù)，其目的是在障礙物已知的環(huán)境中搜索到一條符合預(yù)定要求的路徑[1]。目前路徑規(guī)劃算法種類眾多，然而這些路徑規(guī)劃算法往往只將路程距離作為考量因素，這會(huì)導(dǎo)致機(jī)器人在實(shí)際應(yīng)用中產(chǎn)生一些問(wèn)題。因?yàn)樵谝恍┨囟ǖ沫h(huán)境中，所得到的路徑最優(yōu)結(jié)果可能伴隨著較多的轉(zhuǎn)彎次數(shù)，或者出現(xiàn)頻繁上下坡等情況，機(jī)器人在這樣的道路上行進(jìn)不僅會(huì)耗費(fèi)更多的時(shí)間，還會(huì)對(duì)機(jī)器人的性能和壽命產(chǎn)生影響。所以，未來(lái)機(jī)器人的路徑規(guī)劃應(yīng)該結(jié)合工作環(huán)境和作業(yè)需求，尋找一條綜合性能最優(yōu)的路徑。

蟻群算法具有魯棒性強(qiáng)，容易用計(jì)算機(jī)語(yǔ)言表達(dá)，且能很好地應(yīng)用于路徑規(guī)劃問(wèn)題等優(yōu)點(diǎn)[2]，但同時(shí)存在容易陷入局部最優(yōu)解、迭代次數(shù)過(guò)多、路徑轉(zhuǎn)彎次數(shù)多等問(wèn)題[3]。針對(duì)以上蟻群算法的缺陷，學(xué)者們通過(guò)不斷地研究提出了一系列的方法進(jìn)行改進(jìn)。XIONG等[4]將節(jié)點(diǎn)之間的采樣信息加入蟻群算法的啟發(fā)函數(shù)，并劃分機(jī)器人信息采集區(qū)域，提高算法計(jì)算效率。李二超等[5]將初始信息素按照與起點(diǎn)和終點(diǎn)連線的距離進(jìn)行非均勻分布，加快螞蟻前期搜索速度，同時(shí)引入B樣條曲線，對(duì)螞蟻路徑做平滑處理。馬小陸等[6]通過(guò)結(jié)合跳點(diǎn)搜索法，減少勢(shì)場(chǎng)蟻群算法對(duì)無(wú)用點(diǎn)的評(píng)估，提高了搜索效率，所得的路徑更優(yōu)。姜偉楠等[7]采用改進(jìn)人工勢(shì)場(chǎng)法，縮小地圖搜索范圍，減少蟻群算法迭代次數(shù)。WANG等[8]通過(guò)遺傳算法得到初始路徑，減少蟻群算法前期搜索盲目性，提高算法運(yùn)算速度。任紅格等[9]用目標(biāo)點(diǎn)信息提高蟻群整體搜索效率，同時(shí)引入動(dòng)態(tài)信息素?fù)]發(fā)系數(shù)公式，減少劣質(zhì)解的影響。

前人的研究在一定程度上對(duì)蟻群算法的缺點(diǎn)做了優(yōu)化，但仍無(wú)法同時(shí)滿足機(jī)器人在實(shí)際工作中對(duì)搜索效率與綜合最優(yōu)路徑的需求。為此，本文提出多因素A*蟻群算法。該算法利用改進(jìn)A*算法得到的路徑差異化地圖信息素初始值，避免蟻群算法前期搜索的盲目性；在啟發(fā)式函數(shù)和信息素更新公式中加入轉(zhuǎn)彎次數(shù)、顛簸程度作為考量因素，并優(yōu)化距離因素，增加目標(biāo)點(diǎn)信息，同時(shí)在啟發(fā)信息中引入動(dòng)態(tài)調(diào)節(jié)因子，實(shí)現(xiàn)前期路徑搜索依靠啟發(fā)信息，后期依靠信息素；為防止信息素積累過(guò)快而陷入局部最優(yōu)解，在引入動(dòng)態(tài)調(diào)節(jié)信息素?fù)]發(fā)系數(shù)的同時(shí)，設(shè)置信息素濃度的取值范圍。

1 環(huán)境建模

1.1 環(huán)境地圖

圖1 柵格地圖

柵格法地圖建模是指將機(jī)器人的工作環(huán)境劃分為大小相等的若干個(gè)正方形柵格，由于柵格法比較直觀且易于實(shí)現(xiàn)，故本文地圖使用柵格法進(jìn)行實(shí)現(xiàn)，具體如圖1所示。柵格法地圖由只包含0和1矩陣G定義，矩陣中0代表可行柵格，機(jī)器人可以通行，在地圖中用白色填充，1代表障礙柵格，機(jī)器人無(wú)法通過(guò)，在地圖中用黑色填充。為了讓地圖產(chǎn)生坡度變化，采用與地圖大小相同的峰谷隨機(jī)函數(shù)存儲(chǔ)每一個(gè)柵格的高度，同時(shí)用灰色渲染，顏色越深的柵格的高度更高。表示柵格地圖的矩陣G中的行數(shù)i與列數(shù)j與地圖柵格的中心點(diǎn)坐標(biāo)x、y的對(duì)應(yīng)關(guān)系表達(dá)式：

(1)

式中，R表示柵格地圖的G的行數(shù)。

1.2 規(guī)定行進(jìn)方式

圖2 相鄰柵格標(biāo)號(hào)

為了保證移動(dòng)機(jī)器人行進(jìn)路線的安全性，不會(huì)與柵格地圖中的障礙物發(fā)生碰撞。規(guī)定即使是障礙物的頂點(diǎn)，也不能觸碰，即在柵格地圖中，當(dāng)機(jī)器人想要斜著走時(shí)，與前行路線相交的3個(gè)柵格都是可行柵格時(shí)，機(jī)器人才能行進(jìn)。以圖2為例，如果機(jī)器人在柵格i處，下一步想要前往柵格3處，只有柵格2、3、4均為可行柵格，機(jī)器人才能行進(jìn)。為了實(shí)現(xiàn)該行進(jìn)方式，本文通過(guò)引入一個(gè)900×8的距離矩陣D，用于存儲(chǔ)柵格地圖中900個(gè)柵格到其相鄰8個(gè)柵格的距離，再引入判斷條件如式(2)所示，計(jì)算相鄰柵格間的距離。

(2)

式中，D(i,k)表示矩陣D的第i行第k列的值，同時(shí)也表示柵格i到其相鄰的第k個(gè)柵格的距離，柵格i與相鄰柵格序號(hào)k的關(guān)系如圖2所示；mod為求余函數(shù)，用于區(qū)分直行與斜行；jk表示與柵格i相鄰的第k個(gè)柵格的柵格號(hào)。

2 A*蟻群算法

A*算法在蟻群算法中主要起到差異化地圖初始信息素的作用，在蟻群開(kāi)始搜索前，通過(guò)A*算法找到一條距離最短的路徑，將地圖上這條路徑的初始信息素的濃度提高，這樣既可以提高蟻群算法前期搜索效率，也可以避免螞蟻過(guò)多地走入死路。

2.1 傳統(tǒng)A*算法及其改進(jìn)

A*算法的啟發(fā)函數(shù)同時(shí)包含了起點(diǎn)和終點(diǎn)的信息，能夠在柵格地圖中快速找到一條距離最短的路徑，其啟發(fā)函數(shù)為：

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

(3)

式中，n為當(dāng)前柵格編號(hào)；g(n)為起始柵格到達(dá)當(dāng)前柵格n的已知最短長(zhǎng)度；h(n)為當(dāng)前柵格n達(dá)到目標(biāo)柵格的距離，一般采用歐氏距離表示。

傳統(tǒng)A*算法中，會(huì)將每個(gè)當(dāng)前柵格的可行未遍歷相鄰柵格加入待遍歷柵格集合中，然后按照待遍歷柵格的啟發(fā)函數(shù)的值從小到大逐個(gè)遍歷這些柵格，產(chǎn)生了大量無(wú)效遍歷。因此，本文通過(guò)引入一個(gè)評(píng)價(jià)函數(shù)對(duì)當(dāng)前柵格的相鄰柵格進(jìn)行判斷，減少無(wú)用柵格加入待遍歷集合，提高算法計(jì)算速度。評(píng)價(jià)函數(shù)如式(4)所示。

H(n)=h(n)-h(n-1)+μ

(4)

式中，h(n)為相鄰柵格到目標(biāo)柵格的歐式距離；h(n-1)為當(dāng)前柵格到目標(biāo)柵格的歐式距離；μ為評(píng)價(jià)函數(shù)調(diào)節(jié)系數(shù)，根據(jù)地圖環(huán)境取值。

如果當(dāng)前柵格的相鄰柵格中有障礙柵格時(shí)，為了防止陷入局部陷阱而無(wú)法找到目標(biāo)點(diǎn)，仍然將每個(gè)當(dāng)前柵格的可行未遍歷相柵格點(diǎn)加入待遍歷柵格集合中；如果當(dāng)前柵格的相鄰柵格中沒(méi)有障礙柵格，且其評(píng)價(jià)函數(shù)大于0，則將該柵格加入待遍歷柵格集合，否則，不加入。

圖3 傳統(tǒng)A*算法

為了證明本文算法的優(yōu)越性，建立柵格地圖，將傳統(tǒng)A*算法、文獻(xiàn)[10]算法與本文算法做對(duì)照仿真實(shí)驗(yàn)，通過(guò)反復(fù)實(shí)驗(yàn)結(jié)果分析，取評(píng)價(jià)函數(shù)調(diào)節(jié)系數(shù)μ=0.3。仿真實(shí)驗(yàn)結(jié)果對(duì)比如圖3～圖5所示。障礙物和邊界用黑色柵格表示，已遍歷柵格用灰色渲染，起始點(diǎn)為藍(lán)色柵格，目標(biāo)點(diǎn)為綠色柵格。對(duì)每種算法已遍歷柵格的數(shù)目、最終路徑長(zhǎng)度進(jìn)行比較，仿真實(shí)驗(yàn)數(shù)據(jù)如表1所示。

圖4 文獻(xiàn)[10]算法 圖5 本文改進(jìn)A*算法

表1 仿真結(jié)果分析

實(shí)驗(yàn)數(shù)據(jù)表明，在所獲得的最短路徑相同的基礎(chǔ)上，本文改進(jìn)算法對(duì)比文獻(xiàn)[10]算法已遍歷柵格數(shù)減少18.05%，對(duì)比傳統(tǒng)A*算法已遍歷柵格數(shù)減少33.82%，極大地提升了A*算法的搜索效率。

2.2 基本蟻群算法

2.2.1 概率選擇

蟻群算法的轉(zhuǎn)移概率公式用于指導(dǎo)螞蟻從當(dāng)前柵格選擇下一步柵格，螞蟻的狀態(tài)轉(zhuǎn)移概率公式如式(5)所示。

(5)

式中，allowedi表示螞蟻在柵格i時(shí)的可行相鄰柵格的集合；τ表示信息素濃度；η表示啟發(fā)信息；α表示信息素濃度影響因子；β表示啟發(fā)信息影響因子；其中，啟發(fā)信息函數(shù)的表達(dá)式如式(6)所示。

(6)

式中，dij為當(dāng)前節(jié)點(diǎn)i到下一節(jié)點(diǎn)j的歐氏距離。

2.2.2 信息素更新

信息素是模擬自然界螞蟻在尋找食物時(shí)留在路途中用于指導(dǎo)其他螞蟻前進(jìn)方向的某種化學(xué)物質(zhì)[11]。在蟻群算法中，每次迭代中所有螞蟻完成尋路后會(huì)對(duì)地圖的信息素進(jìn)行一次更新，更新公式如式(7)和式(8)所示。

(7)

(8)

2.3 改進(jìn)蟻群算法

2.3.1 初始信息素改進(jìn)

傳統(tǒng)蟻群算法將地圖所有可行柵格的初始信息素設(shè)為一個(gè)常數(shù)C，螞蟻在迭代初期主要依靠啟發(fā)函數(shù)，不僅搜索盲目，還容易陷入地圖死點(diǎn)。為了解決這個(gè)問(wèn)題，在建立柵格地圖后，通過(guò)改進(jìn)A*算法得到的起始點(diǎn)到目標(biāo)點(diǎn)之間的路徑，并將此路徑上所有柵格的集合記為R，重新設(shè)置地圖柵格的初始信息素如式(9)所示。

(9)

式中，n為正數(shù)。

2.3.2 啟發(fā)函數(shù)改進(jìn)

傳統(tǒng)蟻群算法的啟發(fā)函數(shù)僅將當(dāng)前節(jié)點(diǎn)i與相鄰節(jié)點(diǎn)j的歐式距離dij作為決定因素，搜索盲目且求解單一?？紤]到移動(dòng)機(jī)器人工作環(huán)境的復(fù)雜性和自身移動(dòng)結(jié)構(gòu)的局限性，應(yīng)綜合考慮路徑的距離、轉(zhuǎn)彎次數(shù)和顛簸程度等因素。同時(shí)，為了解決傳統(tǒng)蟻群算法迭代次數(shù)過(guò)多，容易陷入局部最優(yōu)解的問(wèn)題，加入動(dòng)態(tài)調(diào)節(jié)因子，在迭代前期，讓啟發(fā)函數(shù)發(fā)揮主導(dǎo)作用，對(duì)蟻群前期搜索給予方向指引。在迭代后期，讓信息素發(fā)揮主導(dǎo)作用，避免算法得到局部最優(yōu)解。優(yōu)化后的啟發(fā)函數(shù)如式(10)所示。

(10)

在路徑的距離因素中，增加相鄰節(jié)點(diǎn)j與目標(biāo)點(diǎn)q的歐式距離diq作為考量因素，能更好地引導(dǎo)螞蟻向目標(biāo)點(diǎn)進(jìn)發(fā)。由于各可行相鄰柵格的dij、djq差別較小，為了體現(xiàn)距離差別，引入距離因素啟發(fā)函數(shù)如式(11)所示。

(11)

式中，D為所求相鄰柵格的dij、djq之和；Dmax、Dmin分別為當(dāng)前柵格的所有相鄰可行柵格的dij、djq之和的最大值和最小值；a、b為距離調(diào)整系數(shù)，由地圖環(huán)境決定，0.01用于避免Dmax=Dmin的情況導(dǎo)致無(wú)法計(jì)算。

在路徑的轉(zhuǎn)彎因素中，通過(guò)圖2所示的相鄰柵格標(biāo)號(hào)，用矩陣dir存儲(chǔ)每次螞蟻前進(jìn)的方向，為了得到轉(zhuǎn)彎次數(shù)較少的規(guī)劃路徑，引入轉(zhuǎn)彎因素啟發(fā)函數(shù)如式(12)所示。

(12)

在路徑的坡度因素中，采用peaks函數(shù)存儲(chǔ)地圖的坡度，并采用與路徑的距離因素類似的方式體現(xiàn)各可行柵格的坡度差別，引入坡度因素啟發(fā)函數(shù)如下：

(13)

式中，H為柵格i的坡度與柵格j的坡度之差的絕對(duì)值；Hmax、Hmin分別為當(dāng)前柵格i與其所有相鄰可行柵格的坡度差絕對(duì)值的最大值和最小值；c、d為坡度修正系數(shù)，根據(jù)地圖環(huán)境取值。

2.3.3 信息素更新方式的改進(jìn)

(14)

Sk(t)=x2Lk(t)+y2TK(t)+z2Fk(t)

(15)

式中，Sk(t)為第t次迭代中第k只螞蟻所尋路徑的綜合性能函數(shù)；Tk(t)為第t次迭代中第k只螞蟻所尋路徑的轉(zhuǎn)彎次數(shù)；Fk(t)第t次迭代中第k只螞蟻所尋路徑的坡度均方差；x2、y2、z2分別為各因素的影響系數(shù)。

(16)

式中，ρ(t+1)為第t+1次迭代時(shí)的揮發(fā)系數(shù)；ρ(t)第t次迭代時(shí)的揮發(fā)系數(shù)，揮發(fā)系數(shù)會(huì)隨著迭代次數(shù)的增大而減小，直到取到設(shè)定的最小揮發(fā)系數(shù)ρmin為止。

(17)

式中，τmin、τmax分別為地圖設(shè)定信息素濃度的下極限值與上極限值。

3 仿真分析

本文改進(jìn)算法流程如圖6所示。

圖6 改進(jìn)算法流程圖

為了驗(yàn)證本文算法的正確性，建立柵格地圖并將傳統(tǒng)蟻群算法、文獻(xiàn)[12]以及本文的改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比分析。由于蟻群算法通過(guò)輪盤賭選擇行進(jìn)方向，每次得到的實(shí)驗(yàn)結(jié)果會(huì)有所差別，故在同一地圖環(huán)境中對(duì)每個(gè)算法進(jìn)行相同次數(shù)的實(shí)驗(yàn)，取其綜合指標(biāo)出現(xiàn)頻率最高的結(jié)果來(lái)進(jìn)行比較分析。

本文的公共參數(shù)初始值經(jīng)大量實(shí)驗(yàn)分析后設(shè)置如表2所示。

表2 公共參數(shù)表

建立較復(fù)雜的30×30的柵格地圖，將本文改進(jìn)蟻群算法、文獻(xiàn)[12]算法和傳統(tǒng)蟻群算法進(jìn)行對(duì)比試驗(yàn)，仿真結(jié)果如表3和圖7所示。

表3 實(shí)驗(yàn)數(shù)據(jù)表

(a) 路徑規(guī)劃圖

(b) 路徑轉(zhuǎn)彎次數(shù)迭代圖 (c)路徑長(zhǎng)度迭代圖

(d) 路徑坡度均方差迭代圖 (e)路徑綜合指標(biāo)迭代圖

由表3可知，在路徑長(zhǎng)度上，雖然三種算法的差距不大，但本文算法所得到的結(jié)果還是優(yōu)于其他兩種算法。在路徑的轉(zhuǎn)彎次數(shù)和坡度均方差上，由于引入了路徑轉(zhuǎn)彎因素和路徑坡度因素，本文算法和文獻(xiàn)[12]算法均明顯優(yōu)于傳統(tǒng)蟻群算法，說(shuō)明本文算法和文獻(xiàn)[12]算法對(duì)于多因素路徑規(guī)劃的可行性。對(duì)比本文算法和文獻(xiàn)[12]算法指標(biāo)，由于融合改進(jìn)A*算法，優(yōu)化啟發(fā)函數(shù)和信息素更新公式，本文算法均優(yōu)于文獻(xiàn)[12]算法，不僅在路徑長(zhǎng)度、坡度均方差、路徑轉(zhuǎn)彎次數(shù)、綜合指標(biāo)上分別優(yōu)化了2.5%、9.5%、6.7%、5.0%，在迭代次數(shù)上更是減少了57.9%。雖然本文算法程序運(yùn)行時(shí)間略高于文獻(xiàn)算法和傳統(tǒng)蟻群算法，但迭代穩(wěn)定估計(jì)時(shí)間卻優(yōu)于它們?？傮w來(lái)看，本文算法在30×30柵格地圖中各方面表現(xiàn)均比較優(yōu)異，對(duì)于考慮多因素機(jī)器人路徑規(guī)劃的問(wèn)題有明顯的優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

本文針對(duì)移動(dòng)機(jī)器人實(shí)際工作環(huán)境需求，提出一種多因素A*算法蟻群算法。通過(guò)改進(jìn)A*算法使得初始信息素不平等分配，降低蟻群算法前期搜索的盲目性，減少迭代次數(shù)；在蟻群算法中加入了路程長(zhǎng)度、轉(zhuǎn)彎次數(shù)和顛簸程度三種因素的影響，彌補(bǔ)了傳統(tǒng)蟻群算法以距離作為唯一因素的不足；在啟發(fā)函數(shù)和揮發(fā)系數(shù)中引入動(dòng)態(tài)調(diào)整因子，讓蟻群前期擴(kuò)大搜索范圍，后期快速向最優(yōu)解收斂。

通過(guò)柵格法搭建地圖環(huán)境的仿真實(shí)驗(yàn)表明，在同一柵格地圖環(huán)境下，本文算法的最終路徑長(zhǎng)度、顛簸程度、轉(zhuǎn)彎次數(shù)、迭代穩(wěn)定次數(shù)均要優(yōu)于傳統(tǒng)算法和文獻(xiàn)[12]算法，所以本文算法尋路的效率更高。在今后的研究過(guò)程中，可以結(jié)合機(jī)器人的實(shí)際工作環(huán)境，對(duì)本文算法中的啟發(fā)函數(shù)和綜合指標(biāo)中各因素系數(shù)的進(jìn)行更合適的分配。