一種無人機(jī)路徑規(guī)劃策略

王婷

（四川職業(yè)技術(shù)學(xué)院，四川 遂寧 629000）

一、引言

當(dāng)前，在智能控制技術(shù)的支撐下，各類無人機(jī)不斷出現(xiàn)，并應(yīng)用于社會(huì)生活的各個(gè)領(lǐng)域。如通過無人機(jī)進(jìn)行空中視頻采集，達(dá)到目標(biāo)偵查效果[1]；還如利用無人機(jī)高效機(jī)動(dòng)的特點(diǎn)提高農(nóng)藥噴灑效率；再如利用無人機(jī)對無線傳感網(wǎng)絡(luò)的通信節(jié)點(diǎn)進(jìn)行信息采集，達(dá)到信息收集的效果。通常，無人機(jī)的通信資源、信息存儲(chǔ)資源、電能資源等均有限制，如何基于無人機(jī)特定資源約束進(jìn)行路徑規(guī)劃成為一項(xiàng)研究課題。李若等[2]提出了一種“基于風(fēng)險(xiǎn)管控的城市空中交通無人機(jī)路徑規(guī)劃”方法，考慮了無人機(jī)起降時(shí)的城市人員密度環(huán)境,并對路徑風(fēng)險(xiǎn)進(jìn)行了評估，進(jìn)而采用A*算法對無人機(jī)路徑規(guī)劃進(jìn)行求解。吳成振等[3]提出了一種“多約束條件下的無人機(jī)軌跡快速規(guī)劃”方法，給出了定位誤差約束下的數(shù)學(xué)模型,推導(dǎo)出了空間圓弧軌跡方程,利用貪心算法對無人機(jī)的航跡進(jìn)行快速規(guī)劃。本文綜合相關(guān)技術(shù)提出了一種無人機(jī)路徑規(guī)劃策略。對無人機(jī)路徑規(guī)劃中的資源約束條件進(jìn)行了分析，生成了整體優(yōu)化模型，并給出了求解方法，進(jìn)而生成路徑規(guī)劃策略，具有一定理論參考價(jià)值。

二、總體技術(shù)理念

本文所述的一種無人機(jī)路徑規(guī)劃策略分為四個(gè)技術(shù)環(huán)節(jié)：第一環(huán)節(jié)是三維空間網(wǎng)格化，將無人機(jī)作業(yè)范圍劃分為格式化數(shù)字空間，并對各空間進(jìn)行標(biāo)號(hào)，進(jìn)而在實(shí)際偵查的基礎(chǔ)上，對各空間網(wǎng)格進(jìn)行注釋，如障礙物、信息節(jié)點(diǎn)等。第二環(huán)節(jié)是無人機(jī)及信息節(jié)點(diǎn)參數(shù)采集，如信息節(jié)點(diǎn)通信距離，無人機(jī)單位距離能量消耗等。第三環(huán)節(jié)是路徑規(guī)劃策略生成，綜合空間網(wǎng)格情況、無人機(jī)及信息節(jié)點(diǎn)參數(shù)信息，構(gòu)建資源分配優(yōu)化模型，進(jìn)而對模型求解得到路徑規(guī)劃策略。第四環(huán)節(jié)，飛行路徑動(dòng)態(tài)變更及信息反饋，如信息節(jié)點(diǎn)不工作，障礙物情況變化等。通過上述四個(gè)環(huán)節(jié)，達(dá)到無人機(jī)路徑規(guī)劃效果。

三、詳細(xì)技術(shù)闡述

（一）空間網(wǎng)格化

定義1(空間網(wǎng)格)：將空間網(wǎng)格定義為一個(gè)五元組G={a,b,c,d,e}，其中a 為經(jīng)度、b 為維度、c 為高度，d 為伸展距離，e 為事物類型，如障礙物，通信節(jié)點(diǎn)等?？臻g網(wǎng)格G 的空間范圍為：經(jīng)度大于等于a-d，且小于等于a+d；維度大于等于b-d，且小于等于b+d；高度大于等于c-d，且小于等于c+d。

算法1：空間網(wǎng)格化。輸入空間作業(yè)范圍，輸出空間網(wǎng)格集合。第一步，新建一個(gè)空間網(wǎng)格集合Q，為空間網(wǎng)格伸展距離d 賦值，假設(shè)為z，z 值越大則網(wǎng)格空間范圍越大，網(wǎng)格化工作效率越高；z值越小則網(wǎng)格空間范圍越小，路徑規(guī)劃越精確。第二步，遍歷作業(yè)空間最小經(jīng)度，以步長2d 增加，直到最大經(jīng)度為止，假設(shè)當(dāng)前經(jīng)度為j；遍歷作業(yè)空間最小維度，以步長2d 增加，直到最大維度為止，假設(shè)當(dāng)前維度為i；遍歷作業(yè)空間最小高度，以步長2d增加，直到最大高度為止，假設(shè)當(dāng)前高度為x；新建一個(gè)空間網(wǎng)格G={a,b,c,d,e}，令a=j,b=i,c=x,d=z；若在空間網(wǎng)格G 的空間范圍內(nèi)存在信息節(jié)點(diǎn)，則令e 為信息節(jié)點(diǎn)；若在空間網(wǎng)格G 的空間范圍內(nèi)存在障礙，則令e 為障礙；若空間網(wǎng)格G 的空間范圍內(nèi)為空白，則令e 為NULL。將空間網(wǎng)格G 放入集合Q 中。第三步，輸出集合Q。

（二）路徑規(guī)劃生成

定義2(路徑規(guī)劃參數(shù))：將路徑規(guī)劃參數(shù)定義為一個(gè)十元組CS={Wj,Xr,Zp,Ts,Jk,Rd,Yn,Ch,Bt,Sl}，其中Wj為無人機(jī)架數(shù)、Xr為單架無人機(jī)信息存儲(chǔ)容量、Zp為無人機(jī)處理器資源數(shù)量、Ts為數(shù)據(jù)通信速率、Jk為數(shù)據(jù)接口數(shù)量、Rd為電池容量、Yn為無人機(jī)單位距離移動(dòng)能耗、Ch為單位數(shù)據(jù)傳輸能耗、Bt為信息節(jié)點(diǎn)通信半徑、Sl為信息節(jié)點(diǎn)數(shù)據(jù)容量。

定義3(無人機(jī)路徑)：將無人機(jī)路徑定義為一個(gè)空間網(wǎng)格隊(duì)列Dk={G1,G2,…,Gn-1,Gn}，其中Gi為空間網(wǎng)格，i=1…n。其含義為無人機(jī)從空間網(wǎng)格G1出發(fā)，依次經(jīng)過G2,…,Gn-1，最后到達(dá)Gn。

算法2：單無人機(jī)路徑規(guī)劃算法。輸入路徑規(guī)劃參數(shù)CS、空間網(wǎng)格集合Q、無人機(jī)起飛空間網(wǎng)格G；輸出無人機(jī)路徑。第一步，新建一個(gè)無人機(jī)路徑集合U、信息節(jié)點(diǎn)集合E、Y，遍歷空間網(wǎng)格集合Q，假設(shè)當(dāng)前元素為v，則若v與G相鄰，則新建一個(gè)無人機(jī)路徑Dk，將元素G、v 依次放入Dk 中。第二步，若v 不等于G，則遍歷空間網(wǎng)格集合Q，假設(shè)當(dāng)前元素為f，若f 與v 相鄰，則將元素f 放入Dk 中，將元素f 標(biāo)記為元素v，重復(fù)執(zhí)行第二步；若v 等于G，則將Dk 放入集合U 中。第三步，遍歷集合Q，假設(shè)當(dāng)前元素為item，若item.e 為信息節(jié)點(diǎn)，則將item 放入集合E 中。第四步，遍歷集合U，假設(shè)當(dāng)前元素為無人機(jī)路徑Dk={G1,G2,…,Gn-1,Gn}，令Y=E，遍歷Dk，假設(shè)當(dāng)前元素為item1，若item1.e為障礙，則將Dk從集合U中刪除。若item1.e為信息節(jié)點(diǎn)，則遍歷集合Y，若當(dāng)前元素為item2，如果item1等于item2，則將item2從集合Y 中刪除。第五步，若Y 不為空，則將Dk 從集合U 中刪除。第六步，遍歷集合U，假設(shè)當(dāng)前元素為無人機(jī)路徑Dk1={G1,G2,…,Gn-1,Gn}，假設(shè)此無人機(jī)路徑的長度為Dis，若Dis 為集合U 中的最短路徑，則輸出無人機(jī)路徑Dk1。

算法3：多無人機(jī)路徑規(guī)劃算法。輸入路徑規(guī)劃參數(shù)CS、空間網(wǎng)格集合Q、無人機(jī)起飛空間網(wǎng)格G；輸出無人機(jī)路徑。第一步，創(chuàng)建評價(jià)函數(shù)H=(a1*無人機(jī)行駛總距離+a2*無人機(jī)消耗總能量)，a1、a2為權(quán)值。第二步，設(shè)立優(yōu)化目標(biāo)為min(H)；設(shè)立約束條件為：單個(gè)無人機(jī)所采集的信息量需小于Xr；單個(gè)無人機(jī)的處理器資源適用量需小于Zp；單個(gè)無人機(jī)可同時(shí)采集Jk個(gè)信息節(jié)點(diǎn)；Wj個(gè)無人機(jī)路徑需要覆蓋所有的信息節(jié)點(diǎn)；單個(gè)無人機(jī)路徑所消耗的能量與信息采集能量消耗之和需要小于電池容量Rd；無人機(jī)在進(jìn)行信息采集時(shí)，與信息節(jié)點(diǎn)的距離應(yīng)小于Bt；單個(gè)無人機(jī)路徑中不應(yīng)出現(xiàn)障礙。第三步，將目標(biāo)函數(shù)作為種群個(gè)體的適應(yīng)度，一條染色體即為一種多無人機(jī)路徑規(guī)劃方案，利用遺傳算法對目標(biāo)函數(shù)進(jìn)行求解，生成多無人機(jī)路徑并輸出。

（三）路徑規(guī)劃變更

路徑變更思想為：在無人機(jī)路徑執(zhí)行過程中，針對路況和信息節(jié)點(diǎn)實(shí)際情況對無人機(jī)路徑進(jìn)行變更。

算法4：路徑變更算法。輸入：無人機(jī)路徑集合P；空間網(wǎng)格集合Q；輸出：更新后的無人機(jī)路徑規(guī)劃。第一步，更新空間網(wǎng)格集合Q，若空間網(wǎng)格G 中的信息節(jié)點(diǎn)停止工作，則更新G.e 為障礙；若空間網(wǎng)格G 中的障礙消除，則更新G.e 為NULL；若空間網(wǎng)絡(luò)G 中出現(xiàn)了障礙，則更新G.e 為障礙。第二步，遍歷無人機(jī)路徑集合P，假設(shè)當(dāng)前元素為Dk，遍歷Dk，假設(shè)當(dāng)前元素為item3，若item3.e 為信息節(jié)點(diǎn)，且此信息節(jié)點(diǎn)信息已經(jīng)采集，則將空間網(wǎng)格集合中的item3.e變更為障礙。第三步，將各無人機(jī)當(dāng)前位置作為出發(fā)點(diǎn)，由算法2 及算法3 生成無人機(jī)路徑規(guī)劃，并輸出。

四、結(jié)語

為了解決基于資源約束的無人機(jī)路徑規(guī)劃問題，本文提出了一種無人機(jī)路徑規(guī)劃策略。對總體技術(shù)理念進(jìn)行了描述，對空間網(wǎng)格化、路徑規(guī)劃及其變更進(jìn)行了闡述，對算法步驟進(jìn)行了詳細(xì)描述，具有一定理論參考價(jià)值。下一步，將對多場景復(fù)雜環(huán)境下的無人機(jī)路徑規(guī)劃問題進(jìn)行研究。