楊俊磊, 段倩倩

(上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院, 上海 201620)

0 引 言

路徑規(guī)劃是平面上從源點(diǎn)出發(fā)經(jīng)若干節(jié)點(diǎn)到達(dá)目標(biāo)終點(diǎn)求最短路的優(yōu)化問題。在路徑規(guī)劃中,常用算法分為全局和局部?jī)煞N，其中,全局路徑規(guī)劃算法有Dijkstra算法、A*算法、粒子群算法、蟻群算法等[1～4]。機(jī)器人無碰撞避開障礙物的路徑規(guī)劃是當(dāng)前學(xué)者研究的熱點(diǎn)問題之一，研究學(xué)者常用柵格法作為機(jī)器人路徑規(guī)劃的地圖模型，不能較好體現(xiàn)實(shí)際地形的復(fù)雜多樣性。

目前，路徑規(guī)劃廣泛應(yīng)用于工廠物資輸送，應(yīng)急車輛避障救援等，這些問題不僅要保證行駛路徑最優(yōu)，時(shí)間短，配送效率高，還需要規(guī)避障礙物[5,6]。何成偉等人應(yīng)用Maklink圖構(gòu)建無向網(wǎng)絡(luò)障礙物模型，保證規(guī)劃的自動(dòng)導(dǎo)引車(automatic guided vehicle,AGV)路徑沿著凸多邊形邊緣行走不會(huì)與真實(shí)的障礙產(chǎn)生碰撞，但實(shí)驗(yàn)研究較為單一，不能體現(xiàn)復(fù)雜障礙物環(huán)境的多樣性[7]。王飛等人利用Graham算法生成凸多邊形并向外擴(kuò)展h的安全距離，確保飛機(jī)航線不與障礙物發(fā)生碰撞，但航線路徑需要遍歷所有節(jié)點(diǎn)，增加了搜索時(shí)間，規(guī)劃路徑非全局最優(yōu)[8]。粒子群算法、蟻群算法等[9，10]具有良好的尋優(yōu)能力、算法精度高、收斂快等優(yōu)點(diǎn)，廣泛應(yīng)用于路徑規(guī)劃問題中，并通過迭代尋找最優(yōu)解。其中，粒子群算法通過適應(yīng)度函數(shù)評(píng)價(jià)路徑解，但算法容易陷入早熟，局部尋優(yōu)解較差。黃超等人[11]通過融合蝗蟲算法的粒子群算法改善收斂速度。文獻(xiàn)[1]采用廣度優(yōu)先法對(duì)遍歷節(jié)點(diǎn)進(jìn)行擴(kuò)展并選出距源點(diǎn)最近節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，但隨著遍歷節(jié)點(diǎn)增多，Open表節(jié)點(diǎn)排序時(shí)間消耗較大，計(jì)算效率較低。文獻(xiàn)[12]通過無線傳感器節(jié)點(diǎn)定位算法對(duì)錨節(jié)點(diǎn)精確定位，繼續(xù)擴(kuò)展未知節(jié)點(diǎn)，定位過程中，盲節(jié)點(diǎn)定義為所需定位的未知節(jié)點(diǎn)。

針對(duì)上述學(xué)者研究成果及存在的不足，本文提出了一種混合節(jié)點(diǎn)定位算法(hybrid node localization algorithm,HNLA)，在不同規(guī)模地圖環(huán)境中有效減少了遍歷節(jié)點(diǎn)及迭代次數(shù)，節(jié)省了搜索時(shí)間并規(guī)劃出最短路徑。

1 相關(guān)工作介紹

1.1 粒子群算法

粒子群算法是Kennedy J和Eberhart R在1995年根據(jù)群鳥和魚群的成群性質(zhì)提出的一種啟發(fā)式算法[13]。粒子群提供搜索算法的初始種群，粒子會(huì)隨時(shí)間改變它們的位置，并在優(yōu)化系統(tǒng)中根據(jù)經(jīng)驗(yàn)選擇最佳位置Pi，全局最佳位置Pg以及搜索速度Vi。粒子速度更新根據(jù)Vid=w×Vid+c1×r1×(Pid-Xid)+c2×r2×(Pgd-Xgd)，其中，w表示慣性權(quán)重；c1和c2為常數(shù)，r1和r2為隨機(jī)函數(shù)，其值都∈(0,1)；粒子位置根據(jù)Xid=Xid+Vid更新，Xid表示粒子i在d維搜索位置。

1.2 蟻群算法

蟻群算法[14]求解路徑規(guī)劃問題主要根據(jù)信息素濃度更新以增強(qiáng)蟻群信息素的濃度值，提高收斂速度。通過輪盤賭法并根據(jù)概率公式(1)判斷并選擇下一節(jié)點(diǎn)

(1)

式中α為訪問各城市節(jié)點(diǎn)的程度因子，β為轉(zhuǎn)移到最近城市的程度因子，τij(t)為螞蟻從節(jié)點(diǎn)i到j(luò)釋放的信息素濃度總量，ηij(t)=1/dij為節(jié)點(diǎn)間路徑期望值，dij為節(jié)點(diǎn)之間距離，allow為待遍歷的節(jié)點(diǎn)集，信息素更新如下

τij(t+1)=(1-ρ)·τij(t)+Δτij(t)

(2)

(3)

圖1 蟻群算法解決TSP流程圖

2 混合定位方法策略

2.1 區(qū)域分割

2.1.1 確定段節(jié)點(diǎn)

根據(jù)文獻(xiàn)[15]構(gòu)建Maklink線規(guī)劃初始參考節(jié)點(diǎn)對(duì)障礙物區(qū)域進(jìn)行分割,并將參考節(jié)點(diǎn)作為相應(yīng)分割區(qū)域的段節(jié)點(diǎn)。圖2為初始段節(jié)點(diǎn)及分割區(qū)域，其中,V1，V2，…,V7為初始段節(jié)點(diǎn)。

圖2 初始段節(jié)點(diǎn)及分割區(qū)域

2.1.2 區(qū)域分割

通過確定的段節(jié)點(diǎn)進(jìn)行路徑搜索，將區(qū)域進(jìn)一步分割：

Step1 將初始節(jié)點(diǎn)坐標(biāo)S作為搜尋盲節(jié)點(diǎn)的質(zhì)心坐標(biāo)(xn,yn)。

Step2 由式(4)確定同段區(qū)域距離質(zhì)心最遠(yuǎn)的盲節(jié)點(diǎn)Am作為分割區(qū)域的搜索節(jié)點(diǎn)，式(5)確定第g段盲節(jié)點(diǎn)區(qū)域

(4)

(5)

式中m為盲節(jié)點(diǎn)數(shù)，dAm,Aj和dAm,Ai為Am與鄰近盲節(jié)點(diǎn)Aj距離及Am同其他盲節(jié)點(diǎn)Ai距離。若dAm,Aj≤dAm,Ai，將節(jié)點(diǎn)Aj加入到Am，作為段節(jié)點(diǎn)新的搜索位置;反之，繼續(xù)區(qū)域分割。

Step3 盲節(jié)點(diǎn)位置確定：1)在每次區(qū)域所分割的段中計(jì)算出已知節(jié)點(diǎn)到不同段中段節(jié)點(diǎn)的距離以及與同段中其它節(jié)點(diǎn)的距離;2)計(jì)算不同段中節(jié)點(diǎn)之間的最小距離差

(6)

Step4 直到所有段節(jié)點(diǎn)區(qū)域分割完畢，停止。

2.2 盲節(jié)點(diǎn)邊界定位

根據(jù)先前步驟計(jì)算得到的段節(jié)點(diǎn)，確定盲節(jié)點(diǎn)位置邊界。應(yīng)用文獻(xiàn)[16]包圍盒技術(shù)的方法計(jì)算矩形邊界，通過dAm,Ai和已知節(jié)點(diǎn)位置(xAi,yAi)計(jì)算矩形邊界，如圖3所示。由已知段節(jié)點(diǎn)Am,A2,A3及dAm,Ai,dAm,Aj確定盲節(jié)點(diǎn)所在位置，根據(jù)式(7)和式(8)計(jì)算盲節(jié)點(diǎn)位置的邊界框Ei以及邊界框的相交面積Sj

Ei=[xAi-dAm,Ai,xAi+dAm,Ai]×

[yAi-dAm,Aj,yAi+dAm,Ai]

(7)

(8)

式中 矩形區(qū)域中心坐標(biāo)為(xSi,ySi)，長(zhǎng)為dAm,Ai×(1-sinθ),寬為dAm,Ai-dAm,Ajsinφ,m為盲節(jié)點(diǎn)數(shù)，其中,1≤i≤m。

圖3 盲節(jié)點(diǎn)邊界定位

2.3 混合算法設(shè)計(jì)

為確保盲節(jié)點(diǎn)定位正確性和計(jì)算速度，使其預(yù)計(jì)位置接近最短路徑上的實(shí)際位置，本文采用粒子群和蟻群相結(jié)合的混合動(dòng)態(tài)算法規(guī)劃路徑。通過最佳節(jié)點(diǎn)所在位置pbk,每段最佳節(jié)點(diǎn)所在位置plS,全局所在最優(yōu)位置gb來提高搜尋速度并對(duì)盲節(jié)點(diǎn)定位。根據(jù)式(9)適應(yīng)度值作為距離和算法收斂速度的衡量標(biāo)準(zhǔn)

(9)

式中 (xAi,yAi)為節(jié)點(diǎn)Ai位置；dAm,Aj為節(jié)點(diǎn)Am到不同區(qū)域段中盲節(jié)點(diǎn)Aj的距離；m為節(jié)點(diǎn)數(shù)量。第k只螞蟻的搜索位置和速度根據(jù)式(10)、式(11)求解

vk(t+1)=w(t)vk(t)+c1r1(pbk-xk(t))+

c2r2(gb-xk(t))+c3r3(pls-xk(t))

(10)

xk(t+1)=xk(t)+vk(t+1)

(11)

(12)

式中w=0.7，c1=c2=c3=1.494，ri∈[0,1],Lup和Ldown為從邊界框中獲得的局部化區(qū)域邊界，t為螞蟻所在最佳位置的不變時(shí)間，t′ 為區(qū)域邊界更新時(shí)間。采用粒子群算法提高搜索速度，搜索最佳節(jié)點(diǎn)位置，計(jì)算當(dāng)前段最短路徑節(jié)點(diǎn)之間長(zhǎng)度Lij，根據(jù)式(2)更新該條路徑上節(jié)點(diǎn)信息素

(13)

根據(jù)式(1)計(jì)算Pij，找出最優(yōu)遍歷節(jié)點(diǎn)，迭代完成后，規(guī)劃出最短路徑L*。改進(jìn)算法流程如圖4所示。

圖4 改進(jìn)算法流程圖

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

為了驗(yàn)證改進(jìn)算法的有效性，在實(shí)驗(yàn)平臺(tái)為Intel?CoreTMi5—4210U CPU@2.40GHz，4.00GB RAM，軟件環(huán)境為 Windows 10專業(yè)版，MATLAB2016a中編程實(shí)現(xiàn)對(duì)文獻(xiàn)[1，7]和改進(jìn)算法路徑規(guī)劃，實(shí)驗(yàn)?zāi)M真實(shí)避障環(huán)境，對(duì)比分析了路徑長(zhǎng)度、擴(kuò)展節(jié)點(diǎn)、搜索時(shí)間以及迭代次數(shù)。

3.1 實(shí)驗(yàn)仿真

構(gòu)建實(shí)驗(yàn)區(qū)面積為50 km×50 km，100 km×100 km,200 km×200 km的不同規(guī)模障礙物空間。目標(biāo)起點(diǎn)分別為S1(5,10)km，S2(10,90)km，S3(20,180)km對(duì)應(yīng)目標(biāo)終點(diǎn)T1(45,45)km，T2(90,15)km，T3(160，90)km，尋找一條從起點(diǎn)S到終點(diǎn)T的最優(yōu)路徑。蟻群算法相關(guān)參數(shù)設(shè)置，螞蟻個(gè)數(shù)為35，信息素因子α為1.6，啟發(fā)式因子β為5，揮發(fā)因子ρ為0.2，信息素總量Q為50，最大迭代次數(shù)為NC=500?；谏鲜鰠?shù)設(shè)置，采用Maklink圖構(gòu)建段節(jié)點(diǎn)，進(jìn)行初始區(qū)域分割，劃分段節(jié)點(diǎn)以及定位節(jié)點(diǎn)，如圖5所示。

圖5 初始區(qū)域分割

3.2 實(shí)驗(yàn)結(jié)果分析

通過實(shí)驗(yàn)研究，隨著障礙物模型增加，路徑復(fù)雜度增加，相應(yīng)分割區(qū)域、段節(jié)點(diǎn)隨之增加。圖6和圖7為文獻(xiàn)[1]、文獻(xiàn)[7]和改進(jìn)算法路徑規(guī)劃結(jié)果以及在不同規(guī)模下迭代次數(shù)與適應(yīng)度值變化曲線。

圖6(b)中點(diǎn)劃線為改進(jìn)算法優(yōu)化路徑，實(shí)線為文獻(xiàn)[1]算法優(yōu)化路徑，虛線為文獻(xiàn)[7]算法優(yōu)化路徑，三種算法實(shí)驗(yàn)結(jié)果對(duì)比見表1。從圖6(b)及表1得出，在不同規(guī)模障礙物下，改進(jìn)算法收斂速度比文獻(xiàn)[1]、文獻(xiàn)[7]算法都快，規(guī)劃路徑長(zhǎng)度最短；采用文獻(xiàn)[2]路徑比的方法衡量三種算法路徑規(guī)劃的效率，實(shí)驗(yàn)表明，改進(jìn)算法在規(guī)避障礙物上搜索全局路徑效果比其他兩種算法路徑更優(yōu)。

圖6 實(shí)驗(yàn)結(jié)果

表1 實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié)束語

隨著路徑規(guī)劃障礙物規(guī)模增大，文獻(xiàn)[1]和文獻(xiàn)[7]算法在問題解精度以及收斂速度上存在不足。提出加快搜索速度、精確節(jié)點(diǎn)定位的改進(jìn)算法，對(duì)節(jié)點(diǎn)所在位置精確估計(jì)，求解最優(yōu)路徑。實(shí)驗(yàn)結(jié)果表明：改進(jìn)算法的最優(yōu)解精度以及收斂速度優(yōu)于其他兩種算法，當(dāng)障礙物規(guī)模、復(fù)雜度增大時(shí)，改進(jìn)算法節(jié)點(diǎn)定位的有效性更加突出。在后續(xù)研究中，將在不同規(guī)模障礙物的三維環(huán)境下，研究改進(jìn)算法的求解精度以及收斂性。