車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察路徑規(guī)劃方法

夏陽(yáng)升 石建邁 陳超 黃金才 程光權(quán)

在現(xiàn)代戰(zhàn)爭(zhēng)中,無(wú)人駕駛飛機(jī)具有成本低、生存能力強(qiáng)、無(wú)人員損失風(fēng)險(xiǎn)、機(jī)動(dòng)性好等優(yōu)點(diǎn),被廣泛用于執(zhí)行枯燥、惡劣、危險(xiǎn)的作戰(zhàn)任務(wù),已經(jīng)成為世界各國(guó)戰(zhàn)場(chǎng)偵察的重要工具[1],并在第四次中東戰(zhàn)爭(zhēng)、海灣戰(zhàn)爭(zhēng)、科索沃戰(zhàn)爭(zhēng)和后來(lái)的伊拉克戰(zhàn)爭(zhēng)中發(fā)揮了重要的作用[2].

無(wú)人機(jī)戰(zhàn)場(chǎng)偵察是利用無(wú)人機(jī)獲取戰(zhàn)場(chǎng)信息的活動(dòng),其中路徑規(guī)劃是無(wú)人機(jī)執(zhí)行偵察任務(wù)的關(guān)鍵支撐技術(shù),是無(wú)人機(jī)偵察任務(wù)規(guī)劃領(lǐng)域的重要研究課題[3].當(dāng)前無(wú)人機(jī)偵察路徑規(guī)劃研究主要針對(duì)地面固定目標(biāo)的偵察任務(wù)進(jìn)行路徑優(yōu)化[4].此外,也有一些考慮敵方雷達(dá)探測(cè)和地面障礙物的規(guī)避路徑[5],以及目標(biāo)的偵察時(shí)間約束[6]等貼近戰(zhàn)場(chǎng)實(shí)際情況的研究,研究領(lǐng)域也從單無(wú)人機(jī)向多無(wú)人機(jī)協(xié)同方向發(fā)展[7].在實(shí)際戰(zhàn)場(chǎng)偵察中,除了固定點(diǎn)目標(biāo),有些時(shí)候還需要獲取某些特定區(qū)域內(nèi)的所有詳細(xì)信息,此時(shí)一般應(yīng)用小型無(wú)人機(jī)對(duì)整個(gè)偵察目標(biāo)區(qū)域進(jìn)行覆蓋掃描.小型無(wú)人機(jī)具有成本低、隱蔽性好、可以低空高精度掃描等優(yōu)點(diǎn),在軍事和民用領(lǐng)域的區(qū)域覆蓋掃描中有著廣泛的應(yīng)用[8].龍國(guó)強(qiáng)等[9]提出集中式預(yù)先規(guī)劃與分布式局部在線(xiàn)再規(guī)劃相結(jié)合的方法,解決多無(wú)人機(jī)協(xié)同區(qū)域覆蓋偵察問(wèn)題.吳青坡等[10]研究了如何提高對(duì)復(fù)雜區(qū)域的偵察效率,高春慶等[11]首先將含障礙物的區(qū)域單元格化,然后為每一架無(wú)人機(jī)劃分子覆蓋區(qū)域,最后使用最小生成樹(shù)的方法為每個(gè)子區(qū)域規(guī)劃偵察路徑.在民用方面,如評(píng)估災(zāi)區(qū)的破壞情況[12],觀(guān)察農(nóng)業(yè)生產(chǎn)中的作物生長(zhǎng)情況[13]和地形圖的測(cè)繪[14]等,都需要優(yōu)化無(wú)人機(jī)對(duì)目標(biāo)區(qū)域的掃描路徑.

當(dāng)前無(wú)人機(jī)區(qū)域覆蓋研究中,大多研究無(wú)人機(jī)如何對(duì)一個(gè)區(qū)域進(jìn)行覆蓋,通過(guò)規(guī)劃無(wú)人機(jī)飛行路徑,以盡可能低的成本完成整個(gè)區(qū)域的覆蓋掃描[15].很多時(shí)候,需要對(duì)多個(gè)戰(zhàn)場(chǎng)區(qū)域進(jìn)行掃描偵察,當(dāng)多個(gè)區(qū)域分散在大范圍戰(zhàn)場(chǎng)的不同位置時(shí),小型無(wú)人機(jī)續(xù)航能力低成為其完成任務(wù)的關(guān)鍵制約因素.

為了擴(kuò)大小型無(wú)人機(jī)執(zhí)行偵察任務(wù)的范圍以完成多區(qū)域覆蓋偵察任務(wù),引入汽車(chē)作為無(wú)人機(jī)的移動(dòng)平臺(tái),攜帶無(wú)人機(jī)在戰(zhàn)場(chǎng)上進(jìn)行大范圍機(jī)動(dòng),構(gòu)建車(chē)機(jī)協(xié)同戰(zhàn)場(chǎng)偵察系統(tǒng).汽車(chē)作為無(wú)人機(jī)的指控與保障平臺(tái),攜帶無(wú)人機(jī)從一個(gè)偵察區(qū)域機(jī)動(dòng)到另一個(gè)偵察區(qū)域,并在機(jī)動(dòng)過(guò)程中為無(wú)人機(jī)充電或更換電池.當(dāng)汽車(chē)攜帶無(wú)人機(jī)達(dá)到某個(gè)目標(biāo)偵察區(qū)域附近時(shí),無(wú)人機(jī)從汽車(chē)起飛,飛到偵察區(qū)域上空完成該區(qū)域的覆蓋偵察后返回汽車(chē).汽車(chē)和無(wú)人機(jī)的結(jié)合可以有效擴(kuò)大小型無(wú)人機(jī)的任務(wù)范圍,提高戰(zhàn)場(chǎng)多區(qū)域偵察的效率.Grocholsky 等[16]為汽車(chē)和無(wú)人機(jī)協(xié)作進(jìn)行空中和地面監(jiān)視構(gòu)建了模型和算法框架.羅志浩、劉忠等[17]建立了一個(gè)由地面車(chē)輛和無(wú)人機(jī)協(xié)作對(duì)多個(gè)點(diǎn)目標(biāo)執(zhí)行情報(bào),監(jiān)視和偵察(ISR)任務(wù)的數(shù)學(xué)模型,并通過(guò)試驗(yàn)表明車(chē)機(jī)協(xié)同模式可以顯著提高ISR 任務(wù)的完成效率.在民用領(lǐng)域,劉瑤等[18]使用模擬退火算法求解車(chē)載無(wú)人機(jī)協(xié)同配送的雙層路徑規(guī)劃問(wèn)題.Tokekar 等人[19]結(jié)合了地面車(chē)輛和無(wú)人機(jī)的優(yōu)勢(shì),設(shè)計(jì)了一個(gè)用于在農(nóng)場(chǎng)的特定位置收集氮含量的系統(tǒng),可以幫助農(nóng)民有效減少肥料的使用.汽車(chē)和小型無(wú)人機(jī)協(xié)同系統(tǒng)在執(zhí)行多種軍事和民用領(lǐng)域的任務(wù)中具有顯著優(yōu)勢(shì).

當(dāng)前車(chē)機(jī)協(xié)同路徑規(guī)劃的研究主要關(guān)注無(wú)人機(jī)對(duì)點(diǎn)目標(biāo)的訪(fǎng)問(wèn)順序和飛行路徑,還沒(méi)有多個(gè)區(qū)域覆蓋偵察路徑規(guī)劃的相關(guān)研究.車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察的路徑規(guī)劃面臨更多新的研究挑戰(zhàn).問(wèn)題中存在兩層路徑,其中空中無(wú)人機(jī)飛行路徑與汽車(chē)在地面路網(wǎng)的行駛路徑在不同的節(jié)點(diǎn)上相互連接.由于車(chē)輛和無(wú)人機(jī)之間在速度、續(xù)航時(shí)間和行駛方式方面的差異,在規(guī)劃過(guò)程中需要考慮兩種路徑相互之間的影響.這種雙層路徑的交互作用使問(wèn)題的解空間比傳統(tǒng)路徑問(wèn)題更為復(fù)雜,求解難度更大.成整個(gè)偵察任務(wù),但無(wú)人機(jī)的續(xù)航能力是有限的,能夠完成一個(gè)區(qū)域的覆蓋偵察,在對(duì)不同區(qū)域偵察時(shí),需要進(jìn)行充電或更換電池.車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察過(guò)程中,一輛汽車(chē)搭載一架小型無(wú)人機(jī)從基地出發(fā),當(dāng)行駛到需要偵察區(qū)域附近時(shí),放飛無(wú)人機(jī),由無(wú)人機(jī)飛到偵察區(qū)域上空進(jìn)行全覆蓋掃描并收集信息;無(wú)人機(jī)完成目標(biāo)區(qū)域的覆蓋掃描后,返回汽車(chē),由汽車(chē)攜帶無(wú)人機(jī)行駛到下一個(gè)偵察區(qū)域,并在行駛過(guò)程中完成無(wú)人機(jī)的充電或更換電池工作;如此循環(huán),汽車(chē)攜帶無(wú)人機(jī)在戰(zhàn)場(chǎng)上機(jī)動(dòng),完成所有目標(biāo)區(qū)域的偵察后,返回基地.汽車(chē)只能在偵察區(qū)域附近的一些特定點(diǎn)(稱(chēng)為臨時(shí)停點(diǎn))放飛和回收無(wú)人機(jī),放飛無(wú)人機(jī)后,汽車(chē)可以等在原地回收無(wú)人機(jī),也可以行駛到其他臨時(shí)停點(diǎn)回收無(wú)人機(jī).

圖1 車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察示例Fig.1 An example of multi-area coverage reconnaissancewith cooperated ground vehicle and drone

1 數(shù)學(xué)模型

1.1 問(wèn)題描述

在車(chē)機(jī)協(xié)同完成多個(gè)區(qū)域的覆蓋偵察任務(wù)中,道路網(wǎng)絡(luò)和偵察區(qū)域的位置、形狀等信息都是已知的.汽車(chē)作為小型無(wú)人機(jī)的移動(dòng)搭載平臺(tái),在行駛過(guò)程中可以為無(wú)人機(jī)充電和更換電池,同時(shí)也是無(wú)人機(jī)的指控中心.汽車(chē)的續(xù)航能力足以攜帶無(wú)人機(jī)完

圖1 給出了車(chē)機(jī)協(xié)同對(duì)3 個(gè)區(qū)域進(jìn)行偵察的示例.可以看出車(chē)機(jī)協(xié)同偵察過(guò)程中,汽車(chē)只能在地面路網(wǎng)上行駛,其訪(fǎng)問(wèn)所有偵察區(qū)域的路徑規(guī)劃屬于典型的旅行商問(wèn)題;無(wú)人機(jī)從汽車(chē)上出發(fā),飛到偵察區(qū)域上空,對(duì)偵察區(qū)域進(jìn)行連續(xù)覆蓋掃描,屬于典型的無(wú)人機(jī)航跡規(guī)劃問(wèn)題.同時(shí)汽車(chē)的路徑需要和無(wú)人機(jī)的路徑密切配合,在滿(mǎn)足無(wú)人機(jī)的續(xù)航能力約束條件下,快速完成所有區(qū)域的偵察.如何優(yōu)化車(chē)輛和無(wú)人機(jī)的路徑,使得在不超出無(wú)人機(jī)最大續(xù)航能力的前提下以最短的時(shí)間完成對(duì)所有區(qū)域的覆蓋,比單純的求解旅行商問(wèn)題和無(wú)人機(jī)航跡規(guī)劃問(wèn)題更加復(fù)雜,需要考慮兩類(lèi)路徑的交互影響.

1.2 問(wèn)題建模

為了便于模型描述,表1 給出了建模過(guò)程中應(yīng)用的所有符號(hào)及其含義.

數(shù)學(xué)規(guī)劃模型如下:

表1 符號(hào)及其含義Table 1 Notations and their meaning

目標(biāo)函數(shù)式(1)最小化完成所有區(qū)域偵察的總時(shí)間,其中第1 部分是汽車(chē)攜帶無(wú)人機(jī)在所有覆蓋區(qū)域和基站之間轉(zhuǎn)移的總行駛時(shí)間,第2 部分是車(chē)載無(wú)人機(jī)在所有偵察區(qū)域進(jìn)行覆蓋掃描的飛行總時(shí)間.為了減少第1 部分的時(shí)間,在不同偵察區(qū)域周?chē)x擇停點(diǎn)的標(biāo)準(zhǔn)之一是選擇彼此之間Floyd 距離較小的停點(diǎn).為了減少第2 部分的時(shí)間,一方面,在同一個(gè)區(qū)域內(nèi)選取彼此之間Floyd 距離小的停點(diǎn);另一方面,選擇合適的臨時(shí)停點(diǎn)以使無(wú)人機(jī)的總飛行距離更短.

約束條件式(2)確保車(chē)載無(wú)人機(jī)必須從基站出發(fā),完成所有覆蓋任務(wù)之后返回同一個(gè)基站.約束條件式(3)確保每個(gè)臨時(shí)停點(diǎn)的出度等于入度,從而確保車(chē)輛行駛路線(xiàn)的連通性.約束條件式(4)確保車(chē)輛進(jìn)入每個(gè)偵察區(qū)域一次并離開(kāi)該區(qū)域一次,即每個(gè)偵察區(qū)域只能訪(fǎng)問(wèn)一次.約束條件式(5)確保無(wú)人機(jī)只能在車(chē)輛所訪(fǎng)問(wèn)的臨時(shí)停點(diǎn)起飛,而約束條件式(6)確保無(wú)人機(jī)只能在車(chē)輛所訪(fǎng)問(wèn)的臨時(shí)停點(diǎn)降落.約束條件式(7)確保無(wú)人機(jī)只能在每個(gè)偵察區(qū)域起飛和降落一次.約束條件式(8)確保無(wú)人機(jī)在每個(gè)偵察區(qū)域飛行路徑的連通性,并且與約束條件式(7)一起確保在每個(gè)偵察區(qū)域僅進(jìn)行一次全覆蓋掃描.約束條件式(9)確保無(wú)人機(jī)在掃描每個(gè)偵察區(qū)域時(shí)的飛行時(shí)間都不會(huì)超過(guò)其最大續(xù)航時(shí)間.約束條件式(10)和式(11)定義0-1 變量的取值范圍.

2 三階段啟發(fā)式算法設(shè)計(jì)

這里提出一種三階段啟發(fā)式算法來(lái)快速求解車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察路徑規(guī)劃問(wèn)題.第1 階段是分析偵察區(qū)域的幾何特征,計(jì)算無(wú)人機(jī)的覆蓋掃描路徑;第2 階段是在無(wú)人機(jī)候選掃描路徑的基礎(chǔ)上,借鑒節(jié)約算法思想,規(guī)劃汽車(chē)的行駛路徑以及無(wú)人機(jī)在每個(gè)區(qū)域的放飛與回收點(diǎn);第3 階段,采用局部搜索算法改進(jìn)第2 階段構(gòu)造的可行解,得到問(wèn)題的最優(yōu)解或近似最優(yōu)解.

作為三階段啟發(fā)式算法的基礎(chǔ)輸入,需要首先計(jì)算出任意兩點(diǎn)之間的Floyd 距離.令表示從點(diǎn)i到點(diǎn)j的Floyd 距離,由Floyd 算法計(jì)算得出.Floyd算法(也稱(chēng)為插值方法)是一種使用動(dòng)態(tài)編程的思想在給定加權(quán)圖中找到多個(gè)點(diǎn)之間最短路徑的算法,與Dijkstra 的算法相似.Floyd 算法的主要過(guò)程如下.

算法1:Floyd算法Input:The coordinates of N0 and N and Ps Output:Floyd distance matrix dis 1Compute adjacency matrix dis[w][w],w is the total number of all points 2FOR k=1:w DO 3FOR i=1:w DO 4FOR j=1:w DO 5 IF dis(i,k)+dis(k, j)＜dis(i, j)THEN 6 dis(i, j)=dis(i,k)+dis(k, j)7END IF 8END FOR 9END FOR 10 END FOR 11 RETURN dis

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

當(dāng)無(wú)人機(jī)對(duì)一個(gè)區(qū)域進(jìn)行覆蓋掃描偵察時(shí),首先需要分析偵察區(qū)域的形狀,為無(wú)人機(jī)選擇合適的掃描模式,如割草式掃描或螺旋式掃描;如果選擇了割草式掃描,需要進(jìn)一步檢查偵察區(qū)域的凹凸性,當(dāng)該區(qū)域?yàn)榘级噙呅螘r(shí),要將其分解為多個(gè)凸多邊形子區(qū)域;最后,根據(jù)無(wú)人機(jī)的相關(guān)性能參數(shù)計(jì)算覆蓋區(qū)域的掃描飛行路徑.

2.1.1 掃描方式的選取

應(yīng)用無(wú)人機(jī)對(duì)一個(gè)區(qū)域進(jìn)行覆蓋掃描時(shí),主要有兩種掃描模式,即割草式掃描模式[20]和螺旋式掃描模式[21].如圖2 給出了兩種掃描模式下無(wú)人機(jī)的飛行路徑.在圖2 中,用黑色邊框包圍的多邊形表示偵察任務(wù)區(qū)域,黃色的圓表示掃描路徑的起點(diǎn)和終點(diǎn),藍(lán)色虛線(xiàn)軌跡表示無(wú)人機(jī)的飛行路徑,箭頭表示無(wú)人機(jī)的飛行方向.兩種掃描模式具體定義如下.

螺旋式掃描模式:無(wú)人機(jī)從偵察區(qū)域的中心開(kāi)始,然后以恒定的螺旋間距向外逐漸掃描,直到覆蓋完整個(gè)區(qū)域.也可從最外開(kāi)始,螺旋向內(nèi)掃描.

割草式掃描模式:無(wú)人機(jī)以平行航跡往復(fù)推進(jìn)的方式從偵察區(qū)域邊緣開(kāi)始以等間隔距離掃描,直到覆蓋完整個(gè)區(qū)域.

圖2 螺旋式掃描模式和割草式掃描模式Fig.2 Spiral pattern and lawn mowing pattern

當(dāng)前研究中大部分采用割草式掃描模式[22-23],少數(shù)采用螺旋式掃描模式,沒(méi)有研究多種掃描模式的選擇優(yōu)化.而實(shí)際工作中,同一區(qū)域采用不同的掃描模式時(shí),掃描路徑的總長(zhǎng)度可能相差很大.例如,在圖2 中,由螺旋式掃描模式生成的飛行路徑明顯長(zhǎng)于使用割草式掃描模式生成的飛行路徑.然而,當(dāng)偵察區(qū)域越接近圓形,使用螺旋式掃描比割草式掃描模式效果會(huì)越好.因此,可以根據(jù)覆蓋區(qū)域與圓的接近程度選擇不同的掃描模式.

多邊形的圓度定義如下:

其中,S是偵察區(qū)域的面積,L是其周長(zhǎng).如果該區(qū)域更接近圓,則其圓度C更接近1.

為了分析對(duì)比兩種典型掃描模式對(duì)不同圓度的多邊形區(qū)域的掃描效率,表2 給出了幾種典型多邊形分別采用兩種掃描模式時(shí)的掃描時(shí)間.表2 中所有的多邊形的面積相等,取值為84 個(gè)平方單位,無(wú)人機(jī)的掃描寬度設(shè)為2 個(gè)單位,速度為1 單位/s.從表2 中可以看出,當(dāng)多邊形的圓度較小時(shí),割草式掃描模式的掃描時(shí)間明顯小于螺旋式掃描模式的掃描時(shí)間.隨著多邊形的圓度逐漸變大,它們之間的差距越來(lái)越小.當(dāng)多邊形是正五邊形(C= 0.86)時(shí),兩種掃描模式的掃描時(shí)間基本相同.當(dāng)多邊形的圓度繼續(xù)增加時(shí),螺旋式掃描模式的時(shí)間變得比割草式掃描模式的時(shí)間更短.因此,通過(guò)試驗(yàn)觀(guān)測(cè)可以總結(jié)如下近似規(guī)律:當(dāng)偵察區(qū)域的圓度小于0.86 時(shí),割草式掃描模式較優(yōu);當(dāng)圓度大于0.86 時(shí),螺旋式掃描模式較優(yōu).

表2 對(duì)于典型多邊形使用兩種掃描模式得到的掃描時(shí)間Table 2 Scanning time for typical polygons by the two scanning patterns

2.1.2 凹多邊形的判定與分解

當(dāng)采用螺旋式掃描模式時(shí),多邊形的凹凸性對(duì)掃描時(shí)間的影響很小.然而,當(dāng)采用割草式掃描模式時(shí),多邊形的凹凸性對(duì)其影響較大.使用割草式掃描模式生成的掃描路徑需要在偵察區(qū)域?yàn)橥苟噙呅蔚那疤嵯逻M(jìn)行規(guī)劃的.當(dāng)偵察區(qū)域是凹多邊形,必須將凹多邊形分解為一系列凸多邊形子區(qū)域.

1)多邊形凹凸性的判定

向量的叉積可以用來(lái)判斷一個(gè)偵察區(qū)域的凹凸性.判定原理如下:具有相同轉(zhuǎn)向的頂點(diǎn)是凸點(diǎn),凸多邊形的每個(gè)頂點(diǎn)都是凸點(diǎn);具有不同轉(zhuǎn)彎的頂點(diǎn)是凹點(diǎn),若多邊形中存在一個(gè)以上的凹點(diǎn),則一定是一個(gè)凹多邊形.假設(shè)多邊形P具有n個(gè)頂點(diǎn)(v1,v2,···,vn),P的凹凸性由P是否具有凹點(diǎn)確定.設(shè)vi為P的一個(gè)隨機(jī)頂點(diǎn),vi-1和vi+1為vi的兩個(gè)相鄰頂點(diǎn).頂點(diǎn)vi的凹度由向量QQQ的叉積決定.

其中,當(dāng)P的所有頂點(diǎn)都為凸點(diǎn)時(shí),該多邊形是凸多邊形,否則P是凹多邊形.

2)凹多邊形的分解

使用割草式掃描模式生成的掃描路徑通常稱(chēng)為Boustrophedon 路徑.將一個(gè)凹多邊形分解為一系列凸多邊形子區(qū)域,然后為每個(gè)凸多邊形規(guī)劃Boustrophedon 路徑稱(chēng)為Boustrophedon 分解(BCD)[24].Li等人[25]提出了一種基于梯形分解的精確BCD 方法,算法復(fù)雜度為O(n).在文獻(xiàn)[26]中,使用凹多邊形的凸包將BCD 方法擴(kuò)展為外部細(xì)胞分解方法,有效地減少了分解的凸多邊形的數(shù)量.本文設(shè)計(jì)了一種基于梯形分解的BCD 方法.由于沿不同角度分解凹多邊形的效果不同,為了減少分解的凸多邊形的個(gè)數(shù)和無(wú)人機(jī)的轉(zhuǎn)彎次數(shù),沿與凹多邊形長(zhǎng)軸平行的方向分解凹多邊形.

對(duì)于凸多邊形的每一條邊,分別計(jì)算不屬于該邊的其他頂點(diǎn)與這條邊的距離.將這些距離的最大值標(biāo)記為該邊的跨度.比較所有邊的跨度,最小跨度所對(duì)應(yīng)的邊稱(chēng)為該凸多邊形的長(zhǎng)軸.為了找到凹多邊形的長(zhǎng)軸,采用凸包生成算法首先生成了一個(gè)凹多邊形的凸包[27].凸包是包含凹多邊形的所有頂點(diǎn)的最簡(jiǎn)單的凸多邊形.該算法總結(jié)如下:

①找到所有頂點(diǎn)中的極點(diǎn)并刪除所有落在由極點(diǎn)形成的多邊形內(nèi)部的點(diǎn),將剩余的點(diǎn)劃分到4 個(gè)區(qū)域.

②對(duì)于區(qū)域1 和2,按其升序?qū)ζ渲械狞c(diǎn)進(jìn)行排序,對(duì)于區(qū)域3 和4,按降序?qū)λ鼈冞M(jìn)行排序.

③對(duì)于每個(gè)區(qū)域,找到從一個(gè)極點(diǎn)到另一個(gè)極點(diǎn)的凸路徑.

然后,將凸包的長(zhǎng)軸視為凹多邊形的長(zhǎng)軸.在沿與長(zhǎng)軸平行的方向?qū)级噙呅翁菪畏纸鉃橐幌盗型苟噙呅沃?通過(guò)使用割草式掃描模式為每一個(gè)凸多邊形生成Boustrophedon 路徑.

圖3 給出了一個(gè)凹多邊形的分解示例.圖3(a)中用實(shí)線(xiàn)包圍的圖形是要分解的凹多邊形,在添加虛線(xiàn)之后,它變成凸多邊形,其中藍(lán)色邊表示凸多邊形的長(zhǎng)軸,并且也是凹多邊形的長(zhǎng)軸.圖3(b)表示將凹多邊形沿著與其長(zhǎng)軸平行的方向進(jìn)行梯形分解,而圖3(c)表示將梯形分解后的一系列凸多邊形合并的過(guò)程.當(dāng)兩個(gè)相鄰的凸多邊形的一條邊彼此重合并且兩者長(zhǎng)軸彼此平行時(shí),可以將它們合并.該過(guò)程可以有效地減少凸多邊形的數(shù)量,并避免無(wú)人機(jī)在不同凸多邊形之間的不必要轉(zhuǎn)移.圖3(d)顯示了使用割草式掃描模式產(chǎn)生的Boustrophedon 路徑.

圖3 凹多邊形的BCD 分解和Boustrophedon 路徑生成過(guò)程Fig.3 BCD decomposition of concave polygon and Boustrophedon path generation process

2.1.3 算法流程

基于無(wú)人機(jī)掃描模式選擇和多邊形區(qū)域分割方法,設(shè)計(jì)無(wú)人機(jī)對(duì)偵察區(qū)域進(jìn)行覆蓋掃描的飛行路徑規(guī)劃算法,總體流程如算法2所示.首先在給定偵察區(qū)域的幾何信息、潛在臨時(shí)停點(diǎn)的位置信息以及無(wú)人機(jī)飛行速度的條件下,計(jì)算偵察區(qū)域的周長(zhǎng)和面積(第1 行),然后計(jì)算偵察區(qū)域的圓度(第2 行).如果該區(qū)域的圓度大于0.86,則采用螺旋式掃描模式,然后獲得掃描路徑(第4 行)以及路徑的起點(diǎn)和終點(diǎn)(第5 行).掃描路徑的長(zhǎng)度在第6 行中計(jì)算.如果圓度小于0.86,則采用割草式掃描模式.在這種情況下,首先檢查該區(qū)域的凹凸性(第9 行).如果該區(qū)域是凹多邊形(第10 行),則使用上節(jié)設(shè)計(jì)的BCD 方法(第11 行)將其分解為一系列凸多邊形,然后規(guī)劃偵察區(qū)域的Boustrophedon 路徑.沿著平行于長(zhǎng)軸的方向開(kāi)始,有兩條掃描路徑(第13 行),分別對(duì)應(yīng)兩對(duì)起點(diǎn)和終點(diǎn)(第14 行).計(jì)算兩條路徑的長(zhǎng)度(第15 ～16 行).

算法2:無(wú)人機(jī)區(qū)域掃描路徑規(guī)劃算法Input:The vertexes(v1,v2,···,vn)of area A Output:All scanning paths U and their start and end points(s,e)1Compute L and S 2C ←4*π*S/L2 3IF C ≥0.86THEN 4U ←spiralpattern(A)5Compute the start and end points 6d ←dis(U)7END IF 8ELSE 9Q ←vi-1vi×vivi+1 10IF Q ＜0 THEN 11Decompose A by the BCD method 12END IF 13U ←lawn-movingpattern(A)14Compute two pairs of start and end points(s1,e1;s2,e2)15d1 ←dis(U1)16d2 ←dis(U2)17 END ELSE 18 RETURN U,d,(s,e)

2.2 車(chē)輛路徑規(guī)劃算法

車(chē)輛路徑規(guī)劃是通過(guò)優(yōu)化汽車(chē)訪(fǎng)問(wèn)偵察區(qū)域的順序和選擇每個(gè)偵察區(qū)域附近的臨時(shí)停點(diǎn),一方面配合無(wú)人機(jī)的掃描路徑使無(wú)人機(jī)的飛行時(shí)間較短,一方面優(yōu)化汽車(chē)的行駛距離,使得汽車(chē)在整個(gè)任務(wù)過(guò)程中的行使時(shí)間較短.結(jié)合這兩個(gè)方面,基于節(jié)約算法思想,設(shè)計(jì)了車(chē)輛的路徑規(guī)劃算法,如算法3所示.首先,根據(jù)全部點(diǎn)的位置信息計(jì)算Floyd 距離矩陣dis(第1 行),然后為每個(gè)區(qū)域選擇掃描路徑(第2行),得到掃描路徑的起點(diǎn)和終點(diǎn)(第3 行).在每個(gè)偵察區(qū)域附近隨機(jī)選擇兩個(gè)臨時(shí)停點(diǎn),然后計(jì)算無(wú)人機(jī)從一個(gè)臨時(shí)停點(diǎn)起飛到掃描路徑起點(diǎn)的距離和從掃描路徑終點(diǎn)飛到另一個(gè)臨時(shí)停點(diǎn)的距離,其中Dis是兩個(gè)距離的和(第4 ～10 行).在每個(gè)偵察區(qū)域中,找到與最小距離Dis對(duì)應(yīng)的兩個(gè)臨時(shí)停點(diǎn)作為該區(qū)域選定的停點(diǎn)(第12 行)以形成停點(diǎn)集合goal(第14行),然后計(jì)算節(jié)約矩陣(第15 ～19 行),并將其降序排列(第20 行).從最大值開(kāi)始,將對(duì)應(yīng)的兩個(gè)偵察區(qū)域連接起來(lái),直到包括所有的偵察區(qū)域,從而得到汽車(chē)和無(wú)人機(jī)路徑規(guī)劃的可行解(第21 行).

算法3:車(chē)輛路徑規(guī)劃算法Input: N0,N and NS and the start and end points of all scanning paths Output:Solution s 1Compute the Floyd distance matrix dis 2Routei ←randomselect(areai),i=1,2,3,···,m 3p1i,p2i ∈Routei 4FOR i=1:m DO 5FOR k ∈Ni DO 6FORt ∈Ni DO 7 Dis(i,k,t)←dis(k,p1i)+dis(p2i,t)8END FOR 9END FOR 10 END FOR 11 FOR i=1:m DO 12Find the k, t corresponding to the smallest Dis(i, k, t)to form Choicei 13 END FOR 14 goal ←(Choice1,Choice2,···,Choicem)15 FOR i=1:(m-1)DO 16FOR j=i+1:m DO 17jieyue(i, j)← dis(N0,goal(i,2))+ dis(N0,goal(j,1))-dis(goal(i,2),goal(j,1))18END FOR 19 END FOR 20 W ←descendsort(jieyue)21 Starting from the W(1),the corresponding two area numbers are connected until all areas are included,and s is obtained 22 RETURN s

2.3 局部搜索算法

通過(guò)前面兩個(gè)階段無(wú)人機(jī)和車(chē)輛路徑規(guī)劃算法可以得到車(chē)機(jī)協(xié)同多區(qū)域偵察的較優(yōu)方案,但很多時(shí)候可能還不是問(wèn)題的最優(yōu)解,還有改進(jìn)的空間.因此,進(jìn)一步設(shè)計(jì)車(chē)輛路徑和無(wú)人機(jī)路徑的局部搜索算法來(lái)改進(jìn)解的質(zhì)量.這里主要采用兩類(lèi)隨機(jī)算子來(lái)進(jìn)行局部搜索,第1 類(lèi)是隨機(jī)交換兩個(gè)偵察區(qū)域的訪(fǎng)問(wèn)順序,搜索改進(jìn)汽車(chē)行駛距離的可行解;第2類(lèi)是隨機(jī)交換汽車(chē)在某個(gè)偵察區(qū)域附近放飛和回收無(wú)人機(jī)的臨時(shí)停點(diǎn),搜索減少無(wú)人機(jī)飛行距離和(或)汽車(chē)行駛距離的可行解.通過(guò)隨機(jī)調(diào)用這兩類(lèi)算子搜索不同的可行解,直到連續(xù)Nmax 次沒(méi)有改進(jìn)時(shí),停止搜索得到最終方案.

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

下面通過(guò)一個(gè)典型算例給出模型和算法的應(yīng)用示例,并說(shuō)明車(chē)機(jī)協(xié)同進(jìn)行多區(qū)域偵察的優(yōu)勢(shì).所有計(jì)算實(shí)驗(yàn)均在華為筆記本電腦上進(jìn)行,該筆記本電腦使用Core i7 1.8 GHz 四核處理器,16 GB 內(nèi)存,Windows 10 操作系統(tǒng),并且應(yīng)用Matlab R2018a 進(jìn)行算法編碼.

3.1 實(shí)驗(yàn)設(shè)計(jì)

在平面上生成7×7 的道路網(wǎng)絡(luò),該道路網(wǎng)絡(luò)將平面分為49 個(gè)正方形網(wǎng)格.將每個(gè)網(wǎng)格的邊長(zhǎng)設(shè)為10 個(gè)單位,從49 個(gè)網(wǎng)格中隨機(jī)選擇20 個(gè)網(wǎng)格,在每個(gè)選中的網(wǎng)格中生成一個(gè)不規(guī)則多邊形,如圖4所示.按從左到右,從下到上的順序?qū)?0 個(gè)多邊形區(qū)域進(jìn)行編號(hào).在所有多邊形的每一條邊上生成一個(gè)隨機(jī)的臨時(shí)停點(diǎn),以藍(lán)色星號(hào)表示,紅色正方形表示基站.最后,將道路網(wǎng)絡(luò)與覆蓋區(qū)域用線(xiàn)段連接起來(lái).汽車(chē)搭載無(wú)人機(jī)從基站出發(fā)對(duì)20 個(gè)區(qū)域進(jìn)行覆蓋偵察,并在完成任務(wù)后返回基站.找到汽車(chē)和無(wú)人機(jī)的最佳路線(xiàn),以完成對(duì)所有區(qū)域的掃描偵察.

圖4 偵察區(qū)域和路網(wǎng)分布Fig.4 Reconnaissance area and road network distribution

車(chē)輛的平均速度設(shè)置為0.5 單位/s,無(wú)人機(jī)的飛行速度設(shè)置為1 單位/s.將無(wú)人機(jī)的掃描寬度設(shè)置為1 個(gè)單位,最大續(xù)航時(shí)間設(shè)為140 s.局部搜索算法中Nmax 設(shè)置為200.應(yīng)用式(12)計(jì)算20 個(gè)偵察區(qū)域的圓度,如表3所示.

從表3 可以看出,區(qū)域1、3、6、11 的圓度明顯大于0.86,因此,采用螺旋式掃描模式,其余區(qū)域采用割草式掃描方式.區(qū)域2、12、14、16、17、18 是凹多邊形,使用先前設(shè)計(jì)的基于梯形分解的BCD 方法分解它們,然后使用割草式掃描模式為它們規(guī)劃Boustrophedon 路徑.

表3 20 個(gè)偵察區(qū)域的圓度Table 3 Roundness of 20 reconnaissance areas

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

如果單純采用無(wú)人機(jī)對(duì)這些區(qū)域進(jìn)行偵察,考慮到無(wú)人機(jī)的最大續(xù)航時(shí)間,以及無(wú)人機(jī)必須安全返回基地等限制,無(wú)人機(jī)無(wú)法飛到區(qū)域14、17、19、20,從而無(wú)法對(duì)這些區(qū)域進(jìn)行偵察,剩下的區(qū)域雖然都在無(wú)人機(jī)的偵察范圍內(nèi),但是只有區(qū)域1、2、3、5、8、9、11、12 能夠在無(wú)人機(jī)一次飛行過(guò)程中偵察完畢,其余區(qū)域都需要無(wú)人機(jī)不斷地返回基站進(jìn)行充電之后,再次前往區(qū)域進(jìn)行偵察才能完成總的任務(wù).因此,對(duì)于大范圍的多區(qū)域偵察問(wèn)題,單純的小型無(wú)人機(jī)很難完成偵察任務(wù).

如果采用車(chē)機(jī)協(xié)同偵察的模式,應(yīng)用三階段啟發(fā)式算法計(jì)算得到的可行解如圖5所示,其中汽車(chē)訪(fǎng)問(wèn)20 個(gè)區(qū)域的順序?yàn)?-1-3-6-4-7-10-14-20-17-19-13-16-18-15-12-9-5-8-11.無(wú)人機(jī)掃描路徑如圖中所示,完成所有區(qū)域掃描偵察的總時(shí)間為2 379.71 s.三階段啟發(fā)式算法求解20 個(gè)偵察區(qū)域的路徑規(guī)劃方案耗時(shí)18′32′′.可以看出,車(chē)機(jī)協(xié)同模式可以高效完成單純采用無(wú)人機(jī)無(wú)法完成的偵察任務(wù),同時(shí)三階段啟發(fā)式算法可以有效解決車(chē)機(jī)協(xié)同帶來(lái)的復(fù)雜路徑規(guī)劃問(wèn)題,滿(mǎn)足實(shí)際作用應(yīng)用需求.

圖5 汽車(chē)和無(wú)人機(jī)的路徑規(guī)劃方案Fig.5 Path planning solutions for cooperated ground vehicle and drone

4 結(jié)論

隨著智能化、無(wú)人化、自主化戰(zhàn)爭(zhēng)的快速發(fā)展,小型無(wú)人機(jī)在戰(zhàn)場(chǎng)情報(bào)偵察中發(fā)揮著越來(lái)越大的作用.如何充分利用小型無(wú)人機(jī)在戰(zhàn)場(chǎng)偵察中隱蔽性強(qiáng)、成本低、風(fēng)險(xiǎn)小的優(yōu)勢(shì),同時(shí)克服其續(xù)航能力小的缺點(diǎn),更好地發(fā)揮小型無(wú)人機(jī)的作戰(zhàn)能力,是無(wú)人機(jī)指控領(lǐng)域的一個(gè)重要課題.車(chē)機(jī)協(xié)同是一種可行且高效的應(yīng)用模式.針對(duì)車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察的路徑規(guī)劃問(wèn)題,提出了偵察區(qū)域掃描方式判定、無(wú)人機(jī)掃描路徑規(guī)劃以及汽車(chē)路徑規(guī)劃等系列方法,在此基礎(chǔ)上,設(shè)計(jì)了一種三階段啟發(fā)式算法,來(lái)快速優(yōu)化汽車(chē)和無(wú)人機(jī)的行駛路徑.

車(chē)機(jī)協(xié)同多區(qū)域覆蓋偵察路徑規(guī)劃屬于路徑規(guī)劃領(lǐng)域的一個(gè)全新方向,當(dāng)前的研究還處于起步階段.通過(guò)解決一車(chē)一機(jī)協(xié)同區(qū)域覆蓋偵察路徑規(guī)劃問(wèn)題,驗(yàn)證了車(chē)機(jī)協(xié)同的優(yōu)勢(shì).下一步該方向還有很多擴(kuò)展研究方向,如一車(chē)多機(jī)、多車(chē)多機(jī)等更廣泛的應(yīng)用模式.同時(shí),在車(chē)機(jī)協(xié)同規(guī)劃中考慮敵方威脅規(guī)避、無(wú)人機(jī)隨機(jī)損失等戰(zhàn)場(chǎng)對(duì)抗因素的影響,研究更加體現(xiàn)戰(zhàn)場(chǎng)不確定性的優(yōu)化方法,也是車(chē)機(jī)協(xié)同領(lǐng)域具有重要實(shí)際價(jià)值的研究.