改進(jìn)人工魚群的移動機(jī)器人避障尋優(yōu)算法

郭凡，何柳，侯媛彬，秦學(xué)斌，盧志強(qiáng)，王冕

西安科技大學(xué) 電氣與控制工程學(xué)院，陜西 西安 710054

近幾年來，隨著計算機(jī)、信息處理與智能控制的迅猛發(fā)展，人們對于機(jī)器人的研究也在逐漸加深，機(jī)器人的功能也在慢慢完善，而本文所研究的移動機(jī)器人也是其中的一種[1]?，F(xiàn)在移動機(jī)器人的研究已進(jìn)入較為成熟的階段，可以先前確定的任務(wù)地點(diǎn)為目標(biāo)，提前對行走的地圖做出規(guī)劃，在移動的過程中根據(jù)周圍復(fù)雜環(huán)境障礙物的情況，進(jìn)行最短距離的判斷，完美地避開障礙物。移動機(jī)器人按照運(yùn)行環(huán)境，可分為海、陸、空3類[2?3]。本文主要解決如何使移動機(jī)器人在行走過程中可獲取最短路徑的問題，即移動機(jī)器人行進(jìn)的路徑規(guī)劃問題。對此，國內(nèi)外眾多專家學(xué)者已進(jìn)行探究并提出對應(yīng)的解決辦法。文獻(xiàn)[4]針對無人機(jī)的航路規(guī)劃問題，提出利用多個處理器來同時執(zhí)行算法優(yōu)化過程的思想，并通過仿真來對粒子群和遺傳算法進(jìn)行對應(yīng)方案的驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，算法的執(zhí)行效率明顯提升。文獻(xiàn)[5]提出將改進(jìn)的人工蜂群算法應(yīng)用至機(jī)器人的路徑規(guī)劃中，并通過仿真結(jié)果將其與差分進(jìn)化算法相比較，從而驗(yàn)證該改進(jìn)蜂群算法的實(shí)用性。文獻(xiàn)[6]提出將傳統(tǒng)的ANN與蟻群算法相結(jié)合的優(yōu)化算法運(yùn)用到路徑規(guī)劃中，并進(jìn)行相應(yīng)的仿真實(shí)驗(yàn)，驗(yàn)證該優(yōu)化算法在規(guī)劃速度和更優(yōu)路徑上的優(yōu)越性。文獻(xiàn)[7]以蟻群算法為基礎(chǔ)，引進(jìn)人工勢場的作用，兩種算法之間優(yōu)劣互補(bǔ)，在復(fù)雜的行走環(huán)境中共同作用以提升尋優(yōu)能力。國際很多專家對人工魚群算法進(jìn)行了改進(jìn)，應(yīng)用在不同的領(lǐng)域，文獻(xiàn)[8]將支持向量機(jī)與人工魚群算法結(jié)合，來解決孿生支持向量機(jī)的參數(shù)選擇問題；文獻(xiàn)[9]針對深度神經(jīng)網(wǎng)絡(luò)AI研究的可解釋性瓶頸，給出了有價值的解釋；文獻(xiàn)[10?12]利用改進(jìn)的人工魚群算法進(jìn)行圖像量化、WSN覆蓋優(yōu)化策略、資源調(diào)度算法；文獻(xiàn)[13?16]研究改進(jìn)的人工魚群算法在時滯系統(tǒng)辨識和非線性優(yōu)化問題中的應(yīng)用，也有專家利用混合聚類或海洋流的流動功率對人工魚群算法進(jìn)行改進(jìn)。

國外的專家對移動機(jī)器人的控制、組隊(duì)進(jìn)行了大量研究，美國專家研究攔截流氓機(jī)器人，捕獲具有多個追蹤器的多個逃逸者的算法[17]；韓國的專家們研究多障礙下移動機(jī)器人避障、路徑規(guī)劃及不穩(wěn)定網(wǎng)絡(luò)下機(jī)器人的跟蹤質(zhì)量問題[18?20]；印度專家對多機(jī)器人系統(tǒng)進(jìn)行建模、實(shí)行分散控制[21?23]；德國、法國和加拿大等的專家研究多機(jī)器人系統(tǒng)的運(yùn)動沖突、測量與優(yōu)化控制問題[24?27]。通過分析國內(nèi)外的研究現(xiàn)狀，可以發(fā)現(xiàn)現(xiàn)有的算法研究仍存在一些可優(yōu)化項(xiàng)，例如：移動機(jī)器人的真實(shí)環(huán)境較為復(fù)雜，存在不定時的障礙物，這就要求機(jī)器人具備實(shí)時避免碰撞的能力。因此，利用更加即時的算法來實(shí)現(xiàn)該場景優(yōu)化具有很強(qiáng)的實(shí)際應(yīng)用意義。

本文針對復(fù)雜環(huán)境下尋找最短路徑問題，提出基于視野自適應(yīng)的改進(jìn)人工魚群(artificial fishswarm algorithm based on adaptive vision,AVAFSA)的機(jī)器人路徑規(guī)劃算法，分別引入衰減函數(shù)和自適應(yīng)算子來改善視覺效果，增強(qiáng)步長的自適應(yīng)能力，從而避免因視野太小而陷入局部最小的情況，由此來縮減機(jī)器人在行走過程中的路徑長度和時間。

1 系統(tǒng)描述

1.1 結(jié)構(gòu)設(shè)計

本文研制的移動機(jī)器人設(shè)計主要由主控制器Arduino單片機(jī)、超聲波測距模塊、電機(jī)驅(qū)動模塊、攝像頭、RS232接口、光電感應(yīng)以及電源等模塊組成。其系統(tǒng)總體框架如圖1所示。其中超聲波測距和光電感應(yīng)模塊主要完成行走環(huán)境的信息獲取，包括障礙物的距離和路線檢測；Arduino可根據(jù)超聲波測距和光電感應(yīng)模塊的輸送信息來進(jìn)行判斷，從而驅(qū)動電機(jī)來合理地移動機(jī)器人。攝像機(jī)主要將機(jī)器人周邊的環(huán)境信息通過RS232接口傳送至上位機(jī)，由PC機(jī)來完成對路徑的優(yōu)化選擇。圖2給出了自制的移動機(jī)器人底部設(shè)計示意圖。圖2中，底部的前面中間的超聲波傳感器用作小車避障，其他4個紅外傳感器(紅外對管)用作尋跡，左右車輪分別由2個12 V直流電機(jī)分別驅(qū)動，兩輪之間裝有型號為ST151的碼盤測速器，萬向輪配合左右車輪運(yùn)動。

圖1 自動搬運(yùn)機(jī)器人系統(tǒng)框圖

圖2 自制的移動機(jī)器人底部設(shè)計示意

1.2 移動機(jī)器人的環(huán)境模型

柵格圖是目前在路徑規(guī)劃中應(yīng)用較為廣泛的一種表達(dá)方法，因此本文通過柵格法來建立移動機(jī)器人的運(yùn)行模型。柵格法把移動機(jī)器人的操作環(huán)境投射為柵格二維空間，其中黑色區(qū)域?yàn)檎系K物所在地，白色為機(jī)器人可行區(qū)域[8]。分析移動機(jī)器人的運(yùn)動環(huán)境，特作以下假設(shè)。

1)運(yùn)行環(huán)境處于二維空間內(nèi)，在一個靜態(tài)平面范圍中。

2)在運(yùn)行空間內(nèi)，靜態(tài)障礙物所處的初始位置、當(dāng)前位置、目標(biāo)位置與大小均知曉。

3)把移動機(jī)器人可看作質(zhì)點(diǎn)。

4)移動機(jī)器人可以隨意變化方向[9]，其變化方向如圖3所示。

圖3 移動機(jī)器人移動方向

5)移動機(jī)器人可以隨意改變行走速度，加速、減速、勻速或者停止等。

2 AVAFSA路徑優(yōu)化算法

2.1 AFSA的基本思想及步驟

人工魚群算法(artificial fish-swarm algorithm,AFSA)是由李曉磊博士在2002年提出的一種群體智能優(yōu)化算法。其基本思想是仿照魚群在一片水域當(dāng)中尋找最優(yōu)解的覓食、聚群和追尾等行為，水域中的每一條魚都對應(yīng)其中的一個優(yōu)化解，該水域即為被優(yōu)化問題的解空間。通過分析人工魚群的優(yōu)化理念，可得其人工魚環(huán)境模型如圖4所示。假設(shè)水域中一條魚現(xiàn)時狀態(tài)是X，其可見范圍為Visual(公式中用Zvisual表示)，在某一時間點(diǎn)對應(yīng)的視點(diǎn)位置為Xk，如果該方位較此時狀態(tài)更優(yōu)，則可往該地點(diǎn)處向前一步，即抵達(dá)Xnext；若該方位無此時狀態(tài)更優(yōu)，則一直在可見視線內(nèi)找尋其他較優(yōu)地點(diǎn)。

圖4 人工魚環(huán)境模型

AFSA在路徑規(guī)劃中的具體步驟如下。

1)初始化設(shè)置。對魚群中的各個參數(shù)進(jìn)行初始設(shè)置，包括：該人工魚群的群體規(guī)模、視野、最大迭代次數(shù)、每一條魚的最大移動步長Step(公式中用Lstep)等參數(shù)。

2)此時迭代的次數(shù)是0，由N條魚組成初始魚群，每個魚表示從初始位置到目標(biāo)位置的一條路徑。

3)對每一條人工魚都進(jìn)行行為模擬：覓食、追尾、聚群與隨機(jī)移動行為，選取其中最優(yōu)的一種行為來操作。4種行為算法的數(shù)學(xué)表達(dá)如下。

覓食行為

聚群行為

追尾行為

任意移動行為

式中Rand()為隨機(jī)函數(shù)，產(chǎn)生0到1之間的隨機(jī)數(shù)。

4)人工魚在每次行為之后，選取自身狀態(tài)和公告牌狀態(tài)較優(yōu)的一種進(jìn)行實(shí)時更新。

5)判斷是否已到最大迭代次數(shù)，若已到達(dá)，則輸出，否則，轉(zhuǎn)第3)繼續(xù)運(yùn)行。

根據(jù)以上對于AFSA基本理論和操作步驟的描述中可看出，視野起到了至關(guān)重要的作用。在移動過程中，視野值若不變，易引起算法收斂速度變慢，計算量變大。

2.2 AVAFSA機(jī)器人路徑規(guī)劃算法

針對上述AFSA在路徑規(guī)劃中所存在的問題，本文提出基于視野自適應(yīng)的改進(jìn)人工魚群算法的機(jī)器人路徑規(guī)劃算法。

人工魚的4種行為中，覓食行為是決定算法是否收斂的關(guān)鍵，因此，僅對覓食行為采用自適應(yīng)改進(jìn)，其他的追尾、聚群以及隨機(jī)移動行為對應(yīng)的視野保持不變。在覓食行為執(zhí)行初期，給予其較大的視野，隨著過程迭代的進(jìn)行慢慢減小。

但是，若行為執(zhí)行到后期時，視野太小，易陷入局部最優(yōu)。所以，設(shè)定在視野的當(dāng)前值縮減至初始值的一半時，數(shù)值保持不變，停止減小。因此，現(xiàn)將覓食行為的數(shù)學(xué)表達(dá)式改寫成式(5)數(shù)學(xué)模型，即目標(biāo)函數(shù)。

式中：k為迭代數(shù)；α為衰減因子，a∈(0,1)；β∈(0,1)為視野的下限因子；Vo代表視野初始值，即為優(yōu)化后覓食行為中的。

AVAFSA機(jī)器人路徑規(guī)劃算法實(shí)現(xiàn)步驟為

1)初始化設(shè)置。結(jié)合柵格圖大小，設(shè)置每格的邊長、障礙物的個數(shù)、機(jī)器人起點(diǎn)S坐標(biāo)和終點(diǎn)T坐標(biāo)位置；為對魚群中的各個參數(shù)進(jìn)行初始設(shè)置，包括：該人工魚群的群體規(guī)模、視野、最大迭代次數(shù)和擁擠度因子等參數(shù)，設(shè)每一條魚的最大移動步長Lstep=1、視野的下限因子β=0.5。

2)迭代的次數(shù)從0開始，由N條魚組成初始魚群，每個魚表示從初始位置到目標(biāo)位置的一條路徑。

3)對每一個人工魚都進(jìn)行行為模擬。包括覓食、追尾、聚群與隨機(jī)移動行為(此處覓食行為的視野是改進(jìn)后的，采用目標(biāo)函數(shù)公式(5)迭代)；在柵格圖上機(jī)器人的當(dāng)前位置，選取當(dāng)中最優(yōu)的一種行為來操作。

4)人工魚在每次行為之后，選取自身狀態(tài)和公告牌狀態(tài)較優(yōu)的一種進(jìn)行實(shí)時更新。

5)判斷運(yùn)行次數(shù)是否等于初始設(shè)置的最大迭代次數(shù)，若是，則繼續(xù)；否則，轉(zhuǎn)到步驟3)繼續(xù)。

6)判斷機(jī)器人是否到達(dá)柵格圖的終點(diǎn)T坐標(biāo)位置，若是，則結(jié)束；否則，轉(zhuǎn)到步驟3)繼續(xù)。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證本文所提改進(jìn)的人工魚群算法與傳統(tǒng)人工魚群在移動機(jī)器人路徑規(guī)劃上的優(yōu)越性，在此選擇相同的運(yùn)行環(huán)境作對比仿真實(shí)驗(yàn)。結(jié)合柵格法[28]，利用MATLAB進(jìn)行仿真驗(yàn)證，柵格圖大小設(shè)為120 cm×120 cm，其每格的邊長為4 cm，序號初始化值是0，在X、Y方向?qū)Ω鱾€柵格按照順序進(jìn)行編號，把障礙物所在的柵格位置標(biāo)記成黑色，其他區(qū)域?yàn)榘咨?，貨物存放?7個，起點(diǎn)S坐標(biāo)為 (2,2)，終點(diǎn)T坐標(biāo)為 (118,118)，最大迭代次數(shù)均設(shè)定為100。2種算法在該相同環(huán)境下各自優(yōu)化的最優(yōu)路線與收斂曲線分別如圖5和圖6所示。相關(guān)數(shù)據(jù)總結(jié)見表1。圖7為自制的移動小車在實(shí)際運(yùn)行的狀態(tài)，圖7(a)為避障選道，圖7(b)為右轉(zhuǎn)彎運(yùn)行。

圖7 自制的移動小車在實(shí)際運(yùn)行的狀態(tài)

表1中，Lf為最優(yōu)路徑長度，Kmin為訓(xùn)練次數(shù)。由仿真圖、實(shí)驗(yàn)及表中數(shù)據(jù)可得，2種算法在移動機(jī)器人路徑規(guī)劃的應(yīng)用中，本文所改進(jìn)的人工魚群算法最優(yōu)路徑長度與迭代次數(shù)上均優(yōu)于傳統(tǒng)的人工魚群算法。由圖4可得，AVAFSA優(yōu)化下的最優(yōu)路徑長度明顯較AFSA短，為186 cm；從圖5可看出，在路徑尋優(yōu)的整個過程中，AVAFSA最終找到最優(yōu)路徑所需迭代的次數(shù)為35次，比AFSA少了15次；此外，當(dāng)2種算法的最大迭代次數(shù)均設(shè)置為100時，AVAFSA會最先達(dá)到次數(shù)上限，迭代用時較短，僅為10.15 s，比AVAFSA縮短了2.18 s?？傊疚乃岢龅幕谝曇白赃m應(yīng)的改進(jìn)人工魚群優(yōu)化算法較傳統(tǒng)的人工魚群算法在移動機(jī)器人的路徑規(guī)劃應(yīng)用上存在明顯的優(yōu)勢。

圖52 種算法的最優(yōu)路徑搜索

圖62 種算法的收斂曲線

表1 2種算法最優(yōu)路徑相關(guān)參數(shù)對比

4 結(jié)論

本文通過建立移動機(jī)器人的環(huán)境模型，分析傳統(tǒng)人工魚群在路徑優(yōu)化方面存在的問題，提出基于視野自適應(yīng)的改進(jìn)人工魚群優(yōu)化算法，結(jié)合柵格圖法的優(yōu)點(diǎn)，形成了AVAFSA機(jī)器人避障和優(yōu)化算法。該算法利用魚群視野自適應(yīng)的形式來對可見視線值的下限進(jìn)行設(shè)定，引入衰減函數(shù)來改善視覺效果，引入自適應(yīng)算子來增強(qiáng)步長的自適應(yīng)能力，從而避免因視野太小而導(dǎo)致易陷入局部最小。計算機(jī)仿真和通過自制的小車實(shí)驗(yàn)結(jié)果表明，如果在環(huán)境中有未知障礙物，本文的AVAFSA機(jī)器人路徑規(guī)劃算法也能實(shí)時避障，重新優(yōu)化運(yùn)行的路徑。在同樣環(huán)境條件下，AVAFSA機(jī)器人避障和優(yōu)化算法相比于傳統(tǒng)的人工魚群算法獲取最優(yōu)路徑的迭代次數(shù)減少了，路徑長度縮短了8.82%，收斂速度提高了17.68%。由此可見，視野自適應(yīng)的人工魚群優(yōu)化算法在移動機(jī)器人的避障和路徑規(guī)劃上效果明顯。