周佳加, 張 強, 王宏健, 張洪泉, 王瑩瑩

(哈爾濱工程大學 自動化學院,黑龍江 哈爾濱 150001)

0 引 言

隨著機器人技術(shù)的發(fā)展,多機器人編隊的需求與日俱增,其中最基本的行為是編隊,其主要解決機器人之間協(xié)調(diào)問題。編隊涉及到每個機器人的路徑規(guī)劃,即在一定約束下,編隊中的每個成員從規(guī)劃空間中尋找出從初始姿態(tài)到期望位置的路徑。當編隊任務有時間約束時,快速形成指向任務點的編隊,有效節(jié)省了完成任務的時間,且增強了編隊任務的機動性。1957年Dubins提出[1]在某個曲率的約束的條件下,可在同一平面內(nèi)尋找出任意兩個矢量點的最短路徑。Yeol J W 等人[2]采用Dubins路徑的方法求取了二維水平面兩點間的最短路徑,并通過微積分將這種方法給予了證明。Teng L等人[3]提出了一種多無人機攻擊多個地面目標的任務規(guī)劃方法。戴健等人[4]采用“Z”型路徑覆蓋方法以及Dubins轉(zhuǎn)彎路徑,對各個無人機開展覆蓋其子區(qū)域的搜索路徑規(guī)劃。Peng C等人[5]提出了一種具有姿態(tài)約束的移動機器人路徑規(guī)劃方法規(guī)劃出一條無障礙路徑。胡永文等人[6]針對每個人和任務的最短時限指派問題提出求解最短時限指派問題的快速決策方法。Burgard W 等人[7]采用匈牙利算法求解出了最優(yōu)分配方法。宗群等人[8]通過粒子群和遺傳優(yōu)化算法雙層優(yōu)化解決大規(guī)模集群編隊中隊形選擇和站位分配問題。

本文對多機器人編隊路徑規(guī)劃問題進行分析,根據(jù)編隊時間、編隊位置分配等約束建立了相應的問題模型,設計了將粒子群優(yōu)化(particle swarm optimization,PSO)與連續(xù)Hopfield神經(jīng)網(wǎng)絡(continuous Hopfield neural network,CHNN)的雙層路徑優(yōu)化的方法求解出最優(yōu)編隊方法。最后通過仿真實驗驗證了本文提出方法的有效性。

1 多機器人編隊問題描述與建模

假設機器人初始隊形中編隊成員在地面坐標系下第i(i=1,2,…,n)個機器人的坐標表示為(xi,yi),ψd表示期望編隊方向,而機器人路徑規(guī)劃空間由機器人最大航程決定。

定義雙層規(guī)劃模型為

(1)

式中P和L為雙層優(yōu)化結(jié)果,f和g為優(yōu)化模型的性能指標,G為優(yōu)化模型的約束指標,a1,a2,…為優(yōu)化有關(guān)參數(shù)。

1.1 約束指標

在多機器人編隊中,根據(jù)機器人的欠驅(qū)動性和任務,還需考慮以下四個約束[9,10]：

1)編隊到達期望隊形時的位置與航向約束

(2)

2)編隊過程的能耗約束

(3)

式中W為編隊過程中機器人總能耗,li為機器人i的路徑長度,k1為常數(shù)。

3)機器人最小轉(zhuǎn)彎半徑的約束

最小轉(zhuǎn)彎半徑用如下公式表示

ρmin=f(max,U)

(4)

4)編隊時間約束

假設在編隊過程中機器人速度v沒有太大波動,則定義參數(shù)k2=1/v,編隊時間定義為

T=k2lmax

(5)

式中l(wèi)max為路徑最長的機器人路徑長度。

1.2 優(yōu)化目標

在三角編隊中,選取編隊完成期望點Pk,再計算第i個機器人到達期望編隊中第j個位置的距離lij,進而計算出編隊過程的總耗費(總路徑)定義優(yōu)化目標函數(shù)

(6)

式中Wmin為編隊集結(jié)點k下的最少能耗,lall為所有機器人到編隊中期望位置的路徑總長度,Tmin為最短編隊時間,lij為機器人i到編隊中期望位置j的路徑長度。

2 雙層路徑優(yōu)化算法

2.1 基于PSO的編隊集結(jié)點優(yōu)化

假設由m個粒子組成的種群X=(x1,x2,…,xm)在搜索空間D中,則第i個粒子在k+1次迭代時速度和位置更新方法為

(7)

式中w為慣性權(quán)重；d=1,2,…,D；i=1,2,…,m;k為迭代次數(shù)；Vid為粒子的速度；c1和c2為非負的常數(shù),稱為加速度因子；r1和r2為分布于[0,1]之間的隨機數(shù)。將位置和速度分別限制在[-Xmax,Xmax],[-Vmax,Vmax]之間。

為了更好平衡算法全局搜索和局部搜索的能力,本文設置權(quán)重為遞減形式[11],初始權(quán)重為ws,終止權(quán)重為we,則權(quán)重的更新方式為

(8)

2.2 基于CHNN的路徑優(yōu)化

在編隊虛擬集結(jié)點Pk約束下,設n個機器人和編隊期望位置,第i個機器人為Ri,機器人編隊中第j個位置為R′j,j=1,2,…，n,在編隊虛擬集結(jié)點Pk下Ri到R′j的路徑距離為lkij。則系數(shù)矩陣為

(9)

引入變量xkij

(10)

指派每個機器人到相應位置的最優(yōu)分配問題的模型為

(11)

(12)

其中,在k(k=1,2,…,m)個編隊虛擬集結(jié)點下每個機器人在總路徑最少的約束下到達期望位置的最優(yōu)位置分配方法。式(12)表示矩陣Xk=(xkij)n×n的行列約束和取值范圍。

將每個機器人從初始位置i到編隊虛擬集結(jié)點Pk隊形中的位置j作為一個變量,每個神經(jīng)元處理一個變量xkij,故整個網(wǎng)絡中神經(jīng)元個數(shù)xkij應該個數(shù)相等。

則神經(jīng)網(wǎng)絡的能量函數(shù)Ek[12]

(13)

式中λ1,λ2為拉格朗日加權(quán)系數(shù)。能量函數(shù)前兩項為行列約束,使得xkij每行每列有且僅有一個1,即每個機器人對應一個期望隊形中的位置；第三項表示總能量耗費約束,即整體路徑最短。

(14)

式中xkij為神經(jīng)元(i,j)的輸出,ukij為神經(jīng)元(i,j)的輸入,xkij=f(ukij),f函數(shù)為神經(jīng)元(i,j)的輸出函數(shù),可以有不同的規(guī)律,這里選取Sigmoid函數(shù)

(15)

網(wǎng)絡輸入初始化

ukij(t)=u0ln(n-1)+δkij

(16)

其中,設置u0=0.1；n為機器人數(shù)量,δkij為區(qū)間[0,1]的隨機數(shù)；導入優(yōu)化參數(shù)lkij。

網(wǎng)絡按照下面方式運行

(17)

式中 Δt為單步時間；ukij(t)為t時刻的神經(jīng)元輸入。

2.3 雙層優(yōu)化算法實現(xiàn)

1)初始化粒子群位置和速度,包括權(quán)重wk,加速度因子c1和c2等。2)第一層優(yōu)化計算,以當前粒子位置為編隊集合點,為每個機器人選擇合適的Dubins路徑,并計算系數(shù)矩陣。3)第二層優(yōu)化計算,采用CHNN算法求解在此系數(shù)矩陣下,每組機器人的最優(yōu)位置分配方法和適應度,第二層優(yōu)化結(jié)束。4)根據(jù)適應度更新局部和全局最優(yōu)集結(jié)點,初始優(yōu)化完成。5)根據(jù)迭代次數(shù)更新位置、速度和權(quán)重w(k)。6)以當前粒子位置為編隊集合點,為每個機器人選擇合適的Dubins路徑,并計算系數(shù)矩陣。7)第二層優(yōu)化計算,采用CHNN算法求解每組機器人的最優(yōu)位置和適應度,第二層優(yōu)化結(jié)束。8)根據(jù)PSO迭代次數(shù)判斷迭代是否完成,完成則算法結(jié)束,否則返回步驟(4)。

3 仿真實驗與分析

本文采用MATLAB 2016a進行仿真實驗,規(guī)劃空間為{(xi,yi)|-100≤xi≤500,-100≤yi≤400},3個欠驅(qū)動機器人組成的編隊,轉(zhuǎn)彎半徑ρ=60 m,初始坐標隨機分布在[-100,100],初始方向角為130°,60°,270°,期望編隊能在B=(400,230)前完成編隊。

采用式(7)PSO算法公式更新位置和速度,取100個粒子,進化次數(shù)為200,式(8)中取慣性權(quán)值參數(shù)ws=0.95,we=0.35,學習因子c1=c2=1.5。式(13)、式(14)中,λ1=150,λ2=80,采樣時間取0.001,迭代次數(shù)取1 000。

圖1(a)是靜態(tài)權(quán)重PSO算法求解最優(yōu)編隊集結(jié)點的適應度曲線,在迭代180次時接近最優(yōu)值276,圖1(b)改進PSO算法在迭代20次時接近最優(yōu)值276,求出最優(yōu)編隊集結(jié)點(276,156)。固定慣性權(quán)值全局搜索和局部搜索無法兼顧,時變的慣性權(quán)重則前期有較強的全局搜索能力,后期更有利于精確的局部搜索。

圖1 靜態(tài)/動態(tài)權(quán)重PSO算法適應度曲線

圖2是最優(yōu)編隊集結(jié)點下采用CHNN分配方法的能量函數(shù),從圖中可知CHNN的能量隨著迭代次數(shù)逐漸降低。在能量變化率趨于0時,整個網(wǎng)絡逐漸接近平衡態(tài),則求得的各航行器最優(yōu)分配路徑。

圖2 CHNN能量函數(shù)

圖3為機器人完整的編隊路徑圖,編隊初始位置在圖左下角,指向設定編隊集結(jié)B點前行,并在A點完成編隊。

圖3 改進粒子群算法路徑仿真

4 結(jié) 論

針對多機器人編隊集結(jié)點的優(yōu)化問題,本文提出了一種多機器人編隊雙層規(guī)劃模型。第一層解決了最優(yōu)隊形編隊集結(jié)點規(guī)劃問題,在時間約束上采用改進PSO算法求取在編隊時間最短的最優(yōu)編隊集合點,并利用動態(tài)遞減的權(quán)重平衡了PSO算法全局與局部的搜索能力。第二層解決了編隊中成員位置分配問題,基于Dubins路徑采用CHNN算法將編隊中的機器人成員以最小能耗的條件下分配到最優(yōu)位置。最后,通過欠驅(qū)動機器人的編隊仿真實驗表明所提算法正確、有效。