宋 宇, 王志明

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

0 引 言

隨著科學(xué)技術(shù)的不斷發(fā)展，無(wú)人機(jī)的應(yīng)用領(lǐng)域不斷擴(kuò)大，從地質(zhì)勘探到無(wú)人機(jī)快遞，無(wú)人機(jī)路徑規(guī)劃都是一項(xiàng)重要的技術(shù)指標(biāo)。

無(wú)人機(jī)路徑規(guī)劃指的是尋找一條或幾條從給定起點(diǎn)到給定終點(diǎn)的最優(yōu)路徑，路徑的優(yōu)劣程度一般由路徑長(zhǎng)度，所經(jīng)過(guò)的威脅區(qū)域如雷達(dá)威脅區(qū)的路徑長(zhǎng)度等決定的。對(duì)路徑規(guī)劃的研究開(kāi)始于20世紀(jì)60年代，期間國(guó)內(nèi)外學(xué)者提出了大量的路徑規(guī)劃方法，包括蟻群算法[1]、粒子群算法[2]、A*算法、Laguerre圖法[3]、PRM算法、人工勢(shì)場(chǎng)法等。文獻(xiàn)[1]采用蟻群算法對(duì)路徑規(guī)劃中的參數(shù)設(shè)置進(jìn)行了研究，文獻(xiàn)[2]提出了基于線性慣性權(quán)重與自然選擇算法的優(yōu)化粒子群算法的無(wú)人機(jī)航跡規(guī)劃，文獻(xiàn)[3]提出了一種基于Delaunay圖的Laguerre圖構(gòu)造算法,證明了當(dāng)兩個(gè)威脅源不相交時(shí)，Laguerre圖生成的備選航路必然從它們之間的空隙內(nèi)穿過(guò)，文獻(xiàn)[4]提出一種障礙物邊界點(diǎn)設(shè)置與平滑算法，文獻(xiàn)[5]利用距離傳感器采用模糊控制的方法進(jìn)行了路徑規(guī)劃研究。對(duì)于三維路徑規(guī)劃問(wèn)題，目前提出的各算法在不同的應(yīng)用場(chǎng)景中各有優(yōu)劣，例如蟻群算法與粒子群算法均易陷入局部最優(yōu)解，A*算法與PRM算法不能保證找到的路徑為全局最優(yōu)路徑，人工勢(shì)場(chǎng)法存在目標(biāo)點(diǎn)不可達(dá)及障礙物邊界附近振蕩的問(wèn)題。WDO算法[6]是一種新的自然啟發(fā)式基于大氣運(yùn)動(dòng)的全局優(yōu)化算法，模擬無(wú)限小的空氣塊遵循牛頓第二定律運(yùn)動(dòng)規(guī)律優(yōu)化目標(biāo)函數(shù)，文中采用WDO算法對(duì)無(wú)人機(jī)進(jìn)行路徑規(guī)劃方法研究[7]。

1 粒子群算法

粒子群優(yōu)化算法由Kennedy和Eberhart在1995年提出，啟發(fā)來(lái)自對(duì)鳥(niǎo)類捕食問(wèn)題的研究，每個(gè)粒子都代表一個(gè)可能解，通過(guò)個(gè)體最優(yōu)與全體最優(yōu)不斷迭代找到待優(yōu)化函數(shù)的最優(yōu)解。其速度更新方式如下：

(1)

式中:ω，c1，c2----權(quán)重系數(shù);

r1，r2----隨機(jī)數(shù);

位置更新方程如下：

(2)

1)初始化粒子種群數(shù)量，最大迭代次數(shù)，系數(shù)ω，c1，c2，速度最大值umax，位置邊界值，適應(yīng)度函數(shù)。

2)任意給定每個(gè)粒子的位置與速度值。

3)依次計(jì)算每個(gè)粒子的適應(yīng)度值(每個(gè)可能解的適應(yīng)度值)，得到第一代粒子的局部最優(yōu)粒子與全局最優(yōu)粒子并記錄之。

4)更新所有粒子的速度并檢查速度值是否越界，若越界，規(guī)定為±umax。

5)更新所有粒子的位置并檢查位置是否越界。

6)依次計(jì)算每個(gè)粒子的適應(yīng)度值(每個(gè)可能解的適應(yīng)度值)，得到當(dāng)前代粒子的局部最優(yōu)粒子與全局最優(yōu)粒子并記錄之。比較當(dāng)前最優(yōu)粒子的適應(yīng)度值是否優(yōu)于之前記錄的最優(yōu)適應(yīng)度值，若是，更新局部最優(yōu)粒子與全局最優(yōu)粒子;若否，全局最優(yōu)解與局部最優(yōu)解不變。

7)檢查是否達(dá)到最大迭代次數(shù)，若未達(dá)到,則跳到4);若達(dá)到，算法結(jié)束，最后一次迭代中粒子的全局最優(yōu)位置記為問(wèn)題的最優(yōu)解。

2 WDO算法

WDO優(yōu)化算法是一種基于種群的迭代全局優(yōu)化算法，啟發(fā)來(lái)自大氣中風(fēng)的運(yùn)動(dòng)，空氣塊的每一個(gè)位置代表一個(gè)可能解，空氣塊的每一個(gè)速度代表可能解的變化量。每個(gè)空氣塊的速度更新公式為:

(3)

其中，α為對(duì)前一個(gè)解的保留系數(shù);等式右端第一項(xiàng)類似于大氣中空氣塊受到摩擦力的影響;右端第二項(xiàng)表示空氣塊速度變化中始終有一個(gè)速度分量指向坐標(biāo)原點(diǎn)的方向，類似于空氣塊受到的重力影響，此項(xiàng)的加入有效地避免了空氣塊的位置陷于邊界值;右端第三項(xiàng)中的i為按壓力值(適應(yīng)度函數(shù))排列當(dāng)前所有空氣塊所得的排列序號(hào)，當(dāng)i=1時(shí)壓力值最小(當(dāng)前最優(yōu)解)，該項(xiàng)表示，空氣塊位置越靠近當(dāng)前最優(yōu)解(i與1的差的絕對(duì)值越小),速度的變化越小;右端第四項(xiàng)表示隨機(jī)選擇的其他維速度對(duì)當(dāng)前維速度的影響，i值越小，影響越大，類似于由于地球自轉(zhuǎn)，空氣塊受到的Coriolis力，此隨機(jī)項(xiàng)的加入，增強(qiáng)了算法全局搜索能力?？諝鈮K位置更新公式為：

xnew=xcur+(unewΔt)

(4)

式中:xnew----更新后的位置;

xcur----更新前的位置;

Δt----通常取為1。

為了防止空氣塊速度過(guò)大，導(dǎo)致空氣塊跳過(guò)最優(yōu)位置，通常事先規(guī)定一個(gè)速度最大值umax，并規(guī)定:

(5)

當(dāng)unew=±umax時(shí)，空氣塊位置會(huì)受到速度更新公式右端第二項(xiàng)的影響而被拉回可能解的尋優(yōu)空間。WDO算法計(jì)算步驟如下：

1)初始化空氣塊種群數(shù)量，最大迭代次數(shù)，系數(shù)α，g，RT，c，速度最大值umax，位置邊界值，空氣壓力函數(shù)(適應(yīng)度函數(shù))。

2)任意給定每個(gè)空氣塊的位置與速度值。

3)依次計(jì)算每個(gè)空氣塊的壓力值(每個(gè)可能解的適應(yīng)度值)，按壓力值大小排列各空氣塊。

4)更新所有空氣塊的速度,并檢查速度值是否越界，若越界，規(guī)定為±umax。

5)更新所有空氣塊的位置,并檢查位置是否越界。

6)檢查是否達(dá)到最大迭代次數(shù)，若未達(dá)到,則跳到3);若達(dá)到，算法結(jié)束，最后一次迭代中空氣塊的位置記為最優(yōu)解。

3 基于WDO的無(wú)人機(jī)三維路徑規(guī)劃

(6)

其中g(shù)可定義為一個(gè)與迭代次數(shù)成正比例關(guān)系的函數(shù)值。隨著迭代次數(shù)的增加,趨向最優(yōu)粒子的速度會(huì)相對(duì)減小，進(jìn)一步增強(qiáng)了發(fā)現(xiàn)最優(yōu)解的潛力。

另外，為了進(jìn)一步增加待選空氣塊在最優(yōu)解附近的尋優(yōu)能力，可將式(3)改為:

(7)

其中q為從1到粒子總數(shù)的一個(gè)隨機(jī)值，增加最后一項(xiàng)后，趨近最優(yōu)解的速度增加了一個(gè)趨向別的粒子的速度分量，增強(qiáng)了發(fā)現(xiàn)最優(yōu)解的潛力。

文中采用WDO進(jìn)行三維路徑規(guī)劃,步驟如下：

1)初始化最大迭代次數(shù)500，令α=0.4，g=0.2,RT=3,c=0.4,中間點(diǎn)的個(gè)數(shù)為10，位置邊界值±10，速度邊界值±3，適應(yīng)度函數(shù)定義為從起點(diǎn)到中間點(diǎn)再到終點(diǎn)的距離之和，若某中間點(diǎn)落在障礙物(文中采用球體來(lái)代表威脅空間或障礙物)之內(nèi)，則此適應(yīng)度函數(shù)值加5。

2)任意給定中間點(diǎn)的位置與速度值。

3)給所有中間點(diǎn)的x坐標(biāo)賦值，令x=((x1-x0)/n)*i,令與之相應(yīng)的速度值為0。

4)依次計(jì)算每個(gè)可能解的適應(yīng)度值，按適應(yīng)度值大小排列各空氣塊(可能解)，記錄當(dāng)前最優(yōu)解。

5)令g=gmin+(gmax-gmin)*ij/100,其中ij為當(dāng)前迭代次數(shù)。按照式(6)依次更新所有空氣塊的速度并檢查速度值是否越界，若越界，規(guī)定為±3max。

6)令更新后的速度值中對(duì)應(yīng)于x坐標(biāo)的速度值等于0。

7)更新所有空氣塊的位置并檢查位置是否越界，若越界，規(guī)定為±10。

8)檢查是否達(dá)到最大迭代次數(shù)，若未達(dá)到,則跳到4);若達(dá)到，算法結(jié)束，最后一次迭代中空氣塊的位置記為最優(yōu)解。

4 仿真與結(jié)果分析

在Matlab2014a環(huán)境下對(duì)起點(diǎn)為(-5，-8，-9),終點(diǎn)為(7，7，7)的路徑規(guī)劃過(guò)程進(jìn)行了仿真，威脅區(qū)域表示圓心坐標(biāo)為(3，3，3),(2，-2，-3)，半徑為2的2個(gè)球體，最大迭代次數(shù)為500，空氣塊種群規(guī)模為30，中間點(diǎn)個(gè)數(shù)為10，gmin=6.1,gmax=7.4。采用粒子群算法與WDO算法的仿真結(jié)果500代后得出的路徑如圖1所示。

圖1 粒子群算法500代后得出的路徑

粒子群算法最短路徑下降曲線如圖2所示。

圖2 粒子群算法最短路徑下降曲線

從仿真結(jié)果可以看出，經(jīng)500次迭代后，適應(yīng)度下降曲線中較長(zhǎng)的橫線表明基本粒子群算法易陷入局部最優(yōu)。

WDO算法500次迭代后生成的最終路徑如圖3所示。

圖3 WDO算法500代后得出的路徑

適應(yīng)度函數(shù)值與迭代次數(shù)的關(guān)系曲線如圖4所示。

圖4 WDO算法最短路徑下降曲線

從圖中可以看出，WDO算法收斂速度較快，路徑較合理。

采用式(4)的速度更新策略得出的路徑規(guī)劃圖如圖5所示。

采用式(6)的速度更新策略得出的最短路徑隨著迭代次數(shù)的下降曲線如圖6所示。

由圖6可知，采用式(6)的速度更新策略得出的解更優(yōu)。

采用式(7)的速度更新策略得出的路徑規(guī)劃圖如圖7所示。

采用式(7)的速度更新策略得出的最短路徑隨著迭代次數(shù)的下降曲線如圖8所示。

圖5 式(6)速度更新策略500代后得出的路徑

圖6 式(6)更新策略最短路徑下降曲線

圖7 式(7)速度更新策略500代后得出的路徑

圖8 式(7)更新策略最短路徑下降曲線

由圖8可知，采用式(7)速度更新策略得出的解更優(yōu)。

5 結(jié) 語(yǔ)

將WDO算法用于無(wú)人機(jī)三維路徑規(guī)劃，成功地在Matlab環(huán)境下進(jìn)行了仿真，并與粒子群算法進(jìn)行了比較，可以看出前者生成的路徑明顯更合理，得出了WDO算法在路徑規(guī)劃問(wèn)題中相對(duì)有效性的結(jié)論。

[1] 史恩秀,陳敏敏,李俊,等.基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報(bào),2014,45(6):53-57.

[2] 張建南,劉以安,王剛.基于優(yōu)化粒子群算法的無(wú)人機(jī)航路規(guī)劃[J].傳感器與微系統(tǒng),2017,36(3):58-61.

[3] 王樹(shù)磊,魏瑞軒,沈東,等.面向航路規(guī)劃的Laguerre圖構(gòu)造算法[J].系統(tǒng)工程與電子技術(shù),2013,35(3):552-556.

[4] Han J, Seo Y. Mobile robot path planning with surrounding point set and path improvement[J]. Applied Soft Computing,2017,57:35-47.

[5] Zhao R, Lee H K. Fuzzy-based path planning for multiple mobile robots in unknown dynamic environment[J]. Journal of Electrical Engineering & Technology,2017,12(2):918-925.

[6] Bayraktar Z, Komurcu M, Bossard J A, et al. The wind driven optimization technique and its application in electromagnetics[J]. IEEE Transactions on Antennas & Propagation,2013,61(5):2745-2757.

[7] 代君,任淑紅,王曉璐.小型無(wú)人機(jī)姿態(tài)航向參考系統(tǒng)信息融合算法[J].長(zhǎng)春工業(yè)大學(xué)學(xué)報(bào),2016,37(1):52-55.