基于A星算法與人工勢(shì)場法的無人機(jī)路徑規(guī)劃

王云常, 戴朱祥, 李 濤

(南京信息工程大學(xué)自動(dòng)化學(xué)院, 南京 210044)

無人機(jī)技術(shù)中常用的路徑規(guī)劃方法有人工勢(shì)場法[1-3], 蟻群算法[4-5]以及可視圖法[6]等．其中, 人工勢(shì)場法設(shè)無人機(jī)在目標(biāo)點(diǎn)引力和障礙物斥力的合力作用下運(yùn)動(dòng), 其路徑平滑、方法簡單、易于實(shí)現(xiàn), 是一種新型的路徑規(guī)劃避障方法．但該方法容易出現(xiàn)局部極小點(diǎn)以及無法避讓大型障礙物的問題．為此, Yan[7]提出將人工勢(shì)場法與蟻群算法相結(jié)合的方法; Zhang等[8]提出一種基于虛擬結(jié)構(gòu)和“領(lǐng)導(dǎo)者跟隨者”控制策略的三維避障控制算法．障礙物在人工勢(shì)場法中被視為質(zhì)點(diǎn)或形狀均勻的圓, 但障礙物實(shí)際的形狀和大小各異, 運(yùn)用人工勢(shì)場法難以計(jì)算斥力．A星算法[9-10]是一種運(yùn)用啟發(fā)式函數(shù)[11]在靜態(tài)地圖中尋找避障路徑的方法, 可以彌補(bǔ)人工勢(shì)場法在避讓大型障礙物方面的不足．本文提出一種將人工勢(shì)場法與A星算法相結(jié)合的改進(jìn)算法, 以人工勢(shì)場法指導(dǎo)全局路徑規(guī)劃、A星算法指導(dǎo)局部路徑規(guī)劃, 在保證安全避障尋路的同時(shí)降低計(jì)算成本．

1 模型建立

圖1 采用傳統(tǒng)人工勢(shì)場法時(shí)無人機(jī)遭遇大型障礙物的受力圖Fig.1 Force diagram of UAV when it encounters large obstacle in traditional artificial potential field method

圖1是采用傳統(tǒng)人工勢(shì)場法時(shí)無人機(jī)遭遇大型障礙物時(shí)的受力圖．如圖1所示,傳統(tǒng)人工勢(shì)場法中斥力Fr與引力Fa的合力F無法引導(dǎo)無人機(jī)繞過障礙物．采用A星算法進(jìn)行掃描探測(cè)則可以檢測(cè)障礙物并規(guī)劃避障路徑,但在無障礙物時(shí),無人機(jī)在A星算法下的飛行成本較高,花費(fèi)時(shí)間較長．為降低計(jì)算成本,本文使用人工勢(shì)場法規(guī)劃總體路徑;當(dāng)檢測(cè)到大型障礙物時(shí),將地圖柵格化,確定避障的起始節(jié)點(diǎn)和終止節(jié)點(diǎn),然后通過A星算法規(guī)劃避障路線;當(dāng)無人機(jī)完成障礙物避讓后,繼續(xù)采用人工勢(shì)場法進(jìn)行路徑規(guī)劃．以此循環(huán),直到到達(dá)目標(biāo)點(diǎn)．改進(jìn)后的算法流程如圖2所示．

圖2 基于A星算法和人工勢(shì)場法的改進(jìn)算法流程Fig.2 Improved algorithm flow based on A-Star algorithm and artificial potential field method

1.1 人工勢(shì)場法的改進(jìn)

在人工勢(shì)場法中, 設(shè)無人機(jī)坐標(biāo)為X(x,y),目標(biāo)點(diǎn)坐標(biāo)Xt(xt,yt), 障礙物坐標(biāo)為Xo(xo,yo), 設(shè)無人機(jī)只受引力作用, 引力系數(shù)為k, 則引力場

式中ρ為無人機(jī)與障礙物的危險(xiǎn)距離．當(dāng)無人機(jī)與障礙物距離大于ρ時(shí), 無人機(jī)在人工勢(shì)場法的引力場下向目標(biāo)位置移動(dòng); 否則進(jìn)行避讓, 無人機(jī)不受引力場作用并停止移動(dòng)．

1.2 A星算法的改進(jìn)

圖3 地圖柵格化和A星算法的起始、終止節(jié)點(diǎn)示意圖Fig.3 Rasterization of the map and schematic diagram of the starting and terminating nodes of the A-Star algorithm

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

本文在操作系統(tǒng)為Windows 10,8 GB內(nèi)存,Intel(R) Core(TM) i5-6500 CPU @ 3.20 GHz 的計(jì)算機(jī)上運(yùn)用Matlab 2010a軟件進(jìn)行仿真試驗(yàn)．設(shè)100 m×100 m的二維空間地圖上有2個(gè)大小不能忽略不計(jì)的障礙物,人工勢(shì)場法的引力系數(shù)為2, 危險(xiǎn)距離為1 m,無人機(jī)的運(yùn)行速度為4 m·s-1, 掃描時(shí)長為0.5 s·輪-1．分別運(yùn)用人工勢(shì)場法、A星算法和本文算法規(guī)劃無人機(jī)從地圖坐標(biāo)系Oxy中的坐標(biāo)點(diǎn)(1,1)至點(diǎn)(99,91)的飛行路線．圖4為不同算法的飛行路徑示意圖．圖4(a)顯示, 在人工勢(shì)場法下,無人機(jī)無法躲避障礙物,與障礙物發(fā)生碰撞,這是由于傳統(tǒng)人工勢(shì)場法將障礙物視為質(zhì)點(diǎn),將障礙物中心看作斥力產(chǎn)生的位置,當(dāng)障礙物體積較大時(shí),無人機(jī)便無法躲避．圖4(b)顯示, 使用A星算法規(guī)劃避障路線時(shí),掃描區(qū)域面積大,計(jì)算時(shí)間也相應(yīng)增加．圖4(c)展示了改進(jìn)算法的飛行路徑: 首先根據(jù)人工勢(shì)場法的計(jì)算路線飛行至障礙物前點(diǎn)(32,29)處; 以該坐標(biāo)點(diǎn)為起始節(jié)點(diǎn),以A星算法探測(cè)的避障路徑飛行至點(diǎn)(45,55)處, 終止A星算法; 繼續(xù)使用人工勢(shì)場法飛行至障礙物前點(diǎn)(69,69)處;再次使用A星算法避障,在點(diǎn)(78,31)處結(jié)束掃描和路徑規(guī)劃;最后,無人機(jī)在人工勢(shì)場法下到達(dá)終點(diǎn)．表1為無人機(jī)采用不同算法的飛行時(shí)間對(duì)比．由于人工勢(shì)場法無法安全避障,所以沒有列出其飛行時(shí)間．與A星算法相比,改進(jìn)算法的飛行時(shí)間明顯縮短, 驗(yàn)證了改進(jìn)算法的可行性與有效性．后續(xù)工作中將繼續(xù)關(guān)注如何躲避大型移動(dòng)障礙物的問題,進(jìn)一步提升算法的實(shí)用性．

圖4 無人機(jī)在人工勢(shì)場法(a),A星算法(b)和改進(jìn)算法(c)下的飛行路徑示意圖Fig.4 The flight path diagram of UAV under the artificial potential field method (a), A-Star algorithm (b) and the improved algorithm (c)

表1 無人機(jī)采用不同算法的飛行時(shí)間對(duì)比Tab.1 Comparison of flight time using different algorithms s