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

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

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

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

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

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

6、)2 ,總 代價(jià)為 F (X) = 10 |&p+ 1 &a| + |yp ya | +.(&e&p 1)2 + (yeyp)2 (.然后比較4個(gè)節(jié)點(diǎn)的估價(jià)函數(shù)大小，將總代價(jià)最小的對(duì)應(yīng)節(jié)點(diǎn)存入開(kāi) 放列表，以此求出起始節(jié)點(diǎn)到終止節(jié)點(diǎn)的避障飛行路線.2仿真結(jié)果與分析圖3地圖柵格化和A星算法的起始、終止節(jié)點(diǎn)示意圖 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ì)算機(jī)上運(yùn)用Matlab 2010a軟件進(jìn)行仿真試 驗(yàn).設(shè)100 mi 100 m的二維空間地圖上有2個(gè) 大小不能忽略不計(jì)的障礙物，人工勢(shì)場(chǎng)法的引力 系數(shù)為2,危險(xiǎn)距離為1 m,無(wú)人機(jī)的運(yùn)行速度為 4m)s1 ,掃描時(shí)長(zhǎng)為0. 5 s 輪t.分別運(yùn)用人 工勢(shì)場(chǎng)法、A星算法和本文算法規(guī)劃無(wú)人機(jī)從地 圖坐標(biāo)系Oxy中的坐標(biāo)點(diǎn)(1,1)至點(diǎn)(99,91)的 飛行路線.圖4為不同算法的飛行路徑示意圖. 圖4(a)顯示，在人工勢(shì)場(chǎng)法下，無(wú)人機(jī)無(wú)法躲避 障礙物，與障礙物發(fā)生碰撞，這是由于傳統(tǒng)人工 勢(shì)場(chǎng)法將障礙物視為質(zhì)點(diǎn)，將障礙物中心看作斥力產(chǎn)生的位置，當(dāng)障礙物體積較

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

9、nd schematc diagram of the starting and terminating nodes of the AStar algorithm障礙物飛行路徑障礙物飛行路徑圖)無(wú)人機(jī)在人工勢(shì)場(chǎng)法(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無(wú)人機(jī)采用不同算法的飛行時(shí)間對(duì)比Tab. 1 Comparison of flight time using diffe