郭凡,何柳,侯媛彬,秦學(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ī)器人在行走過程中的路徑長度和時間。
本文研制的移動機(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è)計示意
柵格圖是目前在路徑規(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ī)器人可以隨意改變行走速度,加速、減速、勻速或者停止等。
人工魚群算法(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)重要的作用。在移動過程中,視野值若不變,易引起算法收斂速度變慢,計算量變大。
針對上述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ù)。
為了驗(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ù)對比
本文通過建立移動機(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ī)劃上效果明顯。