基于改進(jìn)蟻群算法的月面機(jī)器人的路徑規(guī)劃及虛擬仿真*

劉 暢，王逸璇，王婧馨，張富照，張雪芹，曹 濤

(1.華東理工大學(xué) 信息科學(xué)與工程學(xué)院·上?！?00237；2.華東理工大學(xué) 機(jī)械與動力工程學(xué)院·上海 ·200237；3.上海空間智能控制技術(shù)重點實驗室·上?！?01109；4.上海航天控制技術(shù)研究所·上?！?201109)

0 引 言

月面機(jī)器人在月面環(huán)境探索、數(shù)據(jù)信息采集等過程中起著重要作用。為了能夠在月球表面自主行走，需要對月面機(jī)器人的行走路徑進(jìn)行規(guī)劃。同時，由于月面機(jī)器人所帶的能量有限，因此有必要為機(jī)器人規(guī)劃出最短的行走路徑。目前，研究最短路徑規(guī)劃的算法有很多，比如A*算法、模擬退火算法、遺傳算法、粒子群算法等。Li等提出了利用粒子群算法優(yōu)化蟻群算法參數(shù)，合理確定蟻群算法所需要的迭代次數(shù)，減小算法的計算規(guī)模。但是，該算法的執(zhí)行周期過長，增加了大量的時間成本。Hu等提出了采用頭尾雙向搜索策略提高算法的前期效率、引入退火思想以提高跳出局部最優(yōu)解的概率，減少了算法的能耗，但該算法的收斂速度仍然不夠理想。Wang Zhizhong提出了基于頭尾雙向搜索的A*啟發(fā)函數(shù)。但由于相遇即停止的策略，雖然算法的收斂速度獲得了加速，但其全局搜索能力也同時出現(xiàn)了下降。Wang提出了自適應(yīng)啟發(fā)函數(shù)，并采用螞蟻與目的地之間的歐幾里德距離避免了路徑搜索的初始盲目性和后期單一性，使得搜索速度及最佳路徑成功率獲得了提升，并降低了螞蟻在同一位置落入死鎖的概率，但改進(jìn)后的算法的收斂速度不佳。Han提出了基于確定周邊點集(SPS)算法的初始路徑生成方式，在幾何形狀狹小且復(fù)雜度高的地圖中能夠高效生成無沖突路徑，但該算法的收斂速度較慢，最佳路徑成功率偏低。Tong等提出了利用人工勢場法對傳統(tǒng)蟻群算法進(jìn)行改進(jìn)。算法的收斂速度較優(yōu)，但所規(guī)劃的路徑較長。

根據(jù)月面機(jī)器人對路徑規(guī)劃的需求，考慮到蟻群算法具備較強(qiáng)的魯棒性和搜索能力，并且易于并行實現(xiàn)，本文提出了在蟻群算法與人工勢場法融合的基礎(chǔ)上，利用空間信息素劃分方法，提高尋找最短路徑的成功率和算法的收斂速度。

1 機(jī)器人路徑規(guī)劃問題建模

機(jī)器人路徑規(guī)劃任務(wù)是依據(jù)所感知到的障礙物的環(huán)境信息，按照某種優(yōu)化指標(biāo)，規(guī)劃出一條從給定起點到目標(biāo)位置的、無碰撞的最優(yōu)或次最優(yōu)路徑。移動機(jī)器人規(guī)劃路徑主要可分為三種類型：基于事例學(xué)習(xí)的路徑規(guī)劃、基于行為的路徑規(guī)劃和基于環(huán)境模型的路徑規(guī)劃。本文研究的月面機(jī)器人路徑規(guī)劃問題屬于基于環(huán)境模型的路徑規(guī)劃，采用了二維柵格法進(jìn)行環(huán)境建模，采用了蟻群算法進(jìn)行路徑規(guī)劃建模。

1.1 環(huán)境建模

環(huán)境模型是對環(huán)境進(jìn)行分析時所設(shè)定的模型。環(huán)境建模包括柵格圖、切線圖、Voronoi圖、概率圖和可視圖等。柵格法是對地圖進(jìn)行建模的一種常用方法，簡單有效，對不規(guī)則障礙物的適應(yīng)能力強(qiáng)，易于被擴(kuò)展到三維環(huán)境。將地圖進(jìn)行柵格化可以較為清晰地顯示出月面地圖的環(huán)境信息，選擇大小合適的柵格既可以保證環(huán)境信息的清晰度，又可以提高路徑規(guī)劃的速度。

在柵格化地圖中，障礙物處的柵格以涂黑表示，無障礙物處則為空白，如圖 1所示。在算法中，分別用二進(jìn)制“0”和 “1”表示柵格化地圖。

圖1 柵格法月面示意圖Fig.1 Schematic diagram of the lunar surface of the grid method

圖 1利用“0”和“1”所構(gòu)成的矩陣建立了20×20二維柵格圖。網(wǎng)格用整數(shù)標(biāo)記，并且與坐標(biāo)系的單位長度相同。障礙物的坐標(biāo)點可用常見的

XOY

正交坐標(biāo)系來確定。圖1中，柵格序號值

k

從起點處開始依次向右標(biāo)記為1～400，對應(yīng)的某柵格的坐標(biāo)可利用如下公式得到

(1)

式中，mod為取余運算，int為取整運算，

m

為每一行的柵格數(shù)，

m

、

k

均為整數(shù)。通過以上方法，可以將二維規(guī)劃空間離散化。采用柵格法構(gòu)建環(huán)境空間，采用兩點式坐標(biāo)進(jìn)行柵格標(biāo)識，即可以實現(xiàn)月面環(huán)境建模。

1.2 機(jī)器人路徑規(guī)劃建模

路徑規(guī)劃的目的在于規(guī)劃出從起始位置到目標(biāo)位置的最優(yōu)路徑。機(jī)器人的路徑規(guī)劃算法包括了遺傳算法、A*算法、人工勢場法和蟻群算法等多種算法。其中，蟻群算法具有啟發(fā)式搜索、并行計算、信息正反饋和魯棒性強(qiáng)等特點，適合被應(yīng)用于月面機(jī)器人路徑規(guī)劃問題。本文將基于改進(jìn)的蟻群算法實現(xiàn)對月面機(jī)器人的路徑規(guī)劃。

1.2.1 蟻群算法的特點

蟻群算法模擬了自然界中螞蟻覓食的行為規(guī)律。螞蟻會在走過的路徑上留下可被感知的信息素，其他單個螞蟻在覓食時會選擇信息素濃度更大的路徑。因此，某一路徑上的信息素會以此為積累而越來越大，下一只螞蟻選擇此路徑覓食的概率則進(jìn)一步增加。蟻群算法在路徑規(guī)劃領(lǐng)域有較為廣泛的應(yīng)用，蟻群算法具有以下特點：

(1)螞蟻可以通過釋放信息素來改變周圍的環(huán)境，且每個個體能夠感知周圍環(huán)境的實時變化，個體間可通過環(huán)境進(jìn)行間接的通信；

(2)采用正反饋機(jī)制，使得搜索過程不斷收斂，最終逼近最優(yōu)解；

(3)搜索過程采用分布式計算方式，多個個體可同時進(jìn)行并行計算，大大提高了算法的計算能力和運行效率；

(4)和其他算法相比，啟發(fā)式的概率搜索方式不容易陷入局部最優(yōu)，易于尋找到全局最優(yōu)解。

1.2.2 蟻群算法的數(shù)學(xué)模型

設(shè)在每個時間

t

，根據(jù)信息素濃度與啟發(fā)式函數(shù)，螞蟻

k

由當(dāng)前節(jié)點

i

確定轉(zhuǎn)移到下一節(jié)點

j

的轉(zhuǎn)移概率為

P

(

t

)=

(2)

式中，

P

(

t

)表示

t

時刻螞蟻

k

從節(jié)點

i

移動到下一個節(jié)點

j

的轉(zhuǎn)移概率；

τ

(

t

)為

t

時刻

j

點殘留的信息素；

η

(

t

)為節(jié)點

i

到節(jié)點

j

的啟發(fā)函數(shù)；

s

表示螞蟻能夠選擇的節(jié)點；

j

∈allowed表示螞蟻

k

沒有抵達(dá)過的點；

α

和

β

分別為信息素因子和啟發(fā)函數(shù)因子。其中，啟發(fā)函數(shù)

η

(

t

)的定義為

(3)

d

為節(jié)點

i

到節(jié)點

j

的歐氏距離

(4)

螞蟻

k

循環(huán)一次后，信息素的更新方式可表示為

(5)

(6)

式中，

Q

為常量，

L

表示由螞蟻

k

搜索到的路徑長度。上式表明，螞蟻留下的信息素濃度與其搜索到的路徑長度有關(guān)。螞蟻搜索的路徑越短，留下的信息素濃度越高。可見，在蟻群算法中，啟發(fā)函數(shù)和信息素是兩個主要的優(yōu)化參數(shù)。

2 月面機(jī)器人路徑規(guī)劃優(yōu)化算法設(shè)計

月面機(jī)器人攜帶的能量有限，需要在最短的時間內(nèi)，規(guī)劃出起始點到目標(biāo)點的最短路徑。為了進(jìn)一步提高路徑規(guī)劃的效率，加快蟻群算法的收斂速度以及提升最短路徑全局尋優(yōu)的成功率，本文利用人工勢場法，并結(jié)合了空間信息素劃分改進(jìn)經(jīng)典蟻群算法，提高了算法的收斂速度以及最短路徑規(guī)劃的成功率。

2.1 基于人工勢場法改進(jìn)啟發(fā)函數(shù)

人工勢場法是由Khatib提出的一種虛擬力法，它的基本思想是將機(jī)器人在周圍環(huán)境中的運動設(shè)計為一種抽象的人造引力場中的運動。由目標(biāo)點對移動機(jī)器人產(chǎn)生“引力”，由障礙物對移動機(jī)器人產(chǎn)生“斥力”，最后通過求取合力來控制移動機(jī)器人的運動。利用人工勢場法改進(jìn)啟發(fā)函數(shù)，能夠有效避免蟻群算法陷入局部最優(yōu)，并避免由前期盲目搜索而導(dǎo)致的收斂速度過慢。

(1)引力函數(shù)

人工勢場法中的引力函數(shù)

G

(

t

)可定義為月面機(jī)器人與固定目標(biāo)點之間的相對距離

(7)

其中，(

x

,

y

)為機(jī)器人當(dāng)前的坐標(biāo)，(

x

,

y

)是目標(biāo)點的坐標(biāo)。月面機(jī)器人的當(dāng)前節(jié)點與目標(biāo)節(jié)點的距離越近，引力越大。

(2)斥力函數(shù)

人工勢場法中的斥力函數(shù)

R

(

t

)受移動機(jī)器人與障礙物的距離影響，可定義為月面機(jī)器人與障礙物之間的函數(shù)

(8)

其中，(

x

,

y

)是月面機(jī)器人下一步要移動到的坐標(biāo)?！?”表示該節(jié)點是障礙物，狀態(tài)轉(zhuǎn)移函數(shù)式(2)則變?yōu)?，這表示月面機(jī)器人不會移動到此點，即不會與障礙物發(fā)生碰撞。“1”表示該節(jié)點不是障礙物，不影響狀態(tài)轉(zhuǎn)移函數(shù)。

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

基于人工勢場法改進(jìn)的蟻群算法啟發(fā)函數(shù)可定義為

η

(

t

)=

G

(

t

)

R

(

t

)

(9)

改進(jìn)后的啟發(fā)函數(shù)可定義為引力函數(shù)

G

(

t

)與斥力函數(shù)

R

(

t

)的乘積。與原啟發(fā)函數(shù)式(3)相比，引力函數(shù)

G

(

t

)只需考慮月面機(jī)器人當(dāng)前節(jié)點與目標(biāo)節(jié)點的相對距離，而無需考慮下一節(jié)點的位置。引力函數(shù)可以引導(dǎo)機(jī)器人選擇下一節(jié)點，使其逐漸逼近目標(biāo)點，因此可加快蟻群算法的收斂速度；斥力函數(shù)使得月面機(jī)器人在越接近障礙物時越受到強(qiáng)烈的排斥，進(jìn)而促使機(jī)器人自動規(guī)避靜態(tài)障礙物。

2.2 基于空間劃分改進(jìn)信息素更新算法

由于蟻群算法是模擬螞蟻覓食行為的群體智能算法，螞蟻在尋找食物的過程中會在覓食的路徑上留下信息素，之后的蟻群可以根據(jù)信息素堆積的濃度找到蟻穴與食物之間的最短路徑。因此，信息素的更新方式對蟻群算法的性能有著至關(guān)重要的影響。

為了進(jìn)一步加快蟻群算法的收斂速度、提高最短路徑的成功率，本文提出了基于空間劃分調(diào)整信息素更新的方法。當(dāng)確定好尋跡的起點和終點后，讓起點位于柵格地圖左上角的頂點，讓終點位于柵格地圖右下角的頂點，得出相應(yīng)的柵格地圖，并劃分對角區(qū)域為重要區(qū)域，如圖2所示。設(shè)定重要區(qū)域的信息素含量較高，設(shè)定非重要區(qū)域的信息素含量較少。前者可加大蟻群在此區(qū)域中的搜索概率，提高收斂速度，防止陷入局部最優(yōu)。后者可使蟻群在這部分區(qū)域的搜索概率降低，減少了搜索的盲目性。該方法可促使蟻群更傾向于在重要區(qū)域內(nèi)完成搜索。

圖2 空間信息素劃分區(qū)域示意圖Fig.2 Spatial pheromone zoning map

為獲取如圖2所示的空間范圍，算法利用如圖3所示的信息素分布矩陣，為矩陣對角區(qū)域賦予了信息素初值，使得地圖對角區(qū)域內(nèi)的信息素具備一定的初始濃度。在蟻群進(jìn)行路徑搜索時，重要區(qū)域與非重要區(qū)域的信息素分布可通過調(diào)節(jié)信息素的蒸發(fā)速率

ρ

來實現(xiàn)

圖3 信息素劃分矩陣Fig.3 Information element partitioning matrix

(10)

當(dāng)節(jié)點

i

位于如圖2中紅色區(qū)域所示的重要區(qū)域(即對角區(qū)域內(nèi))時，根據(jù)公式(10)計算而得的

ρ

值較小，這意味著信息素的蒸發(fā)速率小，信息素的含量較高。此時，應(yīng)加大螞蟻在此區(qū)域的搜索概率，防止陷入局部最優(yōu)；當(dāng)節(jié)點位于非重要區(qū)域時，

ρ

的取值較大，信息素的蒸發(fā)速率較大，信息素的含量較低，則應(yīng)減小螞蟻在此區(qū)域的搜索概率，以降低搜索的盲目性。

2.3 基于人工勢場和空間信息素劃分的蟻群算法流程

基于人工勢場和空間信息素劃分的蟻群算法的流程圖如圖4所示。

圖4 算法流程圖Fig.4 Algorithm flow chart

算法步驟如下：

第一步：導(dǎo)入月面地圖信息，給定起點與終點坐標(biāo)，初始化柵格地圖；初始化信息啟發(fā)因子

α

、期望啟發(fā)因子

β

、信息素蒸發(fā)速率

ρ

、螞蟻數(shù)量

m

以及最大迭代次數(shù)

N

。通過信息素矩陣對角區(qū)域賦予信息素濃度初值，并用于劃分區(qū)域。第二步：在起點釋放

m

只螞蟻，根據(jù)式(7)、式(8)、式(9)確定啟發(fā)函數(shù)

η

(

t

)，再根據(jù)式(2)尋找螞蟻可行的下一個節(jié)點

j

，并將此節(jié)點加入到禁忌表中。循環(huán)此過程，直至達(dá)到最大的螞蟻數(shù)量。第三步：保存路徑信息，依據(jù)式(5)和式(6)，進(jìn)行信息素的更新。判斷當(dāng)前的迭代次數(shù)是否達(dá)到了所設(shè)定的最大迭代次數(shù)

N

。如果達(dá)到了設(shè)定值，則結(jié)束算法，并輸出此最短路徑信息。

通過利用人工勢場法改進(jìn)啟發(fā)函數(shù)，以及結(jié)合空間信息素劃分方法，可以有效防止蟻群陷入局部最優(yōu)，加快蟻群算法的收斂速度，提高最短路徑尋優(yōu)的成功率。

3 月面機(jī)器人路徑規(guī)劃虛擬仿真設(shè)計

3.1 月面機(jī)器人和月面環(huán)境建模

為實現(xiàn)月球車在虛擬月面環(huán)境上的自主尋路的仿真過程，提升仿真系統(tǒng)的沉浸感和真實感，同時直觀展示月球車根據(jù)改進(jìn)蟻群算法實現(xiàn)的尋路過程，可采用Solidworks、Unity3D、3Dsmax等軟件對月球車和月面環(huán)境進(jìn)行三維建模和渲染。

模擬的玉兔號月球車模型主要由車體、懸架、車輪、太陽翼、定向天線和相機(jī)六部分組成，采用Solidworks進(jìn)行了建模。月球車的模型貼圖、材質(zhì)指定、渲染烘焙等工藝采用3Dsmax軟件完成。在Unity提供的地形編輯器中創(chuàng)建月面地形，模擬真實情況，為月面地形添加適合的材質(zhì)和紋理，結(jié)果如圖5所示。

圖5 玉兔號月球車及月面地形建模Fig.5 Lunar rover and lunar terrain modeling

3.2 Unity與蟻群算法的交互

蟻群算法的開發(fā)基于Python，Unity3D不具備直接與Python進(jìn)行數(shù)據(jù)傳遞的能力。本文提供了一種依賴于XML的讀寫策略，從而可使Unity引擎從外部算法獲取輸出結(jié)果。

在Unity中創(chuàng)建一個負(fù)責(zé)信息交互的腳本，在Using中引入System.Xml、System.IO兩個命名空間，使腳本具有對XML文檔進(jìn)行讀寫操作的功能。在腳本中使用CreateXmlFile函數(shù)，創(chuàng)建與腳本關(guān)聯(lián)的XML文檔，并通過xml.CreateElement和element.SetAttribute函數(shù)創(chuàng)建用于存放點位數(shù)組的節(jié)點，并設(shè)置節(jié)點的屬性。

在用戶選好路徑規(guī)劃的起始與結(jié)束點后，Unity引擎需要將障礙物與路徑規(guī)劃始末點位信息寫入XML文檔中，從而調(diào)用蟻群算法。在腳本中，使用element.AppendChild及element.InnerText函數(shù)將數(shù)組分別寫入不同的節(jié)點，并通過root.AppendChild(element)函數(shù)將節(jié)點一層層添加到XML中，運用xml.Save(path)指定XML文件路徑并實現(xiàn)文檔的保存。

在蟻群算法給出路徑規(guī)劃的結(jié)果并將路徑信息寫入XML文檔中后，腳本中的xml.SelectSingNode(節(jié)點名稱).ChildNodes與foreach函數(shù)將遍歷所有子節(jié)點，并使用textList.Add函數(shù)將讀取到的數(shù)組點存入到指定的數(shù)組中，供執(zhí)行尋路的腳本調(diào)用。

圖6 基于XML讀寫策略的信息交互Fig.6 Information interaction based on XML read-write strategy

3.3 月面機(jī)器人執(zhí)行尋路過程

在Unity中使物體對象按指定路徑移動的方法有多種，主要可分為Rigidbody類、Transform類和WheelCollider類函數(shù)中的方法。在月球車自主尋路場景中，需要確保尋路過程貼近真實情況。月球車軌跡貼合算法給出的規(guī)劃路徑，可控制多次仿真過程中出現(xiàn)的位置、方向變換差異。為保證尋路路徑的準(zhǔn)確性、尋路過程的仿真性和降低過程的隨機(jī)性，此處采用結(jié)合Transform空間變換類和WheelColider輪胎碰撞器類的函數(shù)執(zhí)行尋路的方法。

在月球車位置變換過程中，采用Vector3.MoveTowards(thisPosiyion,targetPosion,Speed)對月球車進(jìn)行移動操作，通過函數(shù)Vector3.Distance 判斷移動的距離。在轉(zhuǎn)彎過程中，調(diào)用四元數(shù)函數(shù)Quaternion.LookRotation得到月球車應(yīng)當(dāng)旋轉(zhuǎn)的參數(shù)rotate，最后調(diào)用四元數(shù)插值函數(shù)Quaternion.Slerp(transform.localRotation,rotate,angleSpeed)，實現(xiàn)月球車方向的平滑調(diào)轉(zhuǎn)。

在此過程中，WheelColider輪胎碰撞器的作用表現(xiàn)為綁定月球車實體模型，在月球車轉(zhuǎn)彎過程中提供前輪轉(zhuǎn)向條件、懸架系統(tǒng)仿真和對輪胎摩擦碰撞情況仿真的功能上，與Transform類函數(shù)、物理引擎互不干涉。通過在腳本中定義輪胎碰撞器變量 WheelColider與車輪模型變量WheelMesh，為變量指定在場景中的輪胎碰撞器與車輪模型對象，使用WheelColider.GetWorldPose(out,out)函數(shù)為WheelMesh.transform參數(shù)進(jìn)行賦值，從而使車輪模型的位置和角度始終跟隨輪胎碰撞器，以實現(xiàn)尋路過程的移動仿真。

該種方法中的Transform類函數(shù)可確保月球車位置和方向的正確性，WheelColider類函數(shù)可確保物理效果的真實度。該方法使得尋路過程的仿真程度較高，月球車的運動狀態(tài)在符合動力學(xué)原理的同時，能很好地確保月球車行進(jìn)路線和規(guī)劃路線之間的吻合程度。

3.4 月面機(jī)器人路徑規(guī)劃虛擬仿真實現(xiàn)流程

在基于Unity搭建的虛擬場景中，當(dāng)引擎對月面地形及月球車模型的渲染烘焙完畢時，用戶開始選擇路線規(guī)劃的起始點與終點；當(dāng)選擇完畢時，Unity將三維地形模型經(jīng)過二維柵格化并加以篩選后的障礙物點位以及用戶選擇出的始末點位以二維數(shù)組的形式傳遞給蟻群算法；蟻群算法在接收到帶有障礙物和規(guī)劃信息的數(shù)組后，返回規(guī)劃出的路線點位；在獲取了蟻群算法給出的路線后，虛擬場景將渲染出規(guī)劃路線的可視化軌跡。月球車將按照蟻群算法給出的路線行進(jìn)，直至抵達(dá)用戶指定的終點，具體流程如圖8所示。

圖8 仿真及虛擬展示實現(xiàn)流程Fig.8 Simulation and virtual display implementation process

為了真實再現(xiàn)月球車在月面行進(jìn)的情況，采用Unity內(nèi)置的NVIDIA的Physx物理引擎，賦予月球車一定的物理特性和運動特性，展示如剛體碰撞、輪胎碰撞、車輛駕駛、重力影響等效果的仿真。

4 仿真驗證與結(jié)果分析

4.1 實驗一：參數(shù)優(yōu)化

本實驗用于尋找信息啟發(fā)因子

α

、期望啟發(fā)因子

β

、信息素蒸發(fā)速率

ρ

的最優(yōu)組合值，使得算法的成功率最高，收斂速度最快。信息啟發(fā)因子

α

、期望啟發(fā)因子

β

、信息素蒸發(fā)速率

ρ

均對算法的收斂速度和成功率有一定的影響。

α

過大，會增大路徑上的信息素影響權(quán)值，導(dǎo)致螞蟻容易陷入局部最優(yōu)；

α

過小，路徑上的信息素對螞蟻的影響降低，導(dǎo)致螞蟻行走的隨機(jī)性提高，算法的收斂速度減慢。相較于

α

，

β

的波動對最短路徑的影響較小。

β

過大，螞蟻在某個局部點上選擇局部最短路徑的可能性越大，但螞蟻搜索最優(yōu)路徑的隨機(jī)性減弱，易陷入局部最優(yōu)；

β

過小，將導(dǎo)致螞蟻群體陷入純粹的隨機(jī)搜索。在這種情況下，很難找到最優(yōu)解。

ρ

過大，會導(dǎo)致螞蟻在搜索最短路徑時陷入局部最優(yōu)，無法找到全局最優(yōu)解；

ρ

過小，則不能較快地找到最優(yōu)路徑，收斂速度也會較慢。在尋找較優(yōu)的參數(shù)組合之前，通過多次反復(fù)實驗大致確定各參數(shù)最優(yōu)值所在的范圍，在各個參數(shù)范圍內(nèi)采用控制變量法試湊而得到接近最優(yōu)值的參數(shù)組合。實驗地圖如圖5所示，網(wǎng)格坐標(biāo)用整數(shù)標(biāo)記且與坐標(biāo)單位長度相同。將螞蟻行走起點設(shè)為(0,0)，終點設(shè)為(19,19)。螞蟻數(shù)量為20只，迭代次數(shù)為50次。初始

α

=1、

β

=13、

ρ

=0

.

8，采用控制變量法，分別在一定范圍內(nèi)改變參數(shù)的大小，實驗結(jié)果如表1、表2和表3所示。

圖9 參數(shù)尋優(yōu)測試地圖Fig.9 Parameter optimization test map

表1 固定參數(shù)β、ρ，改變參數(shù)α下的最短路徑成功率和平均收斂次數(shù)Tab.1 Shortest path success rate and average convergence times β、ρ,changing parameter α with fixed parameters

表2 固定參數(shù)α、ρ，改變參數(shù)β下的最短路徑成功率和平均收斂次數(shù)Tab.2 Shortest path success rate and average convergence times α、ρ,changing parameter β with fixed parameters

表3 固定參數(shù)α、β，改變參數(shù)ρ下的最短路徑成功率和平均收斂次數(shù)Tab.3 Shortest path success rate and average convergence times α、β,changing parameter ρ with fixed parameters

從表1、表2和表3可以看出，當(dāng)

α

=1

.

3、

β

=15、

ρ

=0

.

5時，算法的性能達(dá)到了最佳。

為進(jìn)一步驗證算法的收斂速度，給出算法收斂次數(shù)曲線如圖10所示。從圖10可以看到，傳統(tǒng)蟻群算法由于前期的震蕩而收斂速度較慢，在迭代了42次之后才出現(xiàn)了收斂，而本文改進(jìn)的蟻群算法的收斂速度明顯加快，在迭代4次時就已經(jīng)出現(xiàn)了收斂，大大提高了收斂速度。

圖10 算法收斂曲線對比Fig.10 Comparison of convergence curves

4.2 實驗二：比較實驗

為驗證本文算法的性能，需模擬五種不同障礙物環(huán)境進(jìn)行實驗，分別為僅起點出現(xiàn)障礙物、僅終點出現(xiàn)障礙物、起點與終點均存在障礙物、對角線中間區(qū)域出現(xiàn)簡單障礙物和復(fù)雜障礙物環(huán)境，如圖7所示。將本文所提到的蟻群算法和文獻(xiàn)[13]所提到的基于人工勢場的蟻群算法、遺傳算法、A*算法進(jìn)行了比較，驗證了最短路徑的規(guī)劃能力。在柵格圖中，設(shè)路徑規(guī)劃起點為(0,0)，終點為(19,19)，螞蟻數(shù)量為20只，迭代次數(shù)為100次，實驗結(jié)果如圖11和表4所示。

圖7 執(zhí)行尋路方法的流程圖Fig.7 Flowchart of the execution pathfinding method

(a)僅起點處存在障礙物

表4 五種不同環(huán)境下的最短路徑Tab.4 Shortest paths in five different environments

實驗結(jié)果顯示，A*算法在于不同障礙物環(huán)境下進(jìn)行最短路徑尋優(yōu)時，在圖11(d)與圖11(e)環(huán)境下發(fā)生了尋路錯誤；遺傳算法在進(jìn)行最短路徑尋優(yōu)時，沒有出現(xiàn)尋路錯誤，但其所規(guī)劃的路徑長度不是最短路徑。蟻群算法具備較優(yōu)的路徑尋優(yōu)能力，而本文提出的結(jié)合空間信息素劃分的改進(jìn)蟻群算法能夠規(guī)劃出最短的路徑長度。

圖12給出了一組對照示例。圖12(a)為本文算法在地形(c)下的路徑規(guī)劃，圖12(b)是遺傳算法在地形(c)下的路徑規(guī)劃。由圖12可以看到，本文所提算法能夠使規(guī)劃路徑較好地保持在對角區(qū)域內(nèi)，使得路徑最短。

4.3 實驗三：展示實驗

為還原玉兔號月球車實現(xiàn)路徑規(guī)劃的過程，直觀展示本文算法性能，在Unity3D搭建的尋路場景及在后端蟻群算法的支持下，可模擬玉兔號在月球上的智能導(dǎo)航、自動尋徑過程。在場景中，用戶可選擇玉兔號尋路的目標(biāo)點，系統(tǒng)內(nèi)的蟻群算法將給出最短規(guī)劃路線，玉兔號將沿規(guī)劃路線行駛至目的地。

(a)本文算法在對角區(qū)域內(nèi)可規(guī)劃最優(yōu)路徑

圖13展示了用戶通過界面選擇目標(biāo)點后，系統(tǒng)調(diào)用后端蟻群算法給出規(guī)劃路徑的場景。

圖13 目標(biāo)點選擇及路徑規(guī)劃場景Fig.13 Target point selection and path planning scenarios

圖14展示了玉兔號月球車的尋路場景。為方便用戶觀察尋路過程，實驗場景增添了微縮二維柵格地圖，用以指示玉兔號的實時位置和行進(jìn)方向。

圖14 玉兔號月球車的尋路場景Fig.14 The Yutu lunar rover's pathfinding process

5 結(jié) 論

本文提出了采用蟻群算法制定月面機(jī)器人在月面環(huán)境下的路徑規(guī)劃。同時，為了提高蟻群算法路徑規(guī)劃的成功率和收斂速度，將蟻群算法與人工勢場方法進(jìn)行了結(jié)合，并提出了基于空間信息素劃分的方法。通過提高蟻群在最短路徑區(qū)域附近進(jìn)行搜索的可能性，提高了最短路徑規(guī)劃的成功率。實驗證明，蟻群算法尋找最短路徑的成功率獲得了顯著提高，算法的迭代次數(shù)減少，實現(xiàn)了預(yù)定目標(biāo)。通過建模以及采用Unity3D等技術(shù)，蟻群算法在三維虛擬場景中展示了月面機(jī)器人的路徑規(guī)劃過程。