季 云，曹 弋

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

0 引言

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

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

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

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

1 標準變色龍算法

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

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

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

(1)

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

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

(2)

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

(3)

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

步驟3：眼睛轉動追蹤。變色龍通過眼睛的旋轉在360°范圍內識別獵物。變色龍會根據獵物的位置通過眼睛的旋轉和移動來更新它們的位置。具體更新表達式為：

(4)

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

(5)

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

(6)

2 改進變色龍算法

2.1 Bernoulli混沌映射初始化

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

(7)

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

圖1 Bernoulli映射直方圖

2.2 鄰域搜索策略

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

(8)

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

2.3 基于經驗的交叉及貪婪選擇策略

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

(9)

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

(10)

2.4 改進變色龍算法流程

本文改進變色龍算法的具體步驟如下：

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

步驟2：利用Bernoulli混沌映射初始化變色龍種群，計算得出群體內各個個體的適應度；

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

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

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

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

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

步驟8：判斷是否達到最大迭代數，如果是，則輸出最佳路徑，否則轉回步驟3。

算法流程圖如圖2所示。

圖2 算法流程圖

3 實例仿真及分析

3.1 參數設置

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

表1 參數取值表

3.2 仿真分析

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

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

表2 指標對比

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

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

4 實物實驗

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

圖6 型機器人圖7 實驗環(huán)境

如圖7所示為實地場景，實驗區(qū)域為矩形劃線部分。圖中右下角為起始位置，左上角為目標點，在環(huán)境中設置若干障礙物，參數設置保持與上節(jié)一致，使用改進的CSA算法進行實驗，實驗結果如圖8和圖9所示。

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

由以上兩圖可以看出，在實際的場地中，改進的CSA算法可以幫助移動機器人快速安全的到達目的地。驗證了本文改進CSA算法的可行性及良好的性能。

5 結束語

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