徐亞杰 王海星

(①鄭州升達(dá)經(jīng)貿(mào)管理學(xué)院信息工程學(xué)院，河南 鄭州 451191;②河南理工大學(xué)電氣工程與自動(dòng)化學(xué)院，河南 焦作 454003)

路徑規(guī)劃能力是移動(dòng)機(jī)器人完成自主移動(dòng)必須具備的能力之一，一直以來(lái)都備受國(guó)內(nèi)外學(xué)者的青睞，開(kāi)展了大量的研究工作，許多移動(dòng)機(jī)器人路徑規(guī)劃方法相繼被提出并應(yīng)有。從目前國(guó)內(nèi)外相關(guān)文獻(xiàn)來(lái)看，這些方法大致可分為傳統(tǒng)方法和智能方法兩類。傳統(tǒng)方法主要包括人工勢(shì)場(chǎng)法[1-2]、A*算法[3-4]等，它們的運(yùn)算速度相對(duì)較慢，而智能算法在總體運(yùn)算效率、路徑規(guī)劃效果等方面普遍要比傳統(tǒng)算法更優(yōu)。因此，基于智能算法的機(jī)器人路徑規(guī)劃的應(yīng)用也越來(lái)越多。如變步長(zhǎng)蟻群算法[5]、自適應(yīng)遺傳算法[6]、改進(jìn)人工魚(yú)群算法[7]、混合灰狼算法[8]、混合粒子群算法[9]和鯨魚(yú)優(yōu)化算法[10]等多種智能算法都被應(yīng)用到了機(jī)器人的路徑規(guī)劃中，并且均得到了較為理想的路徑規(guī)劃效果。

2017年提出的蝗蟲(chóng)優(yōu)化算法(grasshopper optimization algorithm, GOA)同前文提及的智能算法一樣，也是一種智能優(yōu)化算法，目前已得到廣泛應(yīng)用[11-13]。但GOA同前文所述的智能算法相似，算法本身存在有易陷入局部最優(yōu)、后期收斂精度不足等問(wèn)題[14-15]，如果直接將其用于機(jī)器人的路徑規(guī)劃中，算法本身存在的缺陷勢(shì)必會(huì)對(duì)路徑規(guī)劃效果造成影響。因此，有必要對(duì)其缺陷進(jìn)行改進(jìn)設(shè)計(jì)，以達(dá)到提升機(jī)器人路徑規(guī)劃效果的目的。

本文以GOA為移動(dòng)機(jī)器人路徑規(guī)劃方法，同時(shí)針對(duì)GOA存在的缺陷，對(duì)其進(jìn)行改進(jìn)設(shè)計(jì)，提出改進(jìn)蝗蟲(chóng)優(yōu)化算法(improved grasshopper optimization algorithm, IGOA)，以提升機(jī)器人路徑規(guī)劃效果。機(jī)器人2種不同行駛環(huán)境的路徑規(guī)劃實(shí)例驗(yàn)證了IGOA算法的有效性。

1 柵格法中的蝗蟲(chóng)優(yōu)化算法

通過(guò)智能算法進(jìn)行移動(dòng)機(jī)器人的路徑規(guī)劃包含兩部分內(nèi)容，一是進(jìn)行環(huán)境建模，二是通過(guò)智能算法反復(fù)迭代得到最優(yōu)路徑。進(jìn)行環(huán)境建模的方法有很多種，如可視圖法、單元分解法、幾何法和柵格法等，其中柵格法最簡(jiǎn)單且應(yīng)用最為廣泛。

根據(jù)柵格法的原理，建立1個(gè)如圖1所示的10×10柵格的機(jī)器人行駛區(qū)域。圖1中，黑色柵格表示障礙物，將其賦值為1，即機(jī)器人不能觸碰或翻越該柵格；白色柵格表示可行區(qū)域，將其賦值為0，即機(jī)器人可在其上自由移動(dòng)。路徑規(guī)劃從左上角的起點(diǎn)至右下角的終點(diǎn)，每步移動(dòng)的長(zhǎng)度在1×1正方形柵格內(nèi)，最長(zhǎng)距離為斜對(duì)角。

2 蝗蟲(chóng)優(yōu)化算法

眾所周知，GOA是模仿自然界蝗蟲(chóng)的覓食行為而提出的一種智能仿生算法。在GOA中，蝗蟲(chóng)個(gè)體所在的位置表示所求優(yōu)化問(wèn)題的一個(gè)候選解，它主要受蝗蟲(chóng)種群間的相互作用力、風(fēng)力和重力等3個(gè)因素的影響，可用式(1)所示的數(shù)學(xué)模型進(jìn)行表示。

Xi=Si+Gi+Ai

(1)

式中:Xi為第i只蝗蟲(chóng)所處的位置；Si為第i只蝗蟲(chóng)所受種群間相互作用力的影響；Gi為第i只蝗蟲(chóng)所受外界重力的影響；Ai為第i只蝗蟲(chóng)所受外界風(fēng)力的影響。在進(jìn)行數(shù)學(xué)優(yōu)化問(wèn)題求解時(shí)，為了對(duì)數(shù)學(xué)模型進(jìn)行優(yōu)化，式(1)中的外界重力影響Gi和風(fēng)力影響Ai需要被替換為目標(biāo)食物的位置Td。這樣，式(1)就可以改寫成式(2)。

Xi=Si+Td

(2)

其中：Si主要通過(guò)式(3)計(jì)算。

(3)

(4)

式(3)中的s函數(shù)為計(jì)算蝗蟲(chóng)種群間相互作用力的函數(shù)，其表達(dá)式如式(5)所示。

(5)

其中：f為吸引強(qiáng)度參數(shù)、r為吸引尺度參數(shù)。

在整個(gè)搜索迭代的過(guò)程中，蝗蟲(chóng)每個(gè)位置優(yōu)劣的評(píng)價(jià)指標(biāo)為適應(yīng)度函數(shù)(目標(biāo)函數(shù))。對(duì)于移動(dòng)機(jī)器人路徑規(guī)劃而言，適應(yīng)度函數(shù)通常采用得最多的是滿足移動(dòng)路徑最短。在進(jìn)行優(yōu)化問(wèn)題的求解過(guò)程中，式(2)被不斷用來(lái)循環(huán)迭代以得到最優(yōu)解，每完成一次迭代后得到的最優(yōu)適應(yīng)度值即被記錄為當(dāng)前得到的最優(yōu)解，最優(yōu)解所在位置即被視為目標(biāo)食物的位置Td，直至達(dá)到最大迭代次數(shù)。

3 改進(jìn)蝗蟲(chóng)優(yōu)化算法

從蝗蟲(chóng)優(yōu)化算法的基本原理可知，在其整個(gè)計(jì)算過(guò)程中，蝗蟲(chóng)種群幾乎沒(méi)有變化，缺乏隨機(jī)因素，且沒(méi)有跳出局部最優(yōu)的機(jī)制，這就使得算法比較容易陷入局部最優(yōu)后無(wú)法跳出，最終影響優(yōu)化性能。文獻(xiàn)[14]提出了一種混合變異蝗蟲(chóng)優(yōu)化算法(MMGOA)，通過(guò)柯西變異對(duì)蝗蟲(chóng)位置進(jìn)行擾動(dòng)，從而保證蝗蟲(chóng)個(gè)體具有一定概率跳出局部最優(yōu)。而柯西分布概率密度函數(shù)可知，生成短步長(zhǎng)的概率遠(yuǎn)高于長(zhǎng)步長(zhǎng)，這就使得對(duì)蝗蟲(chóng)位置的擾動(dòng)以小擾動(dòng)為主，并不能保證蝗蟲(chóng)真正能夠跳出局部最優(yōu)；文獻(xiàn)[15]提出了一種多目標(biāo)蝗蟲(chóng)優(yōu)化算法(MOGOA)，通過(guò)曲線自適應(yīng)策略對(duì)參數(shù)進(jìn)行調(diào)控，從而一定程度上實(shí)現(xiàn)了算法前后搜索能力的平衡。而曲線自適應(yīng)策略的參數(shù)值前大后下，雖前期收斂較快，但在后期參數(shù)值較小時(shí)，容易導(dǎo)致陷入局部最優(yōu)。

針對(duì)上述問(wèn)題，本文借鑒MMGOA和MOGOA對(duì)GOA的改進(jìn)思路，從兩個(gè)方面對(duì)GOA進(jìn)行改進(jìn)設(shè)計(jì)，得到IGOA算法。

3.1 Levy飛行局部搜索策略

Levy飛行策略是一種移動(dòng)步長(zhǎng)隨機(jī)性極強(qiáng)的行走方式，能夠保證生成長(zhǎng)、短步長(zhǎng)的概率大體相當(dāng)(柯西分布短步長(zhǎng)的概率遠(yuǎn)大于長(zhǎng)步長(zhǎng))。將Levy飛行隨機(jī)步長(zhǎng)引入到GOA算法中，可以增強(qiáng)算法的隨機(jī)性和局部搜索能力，提高跳出局部最優(yōu)的概率。當(dāng)蝗蟲(chóng)種群在完成一次迭代搜索后，通過(guò)Levy飛行步長(zhǎng)對(duì)蝗蟲(chóng)個(gè)體所在的位置進(jìn)行局部調(diào)整，如式(6)所示。

X=X+10×sts×L×X

(6)

其中：sts為一個(gè)閾值函數(shù)，用于控制飛行方法和變化概率，其計(jì)算方式如式(7)所示；L為L(zhǎng)evy飛行步長(zhǎng)，其計(jì)算方式如式(8)所示。

sts=sign(xtrans-1)+sign(xtrans+1)

(7)

其中：xtrans為[-3,3]之間的隨機(jī)數(shù)，sign為符號(hào)函數(shù)。

L=μ/|v|1/β

(8)

其中：參數(shù)β范圍為(0,2)，一般取1.5；參數(shù)μ、v服從式(9)所示的正太分布，標(biāo)準(zhǔn)差σμ、σv的取值根據(jù)式(10)計(jì)算。

(9)

(10)

在一定程度上，Levy飛行的引入為蝗蟲(chóng)個(gè)體提供了一定的“視覺(jué)”，能夠讓蝗蟲(chóng)個(gè)體“看清”自身周圍一片區(qū)域內(nèi)食物的情況，使得蝗蟲(chóng)個(gè)體能夠在局部范圍內(nèi)進(jìn)行更有針對(duì)性的搜索。

3.2 線性遞減參數(shù)隨機(jī)跳出策略

為保證GOA前后搜索能力的平衡且具有跳出局部最優(yōu)的機(jī)制，提出線性遞減參數(shù)的隨機(jī)跳出策略(曲線自適應(yīng)策略雖在一定程上平衡了前后搜索能力，但在后期容易導(dǎo)致陷入局部最優(yōu))。當(dāng)蝗蟲(chóng)個(gè)體搜索到當(dāng)前最優(yōu)解的位置后，利用該位置對(duì)原位置進(jìn)行替換，如果沒(méi)有搜索到最優(yōu)解，則啟動(dòng)隨機(jī)跳出策略，其計(jì)算方式如式(11)所示。

Xi=(2×(0.5-rand(0,1))+1)×Xi

(11)

其中：Xi是蝗蟲(chóng)i所在位置。假如搜索到的新Xi更優(yōu)，則對(duì)舊Xi進(jìn)行替換，替換一次則可認(rèn)為成功完成了一次跳出行為。為了保證跳出成功后的位置信息能夠被有效利用，將搜索迭代式(2)調(diào)整為式(12)：

Xi=Si+(1-p)×Td+p×Xi

(12)

其中：p是控制協(xié)調(diào)參數(shù)，首次迭代時(shí)為0。它按照式(13)進(jìn)行計(jì)算。

(13)

根據(jù)式(13)可知，當(dāng)蝗蟲(chóng)個(gè)體未進(jìn)行跳出或者跳出失敗時(shí)，p仍然為0，這就保證了只有Si和Td能夠影響下一次迭代；當(dāng)蝗蟲(chóng)個(gè)體完成了一次成功跳出后，p在后續(xù)的3次迭代中按照0.35的間隔逐步線性遞減為0，這就保證了蝗蟲(chóng)個(gè)體在成功跳出一次局部最優(yōu)后能夠?qū)罄m(xù)3次迭代產(chǎn)生影響。

3.3 IGOA算法流程

根據(jù)GOA算法基本原理和3.1節(jié)、3.2節(jié)的描述，本文提出的IGOA算法流程如圖2所示。

4 機(jī)器人路徑規(guī)劃實(shí)例分析

本文一共構(gòu)建了2種機(jī)器人行駛環(huán)境來(lái)對(duì)本文所提IGOA方法在路徑規(guī)則中的有效性進(jìn)行驗(yàn)證。2種環(huán)境分別為：在MATLAB中構(gòu)建的仿真20×20柵格地圖，用于模擬機(jī)器人較為簡(jiǎn)單的行駛環(huán)境；在MATLAB中構(gòu)建的仿真40×40柵格地圖，用于模擬機(jī)器人較為復(fù)雜的行駛環(huán)境。同時(shí)，為驗(yàn)證本文IGOA的路徑規(guī)劃性能，還將其與GOA、參考文獻(xiàn)[14]中的混合變異蝗蟲(chóng)算法(MMGOA)、參考文獻(xiàn)[15]中多目標(biāo)蝗蟲(chóng)算法(MOGOA)進(jìn)行對(duì)比分析。在進(jìn)行機(jī)器人路徑規(guī)劃時(shí)，上述4種方法中蝗蟲(chóng)種群的規(guī)模均設(shè)置為30，迭代達(dá)到100次后均停止迭代，輸出最優(yōu)結(jié)果，MMGOA和MOGOA兩種方法的相關(guān)其余參數(shù)均按原文獻(xiàn)進(jìn)行設(shè)置。

4.1 仿真20×20柵格地圖分析

利用4種方法進(jìn)行仿真20×20柵格地圖中的機(jī)器人路徑規(guī)劃時(shí)，每種方法均獨(dú)立運(yùn)行30次，記錄下每次計(jì)算的結(jié)果。表1給出了4種方法的計(jì)算結(jié)果統(tǒng)計(jì)，其中平均值為30次計(jì)算結(jié)果的平均值，耗時(shí)為規(guī)劃得到最短路徑的時(shí)間消耗；圖3給出了4種方法所得最短路徑的可視化結(jié)果；圖4給出了4種方法的迭代過(guò)程。

由表1、圖3和圖4的結(jié)果可知，從最短路徑指標(biāo)來(lái)看，IGOA分別比GOA、MMGOA和MOGOA縮短了9.3%、2%和3.9%；從最長(zhǎng)路徑指標(biāo)來(lái)看，IGOA得到結(jié)果比其余3種方法的均要好，特別是比GOA得到的最短路徑還要好；從標(biāo)準(zhǔn)差指標(biāo)來(lái)看，IGOA的標(biāo)準(zhǔn)差最小，表明算法的穩(wěn)定性要好于其余3種；從耗時(shí)指標(biāo)來(lái)看，IGOA、MMGOA和MOGOA均是在GOA的基礎(chǔ)上進(jìn)行的改進(jìn)，因此算法較GOA的復(fù)雜度均有所增加，故耗時(shí)不如GOA更優(yōu)，雖然耗時(shí)增加，但得到的路徑均要好于GOA。以上分析結(jié)果表明，IGOA在5種評(píng)價(jià)指標(biāo)中，除耗時(shí)上不如GOA外，其余4種指標(biāo)均是要優(yōu)于GOA、MMGOA和MOGOA方法。

表1 仿真20×20柵格地圖計(jì)算結(jié)果

4.2 仿真40×40柵格地圖分析

利用4種方法進(jìn)行仿真40×40柵格地圖中的機(jī)器人路徑規(guī)劃，分別得到表2的計(jì)算結(jié)果、圖5的最短路徑可視化結(jié)果和圖6的迭代過(guò)程。

由表2、圖5和圖6的結(jié)果可知，隨著路徑環(huán)境的復(fù)雜，算法的優(yōu)勢(shì)得以更加明顯的體現(xiàn)。同時(shí)也可知，4種方法對(duì)仿真40×40柵格地圖的路徑規(guī)劃結(jié)果和仿真20×20柵格地圖的路徑規(guī)劃結(jié)果比較相似，即：IGOA在5種評(píng)價(jià)指標(biāo)中，除耗時(shí)上不如GOA外，其余4種指標(biāo)均是要優(yōu)于GOA、MMGOA和MOGOA方法。其中，IGOA的最短路徑指標(biāo)分別比GOA、MMGOA和MOGOA縮短了7.3%、3%和6.1%； IGOA的最長(zhǎng)路徑同樣比GOA得到的最短路徑還要好； IGOA的標(biāo)準(zhǔn)差在0.1以下，而其余3種方法均大于0.1； IGOA的耗時(shí)同樣是排名第2。

表2 仿真40×40柵格地圖計(jì)算結(jié)果

5 結(jié)語(yǔ)

為有效提升移動(dòng)機(jī)器人的路徑規(guī)劃效果，針對(duì)GOA存在的不足，將Levy飛行策略局部搜索策略和線性遞減參數(shù)隨機(jī)跳出策略引入到GOA，提出了IGOA算法。通過(guò)移動(dòng)機(jī)器人3種環(huán)境下的路徑規(guī)劃實(shí)例驗(yàn)證了IGOA算法在路徑規(guī)劃中的優(yōu)勢(shì)。