基于情景螢火蟲算法的機(jī)器人路徑規(guī)劃

羅天洪，梁 爽，何澤銀，張 霞

(重慶交通大學(xué) 機(jī)電與車輛工程學(xué)院，重慶 400074)

基于情景螢火蟲算法的機(jī)器人路徑規(guī)劃

羅天洪，梁 爽*，何澤銀，張 霞

(重慶交通大學(xué) 機(jī)電與車輛工程學(xué)院，重慶 400074)

針對(duì)傳統(tǒng)非結(jié)構(gòu)環(huán)境下路徑規(guī)劃時(shí)機(jī)器人運(yùn)動(dòng)狀態(tài)振蕩和適應(yīng)性差等問題，提出了一種基于情景螢火蟲算法(SGSO)的機(jī)器人路徑規(guī)劃策略。該算法基于混沌系統(tǒng)的規(guī)律性、隨機(jī)性和歷遍性以實(shí)現(xiàn)初始化，并利用黃金比分割法進(jìn)行后期優(yōu)化，以提高種群的多樣性，抑制算法的早熟和局部收斂；同時(shí)，引入關(guān)于螢火蟲“天敵”的情景理解，改進(jìn)螢火蟲種群的選擇機(jī)制，解決螢火蟲在非結(jié)構(gòu)環(huán)境下尋跡過程中的擱淺現(xiàn)象，增強(qiáng)了算法的適應(yīng)性和魯棒性。四個(gè)測(cè)試函數(shù)的仿真實(shí)驗(yàn)結(jié)果表明，所提算法的求解精度、收斂效率優(yōu)于基本螢火蟲種群優(yōu)化(GSO)算法；將該算法應(yīng)用于非結(jié)構(gòu)環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃中，檢測(cè)結(jié)果表明，基于SGSO的規(guī)劃路徑更短，且轉(zhuǎn)角處更光滑，有效避免了機(jī)器人大角度轉(zhuǎn)向?qū)?dòng)力系統(tǒng)造成的額外負(fù)荷，驗(yàn)證了所提算法的可行性和有效性。

螢火蟲群優(yōu)化算法；路徑規(guī)劃；非結(jié)構(gòu)環(huán)境；擱淺現(xiàn)象；移動(dòng)機(jī)器人

0 引言

非結(jié)構(gòu)環(huán)境存在表面材質(zhì)性能不均、結(jié)構(gòu)尺寸變化不規(guī)律且不穩(wěn)定、環(huán)境信息非固定或不可知等問題，因此機(jī)器人在非機(jī)構(gòu)環(huán)境中的路徑規(guī)劃存在較大的難度?，F(xiàn)存的算法中人工勢(shì)場(chǎng)法[1]多被運(yùn)用到非結(jié)構(gòu)環(huán)境規(guī)劃中的運(yùn)動(dòng)，可以實(shí)現(xiàn)較低層的實(shí)時(shí)控制；但該方法易出現(xiàn)局部最優(yōu)解，并產(chǎn)生死鎖現(xiàn)象。因此，亟需一種算法實(shí)現(xiàn)移動(dòng)機(jī)器人在非結(jié)構(gòu)環(huán)境中的路徑規(guī)劃問題。螢火蟲群優(yōu)化(Glowworm Swarm Optimization, GSO)[2]算法自提出以來被廣泛應(yīng)用于機(jī)器人軌跡規(guī)劃、路徑規(guī)劃和全局分布優(yōu)化等領(lǐng)域；但該算法存在易陷入局部最優(yōu)解、早熟、精度低等缺點(diǎn)?，F(xiàn)有文獻(xiàn)中已有大量分別關(guān)于GSO算法或非結(jié)構(gòu)環(huán)境下路徑規(guī)劃的研究:郁書好等[3]利用混沌系統(tǒng)的規(guī)律性、隨機(jī)性和遍歷性對(duì)GSO進(jìn)行初始化，提高了算法的求解精度及全收斂效率，并成功用于車輛路徑問題；Liao等[4]通過對(duì)螢火蟲的步長(zhǎng)選擇方式進(jìn)行修改，調(diào)整了螢火蟲的分布結(jié)構(gòu)，應(yīng)用到無障礙環(huán)境中傳感器分布問題,并有效提高了傳感器的覆蓋率；Marinaki等[5]提出一種基于空間分布優(yōu)化的螢火蟲算法，通過連續(xù)優(yōu)化的方式解決了存在隨機(jī)需求車輛的路徑規(guī)劃問題；Zhang等[6]通過對(duì)機(jī)器人傳感器系統(tǒng)進(jìn)行優(yōu)化使機(jī)器人對(duì)障礙物進(jìn)行感知，并基于力分布應(yīng)用到對(duì)機(jī)器人的控制，實(shí)現(xiàn)非機(jī)構(gòu)環(huán)境下的平穩(wěn)行走；于乃功等[7]提出了一種基于梯度守恒假設(shè)和局部加權(quán)對(duì)光流的移動(dòng)機(jī)器人避障策略，抑制光照和噪聲等變量對(duì)其影響，實(shí)現(xiàn)非結(jié)構(gòu)環(huán)境下的無碰撞行走。此外，文獻(xiàn)[8-9]對(duì)螢火蟲的選擇機(jī)制進(jìn)行了優(yōu)化，提高了螢火蟲種群的利用率；文獻(xiàn)[10-12]將GSO算法應(yīng)用到物理和機(jī)械領(lǐng)域，驗(yàn)證了GSO算法相比其他智能算法的優(yōu)點(diǎn)。目前將GSO算法運(yùn)用到非機(jī)構(gòu)環(huán)境下進(jìn)行路徑規(guī)劃的研究較少。

本文根據(jù)非結(jié)構(gòu)環(huán)境的特點(diǎn)，提出一種基于情景螢火蟲算法(GSO algorithm of Scene understanding, SGSO)的路徑規(guī)劃策略。該算法引入了螢火蟲“天敵”的概念，解決螢火蟲面對(duì)“天敵”時(shí)出現(xiàn)的擱淺現(xiàn)象,對(duì)螢火蟲的選擇機(jī)制進(jìn)行影響，保障了求解的精度，降低了傳統(tǒng)螢火蟲算法早熟和局部收斂的發(fā)生概率；同時(shí)引入混沌變量與黃金比分割法則優(yōu)化螢火蟲種群，增強(qiáng)在算法在應(yīng)用過程中的自適應(yīng)性和魯棒性。

1 情景螢火蟲算法

1.1 情景螢火蟲算法原理

GSO算法的原理[10]如下：在多維空間隨機(jī)分布N個(gè)螢火蟲個(gè)體，每個(gè)螢火蟲個(gè)體帶有定量的熒光素li(t)；以概率pij(t)向鄰域集合Ni(t)中選取的較優(yōu)個(gè)體移動(dòng)。計(jì)算出適應(yīng)函數(shù)J(xi(t))所對(duì)應(yīng)值，并重復(fù)這一過程直到達(dá)到一定的迭代次數(shù)，得到問題較優(yōu)解的位置。

GSO算法一個(gè)迭代循環(huán)如下所示：

(1)

(2)

(3)

(4)

li(t+1)=(1-ρ)li(t)+γ*J[xi(t+1)]

(5)

其中：rs為個(gè)體的最大感識(shí)半徑；β為感識(shí)半徑變化系數(shù)；nt為螢火蟲個(gè)體附近鄰域閾值；Ni(t)為螢火蟲個(gè)體的鄰域集合；s為螢火蟲個(gè)體移動(dòng)的步長(zhǎng)；ρ為熒光素?fù)]發(fā)系數(shù)，ρ∈(0,1)；dij(t)為個(gè)體i和個(gè)體j之間的距離；γ為用于調(diào)節(jié)函數(shù)值的常數(shù)量，可以放縮適應(yīng)度函數(shù)J[xi(t+1)]。

與現(xiàn)有的智能群算法相比較，螢火蟲算法中需調(diào)節(jié)的參數(shù)簡(jiǎn)單，且不存在較為繁瑣的進(jìn)化，易于實(shí)現(xiàn)，穩(wěn)定性高；但收斂速度慢、早熟和求解精度不高等缺陷對(duì)搜尋最優(yōu)解造成一定的影響。

1.2 情景螢火蟲選擇策略

為了增強(qiáng)螢火蟲群的搜索能力，擬加入螢火蟲的“天敵”，并引入?yún)?shù)暗度di(t)以表示螢火蟲對(duì)天敵的排斥效果，與基本螢火蟲算法中存在熒光素吸引作用共同作用，綜合模擬螢火蟲在動(dòng)態(tài)環(huán)境和未知環(huán)境中尋跡的真實(shí)過程。

“天敵”對(duì)螢火蟲選擇有抑制作用，參數(shù)Oi(t)表示螢火蟲鄰域內(nèi)存在的天敵數(shù)量，影響螢火蟲感識(shí)半徑的更新，使鄰域內(nèi)螢火蟲和天敵共同決定螢火蟲的選擇機(jī)制。

(6)

其中：dii(t)表示螢火蟲個(gè)體i與感識(shí)半徑內(nèi)天敵i所在點(diǎn)之間的距離。為將天敵對(duì)于螢火蟲路徑選擇策略的干擾，引入暗度di(t)表示螢火蟲個(gè)體i鄰域內(nèi)天敵對(duì)熒光素傳遞的抑制效果，暗度di(t)與天敵數(shù)量Oi(t)的關(guān)系為：

(7)

若螢火蟲的感識(shí)半徑內(nèi)天敵數(shù)量過多或體積過大，螢火蟲易停止搜索，因此設(shè)最大暗度dmax,防止感識(shí)半徑減小到0。

由于具備了天敵對(duì)螢火蟲的刺激作用，個(gè)體i向相鄰鄰域中第j只螢火蟲方向移動(dòng)的概率為：

(8)

加入暗度影響后，選擇機(jī)制的概率分布從[0,1]擴(kuò)展到[-1,1]，更利于螢火蟲選取最優(yōu)解。

1.3 情景螢火蟲種群的優(yōu)化

為抑制GSO算法中因?yàn)殡S機(jī)初始分布而陷入局部解和早熟收斂的問題，在算法中采用混沌變量[3]作為螢火蟲的初始種群，以提高搜索的遍歷性、隨機(jī)性和規(guī)律性。前期通過混沌變量進(jìn)一步提高螢火蟲種群的豐富度和收斂速度，后期通過將適應(yīng)度較低的螢火蟲個(gè)體進(jìn)行黃金分割優(yōu)化，解決螢火蟲的“擱淺現(xiàn)象”，保障了求解精度，增強(qiáng)了螢火蟲種群初始位置的質(zhì)量以提高后期收斂效率。

xn+1=cos(narccosxn)

(9)

(10)

其中：xmax和xmin分別表示螢火蟲個(gè)體搜索范圍的閾值。

然后通過黃金比分割法則重新分布后的部分個(gè)體依式(9)迭代得到xn+1，將經(jīng)過二次優(yōu)化后的螢火蟲和較高熒光素的種群組成螢火蟲的初始種群。

1.4 情景螢火蟲算法的描述

情景螢火蟲算法總的流程如圖1所示，相應(yīng)步驟描述如下。

圖1 情景螢火蟲算法流程Fig.1 Flow chart of SGSO

步驟1 初始化ρ、γ、li(0)及其他常量參數(shù)。隨機(jī)生成D維向量X0=[x0.1,x0.2,…,x0.D]，根據(jù)式(9)進(jìn)行第一次優(yōu)化，依次得到X1，X2，…，XN，將上述N個(gè)混沌向量映射到求解區(qū)域內(nèi)。

步驟2 根據(jù)式(5)更新螢火蟲種群的熒光素值，篩選出熒光素較低的k個(gè)個(gè)體，根據(jù)式(10)進(jìn)行二次優(yōu)化后和一次優(yōu)化后熒光素較高的部分個(gè)體混合組成初始種群。

步驟3 根據(jù)式(4)與式(6)分別計(jì)算出螢火蟲個(gè)體i的鄰域集合Ni(t)和天敵集合Oi(t)。

步驟4 根據(jù)式(8)計(jì)算出螢火蟲i向鄰域內(nèi)高熒光素個(gè)體j移動(dòng)的概率。

步驟6 判斷所求解是否滿足條件或者達(dá)到最大迭代次數(shù)：若滿足條件或達(dá)到最大迭代次數(shù)即輸出結(jié)果；否則轉(zhuǎn)到步驟3。

2 非結(jié)構(gòu)環(huán)境下共融機(jī)器人的路徑規(guī)劃

2.1 非結(jié)構(gòu)環(huán)境中障礙物的識(shí)別和分類

機(jī)器人在非結(jié)構(gòu)環(huán)境中須通過傳感器對(duì)工作環(huán)境進(jìn)行感知和識(shí)別，提取可能存在的障礙物信息并作出相應(yīng)的決策以躲避障礙物。為了在復(fù)雜工況下保障自身安全，機(jī)器人的傳感集成系統(tǒng)多包含不同種類的傳感器。中央控制系統(tǒng)需將各傳感器的信息輸入進(jìn)行融合以及處理，為機(jī)器人的運(yùn)動(dòng)進(jìn)行規(guī)劃。

非結(jié)構(gòu)環(huán)境下障礙物分布不規(guī)律、體積不規(guī)則，而障礙物的隨機(jī)性往往對(duì)移動(dòng)機(jī)器人的運(yùn)動(dòng)性能造成影響。因此，對(duì)于不同種類障礙物，機(jī)器人根據(jù)其特點(diǎn)作出相應(yīng)的避障決策，從而達(dá)到路徑規(guī)劃的目的。障礙物的分類如表1所示。

表1 非結(jié)構(gòu)環(huán)境中常見障礙物分類Tab. 1 Common obstacle classification in unstructured environment

2.2 非結(jié)構(gòu)環(huán)境下路徑規(guī)劃的情景理解

傳統(tǒng)路徑規(guī)劃的算法在建立模型的過程中，障礙物和機(jī)器人的外型通常經(jīng)過結(jié)構(gòu)化或其他簡(jiǎn)化處理，為考慮實(shí)際運(yùn)動(dòng)過程中由體積因素可能帶來的碰撞或沖擊等不利工況，為了細(xì)致地描述環(huán)境的特點(diǎn)，更為精確地在算法中模擬障礙物的分布情況，本文算法在確定環(huán)境參數(shù)的過程中需增加機(jī)器人與障礙物的體積對(duì)路徑的影響，以再現(xiàn)運(yùn)動(dòng)過程中機(jī)器人和障礙物之間相對(duì)位置關(guān)系。

通過關(guān)于障礙物各參數(shù)的收集與處理，分析機(jī)器人可識(shí)別范圍內(nèi)障礙物體積等可增益變量的影響范圍，量化各類障礙物對(duì)于機(jī)器人路徑選擇策略的影響因子，實(shí)現(xiàn)對(duì)于障礙物的膨脹保護(hù)，保證機(jī)器人在運(yùn)動(dòng)過程中的安全。

(11)

其中：α表示機(jī)器人識(shí)別障礙物的展角，rk1表示障礙物k到傳感器最短的距離，rk2表示感知范圍內(nèi)障礙物k到傳感器最遠(yuǎn)的距離，G表示障礙物量化增益系數(shù)。根據(jù)式(11)對(duì)螢火蟲個(gè)體感知范圍內(nèi)的障礙物進(jìn)行識(shí)別和量化。

由于非結(jié)構(gòu)環(huán)境具有未知性和不確定性，且目前傳感器的測(cè)量與分析水平有限，實(shí)際環(huán)境中的障礙物和理想模型中的傳感器必然存在一定的誤差。為避免上述測(cè)量誤差可能引起的碰撞與跌落現(xiàn)象，引入安全系數(shù)s以確保機(jī)器人與障礙物之間始終保持一定的間隙，從而保障尋跡過程的穩(wěn)定性。其中s∈[1.05，1.20]。當(dāng)環(huán)境中障礙物數(shù)量較少時(shí)，選取較小的安全系數(shù)，以減少機(jī)器人的移動(dòng)路徑；當(dāng)環(huán)境中障礙物數(shù)量較多時(shí)，選取較大的安全系數(shù)，以保障運(yùn)動(dòng)過程中的無沖撞[13]。

2.3 非結(jié)構(gòu)環(huán)境下路徑規(guī)劃的目標(biāo)描述

非結(jié)構(gòu)環(huán)境下的路徑規(guī)劃就是確定移動(dòng)機(jī)器人從出發(fā)點(diǎn)到目標(biāo)點(diǎn)所經(jīng)過m+1個(gè)點(diǎn)的集合[13]，由于非結(jié)構(gòu)環(huán)境的障礙存在不確定的因素，機(jī)器人的移動(dòng)路徑應(yīng)適應(yīng)于存在各種障礙的環(huán)境，因此模型的建立必須不依賴障礙物的任何參數(shù)。如圖2所示，以機(jī)器人的出發(fā)點(diǎn)O與目標(biāo)點(diǎn)Pm的連線建立X軸，過出發(fā)點(diǎn)O且垂直于X軸的直線作為Y軸，建立全局坐標(biāo)系O-XY。然后將OPm等分成m段，并過每一個(gè)等分點(diǎn)作垂線,從而的到垂線族(h1,h2,…,hm-1)，而各垂線與路徑的交點(diǎn)即為路徑中部分必須經(jīng)過的目標(biāo)點(diǎn)(P1,P2,…,Pm-1)。在不影響結(jié)果的前提下，為減小計(jì)算量，且便于觀察，將X軸進(jìn)行平移后提取出新的坐標(biāo)系。通過上述策略將移動(dòng)機(jī)器人的路徑規(guī)劃轉(zhuǎn)變?yōu)橐幌盗心繕?biāo)點(diǎn)的選取過程。

圖2 路徑規(guī)劃過程Fig. 2 Process of path planning

為了減小能量的消耗，機(jī)器人從起點(diǎn)到終點(diǎn)所經(jīng)歷總路程應(yīng)盡量短，即要滿足函數(shù)L取最小值。

(12)

其中：LOP1表示點(diǎn)O到點(diǎn)P1間的距離，LPjPj+1表示點(diǎn)Pj到Pj+1間的距離。也可以用坐標(biāo)表示式(12)為：

(13)

最終機(jī)器人的路徑規(guī)劃轉(zhuǎn)化為對(duì)于式(13)的函數(shù)在取值范圍內(nèi)尋找最小的函數(shù)值Lmin。通過多次目標(biāo)轉(zhuǎn)換，使模型的目標(biāo)鎖定為最短路程，且適應(yīng)于非結(jié)構(gòu)環(huán)境下障礙物隨機(jī)分布的特點(diǎn)。

3 算法性能分析

為了進(jìn)一步驗(yàn)證SGSO的有效性，將SGSO與GSO算法、混沌GSO(Chaotic GSO, CGSO)進(jìn)行性能對(duì)比。為方便對(duì)比，選取參考文獻(xiàn)[3]中基準(zhǔn)測(cè)試函數(shù)分布進(jìn)行對(duì)比測(cè)試。首先對(duì)各參數(shù)進(jìn)行初始化，如表2所示。

表2 SGSO與GSO算法的初始化參數(shù)Tab. 2 Initialization parameters of SGSO and GSO algorithms

具體函數(shù)如下：

f1=(|x1|-5)2+(|x2|+5)2；xi∈[-10,10]，i=1,2

該函數(shù)的全局最小值為25。

x1∈[-5,10],x2∈[0,15]

該函數(shù)的全局最優(yōu)值為0.397 898。

x1∈[-5,10],x2∈[0,15]

該函數(shù)的全局最小值為0。

f4=100(x2-x1)2+[6.4(x2-0.5)2-x1-0.6]2；

xi∈[-5,5]；i=1,2

該函數(shù)的全局最小值為0。

由于單次實(shí)驗(yàn)結(jié)果不具有代表性，分別通過GSO算法和SGSO對(duì)上述測(cè)試函數(shù)進(jìn)行100次運(yùn)行，并提取出結(jié)果中的各項(xiàng)值，如表3。

從表3中的數(shù)據(jù)可以看出：求解精度方面，通過SGSO所得到4個(gè)函數(shù)的最差值和平均值皆優(yōu)于GSO算法和CGSO算法，但函數(shù)f3和f4的最優(yōu)值精度不如CGSO算法；通過GSO算法得出函數(shù)f1的最優(yōu)值與最差值與標(biāo)準(zhǔn)值的差值分別為5.654 9×10-3和3.719 6，而通過SGSO的對(duì)應(yīng)值分別為4.512 3×10-6和1.283 894×10-4，其誤差值相比減小到原來的1/29 060和1/1 253。穩(wěn)定性方面，SGSO的標(biāo)準(zhǔn)偏差值均低于GSO算法和SGSO，其中，通過SGSO得到函數(shù)f3的標(biāo)準(zhǔn)偏差相對(duì)GSO算法和SGSO的進(jìn)一步優(yōu)化程度較小，但仍提高23%。收斂效率方面，從圖3可以看出，SGSO的收斂曲線中拐點(diǎn)出現(xiàn)較早，都出現(xiàn)于100次迭代之前，收斂速度明顯快于GSO算法；種群分布方面，從圖4可以看出，在函數(shù)f1和f3中，SGSO中螢火蟲種群收斂于在最優(yōu)解的附近，說明改進(jìn)后的SGSO情景理解模式和選擇機(jī)制提高了算法的求解性能。綜上所述，SGSO求解精度較高，穩(wěn)定性良好，種群分布合理性強(qiáng)，收斂速度快。

圖3 不同算法執(zhí)行f1～f4函數(shù)收斂對(duì)比Fig. 3 Convergence comparison of f1-f4 functions implemented by different algorithms

圖4 不同算法函數(shù)f1、 f3螢火蟲最終分布Fig. 4 Glowworm final distribution of f1, f3 with different algorithm表3 GSO、CGSO與SGSO函數(shù)求解結(jié)果Tab. 3 Functional test results of GSO, CGSO and SGSO

測(cè)試函數(shù)算法最差值最優(yōu)值平均值標(biāo)準(zhǔn)偏差f1GSO28.719652658025.005654937125.95336960841.0061696844CGSO25.092758431025.000012422225.01147030900.0229016010SGSO25.000128389425.000004512325.00003417240.0000333571f2GSO0.42645973110.36605189460.39695675610.0121966388CGSO0.39845820200.39756180950.39789583010.0001739578SGSO0.39788739720.39789355730.39788974761.685610×10-3f3GSO9.719468×10-37.323000×10-76.468320×10-33.945487×10-3CGSO9.715969×10-31.042800×10-61.509961×10-32.534505×10-3SGSO9.612232×10-32.024430×10-51.287434×10-31.934834×10-3f4GSO3.274988×10-18.202069×10-66.464649×10-39.416946×10-3CGSO5.299788×10-24.500000×10-99.298425×10-31.294901×10-2SGSO5.271268×10-59.358547×10-74.702712×10-52.436587×10-3

4 SGSO在危橋檢測(cè)路徑規(guī)劃的應(yīng)用

本文針對(duì)的非結(jié)構(gòu)環(huán)境為存在隱患的危橋部分橋面，其模型參數(shù)為：截取部分長(zhǎng)度L1=8 m，寬度L2=6 m，橋面隨機(jī)存在5到9個(gè)位置未知、尺寸未知的障礙。為驗(yàn)證本文算法不受障礙物分布的隨機(jī)性的影響，選取6次不同障礙分布的情景分別進(jìn)行路徑規(guī)劃。機(jī)器人出發(fā)點(diǎn)的坐標(biāo)為(0,3)，計(jì)算機(jī)器人移動(dòng)到目標(biāo)點(diǎn)(8,3)的路徑。通過SGSO對(duì)目標(biāo)函數(shù)進(jìn)行100次優(yōu)化，在100次優(yōu)化結(jié)果中移動(dòng)路徑的各類值，從而得出路徑規(guī)劃的最優(yōu)解。

圖5是SGSO在6類不同障礙分布的危橋橋面路徑規(guī)劃結(jié)果。圖5(a) ～(b)中分別隨機(jī)分布了5個(gè)障礙物，代表障礙物較少的橋面，結(jié)合表4的數(shù)據(jù)，與GSO算法相比，SGSO的平均路徑分別縮短了0.97%和1.8%；圖5(c) ～(d)中分別隨機(jī)分布了7個(gè)障礙物，代表障礙物較多的橋面，平均路徑分別縮短了1.2%和1.7%；圖5(e) ～(f)中代表含陷阱障礙物，平均路徑分別縮短了1.9%和2.2%，避開陷阱的成功率為100%。此外，GSO算法生成的路徑在靠近圓形或橢圓形時(shí)距離障礙物較近，而靠近直角或銳角障礙時(shí)較遠(yuǎn)；SGSO生成路徑距離各類障礙的距離具有較好的一致性。

圖5 不同障礙分布類型下不同算法路徑規(guī)劃結(jié)果Fig. 5 Path planning results of different algorithms under different obstacle distribution types

傳統(tǒng)路徑規(guī)劃中機(jī)器人的移動(dòng)路徑多與障礙物相切，本文模型建立的過程中加入了安全系數(shù)，優(yōu)化后的路徑與障礙物之間保持了一定的間隙，該方式使移動(dòng)距離略有增加，但極大地降低了與障礙物沖撞的概率，提高了運(yùn)動(dòng)過程的安全性。為進(jìn)一步觀察SGSO關(guān)于運(yùn)動(dòng)效率與避障能力的兼顧性，選取了兩處含尖銳障礙物的局部細(xì)節(jié)圖，以觀察SGSO的路徑規(guī)劃表現(xiàn)，如圖6所示。從圖6中可以看出來，相比通過GSO算法，通過SGSO所生成的路徑在拐點(diǎn)處與障礙物所保持的距離更加穩(wěn)定，且路徑具備更好的光滑度，減小了機(jī)器人過彎的轉(zhuǎn)角調(diào)整，有利于避免機(jī)器人運(yùn)動(dòng)狀態(tài)振蕩。

圖6 不同障礙物分布類型下局部路徑細(xì)節(jié)Fig. 6 Local paths details under under different obstacle distribution types

由于模型的建立不受障礙的位置、性質(zhì)的影響，GSO算法和SGSO皆可以在障礙物隨機(jī)分布的橋面完成移動(dòng)機(jī)器人的路徑規(guī)劃。通過數(shù)據(jù)對(duì)比，SGSO的求解精度和迭代穩(wěn)定性皆高于GSO算法。

表4 GSO與SGSO算法路徑規(guī)劃結(jié)果Tab. 4 Path planning results of GSO and SGSO algorithms

5 結(jié)語

為克服傳統(tǒng)螢火蟲算法易陷入局部最優(yōu)解、早熟、精度低等缺點(diǎn)，本文提出情景螢火蟲算法(SGSO)，用于在非環(huán)境結(jié)構(gòu)下為移動(dòng)機(jī)器人提供可行的路徑規(guī)劃策略。該算法基于混沌映射的歷遍性、隨機(jī)性和規(guī)律性實(shí)現(xiàn)種群初始化，通過黃金比分割法優(yōu)化提高種群的多樣性和機(jī)動(dòng)性，并引入螢火蟲“天敵”的情景理解改善個(gè)體的選擇閾值和精度，進(jìn)化螢火蟲的選擇機(jī)制。通過標(biāo)準(zhǔn)函數(shù)的仿真實(shí)驗(yàn)及對(duì)比分析可知，SGSO比GSO算法及同類算法具備更高的求解精度、穩(wěn)定性和迭代效率，種群的最終分布位置均收斂于最優(yōu)解附近；危橋檢測(cè)應(yīng)用的結(jié)果也驗(yàn)證了所提算法的可行性和有效性。

實(shí)際的非結(jié)構(gòu)環(huán)境具備更多不確定性，下一步將在建模的過程中考慮傳感器的時(shí)滯性、測(cè)量過程的非線性誤差以及邊界條件的變化，進(jìn)一步探索SGSO在非結(jié)構(gòu)環(huán)境中的理論研究和應(yīng)用意義。

References)

[1] LI C, JIANG X, WANG W, et al. A simplified car-following model based on the artificial potential field [J]. Procedia Engineering, 2016, 137: 13-20.

[2] KRISHNANAND K N, GHOSE D. A glowworm swarm optimization based multi-robot system for signal source localization [M]// Design and Control of Intelligent Robotic Systems. Berlin: Springer, 2009: 49-68.

[3] 郁書好,蘇守寶.混沌螢火蟲優(yōu)化算法的研究及應(yīng)用[J].計(jì)算機(jī)科學(xué)與探索,2014,8(3):352-358.(YU S H, SU S B. Research and application of chaotic glowworm swarm optimization algorithm [J]. Journal of Frontiers of Computer Science and Technology,2014, 8(3): 352-358.)

[4] LIAO W H, KAO Y C, LI Y S. A sensor deployment approach using glowworm swarm optimization algorithm in wireless sensor networks [J]. Expert Systems with Applications, 2011, 38(10): 12180-12188.

[5] MARINAKI M, MARINAKIS Y. Glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands [J]. Expert Systems With Applications, 2016, 46(C): 145-163.

[6] ZHANG H, LIU Y B, ZHAO J, et al. Development of a bionic hexapod robot for walking on unstructured zerrain [J]. Journal of Bionic Engineering, 2014, 11(2): 176-187.

[7] 于乃功,鄭宇凌,徐麗,等.基于光流的非結(jié)構(gòu)化環(huán)境中移動(dòng)機(jī)器人避障方法[J].北京工業(yè)大學(xué)學(xué)報(bào),2017,43(1):65-69.(YU N G, ZHENG Y L, XU L, et al. Optical flow based mobile robot obstacle avoidance method in unstructured environment [J]. Journal of Beijing Universityof Technology, 2017, 43(1): 65-69.)

[8] 劉佳,梁秋麗,王書青,等.基于模擬退火算法的螢火蟲群優(yōu)化算法研究[J].計(jì)算機(jī)仿真,2014,31(5):284-288.(LIU J, LIANG Q L, WANG S Q, et al. Research on improved glowworm swarm optimization algorithm based on simulated annealing algorithm [J]. Computer Simulation, 2014, 31(5): 284-288.)

[9] ORAMUS P. Improvements to glowworm swarm optimization algorithm [J]. Computer Science, 2010, 11: 7-20.

[10] 羅天洪,陳才,李富盈.基于時(shí)變螢火蟲群算法的冗余機(jī)器人手臂逆解[J].計(jì)算機(jī)集成制造系統(tǒng),2016,22(2):576-582.(LUO T H, CHEN C, LI F Y. Inverse solution of redundant robot arm based on glow-worm swarm optimization algorithm of time-varying [J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 576-582.)

[11] DING S, AN Y, ZHANG X, et al. Wavelet twin support vector machines based on glowworm swarm optimization [J]. Neurocomputing, 2017, 225(C): 157-163.

[12] CUI H, FENG J, GUO J, et al. A novel single multiplicative neuron model trained by an improved glowworm swarm optimization algorithm for time series prediction [J]. Knowledge-Based Systems, 2015, 88(C): 195-209.

[13] 孫波,陳衛(wèi)東,席裕庚.基于粒子群優(yōu)化算法的移動(dòng)機(jī)器人全局路徑規(guī)劃[J].控制與決策,2005,20(9):1052-1055,1060.(SUN B, CHEN W D, XI Y G. Particle swarm optimization based global path planning for mobile robots [J]. Control and Decision, 2005, 20(9): 1052-1055, 1060.)

This work is partially supported by the National Natural Science Foundation of China (51375519).

LUOTianhong,born in 1975, Ph.D., professor. His research interests include robotics, mechatronics.

LIANGShuang, born in 1993, M. S. candidate. His research interests include robot dynamics and system control.

HEZeyin, born in 1985, Ph. D.,associate professor. His research interests include mechanical design and theory, mechanical reliability analysis.

ZHANGXia,born in 1982, Ph. D., associate professor. Her research interests include robot control method and theory, exoskeleton motion assisted robot.

Pathplanningofrobotbasedonglowwormswarmoptimizationalgorithmofsceneunderstanding

LUO Tianhong, LIANG Shuang*, HE Zeyin, ZHANG Xia

(SchoolofMechanotronicsandVehicleEngineering,ChongqingJiaotongUniversity,Chongqing400074,China)

Against at the problems of oscillation and poor adaptability of robot motion state in the path planning of traditional unstructured environment, a new path planning strategy based on Glowworm Swarm Optimization algorithm of Scene understanding (SGSO) was proposed. The initialization was realized based on the regularity, randomness and generalization of chaotic systems, and golden section method was used for later optimization, which improved the diversity of the population, suppressed the premature and local convergence of the algorithm. And, by introducing scene understanding of glowworm “natural enemy”, the selection mechanism of glowworm swarm was optimized to solve the grounding phenomenon of glowworm in the process of tracing under unstructured environment, which enhanced the adaptability and robustness of the algorithm. The simulation results of four test functions show that, the proposed algorithm is superior to the basic Glowworm Swarm Optimization (GSO) algorithm in solving precision and convergence efficiency. The proposed algorithm was applied to the path planning of mobile robots in unstructured environment, the test results show that the planning path based on SGSO was shorter and the corner was more smooth, which could effectively avoid the additional load on power system caused by large angle steering of robot, verifying the feasibility and effectiveness of the proposed algorithm.

Glowworm Swarm Optimization (GSO) algorithm; path planning; unstructured environment; grounding phenomenon; mobile robot

2017- 05- 08;

2017- 06- 20。

國(guó)家自然科學(xué)基金資助項(xiàng)目(51375519)。

羅天洪(1975—)，男，四川樂至人，教授，博士，主要研究方向：機(jī)器人、機(jī)電一體化； 梁爽(1993—)，男，重慶人，碩士研究生，主要研究方向：機(jī)器人動(dòng)力學(xué)與系統(tǒng)控制； 何澤銀(1985—)，男，四川遂寧人，副教授，博士，主要研究方向：機(jī)械設(shè)計(jì)及理論、機(jī)械可靠性分析；張霞(1982—)，女，重慶銅梁人，副教授，博士，主要研究方向：機(jī)器人控制方法與理論、外骨骼運(yùn)動(dòng)輔助機(jī)器人。

1001- 9081(2017)12- 3608- 06

10.11772/j.issn.1001- 9081.2017.12.3608

(*通信作者電子郵箱137377539@qq.com)

TP391.9;TP242

A