警用無(wú)人機(jī)路徑規(guī)劃技術(shù)研究

劉碩 陳毅雨

武警工程大學(xué)裝備工程學(xué)院，陜西西安，710086

警用無(wú)人機(jī)路徑規(guī)劃技術(shù)研究

劉碩 陳毅雨

武警工程大學(xué)裝備工程學(xué)院，陜西西安，710086

針對(duì)無(wú)人機(jī)在武警部隊(duì)的使用情況，為解決無(wú)人機(jī)路徑規(guī)劃問(wèn)題，搭建無(wú)人機(jī)路徑規(guī)劃的求解框架，分析了無(wú)人機(jī)性能約束及戰(zhàn)場(chǎng)威脅約束，探討了無(wú)人機(jī)路徑幾何建模方法；并介紹了在無(wú)人機(jī)路徑規(guī)劃中用到的幾種路徑規(guī)劃算法（其中包括傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法）。最后，闡述了無(wú)人機(jī)路徑規(guī)劃面臨的重要問(wèn)題及發(fā)展方向。

無(wú)人機(jī)；武警部隊(duì)；路徑規(guī)劃；規(guī)劃算法

1 引言

作為維護(hù)國(guó)家安全的一支重要武裝力量，為了更好的完成使命任務(wù)，武警部隊(duì)不斷加快其信息化發(fā)展的步伐。無(wú)人機(jī)為超低空或近距離偵察、監(jiān)視和打擊提供了平臺(tái)，是超低地面環(huán)境中的有力偵查手段，因而在武警部隊(duì)執(zhí)行任務(wù)中扮演越來(lái)越重要的角色。但是先前的無(wú)人機(jī)都是根據(jù)地面任務(wù)要求，按照預(yù)先計(jì)算設(shè)定好的軌跡飛行。無(wú)人機(jī)實(shí)時(shí)路徑規(guī)劃是無(wú)人機(jī)集群配合、集群戰(zhàn)術(shù)再規(guī)劃、集群戰(zhàn)術(shù)目標(biāo)再制定等自主飛行的技術(shù)基礎(chǔ)，是提高無(wú)人機(jī)的生存概率的一種最有效的方法。

2 無(wú)人機(jī)路徑規(guī)劃

路徑規(guī)劃是根據(jù)任務(wù)目標(biāo)規(guī)劃滿足約束條件的飛行軌跡，是自主系統(tǒng)中不可分割的一個(gè)整體部分，它負(fù)責(zé)從一個(gè)地方運(yùn)動(dòng)到另一個(gè)地方的路徑問(wèn)題。路徑規(guī)劃的目的是根據(jù)預(yù)設(shè)數(shù)字地圖，通過(guò)GPS/INS組合導(dǎo)航系統(tǒng)，在適當(dāng)時(shí)間內(nèi)計(jì)算出最優(yōu)或最短的飛行軌跡?？紤]到數(shù)字地圖誤差及隨機(jī)環(huán)境的影響（如障礙物等），要求無(wú)人機(jī)在飛行過(guò)程中具有動(dòng)態(tài)修正軌跡的能力，能回避犯罪分子威脅到的環(huán)境，安全地完成預(yù)定任務(wù)。無(wú)人機(jī)航跡規(guī)劃主要包括環(huán)境信息（如障礙物、犯罪分子打擊威脅區(qū)、地形因素）、無(wú)人機(jī)系統(tǒng)約束、路徑規(guī)劃器、無(wú)人機(jī)自動(dòng)駕駛儀等。其中無(wú)人機(jī)系統(tǒng)有兩個(gè)回路，內(nèi)回路是自動(dòng)駕駛儀回路；外回路是制導(dǎo)系統(tǒng)回路。制導(dǎo)系統(tǒng)提供側(cè)向加速度指令以保持無(wú)人機(jī)跟蹤路徑，而自動(dòng)駕駛儀控制無(wú)人機(jī)的升降舵、副翼和方向舵實(shí)現(xiàn)所需要的側(cè)向加速度。

路徑規(guī)劃的目標(biāo)和方法按照無(wú)人機(jī)應(yīng)用于武警部隊(duì)領(lǐng)域的不同而不同，這些應(yīng)用包括：監(jiān)視、搜索與跟蹤、營(yíng)救任務(wù)和災(zāi)難監(jiān)控等。主要方法可用圖1所示的簡(jiǎn)化框圖表示。

圖1 現(xiàn)有路徑規(guī)劃算法

3 無(wú)人機(jī)系統(tǒng)性能約束及戰(zhàn)場(chǎng)威脅約束

3.1 無(wú)人機(jī)系統(tǒng)性能約束

無(wú)人機(jī)因有其自身的機(jī)動(dòng)性能和物理限制，在對(duì)無(wú)人機(jī)路徑進(jìn)行規(guī)劃時(shí)有許多約束。路徑規(guī)劃中約束條件主要有以下幾個(gè)方面：

（1）最小路徑段長(zhǎng)度：飛行器的機(jī)動(dòng)性能決定無(wú)人機(jī)在變換下一個(gè)飛行姿態(tài)前，必須飛行的一段最短的直線距離，我們把這個(gè)最短的距離稱(chēng)為最小路徑段長(zhǎng)度。

（2）最大拐彎角：在水平方向無(wú)人機(jī)可以拐彎的最大角度。路徑規(guī)劃時(shí)設(shè)定的路徑必須在不大于最大拐彎角范圍內(nèi)拐彎，路徑規(guī)劃時(shí)必須保證生成的路徑是在允許的拐彎角范圍之內(nèi)變化。則設(shè)無(wú)人機(jī)最大轉(zhuǎn)彎角度：航跡點(diǎn)或，每一航段向量，則最大轉(zhuǎn)彎角約束可寫(xiě)成：

（3）最大爬升/俯沖角：在垂直方向上無(wú)人機(jī)允許爬升和俯沖的最大角度；無(wú)人機(jī)的機(jī)動(dòng)性能約束決定了其在垂直方向上不能以任意角度上升或下降，而是需要在最大爬升或俯沖角允許的范圍內(nèi)變化的。

（4）最大航程：無(wú)人機(jī)飛行的航跡的最大長(zhǎng)度。無(wú)人機(jī)由于自身體積的限制，且所攜帶的燃料也是有限的，所以無(wú)人機(jī)要安全地返回就必須在燃料允許的情況下飛行，其飛行的最大長(zhǎng)度便有了一個(gè)約束。

3.2 戰(zhàn)斗威脅場(chǎng)約束

無(wú)人機(jī)在飛行過(guò)程中要考慮威脅源（包括自然地理障礙、惡劣復(fù)雜氣候、犯罪分子占據(jù)地等）的空間位置、可威脅半徑等。假設(shè)犯罪分子位置坐標(biāo)，可威脅半徑，則區(qū)域

（1）威脅場(chǎng)分區(qū)。

（2）可行路線識(shí)別及網(wǎng)絡(luò)建立。

（3）威脅場(chǎng)包絡(luò)識(shí)別及綜合網(wǎng)絡(luò)建立。

4 無(wú)人機(jī)路徑幾何建模

4.1 基于柵格的幾何建模

柵格，也稱(chēng)網(wǎng)格。是將二維平面按照一定的標(biāo)準(zhǔn)進(jìn)行分解的產(chǎn)物。按照單元格的大小和形狀是否相同，網(wǎng)格可以分為均勻網(wǎng)格和非均勻網(wǎng)格。均勻網(wǎng)格中以正多邊形網(wǎng)格最為常見(jiàn)，包括正三角形網(wǎng)格、正方形網(wǎng)格和正六邊形網(wǎng)格；非均勻網(wǎng)格中以對(duì)均勻網(wǎng)格局部單元遞歸分解得到的遞階網(wǎng)格最為多見(jiàn)；正方形網(wǎng)格由于意義明確、描述方便而最為常用；正六邊形網(wǎng)格具有良好的平面幾何性質(zhì)。

4.2 基于圖形的環(huán)境表示

對(duì)于二維平面內(nèi)的無(wú)人機(jī)路徑規(guī)劃問(wèn)題，根據(jù)圖的來(lái)源不同，可將路徑規(guī)劃中用到的圖劃分為三類(lèi)：

（1）可視圖和切線圖

可視圖法，在穿越的環(huán)境中能產(chǎn)生由視線連接的路徑，這個(gè)路徑是由直線段連接的無(wú)方向圖構(gòu)成的圖形網(wǎng)絡(luò)生成。該方法中，只考慮多邊形障礙物。在圖G=（V，E）中，V表示障礙物的頂點(diǎn)，邊線E表示不與障礙物相交的連接所有頂點(diǎn)的直線段，因此頂點(diǎn)僅包含那些相互間可視的點(diǎn)。如果障礙物也用圓或扇形表示，那么可視圖就演變成切線圖。因此威脅的切線可表示可飛航跡,構(gòu)造出的可飛路徑圖是最短路徑圖。圖3中S為起點(diǎn)，D為目標(biāo)點(diǎn)，圖3（a）和圖3（b）分別表示不同威脅情況下的切線圖。

圖3 不同威脅情況下的切線圖

（2）VORONOI圖

VORONOI圖是由若干個(gè)圍繞障礙物的共邊多邊形產(chǎn)生的連接圖。將VORONOI圖運(yùn)用于無(wú)人機(jī)路徑規(guī)劃當(dāng)中一般分為兩個(gè)步驟，第一個(gè)步驟是先生成初始的航路，將已經(jīng)探明的需要避開(kāi)的一些構(gòu)成威脅的區(qū)域構(gòu)造VORONOI圖，根據(jù)VORONOI圖的性質(zhì)，VORONOI多邊形的每條邊上的點(diǎn)到相對(duì)應(yīng)的兩個(gè)點(diǎn)等距離。也就是說(shuō)，VORONOI邊上的點(diǎn)是到威脅點(diǎn)的最遠(yuǎn)點(diǎn)，所以VORONOI圖的邊界即為無(wú)人機(jī)的所有可供飛行的航路，將這些邊界設(shè)定權(quán)重值后即可利用搜索算法來(lái)求得最優(yōu)的路徑規(guī)劃，這樣就完成了初步的路徑規(guī)劃。圖4為生成VORONOI圖的示例，其中圖4（a）是經(jīng)過(guò)戰(zhàn)場(chǎng)態(tài)勢(shì)分析評(píng)估犯罪分子位置后生成的威脅分布圖，圖4（b）是用平面掃描算法生成上述威脅分布的帶邊界的VORONOI圖模型。

圖4 生成VORONOI圖前后對(duì)比示意圖

（3）概率路標(biāo)圖(PRM)

概率法是隨機(jī)選取相鄰點(diǎn)使其滿足一定的優(yōu)化準(zhǔn)則，如最短距離，此時(shí)概率法稱(chēng)為概率路圖法。在二維平面或三維空間內(nèi)隨機(jī)采樣得到可行路標(biāo)點(diǎn)，連接彼此可見(jiàn)的相鄰路標(biāo)點(diǎn)得到自由路徑，路標(biāo)點(diǎn)和自由路徑即構(gòu)成概率路標(biāo)圖。

5 無(wú)人機(jī)路徑規(guī)劃算法

路徑規(guī)劃算法可以分為傳統(tǒng)經(jīng)典算法和現(xiàn)代智能算法兩大類(lèi)。

傳統(tǒng)經(jīng)典算法主要是動(dòng)態(tài)規(guī)劃法，它是求解多步?jīng)Q策問(wèn)題的一種有效方法，它通過(guò)把一個(gè)多步?jīng)Q策問(wèn)題轉(zhuǎn)化為多個(gè)一步優(yōu)化問(wèn)題并逐個(gè)求解從而降低復(fù)雜決策問(wèn)題求解的難度。該算法應(yīng)用于無(wú)人機(jī)路徑規(guī)劃中，要求模型相對(duì)簡(jiǎn)單，不要求威脅場(chǎng)連續(xù)性，可以獲得全局最優(yōu)解，但缺陷是動(dòng)態(tài)規(guī)劃在用于求解復(fù)雜優(yōu)化問(wèn)題時(shí)可能引起維數(shù)災(zāi)害，這限制了它的應(yīng)用范圍。

現(xiàn)代智能算法主要有A*算法和遺傳算法。A*算法是在無(wú)人機(jī)航跡規(guī)劃中運(yùn)用最為經(jīng)典的方法之一，該算法屬于一種啟發(fā)式搜索算法，啟發(fā)式搜索有利于減少搜索路徑，大大提高了搜索效率。遺傳算法是一種通過(guò)模擬自然進(jìn)化過(guò)程，運(yùn)用于復(fù)雜系統(tǒng)搜索最優(yōu)解的算法，遺傳算法屬于優(yōu)化算法。

6 結(jié)語(yǔ)

隨著無(wú)人機(jī)在武警部隊(duì)承擔(dān)的任務(wù)越來(lái)越復(fù)雜，其飛行環(huán)境的不確定性，對(duì)路徑規(guī)劃的要求也將越來(lái)越高。未來(lái)無(wú)人機(jī)在算法方面的發(fā)展方向及研究重點(diǎn)主要有：（1）不確定環(huán)境下的實(shí)時(shí)路徑規(guī)劃。對(duì)多傳感信息運(yùn)用不確定性理論進(jìn)行綜合處理，真正實(shí)現(xiàn)在無(wú)人干預(yù)的情況下，根據(jù)探測(cè)結(jié)果自動(dòng)修改路徑；（2）戰(zhàn)術(shù)級(jí)的強(qiáng)實(shí)時(shí)的路徑規(guī)劃問(wèn)題；（3）多任務(wù)目標(biāo)（如低空突防、目標(biāo)搜索營(yíng)救、信息偵察等任務(wù)）綜合的規(guī)劃算法；（4）多機(jī)協(xié)同規(guī)劃算法；（5）針對(duì)地形、敵情信息處理方法的研究算法。

[1]鄭昌文,嚴(yán)平,丁明躍.飛行器航跡規(guī)劃研究現(xiàn)狀與趨勢(shì)[J].宇航學(xué)報(bào),2007.28(6):1441-1446.

[2]徐翔,梁瑞仕,楊會(huì)志.基于改進(jìn)遺傳算法的智能體路徑規(guī)劃仿真[J].計(jì)算機(jī)仿真,2014.31(6):357-361.

[3]Roberge V，Tarbouchi M，Labonte G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J].IEEE Transactions on Industrial Informatics,2013，9(1):132-141.

[4]周青,李廣文.基于A*算法的無(wú)人機(jī)四維航跡規(guī)劃研究[J].計(jì)算機(jī)仿真,2014.31(4):92-96.

[5]葛艷,稅薇,韓玉.基于貝葉斯網(wǎng)絡(luò)和蟻群算法的航路優(yōu)化[J].計(jì)算機(jī)工程,2009.35(12):175-177.

[6]J Yang,Y Zhuang. An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem[J].Applied soft computing,2010,10(2):653-660.

[7]Sun H L,Yue L Y,Yao S Y. Study on selection of emergency rescue based on GIS[J].Advanced Materials Research，2014,864:2804-2807.

[8]王俊,周樹(shù)道,朱國(guó)濤.無(wú)人機(jī)航跡規(guī)劃常用算法[J].火力與指揮控制,2012.37(8):5-8.

[9]任波,于雷,韓李勛.自適應(yīng)蟻群算法的無(wú)人機(jī)航跡規(guī)劃方法[J].電光與控制,2007.14(6):36-39.

[10]馮軍紅,陳明強(qiáng).基于自適應(yīng)蟻群算法的救援直升機(jī)航跡規(guī)劃[J].計(jì)算機(jī)仿真,2015.32(5):55-57.

劉碩/1992年生/男/遼寧沈陽(yáng)人/碩士/研究方向?yàn)檠b備科研與實(shí)驗(yàn)

陳毅雨/1992年生/男/廣東湛江人/碩士/研究方向?yàn)檠b備建設(shè)與發(fā)展