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

1、基于A星算法與人工勢場法的無人機(jī)路徑規(guī)劃摘要：為簡化無人機(jī)飛行路徑規(guī)劃算法并提高其避障效果，本文提出一種人工勢場法和?星算法相結(jié)合 的路徑規(guī)劃算法：以人工勢場法指導(dǎo)全局路徑規(guī)劃，通過引力場控制無人機(jī)的飛行方向；以?星算法指導(dǎo) 局部路徑規(guī)劃，避讓大型障礙物.仿真試驗證明，該算法與人工勢場法和?星算法相比，提高了避障效果, 縮短了搜索時間.關(guān)鍵詞：無人機(jī);路徑規(guī)劃；人工勢場法 ?星算法;避障無人機(jī)技術(shù)中常用的路徑規(guī)劃方法有人工勢場法（，蟻群算法以及可視圖法句等.其中，人 工勢場法設(shè)無人機(jī)在目標(biāo)點引力和障礙物斥力的合力作用下運動，其路徑平滑、方法簡單、易于實 現(xiàn)，是一種新型的路徑規(guī)劃避障方法.但該方

2、法容易出現(xiàn)局部極小點以及無法避讓大型障礙物的問 題.為此，Yan!（提出將人工勢場法與蟻群算法相結(jié)合的方法; Zhang等提出一種基于虛擬結(jié)構(gòu)和 領(lǐng)導(dǎo)者跟隨者控制策略的三維避障控制算法.障礙物在人工勢場法中被視為質(zhì)點或形狀均勻的圓， 但障礙物實際的形狀和大小各異，運用人工勢場法難以計算斥力.A星算法A。是一種運用啟發(fā)式 函數(shù)在靜態(tài)地圖中尋找避障路徑的方法，可以彌補(bǔ)人工勢場法在避讓大型障礙物方面的不足.本 文提出一種將人工勢場法與A星算法相結(jié)合的改進(jìn)算法，以人工勢場法指導(dǎo)全局路徑規(guī)劃、A星算 法指導(dǎo)局部路徑規(guī)劃，在保證安全避障尋路的同時降低計算成本.目標(biāo)點圖1采用傳統(tǒng)人工勢場法時無人機(jī) 遭遇大型

3、障礙物的受力圖Force diagram of UAV when it encounters large1模型建立障礙物目標(biāo)點圖1采用傳統(tǒng)人工勢場法時無人機(jī) 遭遇大型障礙物的受力圖Force diagram of UAV when it encounters largeFig.lobstacle in traditional artificial potential field method圖1是采用傳統(tǒng)人工勢場法時無人機(jī)遭遇大 型障礙物時的受力圖.如圖1所示，傳統(tǒng)人工勢場 法中斥力M與引力Fa的合力F無法引導(dǎo)無人機(jī) 繞過障礙物.采用A星算法進(jìn)行掃描探測則可以檢 測障礙物并規(guī)劃避障路徑，但在無

4、障礙物時，無人 機(jī)在A星算法下的飛行成本較高，花費時間較長. 為降低計算成本，本文使用人工勢場法規(guī)劃總體路 徑；當(dāng)檢測到大型障礙物時，將地圖柵格化，確定避 障的起始節(jié)點和終止節(jié)點，然后通過A星算法規(guī)劃 避障路線；當(dāng)無人機(jī)完成障礙物避讓后，繼續(xù)采用 人工勢場法進(jìn)行路徑規(guī)劃.以此循環(huán)，直到到達(dá)目標(biāo)點.改進(jìn)后的算法流程如圖2所示.Fig.lobstacle in traditional artificial potential field method1.1人工勢場法的改進(jìn)在人工勢場法中，設(shè)無人機(jī)坐標(biāo)為X(z,)，目標(biāo)點坐 標(biāo)，障礙物坐標(biāo)為X (xa ,y0),設(shè)無人機(jī)只受引 力作用，引力系數(shù)為k,

5、則引力場U(&) =7(X-Xl)z/2, |X-X0U(&) =&0, |X-X0| (&p ,yp + 1), X$ (& , yp-1)分別代入估價函數(shù)計算.以計算節(jié)點 X (&p + 1, 9p)為例，設(shè)無人機(jī)每移動一個節(jié)點的代價為10,則有g(shù)(X) = 10( |&p + 1 &a | + |yp L2 A星算法的改進(jìn)圖2基于A星算法和人工勢場法的 改進(jìn)算法流程Fig. 2 Improved algorithm flowbased on A-Star algorithm andartificial potential field method10 .(xe&p 1)2 + (yeyp

6、)2 ,總 代價為 F (X) = 10 |&p+ 1 &a| + |yp ya | +.(&e&p 1)2 + (yeyp)2 (.然后比較4個節(jié)點的估價函數(shù)大小，將總代價最小的對應(yīng)節(jié)點存入開 放列表，以此求出起始節(jié)點到終止節(jié)點的避障飛行路線.2仿真結(jié)果與分析圖3地圖柵格化和A星算法的起始、終止節(jié)點示意圖 Fig. 3 Rasterization of the map and schematc diagram of the starting and terminating nodes of the AStar algorithm本文在操作系統(tǒng)為Windows 10,8 GB內(nèi)存, Inlel

7、(R) Cre(WM) 20 ZHz 的計算機(jī)上運用Matlab 2010a軟件進(jìn)行仿真試 驗.設(shè)100 mi 100 m的二維空間地圖上有2個 大小不能忽略不計的障礙物，人工勢場法的引力 系數(shù)為2,危險距離為1 m,無人機(jī)的運行速度為 4m)s1 ,掃描時長為0. 5 s 輪t.分別運用人 工勢場法、A星算法和本文算法規(guī)劃無人機(jī)從地 圖坐標(biāo)系Oxy中的坐標(biāo)點(1,1)至點(99,91)的 飛行路線.圖4為不同算法的飛行路徑示意圖. 圖4(a)顯示，在人工勢場法下，無人機(jī)無法躲避 障礙物，與障礙物發(fā)生碰撞，這是由于傳統(tǒng)人工 勢場法將障礙物視為質(zhì)點，將障礙物中心看作斥力產(chǎn)生的位置，當(dāng)障礙物體積較

8、大時，無人機(jī)便無法 躲避.圖4(b)顯示，使用A星算法規(guī)劃避障路線時，掃描區(qū)域面積大，計算時間也相應(yīng)增加.圖4(c) 展示了改進(jìn)算法的飛行路徑：首先根據(jù)人工勢場法的計算路線飛行至障礙物前點(32,29)處以該 坐標(biāo)點為起始節(jié)點，以A星算法探測的避障路徑飛行至點（45,55）處，終止A星算法；繼續(xù)使用人工 勢場法飛行至障礙物前點（69,69）處；再次使用A星算法避障，在點（7%,31）處結(jié)束掃描和路徑規(guī)劃； 最后，無人機(jī)在人工勢場法下到達(dá)終點.表1為無人機(jī)采用不同算法的飛行時間對比.圖3地圖柵格化和A星算法的起始、終止節(jié)點示意圖 Fig. 3 Rasterization of the map a

9、nd schematc diagram of the starting and terminating nodes of the AStar algorithm障礙物飛行路徑障礙物飛行路徑圖)無人機(jī)在人工勢場法(a), A星算法(b)和改進(jìn)算法(c)下的飛行路徑示意圖Fig.) The flight path diagram of UAV under the artificial potential field method (a) , A-Staralgorithm (b) and the improved algorithm (c)表1無人機(jī)采用不同算法的飛行時間對比Tab. 1 Comparison of flight time using diffe