基于遙感任務(wù)的凹多邊形區(qū)域無人機(jī)航跡規(guī)劃算法

劉旭林，李榮昊，蔡翔遠(yuǎn)，陳曉桐，魏江南，李芹，趙紅穎

( 北京大學(xué) 地球與空間科學(xué)學(xué)院, 北京 100871 )

0 引 言

由于無人機(jī) (UAV) 具有靈活、高效的特點(diǎn)，不僅在遙感監(jiān)測(cè)、自然災(zāi)害救援與評(píng)估等方面?zhèn)涫芮嗖A，而且可以快速獲取所需地區(qū)的遙感影像，以便進(jìn)行監(jiān)督與決策. 在UAV航跡規(guī)劃領(lǐng)域，單機(jī)航跡規(guī)劃算法已相對(duì)成熟，根據(jù)獲取影像區(qū)域的特點(diǎn)可分為凸多邊形區(qū)域單機(jī)航跡規(guī)劃與凹多邊形區(qū)域單機(jī)航跡規(guī)劃. 對(duì)于凸多邊形區(qū)域單機(jī)航跡規(guī)劃算法，陳海等[1]從理論上獲取了在理想情況下的飛行方案，證明當(dāng)UAV的主飛行方向采用凸多邊形最小寬度所在邊的方向時(shí)，UAV的轉(zhuǎn)彎次數(shù)最小，從而其總路程最短.COOMBES等[2]考慮了風(fēng)速對(duì)UAV航跡的影響，用實(shí)驗(yàn)證明在風(fēng)速較大的情況下，垂直于風(fēng)速飛行總時(shí)間最短. 對(duì)于凹多邊形區(qū)域而言，王自亮等[3]提出了基于掃描線的UAV航跡規(guī)劃算法，并利用之字形策略實(shí)現(xiàn)了區(qū)域的全覆蓋.

對(duì)于單機(jī)而言，其獲取一定區(qū)域的影像往往時(shí)間較長(zhǎng)，在處理自然災(zāi)害救援等緊急任務(wù)時(shí)，采用多機(jī)聯(lián)合方案則顯得尤為重要. 對(duì)于多機(jī)聯(lián)合方案，目前的算法思路是將其分解為兩個(gè)子問題來分別求解，即飛行區(qū)域劃分優(yōu)化與UAV全覆蓋航跡優(yōu)化[4-7]. 由于這兩個(gè)子問題是分別進(jìn)行優(yōu)化的，所以每個(gè)飛行區(qū)域中的UAV主飛行方向并不完全相同，在野外實(shí)驗(yàn)時(shí)，由于存在極端環(huán)境，這種方法會(huì)存在UAV在飛行過程中相撞的風(fēng)險(xiǎn). 對(duì)于基于遙感任務(wù)的航跡規(guī)劃而言，飛行區(qū)域選在郊區(qū)是常見的現(xiàn)象，這些區(qū)域會(huì)受到比較嚴(yán)重的風(fēng)速干擾，UAV可能會(huì)發(fā)生偏航現(xiàn)象，采用不同區(qū)域不同主飛行方向?qū)⒃龃骍AV相撞的風(fēng)險(xiǎn)；而且在進(jìn)行航跡規(guī)劃設(shè)計(jì)時(shí)，UAV的轉(zhuǎn)彎軌跡沒有被較好地考慮，不同類型的UAV往往會(huì)采取不同的轉(zhuǎn)彎策略，主方向不統(tǒng)一會(huì)增大UAV相撞的風(fēng)險(xiǎn). 此外，對(duì)于遙感任務(wù)而言，其航跡飛行需要獲取到航拍影像，后期還需要將這些影像拼接成圖，但目前的算法方案各個(gè)區(qū)域是獨(dú)立的，不同區(qū)域之間缺少重疊度，無法滿足遙感成圖的需求. 再者，目前的航跡規(guī)劃方案都是采用定時(shí)拍攝影像，即相機(jī)每隔一定的時(shí)間進(jìn)行拍攝，不需要給出具體的拍攝地點(diǎn)，因此不需要獲取相應(yīng)的航拍點(diǎn)位，但是由于UAV自身或者氣候因素，UAV可能會(huì)發(fā)生偏航，采用這種方式獲得的遙感影像質(zhì)量往往較差，滿足不了成圖需求. 對(duì)于目前的多機(jī)航跡規(guī)劃算法，它們大多適用于其他目的，并不適用于遙感成圖. 如迪杰斯拉特算法(Dijkstra)及其相應(yīng)改進(jìn)算法[8]適用于偵查或打擊任務(wù)，快速搜索隨機(jī)樹(RRT)及其相應(yīng)改進(jìn)算法[9-10]適用于火災(zāi)撲救及UAV避障，蟻群算法以及相應(yīng)改進(jìn)算法[11-13]適用于點(diǎn)對(duì)點(diǎn)的路徑規(guī)劃及偵查， A*及其改進(jìn)算法適用于點(diǎn)對(duì)點(diǎn)的路徑規(guī)劃以及跨區(qū)域間的搜索[14-15].它們無法很好地獲取待觀測(cè)區(qū)域的全覆蓋影像，并且所獲取的影像航帶間的聯(lián)系性不強(qiáng)，圖像拼接較為困難，無法得到高質(zhì)量的遙感影像圖.

綜上，目前的航跡規(guī)劃算法仍不能很好地適用于遙感任務(wù)中，缺少對(duì)成圖需求、UAV飛行情況與特殊情況的考慮，算法魯棒性與成圖效果不盡人意. 因此本文提出基于遙感任務(wù)的凹多邊區(qū)域UAV航跡規(guī)劃算法，利用多機(jī)協(xié)同來進(jìn)行規(guī)劃，采用統(tǒng)一的主飛行方向、定點(diǎn)拍攝來進(jìn)行成圖，考慮遙感影像成圖所需的重疊度. 在滿足拍攝影像全覆蓋的前提下，使得飛行任務(wù)整體時(shí)間最短.

1 基于遙感任務(wù)的UAV航跡規(guī)劃算法

基于遙感任務(wù)的UAV航跡規(guī)劃算法的最終目的是獲得滿足需求空間分辨率的高質(zhì)量遙感影像，為了解耦合航跡規(guī)劃與圖像拼接過程，可將圖像拼接的需求濃縮為空間分辨率、航向重疊度與旁向重疊度三個(gè)指標(biāo).

對(duì)于空間分辨率，它是指影像中的長(zhǎng)度對(duì)應(yīng)到實(shí)際地面時(shí)的比值，它與UAV的飛行高度相關(guān)，計(jì)算公式為

式中：m為空間分辨率；f為相機(jī)焦距；H為UAV飛行高度.

對(duì)于航向重疊度，它是指沿著UAV飛行方向兩影像間的重疊度，而旁向重疊度則是指垂直UAV飛行方向兩影像間的重疊度. 重疊度的計(jì)算公式如下：

式中：a為航向重疊度；b為旁向重疊度；xd為航向航點(diǎn)間隔；yd為旁向航點(diǎn)間隔；wg與hg為每張拍攝影像對(duì)應(yīng)到地面實(shí)際的長(zhǎng)度和寬度.

為了獲得高質(zhì)量的遙感影像，需要對(duì)影像進(jìn)行定點(diǎn)拍攝，獲取到精確的定位. 如果采用定時(shí)拍攝，當(dāng)受到周邊環(huán)境或自身因素影響，UAV并不能到合適的點(diǎn)位采集到數(shù)據(jù)，造成圖像拼接質(zhì)量的不穩(wěn)定. 在遙感任務(wù)的規(guī)劃中，利用影像的大小、影像空間分辨率、影像間的重疊度可以得到每張影像對(duì)應(yīng)到地面的大小、航向航點(diǎn)間隔與旁向航點(diǎn)的間隔. 為了提高算法的魯棒性，考慮到UAV轉(zhuǎn)彎等實(shí)際飛行情況與UAV偏航等特殊情況，本次算法采用統(tǒng)一的主飛行方向進(jìn)行航跡規(guī)劃，盡可能避免UAV之間發(fā)生碰撞.考慮到算法的通用性，此算法利用多機(jī)協(xié)同來解決凹多邊區(qū)域航跡規(guī)劃，凸多邊形區(qū)域是凹多邊形區(qū)域的一種特殊情形.

因此，本次算法可描述如下：在給定遙感圖像大小w*h、 空間分辨率s、航向重疊度a、 旁向重疊度b的前提下，令m架性能相同的UAV載有同一焦距f的相機(jī)去一待觀測(cè)的凹多邊形區(qū)域 S 執(zhí)行遙感觀測(cè)任務(wù)，如何進(jìn)行UAV航跡規(guī)劃設(shè)計(jì)，使得任務(wù)的總體時(shí)間最短，忽略從機(jī)場(chǎng)到飛行起始點(diǎn)的耗時(shí)，約束條件為所有UAV的主飛行方向相同. 因此本次算法主要分為兩部分，一個(gè)是UAV主飛行方向的選取，另一個(gè)是選取某一主方向后，航跡規(guī)劃的設(shè)計(jì). 為了便于理解，本文將先進(jìn)行第二部分的介紹，再進(jìn)行主飛行方向選取的討論，技術(shù)路線如圖1所示.

圖 1 基于遙感任務(wù)的凹多邊形區(qū)域航跡規(guī)劃技術(shù)路線

2 給定主飛行方向的航跡優(yōu)化模型

本節(jié)將討論給定UAV的主飛行方向后的航跡優(yōu)化. 對(duì)于凹多邊形區(qū)域而言，給定主飛行方向后有三種可能的思路，如圖2所示. 第一種思路是求取凹多邊形的最小凸包，將凹多邊形轉(zhuǎn)換為凸多邊形來進(jìn)行航跡規(guī)劃，如圖2(a)所示. 該方法雖然簡(jiǎn)單有效，但是存在很多無效的航線，算法整體效率不高. 第二種是利用掃描線算法來對(duì)凹多邊形進(jìn)行劃分，分割出多個(gè)區(qū)域，進(jìn)而進(jìn)行航跡規(guī)劃，如圖2(b)所示. 這種方法消除了無效的航線，極大地提升了航線的利用率，但是會(huì)存在分割的碎片區(qū)域過多問題，額外派UAV去執(zhí)行飛行任務(wù)將花費(fèi)較大的代價(jià). 第三種思路是對(duì)圖2中的碎片多邊形進(jìn)行適當(dāng)合并，從而使UAV分配更為合理并提高算法效率，如圖2(c)所示.本次算法將采用第三種思路進(jìn)行，整體算法依次可分解為五個(gè)部分，即航線分割點(diǎn)求取、多邊形劃分、UAV分配、碎片多邊形合并與UAV再分配以及航點(diǎn)信息求取.

圖 2 三種凹多邊形航跡規(guī)劃思路

2.1 航線分割點(diǎn)求取

對(duì)于航線求取而言，需要獲取航帶間的旁向間隔，其計(jì)算公式為

式中：yb為航帶間的旁向間隔；b為旁向重疊度；h為影像垂直于UAV飛行方向的長(zhǎng)度；m為空間分辨率.

知曉主飛行方向與航帶間的旁向間隔后可以獲取航線的空間分布，獲取航線的分割點(diǎn)仍有兩種思路. 第一種是通過航線與待觀測(cè)區(qū)域求交點(diǎn)獲得；另一種是通過航帶多邊形與待觀測(cè)區(qū)域求交，得到相交多邊形在沿著航向方向上的兩個(gè)端點(diǎn)值. 對(duì)于第一種方案，存在遺漏區(qū)域、過度分割、獲取的邊界圖像質(zhì)量較差等問題. 因此本次算法采用方案二進(jìn)行.

2.2 多邊形劃分

對(duì)于多邊形劃分，將采用順序掃描法與堆棧處理進(jìn)行，利用相鄰條帶間的連接關(guān)系來對(duì)多邊形進(jìn)行劃分，劃分示意圖如圖2(b)所示，算法流程如圖3所示.

圖 3 多邊形劃分算法流程圖

2.3 UAV分配

UAV的分配問題可以簡(jiǎn)單描述如下：給定UAV數(shù)量m，給定多個(gè)多邊形區(qū)域S1，S2，···，St，以及每個(gè)區(qū)域中每條航帶的長(zhǎng)度，如何分配UAV，使得UAV執(zhí)行飛行任務(wù)時(shí)最大飛行距離最小. 它可以拆分為兩個(gè)子問題，一個(gè)從局部入手，討論同一多邊形區(qū)域內(nèi)UAV的分配問題，另一個(gè)從整體入手，討論不同多邊形區(qū)域間UAV的整體分配問題. 由于需要考慮UAV轉(zhuǎn)彎時(shí)花費(fèi)的距離，為簡(jiǎn)單說明，可以給每條航帶增加一次UAV轉(zhuǎn)彎花費(fèi)的距離.

2.3.1 區(qū)域內(nèi)UAV分配算法

區(qū)間內(nèi)的UAV分配算法主要是獲取分配航帶的方案，使得UAV執(zhí)行飛行任務(wù)時(shí)最大的飛行距離最小. 這個(gè)問題可以簡(jiǎn)化為：給定一個(gè)整數(shù)m以及非負(fù)數(shù)組listx，如何將listx分成m個(gè)非空連續(xù)子數(shù)組，使得各個(gè)子數(shù)組之和的最大值最小，記listx中元素的個(gè)數(shù)為n. 解決這個(gè)問題有兩種方案：一個(gè)是動(dòng)態(tài)規(guī)劃，另一個(gè)是二分查找與貪心策略. 對(duì)于動(dòng)態(tài)規(guī)劃策略來說，可以令dp[i][j]表示將listx的前i個(gè)數(shù)分成j個(gè)非空數(shù)組時(shí)，最小的各個(gè)子數(shù)組之和的最大值. 轉(zhuǎn)移方程為

式中： s ub(k+1,i) 表示數(shù)組listx坐標(biāo)落在 [k+1,i] 中所有數(shù) 字的和； d p[k][j-1] 表 示 將listx的前k個(gè)數(shù) 分 成j-1個(gè)非空數(shù)組時(shí)，最小的各個(gè)子數(shù)組之和的最大值.

通過遞推，可以求得 dp 表， d p[n-1][m] 即為最終所求的結(jié)果. 采用動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為O(n2m) ，空間復(fù)雜度為O(nm) ，空間復(fù)雜度為動(dòng)態(tài)規(guī)劃數(shù)組所需的空間開銷.

對(duì)于二分查找與貪心策略而言，可以用二分法來查找各個(gè)子數(shù)組之和最大值的最小值，其搜索空間的上限是listx中所有數(shù)字的和，即listsum，搜索下界是listx中的最大值listmax. 假定好這個(gè)最小的最大值后，可以按照貪心策略依次進(jìn)行l(wèi)istx的劃分. 依據(jù)貪心策略劃分出的listx子數(shù)組的數(shù)量與m的關(guān)系決定二分查找的方向，直到找出最優(yōu)解. 第二種策略的時(shí)間復(fù)雜度為O(n*log(listsum-listmax)) ， 空間復(fù)雜度為O(1) . 在n比較大時(shí)，采用第二種算法性能更優(yōu)，因此本次區(qū)域內(nèi)無人機(jī)分配算法采用二分查找與貪心策略進(jìn)行計(jì)算.

2.3.2 區(qū)域間UAV的整體分配算法

區(qū)域間UAV的整體分配算法采用貪心策略以得到合適的UAV分配方案，使得在多個(gè)多邊形區(qū)域中，各個(gè)UAV執(zhí)行飛行任務(wù)時(shí)最大飛行距離最小.具體而言，區(qū)域間UAV的整體分配方法可簡(jiǎn)單表述如下：給定UAV數(shù)量m，區(qū)域數(shù)量為n，將區(qū)域內(nèi)總航跡長(zhǎng)度按從小到大進(jìn)行排序，組成多邊形區(qū)域數(shù)組lists，每個(gè)多邊形區(qū)域包含每條航帶的長(zhǎng)度信息，求對(duì)應(yīng)多邊形的UAV數(shù)量列表listp.

該問題的求解可以具體分成三個(gè)步驟S1、S2與S3. 對(duì)于步驟S1，可以令初始UAV數(shù)量列表listp為[1,1,···,1,m-n+1]，利用區(qū)間內(nèi)UAV分配算法，在每個(gè)區(qū)域lists[i]內(nèi)計(jì)算當(dāng)分配listp[i]架UAV時(shí)，所有UAV航程最大的最小值，將這些最小值組成數(shù)組listmax，之后轉(zhuǎn)到步驟S2.

對(duì)于步驟S2，在listmax中查詢最大值的下標(biāo)，將其記為idmax，對(duì)應(yīng)的最大值記為valuemax，若idmax為n-1，則直接返回?cái)?shù)組listp，否則轉(zhuǎn)到步驟S3.

對(duì)于步驟S3，需要在listp中尋找同時(shí)滿足以下三個(gè)條件的idneed：idneed≠idmax；listp[idneed]＞1；當(dāng)listp[idneed]為listp[idneed]-1時(shí)，對(duì)應(yīng)區(qū)域中UAV的最大航程的最小值小于valuemax. 如果不存在滿足條件的idneed，則獲得最終結(jié)果，直接返回?cái)?shù)組listp；如果存在，則給listp[idneed]賦值為listp[idneed]-1，給listp[idmax]賦值為listp[idmax]+1，更新listmax，轉(zhuǎn)到步驟S2繼續(xù)進(jìn)行循環(huán).

最終求得的listp便是本算法所期望的結(jié)果.

2.4 碎片多邊形合并與UAV再分配

對(duì)于碎片多邊形的合并，主要解決問題是碎片多邊形和哪個(gè)多邊形合并以及合并后是否更優(yōu)的問題.由于是采用掃描線算法劃分的多邊形，掃描線算法很好地保持了多邊形的鄰近性原則，可以讓碎片多邊形沿主飛行方向進(jìn)行合并，如圖2(c)所示.

對(duì)于多邊形合并是否更優(yōu)問題，算法流程圖如圖4所示，主要分成兩種情況，第一種是碎片多邊形只指派一架UAV執(zhí)行飛行任務(wù)，第二種是碎片多邊形指派多于一架UAV的情形，第二種情況可能會(huì)融合碎片多邊形的部分條帶.

圖 4 多邊形合并算法流程圖

2.5 航點(diǎn)信息求取

為每架UAV分配好航線后還需要獲取具體的航拍點(diǎn)位，航拍點(diǎn)位的獲取依據(jù)航向拍攝間隔，其計(jì)算公式為

式中：xd為航帶間的航向拍攝間隔；a為航向重疊度；w為影像平行于UAV飛行方向的長(zhǎng)度；m為實(shí)際分辨率.

得到UAV的航向拍攝間隔后可以得到UAV各個(gè)航線的航點(diǎn)分布，可以設(shè)置UAV第一條航線的起始點(diǎn)都在待觀測(cè)區(qū)域的同一側(cè).

3 UAV主飛行方向的選取

在選定主飛行方向的情況下使得UAV航跡規(guī)劃最優(yōu)，則可以通過選取合適的主飛行方向使得整體方案最優(yōu). 對(duì)于凸多邊形區(qū)域，陳海等[5]證明主飛行方向平行于凸多邊形最小寬度所對(duì)應(yīng)的邊時(shí)整體路徑最短. 但是對(duì)于凹多邊形而言，采用這種方式飛行可能會(huì)增加無效的航程，使得整體方案不能達(dá)到最優(yōu). 如圖8所示，采用圖8(b)的主方向飛行反而比采用圖8(a)的主方向飛行更優(yōu). 通過大量實(shí)驗(yàn)可發(fā)現(xiàn)，不論是凸多邊形還是凹多邊形，它們的最優(yōu)主方向都屬于多邊形及其凸包所在邊的方向. 因此，猜想凹多邊形區(qū)域的最優(yōu)主方向?qū)儆诎级噙呅渭捌渫拱谶叺姆较?，在?節(jié)的實(shí)驗(yàn)部分將采用實(shí)驗(yàn)來證明其合理性. 由于計(jì)算一個(gè)主飛行方向的最優(yōu)航點(diǎn)分布所需的時(shí)間較短，不足0.01 s，因此可以通過采用多邊形及其凸包所在邊的所有方向分別為UAV的主飛行方向，來尋找全局最優(yōu)解.

4 實(shí)驗(yàn)分析

4.1 航跡優(yōu)化分析

第2節(jié)中，針對(duì)主方向選定的航跡規(guī)劃有三種算法思路，本節(jié)將通過實(shí)驗(yàn)證明算法的優(yōu)越性. 給定任務(wù)一如下所示.

觀測(cè)區(qū)域S1，如圖5所示，共13個(gè)頂點(diǎn)，其頂點(diǎn)坐標(biāo)為

圖 5 待觀測(cè)區(qū)域一

旁向重疊度為0.5，航向重疊度為0.5，航向間隔為400 m，旁向間隔為300 m，UAV 4架，一次轉(zhuǎn)彎花費(fèi)500 m，UAV的飛行速度設(shè)為45 km/h.

三種思路的航跡規(guī)劃結(jié)果如圖6所示，圖6(a)是將凹多邊形區(qū)域轉(zhuǎn)為凸多邊形區(qū)域，進(jìn)而進(jìn)行UAV航跡規(guī)劃. 目前在遙感領(lǐng)域，大多數(shù)算法都采取這種方式. 圖6(b)是將凹多邊形通過掃描線算法分解成多個(gè)區(qū)域，在每個(gè)區(qū)域分別分配不同的UAV去執(zhí)行飛行任務(wù). 這種方法主要存在的缺點(diǎn)是區(qū)域間的UAV分配不均勻，導(dǎo)致算法性能受到限制. 圖6(c)是本文提供的算法，是在凹多邊形劃分算法的基礎(chǔ)上進(jìn)行優(yōu)化，將部分碎片多邊形區(qū)域或者其部分區(qū)域進(jìn)行合并，從而得到更好的結(jié)果. 耗時(shí)與總路程結(jié)果如表1所示. 可以看到，本文提出的算法與凹多邊形分割算法相比總路程雖差不多，但耗時(shí)縮短22.4%，這得益于UAV任務(wù)分配的均衡；與傳統(tǒng)的轉(zhuǎn)換到凸包的算法相比，本文提出的算法耗時(shí)縮短4.0%，總路程縮短15.0%，極大地減少了冗余航線，從而提升了算法的效率.

表 1 不同航跡規(guī)劃算法的UAV耗時(shí)與總路程

圖 6 不同的航跡規(guī)劃算法結(jié)果

4.2 主方向選取分析

對(duì)于凹多邊形區(qū)域主方向選取問題，王自亮等[3]認(rèn)為應(yīng)該先求凹多邊形區(qū)域的最小凸包，將凸包的最小寬度所對(duì)應(yīng)邊的方向選取為最優(yōu)主方向，但是這種選擇方式對(duì)于本文提出的算法并不適用. 考慮任務(wù)二如表2所示：

表 2 不同方向航跡規(guī)劃UAV耗時(shí)與總路程

給定觀測(cè)區(qū)域S2，如圖7所示，共5個(gè)頂點(diǎn)，

圖 7 待觀測(cè)區(qū)域二

圖 8 不同方向航跡規(guī)劃結(jié)果

其頂點(diǎn)坐標(biāo)如下

旁向重疊度為0.5，航向重疊度為0.5，航向間隔為400 m，旁向間隔為300 m，UAV2架，一次轉(zhuǎn)彎花費(fèi)500 m，UAV的飛行速度設(shè)為45 km/h.

圖8(a)是采用凸包的最小寬度所在邊的方向?yàn)橹鞣较驎r(shí)進(jìn)行的航跡規(guī)劃方案，圖8(b)是采用本文提出的全局比較得到的最優(yōu)主方向進(jìn)行的航跡規(guī)劃方案. 表2是兩種方案的耗時(shí)與總路程比較結(jié)果. 可以發(fā)現(xiàn)，采用全局比較得到的結(jié)果比采用凸包的最小寬度所在邊的方向?yàn)橹鞣较虻慕Y(jié)果耗時(shí)縮短25.7%，總路程縮短25.7%. 主要原因是選用凸包的最小寬度所在邊的方向?yàn)橹鞣较驎r(shí)，可能存在區(qū)域劃分不均衡現(xiàn)象并導(dǎo)致碎片多邊形進(jìn)行合并，從而引起冗余距離的增加. 這種冗余距離的增加可能抵消轉(zhuǎn)彎次數(shù)減小帶來的收益.

對(duì)于全局比較而言，其選擇的主方向范圍是凹多邊形及凹多邊形對(duì)應(yīng)凸包所在邊的方向. 為了證明選擇范圍的合理性，將通過任務(wù)一與任務(wù)二，主飛行方向以每隔20°在[0°, 180°]范圍中分別進(jìn)行UAV航跡規(guī)劃. 表3是各個(gè)角度的耗時(shí)與總路程比較結(jié)果，通過比較發(fā)現(xiàn)，采用最優(yōu)方向時(shí)，UAV耗時(shí)最短、總路程最短，從而證實(shí)全局比較范圍選取的合理性.

表 3 各個(gè)方向航跡規(guī)劃UAV耗時(shí)與總路程

5 結(jié) 論

結(jié)合遙感圖像拼接任務(wù)，為更高效地獲取高質(zhì)量影像，本文提出了基于遙感任務(wù)的凹多邊形區(qū)域UAV航跡規(guī)劃算法. 算法主要分為兩部分，第一部分是選定主飛行方向后的UAV航跡優(yōu)化，該優(yōu)化方法采用掃描線算法進(jìn)行多邊形的劃分，結(jié)合二分算法與貪心算法合并碎片多邊形或碎片多邊形部分區(qū)域，使得任務(wù)分配更為合理，從而提升算法效率；第二部分是主飛行方向的選取，通過實(shí)驗(yàn)證明最優(yōu)主方向在凹多邊形及其凸包的邊所在的方向上，從而可以通過全局比較選擇合適的主飛行方向. 本算法不僅適用于凹多邊形區(qū)域，也適用于凸多邊形區(qū)域，可以對(duì)指定方向進(jìn)行UAV航跡規(guī)劃，也適用于不同架次的UAV規(guī)劃，因此有較為廣泛的適用性.

但是本文只考慮了聯(lián)通區(qū)域的UAV航跡規(guī)劃，還缺少對(duì)非聯(lián)通區(qū)域UAV航跡規(guī)劃算法的研究. 對(duì)于UAV以及載荷也都是統(tǒng)一的，缺少多樣性的考慮.當(dāng)UAV載荷的焦距不同時(shí)，每架UAV的飛行高度會(huì)存在差異，這會(huì)導(dǎo)致每架UAV擁有獨(dú)自的航向間隔與旁向間隔，使得觀測(cè)區(qū)域分配與UAV相耦合，這些也是本文后續(xù)要進(jìn)一步研究的方向.