基于改進(jìn)瞪羚優(yōu)化算法的機(jī)器人路徑規(guī)劃

鄧 毅,廖秋麗

(1.桂林師范高等專科學(xué)校物理與工程技術(shù)系,廣西 桂林 541199)(2.桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院,廣西 桂林 541004)

移動(dòng)機(jī)器人是涵蓋了環(huán)境數(shù)據(jù)采集、動(dòng)作執(zhí)行、規(guī)劃作業(yè)等多性能的綜合性移動(dòng)硬件平臺(tái)[1-5],其可以實(shí)現(xiàn)自主行駛、定位導(dǎo)航、環(huán)境感知及人機(jī)交互等各類行為。移動(dòng)機(jī)器人已經(jīng)廣泛應(yīng)用于車(chē)站、機(jī)場(chǎng)和郵局等場(chǎng)所,并迅速在日常生活中占據(jù)重要地位。機(jī)器人在復(fù)雜或不確定的實(shí)際環(huán)境中導(dǎo)航時(shí),必須規(guī)劃出合適的移動(dòng)路徑。路徑規(guī)劃即在指定的環(huán)境中尋得一條無(wú)碰撞的路徑,其在過(guò)去的幾十年里得到了快速發(fā)展。

近年來(lái),研究人員提出了各種不同的路徑規(guī)劃方法并在機(jī)器人或自動(dòng)導(dǎo)引車(chē)(automated guided vehicle,AGV)上加以應(yīng)用。經(jīng)典的路徑規(guī)劃算法包括遺傳算法(genetic algorithm,GA)[6]、蟻群優(yōu)化算法(ant colony optimization,ACO)[7]、快速探索隨機(jī)樹(shù)算法(rapidly-exploring radom tree,RRT)[8]、A*算法[9]、人工勢(shì)場(chǎng)法[10]、強(qiáng)化學(xué)習(xí)[11]等。當(dāng)前移動(dòng)機(jī)器人工作環(huán)境愈發(fā)復(fù)雜,許多經(jīng)典算法已無(wú)法滿足機(jī)器人規(guī)劃需求。因此,需要尋得一種高效、安全的路徑規(guī)劃算法,幫助機(jī)器人完成規(guī)劃作業(yè)。

瞪羚優(yōu)化算法(gazelle optimization algorithm,GOA)是一種新穎、簡(jiǎn)單、搜索能力強(qiáng)的全局隨機(jī)優(yōu)化算法,于2022年被提出。研究表明,GOA相比其他先進(jìn)的啟發(fā)式算法在優(yōu)化問(wèn)題上有更好表現(xiàn)[12]。因此,本文嘗試將GOA應(yīng)用于機(jī)器人路徑規(guī)劃領(lǐng)域,提出一種改進(jìn)的瞪羚優(yōu)化算法(improved gazelle optimization algorithm,IGOA)。對(duì)其存在的易早收斂、規(guī)劃效率低等問(wèn)題,利用正交學(xué)習(xí)及Rosenbrock直接旋轉(zhuǎn)兩種策略進(jìn)行改進(jìn),從而提升算法綜合性能,幫助機(jī)器人高效完成規(guī)劃任務(wù)。

1 瞪羚優(yōu)化算法

對(duì)于獵豹和獅子等掠食者來(lái)說(shuō),瞪羚的奔跑速度非常快。大多數(shù)掠食者能否成功取決于它們是否能隱蔽地跟蹤瞪羚;如果不能出其不意,瞪羚大多會(huì)以高速跑過(guò)捕食者。GOA就是以瞪羚逃避捕食者的行為為核心思想來(lái)進(jìn)行探索和開(kāi)發(fā),具體模型如下:

1)初始化。

GOA是一種基于種群的優(yōu)化算法,它使用隨機(jī)初始化的瞪羚作為搜索個(gè)體。搜索個(gè)體為候選解的n×d矩陣,表達(dá)式如下:

(1)

式中:X為候選種群的位置向量矩陣;xi,j為第i個(gè)種群在第j維隨機(jī)生成的向量位置,i=1,2,…,n,j=1,2,…,d,其中n為瞪羚數(shù)量,d為維數(shù)。xi,j表達(dá)式如下:

xi,j=rand×(UBj-LBj)+LBj

(2)

式中:rand為隨機(jī)數(shù),UBj和LBj分別為種群的上界和下界。在每次迭代中,每個(gè)個(gè)體xi,j產(chǎn)生一個(gè)候選解。將目前得到的最優(yōu)解命名為頂端瞪羚,構(gòu)造一個(gè)精英矩陣E。該矩陣用于為瞪羚進(jìn)行下一步搜索,其表達(dá)式如下:

(3)

2)開(kāi)發(fā)階段。

這個(gè)階段假設(shè)瞪羚在沒(méi)有捕食者或者當(dāng)捕食者跟蹤瞪羚時(shí)只是安靜地吃草。在這一階段,利用布朗運(yùn)動(dòng)進(jìn)行開(kāi)發(fā)。假設(shè)瞪羚在吃草時(shí)以布朗運(yùn)動(dòng)進(jìn)行活動(dòng),具體模型表示如下:

gi+1=gi+s·R·RB·(Ei-RB·gi)

(4)

式中:gi+1為下一次迭代的解,gi為當(dāng)前迭代的解,s為瞪羚的掠食速度,RB為布朗運(yùn)動(dòng)的隨機(jī)數(shù)向量,R為[0,1]內(nèi)的均勻隨機(jī)數(shù)向量,Ei為精英矩陣。

3)探索階段。

一旦瞪羚個(gè)體發(fā)現(xiàn)捕食者,探索階段就開(kāi)始了。此階段采用了Levy飛行,整個(gè)過(guò)程包括小步前進(jìn)和偶爾的跳躍。假設(shè)每次迭代都發(fā)生方向突變;當(dāng)?shù)螖?shù)為奇數(shù)時(shí),瞪羚向一個(gè)方向移動(dòng),當(dāng)?shù)螖?shù)為偶數(shù)時(shí),瞪羚向另一個(gè)方向移動(dòng)。瞪羚首先做出反應(yīng),捕食者的反應(yīng)較慢,所以假設(shè)它的跑動(dòng)過(guò)程是按照布朗運(yùn)動(dòng)進(jìn)行,然后再換成Levy飛行。當(dāng)?shù)闪绨l(fā)現(xiàn)捕食者后,其行為的數(shù)學(xué)模型如下:

gi+1=gi+S·μ·R·RL·(Ei-RL·gi)

(5)

式中:μ為常數(shù),S為瞪羚能達(dá)到的最高速度,RL為基于Levy分布的隨機(jī)數(shù)向量。捕食者追逐瞪羚的行為的數(shù)學(xué)模型如下:

(6)

式中:iter為當(dāng)前迭代次數(shù),max_iter為最大迭代次數(shù)。

設(shè)PSRs代表捕食者成功率,可利用PSRs防止GOA陷入局部最小值。位置更新具體模型如下:

(7)

(8)

式中:UB和LB分別為種群的上界和下界,U為二進(jìn)制向量,r為[0,1]中的隨機(jī)數(shù),gr1和gr2為瞪羚矩陣的隨機(jī)指數(shù)。

2 改進(jìn)瞪羚優(yōu)化算法

2.1 正交學(xué)習(xí)機(jī)制

分?jǐn)?shù)實(shí)驗(yàn)是正交設(shè)計(jì)的核心。利用部分實(shí)驗(yàn)的特征產(chǎn)生所有可能的水平組合,可以快速找到最佳水平組合。為每個(gè)變量尋找最佳水平組合的標(biāo)準(zhǔn)方法是遍歷所有水平組合,假設(shè)客觀問(wèn)題依賴于K個(gè)因子,且可以被分成Q個(gè)水平。這種遍歷方法不同于正交設(shè)計(jì),其構(gòu)建過(guò)程如下:首先構(gòu)建介紹性列,然后構(gòu)建非基本列。式(9)為創(chuàng)建的L10(34)的正交數(shù)組。

(9)

2.2 Rosenbrock直接旋轉(zhuǎn)策略

在Rosenbrock直接旋轉(zhuǎn)局部搜索策略中,坐標(biāo)軸主要用于初始路徑的搜索,種群個(gè)體沿著坐標(biāo)軸方向旋轉(zhuǎn),然后移動(dòng)到新的排列點(diǎn),同時(shí)在此處產(chǎn)生有效解,直到在每個(gè)搜索方向至少產(chǎn)生一個(gè)有效解和一個(gè)無(wú)效解。在這種情況下,當(dāng)前階段將結(jié)束搜索,標(biāo)準(zhǔn)正交基將被修改,并且考慮所有維度中全部有效解的累積影響。標(biāo)準(zhǔn)正交基更新如下:

(10)

式中:xk+1為第k個(gè)個(gè)體的下一代有效解,xk為本次迭代有效解,di為第i個(gè)個(gè)體的坐標(biāo),λi為設(shè)計(jì)變量的總數(shù)。此時(shí)最有利的搜索方向是xk+1-xk,因此它必須包含在修正的搜索方向中。

(11)

式中:pi為標(biāo)準(zhǔn)正交向量,dj為第j個(gè)個(gè)體的坐標(biāo)。Gram-Schmidt正交歸一化過(guò)程更新搜索結(jié)果如下所示:

(12)

式中:qj為標(biāo)準(zhǔn)正交向量。

歸一化時(shí)修改的搜索指令為:

(13)

在更新局部搜索之后,在相反方向再次搜索,直到滿足結(jié)束條件。

2.3 算法流程

本文算法具體流程如圖1所示。

圖1 算法流程

3 仿真及分析

3.1 仿真實(shí)驗(yàn)

為驗(yàn)證本文算法性能,采用本文算法與標(biāo)準(zhǔn)GOA、文獻(xiàn)[8]和文獻(xiàn)[10]算法基于MATLAB R2020b平臺(tái)分別在簡(jiǎn)易環(huán)境及多陷阱環(huán)境下進(jìn)行仿真實(shí)驗(yàn)。使用的硬件包括Windows 11操作系統(tǒng)、英特爾酷睿i7-7700@3.60 GHz處理器和16 GB運(yùn)行內(nèi)存。本文算法群體大小設(shè)置為50,最大迭代次數(shù)為100。每個(gè)算法的獨(dú)立運(yùn)行次數(shù)設(shè)置為30次。具體結(jié)果如圖2、圖3及表1所示。

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

圖2 簡(jiǎn)易環(huán)境仿真結(jié)果

根據(jù)圖2及圖3可知,4種算法均可以在兩種環(huán)境中找到無(wú)碰路徑。從表1的具體指標(biāo)可以看出,在簡(jiǎn)易環(huán)境中,本文算法相較于標(biāo)準(zhǔn)GOA、文獻(xiàn)[8]和文獻(xiàn)[10]算法路徑長(zhǎng)度分別縮短3.79%、2.62%、2.39%,運(yùn)算時(shí)間分別縮短13.97%、5.65%、2.50%。在多陷阱環(huán)境中,本文算法相較于標(biāo)準(zhǔn)GOA、文獻(xiàn)[8]和文獻(xiàn)[10]算法路徑長(zhǎng)度分別縮短8.03%、2.57%、3.08%,運(yùn)算時(shí)間分別縮短16.04%、7.41%、7.03%。由此可以看出IGOA在路徑規(guī)劃問(wèn)題上具有優(yōu)良性能,引入的多種改進(jìn)策略提升了規(guī)劃效率,可幫助機(jī)器人更快地完成規(guī)劃任務(wù)。

3.2 實(shí)車(chē)實(shí)驗(yàn)

為了驗(yàn)證本文算法在真實(shí)場(chǎng)景中的有效性,在實(shí)際場(chǎng)景下進(jìn)行實(shí)車(chē)實(shí)驗(yàn)。實(shí)驗(yàn)使用的硬件平臺(tái)是FS-AIROBOTB智能機(jī)器人。將本文算法寫(xiě)入操作系統(tǒng),利用即時(shí)定位與地圖構(gòu)建(simultaneous localization and mapping, SLAM)算法構(gòu)建測(cè)試地圖。路徑規(guī)劃實(shí)際測(cè)試環(huán)境和運(yùn)行結(jié)果如圖4所示,其中S為起點(diǎn),G為目標(biāo)點(diǎn)。

圖4 實(shí)車(chē)實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中,建立了IGOA的應(yīng)用環(huán)境,并進(jìn)行了自主導(dǎo)航測(cè)試。實(shí)驗(yàn)結(jié)果表明,移動(dòng)機(jī)器人能夠自主規(guī)劃出可靠平滑的路徑,完成從起點(diǎn)到終點(diǎn)的路徑自主導(dǎo)航。該實(shí)驗(yàn)驗(yàn)證了IGOA可以應(yīng)用于移動(dòng)機(jī)器人,并具有應(yīng)用于工業(yè)場(chǎng)景的潛力,展現(xiàn)出良好的適用性及有效性。

4 結(jié)束語(yǔ)

針對(duì)機(jī)器人路徑規(guī)劃中效率低、尋優(yōu)速度慢等問(wèn)題,本文設(shè)計(jì)了一種IGOA。仿真結(jié)果表明,在簡(jiǎn)易環(huán)境中,本文算法相較于對(duì)比的算法路徑長(zhǎng)度縮短2.39%～3.79%,運(yùn)算時(shí)間縮短2.50%～13.97%。在多陷阱環(huán)境中,本文算法相較于對(duì)比算法路徑長(zhǎng)度縮短2.57%～8.03%,運(yùn)算時(shí)間縮短7.41%～16.04%。同時(shí)通過(guò)實(shí)車(chē)實(shí)驗(yàn)驗(yàn)證了本文算法的有效性。