基于改進(jìn)變色龍算法的移動(dòng)機(jī)器人避障研究*

季 云，曹 弋

(1.常州信息職業(yè)技術(shù)學(xué)院，常州 213164；2.大連交通大學(xué)交通運(yùn)輸工程學(xué)院，大連 116028)

0 引言

移動(dòng)機(jī)器人廣泛應(yīng)用于工農(nóng)業(yè)、醫(yī)藥、軍事等領(lǐng)域，可以輔助或替代人類工作。機(jī)器人還可以提高工作效率，降低成本。目前，機(jī)器人技術(shù)正逐漸普及并應(yīng)用在生活的方方面面。避障是機(jī)器人導(dǎo)航的重要研究課題，是移動(dòng)機(jī)器人的前提和基礎(chǔ)[1-3]。為了保證機(jī)器人可以安全躲避障礙物并更快地抵達(dá)目標(biāo)地點(diǎn)，有必要對(duì)算法進(jìn)行更詳細(xì)的研究。

路徑規(guī)劃算法是避障技術(shù)的核心,許多算法用于解決避障問題，也取得了良好的表現(xiàn)。如WEI等[4]針對(duì)現(xiàn)行的RRT算法在動(dòng)態(tài)非結(jié)構(gòu)環(huán)境下的路徑規(guī)劃中存在一定的局限性，提出了一種以定向節(jié)點(diǎn)為目標(biāo)且融合最大曲率約束優(yōu)化策略的S-RRT路徑規(guī)劃算法。LI等[5]使用改進(jìn)的人工勢場法，使機(jī)器人躲避固定障礙物，以最優(yōu)路徑到達(dá)目標(biāo)，通過改進(jìn)代價(jià)函數(shù)和約束使得算法不會(huì)陷入局部最小值。其他還有蟻群算法[6]、遺傳算法[7]、粒子群算法[8]和螢火蟲算法[9]等，這些算法主要是在定義的問題空間中搜索最優(yōu)解。

變色龍算法(CSA)是一種仿生算法[10]，在數(shù)學(xué)上模擬并實(shí)現(xiàn)了變色龍狩獵的行為步驟，包括搜索食物，眼睛360°旋轉(zhuǎn)追蹤食物及使用自身舌頭定位并抓住獵物的行為。變色龍算法可以很好的運(yùn)用在實(shí)際問題當(dāng)中并取得好的表現(xiàn)。SAID等[11]將CSA用于經(jīng)濟(jì)負(fù)荷調(diào)度問題的優(yōu)化，并與其他算法進(jìn)行了比較，仿真顯示CSA計(jì)算結(jié)果更優(yōu)。RIZK等[12]設(shè)計(jì)了一種改進(jìn)變色龍群算法，從而提取SOFC模型的可靠和精確參數(shù)。

CSA對(duì)各類問題具有很強(qiáng)的計(jì)算能力和適應(yīng)力，因此嘗試將CSA算法引入移動(dòng)機(jī)器人避障領(lǐng)域，幫助機(jī)器人尋得一條可靠的通行路徑，從而實(shí)現(xiàn)高效作業(yè)。同時(shí)針對(duì)在避障過程中CSA出現(xiàn)的尋路效率慢、易陷入局部最優(yōu)的問題，提出一種改進(jìn)的變色龍算法。改進(jìn)標(biāo)準(zhǔn)CSA中的初始化方法，在迭代階段引入記憶機(jī)制，從而提升算法尋優(yōu)性能。

1 標(biāo)準(zhǔn)變色龍算法

變色龍算法(CSA)是最新的元啟發(fā)式算法之一，模仿了變色龍的狩獵行為。狩獵過程主要包括搜尋獵物、視線追蹤獵物和捕獲獵物。該算法的數(shù)學(xué)模型和步驟如下：

步驟1：種群初始化。假設(shè)初始種群共有n條變色龍，其中種群中的每條變色龍都是使用均勻隨機(jī)分布在D維搜索空間中創(chuàng)建的。其具體表達(dá)式為：

zi=Lj+r(Lj-Uj),?i∈n,j∈D

(1)

式中，zi為第i個(gè)變色龍的初始位置向量；Lj和Uj分別為第j維中搜索空間的下界和上界；r為[0，1]范圍內(nèi)的隨機(jī)數(shù)。

步驟2：搜尋獵物。變色龍覓食過程的移動(dòng)行為可以描述為：

(2)

μ=γe(-αt/T)β

(3)

式中，T和t分別為最大迭代數(shù)和當(dāng)前迭代數(shù)；γ、α和β為用于控制探索和開發(fā)能力的常數(shù)值。

步驟3：眼睛轉(zhuǎn)動(dòng)追蹤。變色龍通過眼睛的旋轉(zhuǎn)在360°范圍內(nèi)識(shí)別獵物。變色龍會(huì)根據(jù)獵物的位置通過眼睛的旋轉(zhuǎn)和移動(dòng)來更新它們的位置。具體更新表達(dá)式為：

(4)

步驟4：捕獲獵物。在此階段，變色龍通過攻擊獵物來完成捕獲，當(dāng)它離獵物較近時(shí)，變色龍可以用舌頭捕獲獵物，離獵物最近的變色龍被稱為最優(yōu)解。而捕捉獵物與變色龍吐出舌頭的速度有關(guān)，該速度表達(dá)式為：

(5)

吐舌過程中變色龍的位置更新為：

(6)

2 改進(jìn)變色龍算法

2.1 Bernoulli混沌映射初始化

在標(biāo)準(zhǔn)變色龍算法中，變色龍初始種群為均勻隨機(jī)分布產(chǎn)生。由于混沌過程同時(shí)具備遍歷性、隨機(jī)性、非線性等優(yōu)勢，因此與原始的種群初始化方法相比，混沌映射可以提升群體的豐富性，使得解空間更加的均勻，防止算法過早收斂。Bernoulli混沌映射作為一種混沌映射的代表性方法，有著優(yōu)良的特性，其具體表達(dá)式為：

(7)

式中，k=0,1,2,…,n為空間維數(shù)，其迭代100 000次時(shí)的分布直方圖如圖1所示。

圖1 Bernoulli映射直方圖

2.2 鄰域搜索策略

為了豐富和回溯搜索空間內(nèi)的相鄰區(qū)域，可以在全局最佳變色龍(G)中采用一種新穎的搜索策略，其中從總體中隨機(jī)選擇兩個(gè)解決方案，并使用適應(yīng)度確定潛在搜索方向。其具體原理描述如下：

(8)

式中，zr和zl為從種群中隨機(jī)選擇的兩只變色龍；C為1～0線性減小的比例因子，目的是控制兩變色龍之間的差異。在探索階段C值較大，而開發(fā)階段C值較小。

2.3 基于經(jīng)驗(yàn)的交叉及貪婪選擇策略

基于經(jīng)驗(yàn)的交叉策略主要是通過合并變色龍獲得的獵物信息和鄰域解決方案來保持種群多樣性，該交叉策略表示為：

(9)

式中，CR為采用的交叉概率；rand為(0,1)內(nèi)均勻分布的隨機(jī)數(shù)。在通過式(9)更新后，在兩次連續(xù)迭代中進(jìn)行貪婪選擇策略以確定存活的或最佳變色龍。貪婪選擇策略表達(dá)式為：

(10)

2.4 改進(jìn)變色龍算法流程

本文改進(jìn)變色龍算法的具體步驟如下：

步驟1：初始化運(yùn)行環(huán)境及變色龍算法各項(xiàng)參數(shù)及需要人為設(shè)定的參數(shù)取值；

步驟2：利用Bernoulli混沌映射初始化變色龍種群，計(jì)算得出群體內(nèi)各個(gè)個(gè)體的適應(yīng)度；

步驟3：根據(jù)式(3)、式(6)和式(10)更新參數(shù)μ、慣性權(quán)重及a值；

步驟4：依據(jù)式(2)及式(8)搜索獵物；

步驟5：利用式(4)眼睛旋轉(zhuǎn)特征更新變色龍的位置，根據(jù)式(5)和式(6)進(jìn)行獵物的狩獵；

步驟6：利用變色龍的位置初始化記憶矩陣；

步驟7：通過式(8)執(zhí)行鄰域策略，根據(jù)式(9)和式(10)進(jìn)行個(gè)體的交叉和選擇，并評(píng)估新位置且記錄全局最佳位置；

步驟8：判斷是否達(dá)到最大迭代數(shù)，如果是，則輸出最佳路徑，否則轉(zhuǎn)回步驟3。

算法流程圖如圖2所示。

圖2 算法流程圖

3 實(shí)例仿真及分析

3.1 參數(shù)設(shè)置

由上述小節(jié)可知，變色龍算法中存在許多參數(shù)需要人工設(shè)置，而這些參數(shù)取值一般根據(jù)大量的實(shí)驗(yàn)仿真獲得，選取性能較優(yōu)時(shí)的數(shù)值作為仿真時(shí)的取值。本文參考了文獻(xiàn)[10]中的仿真實(shí)例，確定最終參數(shù)值，主要的算法參數(shù)值及環(huán)境設(shè)置如表1所示。

表1 參數(shù)取值表

3.2 仿真分析

為了驗(yàn)證本文改進(jìn)算法的避障性能，基于MATLAB2018b平臺(tái)搭建二維地圖靜態(tài)環(huán)境，環(huán)境尺寸為100×100，CSA算法改進(jìn)前后的參數(shù)值設(shè)置如上節(jié)，圖中黑色為障礙區(qū)域，白色區(qū)域可無限制通行。分別對(duì)標(biāo)準(zhǔn)變色龍算法、文獻(xiàn)[3]算法、改進(jìn)變色龍算法進(jìn)行仿真實(shí)驗(yàn)。仿真結(jié)果如圖3～圖5所示，各項(xiàng)指標(biāo)對(duì)比如表2所示。

圖3 環(huán)境1仿真圖

表2 指標(biāo)對(duì)比

由圖3～圖4及表2可知，對(duì)比標(biāo)準(zhǔn)CSA算法和文獻(xiàn)[3]算法，本文改進(jìn)的CSA算法規(guī)劃出的路徑距離更短，尋路效率更高。在相對(duì)簡易的環(huán)境1下，具體表現(xiàn)為相比于標(biāo)準(zhǔn)CSA算法和文獻(xiàn)[3]算法，本文算法路徑長度分別減少約5.6%和3.2%，搜索時(shí)間分別縮短約46.8%和18.2%，迭代次數(shù)分別減少約51.7%和12.5%。在更為復(fù)雜的環(huán)境2中，改進(jìn)CSA算法相比于標(biāo)準(zhǔn)CSA算法和文獻(xiàn)[3]算法，其中路徑長度分別減少約8.1%和1.4%，搜索時(shí)間分別縮短約59.3%和33.9%，迭代次數(shù)分別減少約53.2%和29%。在環(huán)境3中，改進(jìn)CSA算法相比于標(biāo)準(zhǔn)CSA算法和文獻(xiàn)[3]算法，路徑長度分別減少約26.2%和13.5%，搜索時(shí)間分別縮短約59.6%和33.3%，迭代次數(shù)分別減少約55.9%和31.2%?？梢钥闯觯疚母倪M(jìn)的CSA算法在各類環(huán)境下有著良好的表現(xiàn)，優(yōu)化效果明顯，在保證安全性的前提下能夠滿足移動(dòng)機(jī)器人的避障需求。

圖4 環(huán)境2仿真圖圖5 環(huán)境3仿真圖

4 實(shí)物實(shí)驗(yàn)

為了驗(yàn)證CSA算法實(shí)際性能，利用REVV-B22型履帶式移動(dòng)機(jī)器人進(jìn)行實(shí)物實(shí)驗(yàn)，如圖6所示。此類機(jī)器人既能夠用于研究路徑規(guī)劃算法實(shí)驗(yàn)，還可用于計(jì)算機(jī)視覺、環(huán)境搭建等課題的研究。實(shí)物實(shí)驗(yàn)平臺(tái)為ROS系統(tǒng)。

圖6 型機(jī)器人圖7 實(shí)驗(yàn)環(huán)境

如圖7所示為實(shí)地場景，實(shí)驗(yàn)區(qū)域?yàn)榫匦蝿澗€部分。圖中右下角為起始位置，左上角為目標(biāo)點(diǎn)，在環(huán)境中設(shè)置若干障礙物，參數(shù)設(shè)置保持與上節(jié)一致，使用改進(jìn)的CSA算法進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖8和圖9所示。

圖8 實(shí)際環(huán)境1路徑圖 圖9 實(shí)際環(huán)境2路徑圖

由以上兩圖可以看出，在實(shí)際的場地中，改進(jìn)的CSA算法可以幫助移動(dòng)機(jī)器人快速安全的到達(dá)目的地。驗(yàn)證了本文改進(jìn)CSA算法的可行性及良好的性能。

5 結(jié)束語

針對(duì)移動(dòng)機(jī)器人的避障問題，本文提出了一種改進(jìn)的變色龍算法。在變色龍種群初始化階段，采用Bernoulli混沌映射使得個(gè)體分布更加均勻，從而豐富了群體的多樣性。同時(shí)，在迭代過程中引入鄰域搜索策略、基于經(jīng)驗(yàn)的交叉策略和貪婪選擇策略。在3種環(huán)境下的仿真結(jié)果表明，本文改進(jìn)的變色龍算法較對(duì)比的其他算法，在路徑長度、搜索時(shí)間、迭代次數(shù)等方面有不同程度上的提升，能夠幫助機(jī)器人在各種不同的環(huán)境下進(jìn)行避障，并且基于實(shí)物實(shí)驗(yàn)驗(yàn)證了改進(jìn)算法的有效性。