基于網(wǎng)格PRM的無人機多約束航路規(guī)劃

曾國奇, 趙民強, 劉方圓, 丁文銳

(1. 北京航空航天大學無人駕駛飛行器設計研究所, 北京 100191;2. 北京航空航天大學電子信息工程學院, 北京 100191)

?

基于網(wǎng)格PRM的無人機多約束航路規(guī)劃

曾國奇1, 趙民強2, 劉方圓2, 丁文銳1

(1. 北京航空航天大學無人駕駛飛行器設計研究所, 北京 100191;2. 北京航空航天大學電子信息工程學院, 北京 100191)

目前，無人機航路規(guī)劃技術存在約束條件少,不能滿足實際飛行需求,規(guī)劃效率低等不足,文章主要針對上述問題提出改進措施。首先,將航路約束條件進行分類,提出了基本約束、平臺安全約束和鏈路載荷約束,并對約束條件建模,完善無人機航路約束模型。為了提高無人機航路規(guī)劃效率,提出了網(wǎng)格概率地圖法(gridprobabilisticroadmap,GPRM),利用約束模型構建代價函數(shù),實現(xiàn)無人機航路的多約束快速航路規(guī)劃。GPRM的實驗仿真表明，GPRM規(guī)劃效率相比較傳統(tǒng)PRM有顯著提升,同時規(guī)劃結果更加符合實際任務需求,證明基于GPRM的無人機航路規(guī)劃具有一定的工程應用價值。

無人機; 航路規(guī)劃; 網(wǎng)格概率地圖法; 多約束; 鏈路載荷

0　引　言

近年來,無人機技術取得了迅速發(fā)展,其指揮控制系統(tǒng)正在朝著自主化、智能化方向發(fā)展,無人機航路規(guī)劃是實現(xiàn)無人機自主化的重要技術環(huán)節(jié)。無人機航路規(guī)劃是指無人機在得到任務信息后根據(jù)執(zhí)行任務的環(huán)境信息規(guī)劃出滿足一系列約束條件和性能指標的最優(yōu)或較優(yōu)的可行航路。高效的航路規(guī)劃系統(tǒng)可以使無人機在惡劣環(huán)境中安全、高效地完成任務。因此,無人機航路規(guī)劃技術吸引了越來越多學者的關注。

航路規(guī)劃算法通常分為幾何方法、數(shù)學規(guī)劃方法、人工勢場法[1]和智能優(yōu)化方法[2]。幾何方法一般指基于圖論的搜索方法,如基于概略圖的通視圖法、Voronoi法[3]、概率地圖法(probabilisticroadmapmethod,PRM)、A*算法,以及基于柵格的搜索方法。數(shù)學規(guī)劃方法包括動態(tài)規(guī)劃法、非線性規(guī)劃法等。人工勢場法在規(guī)劃空間構建人工勢場,通過勢場力的作用來求解。智能優(yōu)化方法有進化算法[4-5]、蟻群算法[6-7]等。

PRM因具有實現(xiàn)簡單,幾何計算需求小,擴展性好而被廣泛應用于路徑規(guī)劃問題[8]。PRM的基本思想最初由文獻[8-9]提出,主要用來解決機器人的運動規(guī)劃問題和其他類似問題。文獻[10]對PRM中的距離參數(shù)和局部規(guī)劃器的選取進行了研究,提出了一般性的參數(shù)選取指導。針對不同的應用,對PRM的改進包括提高PRM在障礙聚集區(qū)的性能[11],提高PRM圖的連通性[12]等。文獻[13-14]將PRM應用于類車機器人的路徑規(guī)劃。文獻[15]利用PRM解決了自主水下航行器的路徑規(guī)劃。文獻[16]利用改進的PRM解決了無人機低空突防的航跡規(guī)劃問題。

目前，PRM在解決無人機航路規(guī)劃時還存在著一些不足。首先,對無人機航路規(guī)劃的約束條件考慮不夠完善[9-10],沒有充分考慮無人機實際飛行需求,如對通訊鏈路的要求。其次,無人機規(guī)劃空間大,PRM在學習階段將消耗較多時間,限制了PRM在大范圍無人機航路規(guī)劃中的應用。

針對上述存在的問題,本文首先結合實際需求,對真實環(huán)境中無人機航跡的約束條件進行分類和建模。其次,對傳統(tǒng)PRM進行改進,提出網(wǎng)格PRM的方法,在三維空間進行采樣,構建了三維的規(guī)劃空間,應用網(wǎng)格數(shù)據(jù)結構,實現(xiàn)了無人機多約束條件下航路的快速規(guī)劃。

1　航路規(guī)劃的約束條件

無人機在復雜環(huán)境中進行航路規(guī)劃時必須滿足以下約束條件。第一,無人機基本約束,包括地形、人工禁飛區(qū)、無人機最小直飛距離與轉彎半徑、無人機最大爬升角等約束;第二,無人機平臺安全約束,包括雷達威脅源、高炮威脅源等約束;第三,無人機鏈路載荷約束,如鏈路與干擾等。

根據(jù)上述約束條件對航路質量評價的影響,以上約束條件的代價函數(shù)又可分為3類：第1類為剛性代價函數(shù),包括地形、禁飛區(qū)、航跡段直飛距離、最小轉彎半徑和最大爬升角約束,該指標航路的評價是二值的,即可行或不可行；第2類為成本型代價函數(shù),如雷達威脅源,函數(shù)值越小航路評價越好；第3類為效益型代價函數(shù),如鏈路與干擾,函數(shù)值越大航路評價越好。

2　約束模型

根據(jù)3類約束條件對航路質量評價的影響,對不同約束條件進行建模后獲得各約束條件下的代價模型與總的代價模型。

2.1基本約束數(shù)學量與符號使用規(guī)范

2.1.1地形

記航跡段E上航點距地面高度的集合為H={h(p)|p∈E},ch為航跡段E的地形威脅代價,hmin為最小安全飛行高度,則有

(1)

2.1.2禁飛區(qū)

由于航跡段E不能穿越禁飛區(qū),因此有代價函數(shù)

(2)

式中,cr為無人機的禁飛區(qū)代價。

2.1.3直飛距離與轉彎半徑

為滿足最小直飛距離和最小轉彎半徑約束,需要同時檢測當前航跡段與前后相鄰航跡段的關系。

假設無人機的轉彎半徑恒定,如圖1所示,其中AB、BC、CD分別為連續(xù)航點形成的航跡在水平面的投影,rmin為最小轉彎半徑,EF為航跡段BC中的無人機直飛距離。α,β分別為航跡AB與BC、BC與CD的夾角。則無人機在BC航跡段的直飛距離為

(3)

式中,l為BC段的長度。設lmin為需要滿足的最小直飛距離,cs為最小直飛距離與轉彎半徑代價,則有

(4)

圖1　轉彎半徑約束示意圖Fig.1　Constraints of turning radius

2.1.4最大爬升角

記航跡段E的爬升角為θ,則航跡段E的爬升角代價為

(5)

式中,θmax為最大爬升角。

2.2平臺安全約束

無人機平臺安全約束包括雷達威脅源、高炮威脅源等,本來主要針對雷達威脅源代價進行分析,將被雷達偵測到的回波能量轉化為無人機航路的代價。

由雷達特性方程可知,雷達接收到的回波功率為

(6)

式中,Pt為雷達發(fā)射功率;Gt、Gr分別為雷達發(fā)射和接收天線增益;λ為雷達波長;σ為無人機散射截面積;R為無人機與雷達距離。

記雷達的最小可檢測信號功率為Simin,則由式(6)可得雷達最遠作用距離

(7)

假設無人機的雷達散射截面積σ為常數(shù)時,代入式(6)有

(8)

對式(8)進行歸一化,并去除極點得到距離雷達dr時的雷達威脅模型

(9)

記航跡段E上航點p距雷達距離為dr(p),則有航跡段E的雷達威脅源代價為

(10)

2.3數(shù)據(jù)鏈路與干擾

距鏈路或干擾發(fā)射天線距離為R處的信號功率密度為

(11)

記Smin為鏈路或干擾的最小有效功率,則可得鏈路或干擾的最大作用距離為

(12)

代入式(11)得

(13)

對式(13)進行歸一化,并去除極點，得到距離鏈路或干擾d 時的模型

(14)

式中,L(d)和I(d)分別為鏈路和干擾模型,應用信噪比模型,記航跡段E上一航點p,有一個鏈路信號源,多個干擾源的情況下,點p處鏈路與干擾模型為

(15)

式中,LI(p)為p點的鏈路與干擾代價;dI_k(p)為p點距第k個干擾源的距離;dL(p)為p點距鏈路的距離。則航跡段E的鏈路與干擾的代價為

(16)

2.4航路總代價模型

由式(1)、式(2)、式(4)、式(5)、式(10)和式(16)得到無人機航路代價模型為

CT=ch+cr+cs+cp+ce+wt·ct+wl·cl=

wl·LI(d(p)))dp

(17)

式中,CT為無人機航路的總代價;ce為該航路段的歐式距離;wt為對應雷達威脅的權值系數(shù);wl為對應鏈路與干擾的權值系數(shù)。

3　航路規(guī)劃

3.1PRM算法分析

PRM算法是一種基于取樣的規(guī)劃算法,被廣泛應用于地面機器人的路徑規(guī)劃。PRM算法分為兩個階段:第一階段是學習階段即地圖的構造階段；第二階段是查詢階段[9]。

在學習階段,PRM算法漸進增地、隨機地構建出C空間中避撞點和避撞路徑組成的路線圖G(V,E), 其中V為圖2中節(jié)點的集合,E為避撞路徑(圖2中的邊)的集合。

在查詢階段,PRM算法采用圖搜索算法在圖2中搜索從起點到終點的最優(yōu)路徑,從而將最優(yōu)路徑搜索問題變成圖搜索問題。查詢階段分為兩步,首先將查詢的起始點s和終點g分別連接到航路圖中的s′和g′,然后對航路圖進行搜索,找到連接s′和g′的一系列的邊,這樣,就是實現(xiàn)了從s到g的航線的搜索。圖2為PRM算法在簡單環(huán)境下求得的航跡。

圖2　PRM圖和規(guī)劃結果Fig.2　PRM diagram and results of plan

PRM算法在二維規(guī)劃空間有著良好的性能,在地面機器人的航路規(guī)劃中較多的應用,但是由于無人機的規(guī)劃空間由二維拓展到三維,圖2中的節(jié)點數(shù)與邊數(shù)呈指數(shù)上升,該方法在無人機航路規(guī)劃時存在性能較低的缺陷。為提高大范圍無人機航路規(guī)劃的性能,本文提出網(wǎng)格PRM算法。

3.2網(wǎng)格PRM算法學習階段

在大范圍無人機航路規(guī)劃應用中,由于規(guī)劃空間的高度尺度要遠小于長寬尺度,采用等高度間隔采樣,提出基于分層的地圖構建。將規(guī)劃區(qū)域以高度間隔dinterval進行分層,在每層的概率地圖構造中將空間再劃分為邊長為Lgridsize的正方形網(wǎng)格,在網(wǎng)格種以每單位面積的密度進行隨機采樣。

圖3為兩種算法在學習階段的流程對比圖。

圖3　兩種算法在學習階段的流程對比圖Fig.3　Comparison of two methods during the learning phase

通過對比可以看出,網(wǎng)格PRM算法相比于傳統(tǒng)PRM算法增加了對規(guī)劃空間的網(wǎng)格劃分,同時丟棄了對路徑的地形躲避檢測。在完成地圖的構造之后,將地圖中的邊定義為當前節(jié)點與當前節(jié)點所在網(wǎng)格的相鄰網(wǎng)格中的所有節(jié)點構成的邊。因此,通過將空間劃分為網(wǎng)格,使得節(jié)點的鄰接關系轉化為網(wǎng)格的鄰接關系。

采用基于網(wǎng)格的PRM的構造方法主要有兩大優(yōu)勢。第一,將學習階段需要大量運算量的路徑地形躲避檢測推遲到查詢階段,加快學習階段速度；同時,由于查詢階段只檢測最可行的路徑,大大減少了路徑的地形避讓檢測次數(shù),算法速度加快。第二,將采樣點根據(jù)網(wǎng)格劃分,只需要保存網(wǎng)格的關系,將點的關系由網(wǎng)格關系導出,大大減小存儲空間；同時,在查詢階段可以根據(jù)網(wǎng)格關系,結合無人機飛行約束條件丟棄無用網(wǎng)格中點的擴展,進一步加快查詢速度。

3.3網(wǎng)格PRM算法查詢階段

為了加快PRM算法查詢階段的速度,在查詢階段應用A*算法進行搜索。

3.3.1A*搜索算法分析

A*算法在搜索過程中保留兩個節(jié)點表：一是open表,表中存放在節(jié)點擴展過程中已經(jīng)出現(xiàn)但還沒有檢查過的節(jié)點;二是close表,表中存放在節(jié)點搜索過程中已經(jīng)檢查過的節(jié)點。為了提高節(jié)點搜索效率,對open表中存放的節(jié)點以一定的權值進行排列,使open表中最有希望的節(jié)點總是最先取出的。

在傳統(tǒng)PRM圖上應用A*算法在節(jié)點擴展時需要計算節(jié)點的每個相鄰節(jié)點。考慮到無人機的飛行動力約束,節(jié)點的有效擴展區(qū)域如圖4所示。

圖4　節(jié)點有效擴展區(qū)域Fig.4　Node effective extension area

圖4中球心Pn點為當前的節(jié)點,Pn-1點為Pn的上一節(jié)點,則圖中紅色球面與藍色球面形成的球殼Rall是傳統(tǒng)PRM算法中節(jié)點Pn的節(jié)點擴展區(qū)域,以球心為頂點的四棱錐與球殼的相交區(qū)域Rvalid是考慮無人機飛行性能后的節(jié)點有效擴展區(qū)域。

A*算法在節(jié)點擴展階段計算每一相鄰節(jié)點的航路代價并將其放入open表中,由于傳統(tǒng)PRM中的只包含節(jié)點是否相鄰的信息,因此不能利用無人機飛行約束對節(jié)點擴展進行有效縮減。網(wǎng)格PRM將節(jié)點分層并分塊存儲,可以通過快速剔除無效擴展塊來加速A*算法的擴展速度。

3.3.2基于網(wǎng)格的A*算法節(jié)點擴展

利用網(wǎng)格PRM圖的節(jié)點結構,得到節(jié)點的擴展流程如下。

(1) 計算當前節(jié)點所在網(wǎng)格的位置(x,y)和節(jié)點所在層z,根據(jù)無人機的飛行性能約束,快速計算當前節(jié)點的有效擴展塊。根據(jù)當前節(jié)點是否為起始起點,可將擴展過程分為兩類情況。

① 如果當前節(jié)點為起始節(jié)點P0,則當前節(jié)點的下一節(jié)點為層z、z+1、z-1中的網(wǎng)格位置為(x-1,y-1)、(x,y-1)、(x+1,y-1)、(x-1,y)、(x+1,y)、(x-1,y+1)、(x,y+1)、(x+1,y+1)中的節(jié)點,如圖5所示。

圖5　起始節(jié)點的塊擴展Fig.5　Starting nodes grid extension area

② 如果當前節(jié)點Pn不是起始節(jié)點,則計算當前節(jié)點的上一節(jié)點Pn-1所在的網(wǎng)格位置(x,y)和節(jié)點所在的層z,根據(jù)上一節(jié)點所在網(wǎng)格的位置和層可以出現(xiàn)圖6所示情況。

圖6　普通節(jié)點的塊擴展Fig.6　Ordinary nodes grid extension area

圖5、圖6中,藍色網(wǎng)格為當前節(jié)點所在網(wǎng)格,紅色網(wǎng)格為當前節(jié)點的上一節(jié)點所在網(wǎng)格,綠色網(wǎng)格為當前節(jié)點的擴展節(jié)點所在的網(wǎng)格。

(2) 在得到節(jié)點的擴展網(wǎng)格后,將擴展網(wǎng)格中的所有節(jié)點作為當前節(jié)點的下一節(jié)點作為A*搜索時的擴展節(jié)點。

采用新的基于網(wǎng)格的節(jié)點擴展方法的優(yōu)勢有:一是,可以有效減少由于不符合最小航跡段長度要求和較長航跡段的節(jié)點的無效擴展；二是,可以減少由于不符合無人機最小轉彎半徑的節(jié)點的無效擴展；三是,可以減少不符合無人機最大爬升角的航點的無效擴展。

3.3.3A*算法的函數(shù)選取

在得到當前節(jié)點的擴展節(jié)點后對所有的擴展節(jié)點進行評價。選取式(17)作為代價函數(shù),保證了規(guī)劃航跡的準確性和有效性。選取較大的啟發(fā)函數(shù)可以加速算法的收斂,但過大的啟發(fā)函數(shù)將使規(guī)劃失去最優(yōu)解,為了保證航路的確定性,將歐氏距離作為啟發(fā)函數(shù)。由式(17)可知,即使在不同的權重因子的情況下,可以保證啟發(fā)函數(shù)將嚴格小于代價函數(shù),保證了航路規(guī)劃的確定性。假設當前節(jié)點為Pcur,上一節(jié)點為Ppre,終點為Pg,則Pcur的代價為

(18)

Pcur的優(yōu)先級為

Pcur·priority=Pcur·cost+ce(Pcur,Pg)

(19)

3.4算法復雜度分析

現(xiàn)對網(wǎng)格PRM和傳統(tǒng)PRM法算法復雜度進行分析。設規(guī)劃區(qū)域采樣點數(shù)為N,傳統(tǒng)PRM法在學習階段每一節(jié)點可平均形成M條可行路徑,同時網(wǎng)格PRM法在采樣區(qū)域采樣個數(shù)為m,設最終規(guī)劃結果節(jié)點數(shù)為n。

3.4.1學習階段

傳統(tǒng)PRM:由于傳統(tǒng)PRM在學習階段每次采樣都進行路經(jīng)檢測,因此時間復雜度為O(N2)。

網(wǎng)格PRM:網(wǎng)格PRM法在學習階段不進行路經(jīng)檢測,時間復雜度為O(N)。

3.4.2查詢階段

傳統(tǒng)PRM:由于傳統(tǒng)PRM在查詢階段不能對搜索進行剪枝,因此時間復雜度為O(Mn)。

網(wǎng)格PRM:網(wǎng)格PRM法在查詢階段平均每次僅擴展6～9個網(wǎng)格分節(jié)點,假設平均為8個網(wǎng)格,則時間復雜度為O((8m)n)。通過對高度間隔dinterval及網(wǎng)格邊長為Lgridsize的值進行選取應有關系:

M≈26m

(19)

式(19)表示網(wǎng)格PRM法中的網(wǎng)格中節(jié)點的可行路徑與傳統(tǒng)PRM法中節(jié)點的可行路徑數(shù)量想當。則網(wǎng)格PRM法時間復雜度約為O((M/3)n)。

通過比較可知網(wǎng)格PRM法較傳統(tǒng)PRM法在學習階段和查詢階段時間復雜度有巨大優(yōu)勢。

4　實驗驗證

選取100km×100km的地形,使用Matlab繪制地形高度圖,如圖7所示,在地圖的右下方存在高度3 000m的山脈。

圖7　高度地形圖Fig.7　Topographic map

設置采樣高度間隔dinterval=250m,網(wǎng)格邊長Lgridsize=5km,每平方公里采樣密度為5個。無人機最小直飛航跡段為ls=5km,最小轉彎半徑為rmin=1km。起始點坐標為(1km,1km,0.28km),終點坐標為(99km,99km,1.32km)。在沒有禁飛區(qū)、雷達威脅源,且不考慮數(shù)據(jù)鏈路的情況下,得到規(guī)劃航跡如圖8所示。

圖8　場景1規(guī)劃結果Fig.8　Planning results of scene 1

從圖8可看出，當環(huán)境簡單時,規(guī)劃的航路為避開地形的從起始點到終點的近似直線。

分別在(86km,78km)和(12km,20km)處設置半徑為12km的禁飛區(qū),得到航跡如圖9所示。

圖9　場景2規(guī)劃結果Fig.9　Planning results of scene 2

從圖9可以看出，規(guī)劃出的無人機航路成功避開了人工禁飛區(qū),但無人機航路較圖8更長。

在以上基礎上增加雷達威脅源,對于小型無人機,雷達對其可偵察最大半徑較常規(guī)目標縮小,因此在(35km,68km,0.482km)處設置半徑為36km的雷達威脅,分別在不同的雷達威脅權重時得到如圖10所示航跡。航跡1和航跡2分別為權重因子取值為5.0和1.0時的規(guī)劃航跡。

圖10　場景3和場景4規(guī)劃結果Fig.10　Planning results of scene 3 and scene 4

由圖10可以看出,當航路的雷達威脅權重因子為1.0時航路掠過雷達威脅源,當雷達威脅權重因子為5.0時航路完全避開了威脅源,但較前者航路長度增加。因此,設置不同的雷達威脅權重因子可在航路的安全性和其他因素之間進行權衡。

當考慮無人機鏈路安全的因素,在(17km,92km,1.1km)處設置半徑為109km的鏈路,在(64km,36km,0.738km)處設置半徑為41km的干擾源,得到如圖11所示航跡。

圖11　場景5規(guī)劃結果Fig.11　Planning results of scene 5

本文測試計算機配置如下:

CPU:Intel(R)Core(TM)i3M330 @ 2.13GHz

RAM: 4.0GB

傳統(tǒng)PRM法和網(wǎng)格PRM法的航路規(guī)劃耗時如表1所示。

表1　航跡規(guī)劃時間

由表1可知,在相同場景下網(wǎng)格PRM比傳統(tǒng)PRM規(guī)劃速度快5～10倍不等。同時,傳統(tǒng)PRM法在航路規(guī)劃時需要內存為1 200 MB左右,網(wǎng)格PRM法所需內存僅為90 MB左右,所需運行時空間顯著降低。由于選取的啟發(fā)函數(shù)為歐式距離函數(shù),故兩種算法都為確定性算法,因此規(guī)劃結果相似。由表1可知,網(wǎng)格PRM法在不同的場景下,規(guī)劃耗時較短,規(guī)劃航路滿足無人機實際飛行要求,規(guī)劃速度滿足離線規(guī)劃要求。

5　結　論

本文針對PRM算法應用于三維航跡規(guī)劃時效率低的問題,結合無人機航路規(guī)劃時的約束條件,對無人機航路規(guī)劃進行研究,得到了如下成果:

(1) 對無人機真實飛行時的約束條件進行分類,對不同的約束條件分別建立了模型,同時得到了約束條件的總代價模型;

(2) 提出了網(wǎng)格PRM算法,實現(xiàn)了三維空間大范圍環(huán)境下的航路的快速規(guī)劃；

(3) 針對典型情景進行仿真,快速規(guī)劃出了滿足安全性要求的無人機航路,證明了本方法的有效性和高效性。

然而，本文中的方法對于動態(tài)的環(huán)境信息不具備處理能力,今后將繼續(xù)改進算法以實現(xiàn)無人機局部實時的航路重規(guī)劃。同時,本文實現(xiàn)了起飛點到任務地點的航路規(guī)劃,在此基礎上將對無人機的載荷規(guī)劃進行研究。

[1] Bellini A C, Lu W, Naldi R, et al. Information driven path planning and control for collaborative aerial robotic sensors using artificial potential functions[C]∥Proc.oftheAmericanControlConference, 2014: 590-597.

[2] Mao H B, Tian S, Chao A N, et al.UAVmissionplanning[M]. Beijing: National Defense Industry Press, 2015:82-83.(毛紅保,田松,晁愛農,等.無人機任務規(guī)劃[M].北京:國防工業(yè)出版社,2015:82-83.)

[3] Zhang T S, Lu Y, Zhang L, et al. UAV path planning based on improved Voronoi diagram and dynamic weights A*algorithm[J].FireControl&CommandControl,2015(2):156-160.(張?zhí)陨?魯藝,張亮,等.改進Voronoi圖和動態(tài)權值A*算法的無人機航跡規(guī)劃[J]. 火力與指揮控制, 2015(2):156-160.)

[4] Yan J L. Evolutionary algorithm based route planer for unmanned air vehicles[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2008.(嚴建林. 基于進化算法無人機航路規(guī)劃技術研究[D]. 南京:南京航空航天大學, 2008.)

[5] Ozalp N, Sahingoz O K. Optimal UAV path planning in a 3D threat environment by using parallel evolutionary algorithms[C]∥Proc.oftheIEEEInternationalConferenceonUnmannedAircraftSystems, 2013: 308-317.

[6] Li D, Cao Y H, Su Y, et al. Trajectory planning for low attitude penetration based on improved ant colony algorithm[J].JournalofBeijingUniversityofAeronauticsandAstronautics, 2006, 32(3):258-262.(李棟, 曹義華, 蘇媛, 等. 基于改進蟻群算法的低空突防航跡規(guī)劃[J]. 北京航空航天大學學報, 2006, 32(3):258-262.)

[7] Ma G J, Duan H B, Liu S Q. Improved ant colony algorithm for global optimal trajectory planning of UAV under complex environment[J].InternationalJournalofComputerScienceandApplications, 2007，4(3):57-68.

[8] Overmars M H, Mark H. A random approach to motion planning[R].Netherlamd: Utrecht University Repository, 1992.

[9] Kavraki L E, Svestka P, Latombe J C, et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J].IEEETrans.onRoboticsandAutomation,1996,12(4):566-580.

[10] Amato N M, Bayazit O B, Dale L K, et al. Choosing good distance metrics and local planners for probabilistic roadmap methods[C]∥Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation, 1998: 630-637.

[11] Amato N M, Wu Y. A randomized roadmap method for path and manipulation planning[C]∥Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation, 1996: 113-120.

[12] Morales M, Rodriguez S, Amato N M. Improving the connectivity of PRM roadmaps[C]∥Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation, 2003: 4427-4432.

[13] Song G, Amato N M. Randomized motion planning for car-like robots with C-PRM[C]∥Proc.oftheIEEEInternationalConferenceonIntelligentRobotsandSystems, 2001:37-42.

[14] Balakirsky S, Dimitrov D. Single-query, Bi-directional, Lazy roadmap planner applied to car-like robots[C]∥Proc.oftheIEEEInternationalConferenceonRoboticsandAutomation, 2010:5015-5020.

[15] Poppinga J, Birk A, Pathak K, et al. Fast 6-DOF path planning for autonomous underwater vehicles(AUV) based on 3D plane mapping[C]∥Proc.oftheIEEEInternationalSymposiumonSafety,Security,andRescueRobotics, 2011: 345-350.

[15] Li Q R, Wei C, Wu J, et al. Improved PRM method of low altitude penetration trajectory planning for UAVs[C]∥Proc.oftheIEEEChineseGuidance,NavigationandControlConference, 2014: 2651-2654.

Multi-constraints UAV path planning based on grid PRM

ZENG Guo-qi1, ZHAO Min-qiang2, LIU Fang-yuan2, DING Wen-rui1

(1. UAV Research Academy, Beihang University, Beijing 100191, China;2. School of Electronic Information Engineering, Beihang University, Beijing 100191, China)

Nowadaystheunmannedarielvehicle(UAV)’spathplanningtechnologyhasseveraldefects,suchasfewconstraintswhichleadtodissatisfactoryofrealisticflyingdemands,lowefficiencyinpathplanning,thispapermainlydealswiththeseproblems.First,classifytheconstraintsintothreetypes,basicconstraints,platformsafetyconstraintsandlinkloadconstraints.ThenmodeltheconstraintstorefineUAVpathconstrainmodel.Next,toimprovetheplanningefficiencythegridprobabilisticroadmap(GPRM)methodisproposed.Finally,bydevisingacostfunctionusingconstraintmodels,thehighefficiencymulti-constraintspathplanningforUAVisobtained.SimulationsshowthatpathplanningusingGPRMisfasterthanthatusingtraditionalPRM,andalsonoticethatthepathobtainedbyGPRMismorerealisticfortheactualflight,thustheengineerapplicationvalueofthismethodisproved.

unmannedarielvehicle(UAV);pathplanning;gridprobabilisticroadmap(GPRM)method;multi-constraints;linkload

2015-09-20；

2016-05-31；網(wǎng)絡優(yōu)先出版日期：2016-06-22。

國家高技術研究發(fā)展計劃(863計劃)(2013AA122103)；中央高校基本科研業(yè)務費專項資金(YWF-14-WRJS-005,YWF-15-WRJS-001,YWF-15-GJSYS-061)資助課題

V279;TP301.6

ADOI:10.3969/j.issn.1001-506X.2016.10.13

曾國奇(1978-),男,高級實驗師,博士,主要研究方向為無人機測控、電磁兼容、共形相控陣天線。

E-mail:zengguoqi@buaa.edu.cn

趙民強(1989-),男,碩士,主要研究方向為無人機任務規(guī)劃。

E-mail:beyond21299@163.com

劉方圓(1989-),男,碩士,主要研究方向為無人機航路規(guī)劃。

E-mail:1019365767@qq.com

丁文銳(1971-),女,研究員,博士,主要研究方向為圖像處理和信號處理。

E-mail:ding@buaa.edu.cn

網(wǎng)絡優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160622.1127.006.html