馬 燁,王淑青，毛月祥

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

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

1 路徑規(guī)劃

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

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

1.2 環(huán)境建模

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

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

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

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

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

適應(yīng)度函數(shù)用于評價移動機(jī)器人路徑規(guī)劃的性能，其中主要有三個性能指標(biāo)：路徑長度、安全性和路徑平滑性。在本文中，路徑長度和平滑度相結(jié)合，用于評價移動機(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個偏轉(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分別對應(yīng)路徑長度和平滑度的權(quán)重系數(shù)。

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

2.1 神經(jīng)過程

神經(jīng)過程(NPs)是一個基于神經(jīng)網(wǎng)絡(luò)的公式，它學(xué)習(xí)了一個隨機(jī)過程的近似，是一類結(jié)合了神經(jīng)網(wǎng)絡(luò)和隨機(jī)過程優(yōu)點的模型[7]。NPs顯示了高斯過程的一些基本特性，即對函數(shù)分布進(jìn)行建模，能夠根據(jù)觀察樣本點來估計預(yù)測的不確定性，并將一些工作負(fù)載從訓(xùn)練轉(zhuǎn)移到測試時間，給予了模型的靈活性，而且NPs可以以更高的效率生成預(yù)測。在給定n個樣本點和m個目標(biāo)點的情況下，經(jīng)過訓(xùn)練的神經(jīng)過程推理對應(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對應(yīng)于函數(shù)y=f(x)的數(shù)據(jù)。C和T分別為樣本點和目標(biāo)點的個數(shù)，z為全局潛在變量。灰色背景表示觀察到該變量。圖2b中圓圈的變量對應(yīng)于圖2a中的圖形模型中的變量，方框中的變量對應(yīng)于NPs的中間表示形式，粗體字母對應(yīng)于以下計算模塊:h-編碼器、a-聚集器和g-解碼器。在實現(xiàn)過程中，h和g對應(yīng)于神經(jīng)網(wǎng)絡(luò)，a對應(yīng)于均值函數(shù)。連續(xù)線描述生成過程，虛線描述推理過程。

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

1)從輸入空間到表示空間的編碼器模塊h，h被參數(shù)化為一個神經(jīng)網(wǎng)絡(luò)，它接受一對(x,y)的樣本點，ri=h((x,y)i)為編碼器h對每一對樣本點產(chǎn)生的一個對應(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為粒子編號，d為空間維數(shù)，p(p-best)i和pg-best分別為個體和群體的最優(yōu)點；ω是慣性因子。

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

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

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

yT=g(xT)

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

2.4 實現(xiàn)流程

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

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

3 仿真實驗與分析

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

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

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

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

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

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

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

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

4 結(jié)束語

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