多因素A*蟻群算法的機器人路徑規(guī)劃*

徐勁力，柳 佳，司馬立萱

(武漢理工大學機電工程學院，武漢 430070)

0 引言

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

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

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

1 環(huán)境建模

1.1 環(huán)境地圖

圖1 柵格地圖

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

(1)

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

1.2 規(guī)定行進方式

圖2 相鄰柵格標號

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

(2)

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

2 A*蟻群算法

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

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

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

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

(3)

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

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

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

(4)

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

如果當前柵格的相鄰柵格中有障礙柵格時，為了防止陷入局部陷阱而無法找到目標點，仍然將每個當前柵格的可行未遍歷相柵格點加入待遍歷柵格集合中；如果當前柵格的相鄰柵格中沒有障礙柵格，且其評價函數(shù)大于0，則將該柵格加入待遍歷柵格集合，否則，不加入。

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

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

圖4 文獻[10]算法 圖5 本文改進A*算法

表1 仿真結果分析

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

2.2 基本蟻群算法

2.2.1 概率選擇

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

(5)

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

(6)

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

2.2.2 信息素更新

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

(7)

(8)

2.3 改進蟻群算法

2.3.1 初始信息素改進

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

(9)

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

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

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

(10)

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

(11)

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

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

(12)

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

(13)

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

2.3.3 信息素更新方式的改進

(14)

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

(15)

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

(16)

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

(17)

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

3 仿真分析

本文改進算法流程如圖6所示。

圖6 改進算法流程圖

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

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

表2 公共參數(shù)表

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

表3 實驗數(shù)據(jù)表

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

(b) 路徑轉彎次數(shù)迭代圖 (c)路徑長度迭代圖

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

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

4 結束語

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

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