基于神經(jīng)過程-粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃

馬 燁,王淑青，毛月祥

(1 湖北工業(yè)大學(xué)電氣與電子工程學(xué)院，湖北 武漢 430068；2 國(guó)網(wǎng)湖北省電力有限公司直流運(yùn)檢公司，湖北 武漢 430050)

移動(dòng)機(jī)器人路徑規(guī)劃問題一直是機(jī)器人導(dǎo)航領(lǐng)域的研究熱點(diǎn)。移動(dòng)機(jī)器人路徑規(guī)劃是指機(jī)器人根據(jù)起點(diǎn)和終點(diǎn)坐標(biāo)信息，搜索出一條能耗低、用時(shí)少、距離短，并且能避開所有障礙物的有效路徑。PSO是模擬鳥類捕食的一種智能隨機(jī)搜索算法[1]。相對(duì)于蟻群算法、遺傳算法等，標(biāo)準(zhǔn)PSO算法具有易于實(shí)現(xiàn)、參數(shù)較少等優(yōu)點(diǎn)，但是基本PSO算法存在早熟和局部收斂，后期算法多樣性降低，算法精度得不到提升等問題，為此國(guó)內(nèi)外相關(guān)作者做了大量研究，并提出了各種改進(jìn)算法。趙甜甜引入細(xì)菌覓食優(yōu)化算法和PSO算法結(jié)合，縮短了搜索時(shí)間，減少了迭代次數(shù)[2]。賈會(huì)群等引入雞群算法的母雞更新方程和小雞更新方程對(duì)搜索停滯的粒子進(jìn)行擾動(dòng)，使粒子向全局最優(yōu)解靠近[3]。蒲興成等將反向策略引入PSO算法，提高了粒子群算法的尋優(yōu)能力和穩(wěn)定性[4]。綜上所述，制定有效的機(jī)制使粒子逃離局部最小值并提高收斂精度是提高粒子群算法性能的關(guān)鍵。本文提出了神經(jīng)過程-粒子群混合算法的移動(dòng)機(jī)器人路徑規(guī)劃。首先建立環(huán)境模型，在傳統(tǒng)粒子群算法的基礎(chǔ)上，引入神經(jīng)過程預(yù)測(cè)每一代粒子的個(gè)體位置，在保證粒子多樣性的同時(shí)，增加了粒子擺脫局部最優(yōu)的能力。最后對(duì)基于神經(jīng)過程-粒子群混合算法和傳統(tǒng)粒子群算法進(jìn)行了仿真實(shí)驗(yàn)，仿真結(jié)果驗(yàn)證了本文算法在路徑規(guī)劃應(yīng)用上的優(yōu)越性和可行性。

1 路徑規(guī)劃

1.1 路徑規(guī)劃問題描述

由于啟發(fā)式智能技術(shù)可以有效地解決約束優(yōu)化問題，所以把路徑規(guī)劃問題轉(zhuǎn)化為約束優(yōu)化問題是目前常用的一種方式[5]。通過建立路徑長(zhǎng)度、平滑度、碰撞距離等約束函數(shù)，將尋找最優(yōu)路徑轉(zhuǎn)化為尋找函數(shù)最優(yōu)值，從而實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃。

1.2 環(huán)境建模

目前基本的環(huán)境建模方法主要有柵格法、可視圖法和拓?fù)浞ǖ萚6]。其中可視圖法通過映射環(huán)境信息為幾何形狀，可以簡(jiǎn)化路徑規(guī)劃為尋找最短路線的約束優(yōu)化問題，因此本文采取可視圖法進(jìn)行環(huán)境建模。圖1為移動(dòng)機(jī)器人路徑規(guī)劃的環(huán)境模型。在該模型中，障礙物以不同形狀和大小的實(shí)體的形式呈現(xiàn),通過建立起點(diǎn)S到終點(diǎn)T的局部坐標(biāo)系S-X′Y′，由D條垂直于X′的直線L1～LD將路徑平均分成D+1段，在垂直線Li(i=1,2,…,D)上隨機(jī)選取一個(gè)沒有碰撞的節(jié)點(diǎn)Pi，構(gòu)成一條完整的路徑

Ppatp={P1-S,…,PD-PD-1,T-PD}

要得到全局坐標(biāo)系O-X′Y′中路徑上的任意點(diǎn)，需要得到局部坐標(biāo)系與全局坐標(biāo)系之間的變換矩陣。x′(d),y′(d)在局部坐標(biāo)系上可以轉(zhuǎn)化為在全局坐標(biāo)系統(tǒng)的x(d),y(d)，轉(zhuǎn)換方程如下

圖1 移動(dòng)機(jī)器人路徑規(guī)劃的環(huán)境模型

1.3 建立適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評(píng)價(jià)移動(dòng)機(jī)器人路徑規(guī)劃的性能，其中主要有三個(gè)性能指標(biāo)：路徑長(zhǎng)度、安全性和路徑平滑性。在本文中，路徑長(zhǎng)度和平滑度相結(jié)合，用于評(píng)價(jià)移動(dòng)機(jī)器人的路徑規(guī)劃性能標(biāo)準(zhǔn)。適應(yīng)度函數(shù)如下

F(P)=ω1·L(P)+ω2·S(P)

其中‖Pi+1-Pi‖表示Pi到Pi+1的歐氏距離。αi表示路徑生成的第i個(gè)偏轉(zhuǎn)角(弧度范圍為0到π)，(Pi-Pi-1)·(Pi+1-Pi)表示(Pi-Pi-1)和(Pi+1-Pi)向量之間的內(nèi)積,|Pi-Pi-1|和|Pi+1-Pi|表示向量范數(shù)。ω1和ω2分別對(duì)應(yīng)路徑長(zhǎng)度和平滑度的權(quán)重系數(shù)。

2 神經(jīng)過程-粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃

2.1 神經(jīng)過程

神經(jīng)過程(NPs)是一個(gè)基于神經(jīng)網(wǎng)絡(luò)的公式，它學(xué)習(xí)了一個(gè)隨機(jī)過程的近似，是一類結(jié)合了神經(jīng)網(wǎng)絡(luò)和隨機(jī)過程優(yōu)點(diǎn)的模型[7]。NPs顯示了高斯過程的一些基本特性，即對(duì)函數(shù)分布進(jìn)行建模，能夠根據(jù)觀察樣本點(diǎn)來估計(jì)預(yù)測(cè)的不確定性，并將一些工作負(fù)載從訓(xùn)練轉(zhuǎn)移到測(cè)試時(shí)間，給予了模型的靈活性，而且NPs可以以更高的效率生成預(yù)測(cè)。在給定n個(gè)樣本點(diǎn)和m個(gè)目標(biāo)點(diǎn)的情況下，經(jīng)過訓(xùn)練的神經(jīng)過程推理對(duì)應(yīng)于深度神經(jīng)網(wǎng)絡(luò)中的正向傳遞，深度神經(jīng)網(wǎng)絡(luò)的尺度為o(n+m)，遠(yuǎn)少于經(jīng)典高斯過程中的o(n+m)3。

(a)神經(jīng)過程的圖形模型

(b)神經(jīng)過程執(zhí)行圖圖2

圖2a中x和y對(duì)應(yīng)于函數(shù)y=f(x)的數(shù)據(jù)。C和T分別為樣本點(diǎn)和目標(biāo)點(diǎn)的個(gè)數(shù)，z為全局潛在變量?；疑尘氨硎居^察到該變量。圖2b中圓圈的變量對(duì)應(yīng)于圖2a中的圖形模型中的變量，方框中的變量對(duì)應(yīng)于NPs的中間表示形式，粗體字母對(duì)應(yīng)于以下計(jì)算模塊:h-編碼器、a-聚集器和g-解碼器。在實(shí)現(xiàn)過程中，h和g對(duì)應(yīng)于神經(jīng)網(wǎng)絡(luò)，a對(duì)應(yīng)于均值函數(shù)。連續(xù)線描述生成過程，虛線描述推理過程。

在執(zhí)行神經(jīng)過程期間必須考慮兩個(gè)條件：樣本點(diǎn)順序的不變性和計(jì)算效率。得到的模型可以歸結(jié)為以下三個(gè)模塊(圖1b):

1)從輸入空間到表示空間的編碼器模塊h，h被參數(shù)化為一個(gè)神經(jīng)網(wǎng)絡(luò)，它接受一對(duì)(x,y)的樣本點(diǎn)，ri=h((x,y)i)為編碼器h對(duì)每一對(duì)樣本點(diǎn)產(chǎn)生的一個(gè)對(duì)應(yīng)的輸出。

2.2 粒子群算法

粒子群優(yōu)化算法(PSO)最基本的算法模型就是帶慣性權(quán)重的PSO模型[8]。其模型描述為

其中c1和c2為學(xué)習(xí)因子；r1和r2為[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)；v和x分別為粒子速度和位置，t為代數(shù)，i為粒子編號(hào)，d為空間維數(shù)，p(p-best)i和pg-best分別為個(gè)體和群體的最優(yōu)點(diǎn)；ω是慣性因子。

2.3 神經(jīng)過程-粒子群算法

粒子群的運(yùn)動(dòng)過程是一個(gè)隨機(jī)過程，而神經(jīng)過程是學(xué)習(xí)一個(gè)隨機(jī)過程的近似，將每一次迭代過程中各個(gè)粒子的位置和神經(jīng)過程輸出的粒子預(yù)測(cè)位置保存為樣本點(diǎn)，粒子的位置和預(yù)測(cè)位置與當(dāng)前全局最優(yōu)點(diǎn)差值最小的點(diǎn)作為目標(biāo)點(diǎn)，這樣在迭代過程中不斷進(jìn)行，粒子可以快速找到當(dāng)前全局最優(yōu)點(diǎn)，并且粒子也不會(huì)喪失其多樣性，在神經(jīng)過程的不斷預(yù)測(cè)中，跳出局部最優(yōu)。神經(jīng)過程-粒子群算法可以保證粒子的多樣性，顯著減少預(yù)測(cè)過程的計(jì)算量，提高算法速度的同時(shí)避免算法陷入局部最優(yōu)。算法描述為

xi+1=f(xi),C={xi,x2,…,xT-1}

yT=g(xT)

其中:函數(shù)f(x)為粒子群的運(yùn)動(dòng)過程；gx為參數(shù)化的神經(jīng)網(wǎng)絡(luò)即神經(jīng)過程；xi為第i次迭代時(shí)的粒子位置；C為目標(biāo)點(diǎn)集，包含了第1次迭代至第T-1次迭代時(shí)粒子位置的集合；xT為當(dāng)前迭代次數(shù)T時(shí)的目標(biāo)位置；yT為得到的預(yù)測(cè)位置。

2.4 實(shí)現(xiàn)流程

神經(jīng)過程-粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃的流程見圖3。

圖3 神經(jīng)過程-粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃

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

本文選取常見的Rastrigin函數(shù)驗(yàn)證算法的全局尋優(yōu)能力。Rastringin函數(shù)有非常多的局部極小點(diǎn)，而僅僅只有一個(gè)全局最小點(diǎn)，這個(gè)點(diǎn)就是(0,0)，在該點(diǎn)處的函數(shù)值為0，因此該函數(shù)被用來評(píng)價(jià)算法的優(yōu)化性能。圖4為函數(shù)的運(yùn)行結(jié)果，本文算法在迭代42次時(shí)達(dá)到最優(yōu)解，而傳統(tǒng)PSO算法在迭代38次陷入局部最小值，經(jīng)過200次迭代仍然不能達(dá)到全局最小值。

圖4 Rastrigin函數(shù)運(yùn)行圖

隨機(jī)生成一組具有多個(gè)障礙物的700×700地圖進(jìn)行仿真實(shí)驗(yàn)。仿真參數(shù)如下:粒子的個(gè)數(shù)為N=100,維度D=10,加速因子c1=c2=1.4962,最大迭代次數(shù)MaxDT=200。

由圖5與圖7所示的傳統(tǒng)PSO算法和圖6與圖8所示的本文神經(jīng)過程-粒子群算法可知，兩種算法都能從起始點(diǎn)避開障礙物到達(dá)終點(diǎn)，但是傳統(tǒng)PSO算法規(guī)劃出的路徑經(jīng)過了較多的障礙物邊緣，并且選擇的不是最優(yōu)并且最短的路徑。本文提出的NPPSO算法從平滑度和長(zhǎng)度而言，均優(yōu)于傳統(tǒng)PSO算法規(guī)劃出的路徑，有效地避免了與障礙物邊緣相切的非最優(yōu)路徑。

圖5 傳統(tǒng)粒子群算法路徑規(guī)劃仿真

圖6 本文算法路徑規(guī)劃仿真

圖7 傳統(tǒng)粒子群算法路徑規(guī)劃仿真

圖8 本文算法路徑規(guī)劃仿真

4 結(jié)束語

本文提出了一種基于神經(jīng)過程-粒子群算法的移動(dòng)機(jī)器人的路徑規(guī)劃，通過在粒子群的迭代過程中引入預(yù)測(cè)運(yùn)動(dòng)的神經(jīng)過程思想，保證了粒子的多樣性，避免陷入局部最優(yōu)。采用Rastrigin函數(shù)對(duì)本文算法進(jìn)行性能評(píng)估，取得了良好的測(cè)試結(jié)果，并且在隨機(jī)建立的環(huán)境模型下，能夠有效、準(zhǔn)確地得到目標(biāo)點(diǎn)的路徑。