利用加權(quán)Voronoi圖對無人機(jī)飛行規(guī)劃的問題研究*

李洪濤 趙紀(jì)初

（1.92941部隊 葫蘆島 125001）（2.92728部隊 上海 200040）

1 引言

隨著通信技術(shù)日益成熟，我們對武器戰(zhàn)場態(tài)勢信息的需求也越來越精確，無人機(jī)將會承擔(dān)越來越多的探測和打擊任務(wù)，不同作戰(zhàn)區(qū)域的環(huán)境，對無人機(jī)布置提出了更高更精準(zhǔn)的要求，在最優(yōu)區(qū)域劃分方面有不少類似的研究，如Huy Trandac利用啟發(fā)式算法來建立Voronoi多邊形，確定二維扇區(qū)的邊界［1］；唐小波、劉笠等提出了自適應(yīng)的Voronoi圖能力區(qū)劃方法，使得配電站設(shè)置更合理高效，解決了部分區(qū)域電源覆蓋面不全的問題［2］；戴福青提出了Power圖的劃分方法研究，將扇區(qū)結(jié)構(gòu)特征作為約束條件，應(yīng)用遍歷搜索算法來搜索尋優(yōu)，得到最終優(yōu)化的扇區(qū)［3］。在無人機(jī)航跡規(guī)劃方面，李亞女［4］、趙文婷［5］都利用了“V圖的邊的被探測概率最小”這一性質(zhì)進(jìn)行了航跡搜索和航跡優(yōu)化。

2 定義及其相關(guān)算法

在能力范圍的可視化方面，Voronoi圖具有其獨(dú)特的優(yōu)勢。該算法是由俄國數(shù)學(xué)家Georgy Fedo—seevich Voronoi首次提出，并以他的名字來命名。其在計算機(jī)輔助設(shè)計、圖形圖像處理、地理信息系統(tǒng)、智能決策領(lǐng)域以及優(yōu)化算法［6］等方面有著廣泛的用途。當(dāng)所有觸發(fā)單元的擴(kuò)張能力或權(quán)重相同時，生成的是如圖1（a）的標(biāo)準(zhǔn)V圖，若權(quán)值不同生成的是如圖1（b）的加權(quán)V圖。

圖1 標(biāo)準(zhǔn)Voronoi圖與加權(quán)Voronoi圖直觀對比

這里關(guān)鍵的參數(shù)就是觸發(fā)點(diǎn)擴(kuò)展系數(shù)以及權(quán)重的問題，可以對體系對抗能力、態(tài)勢感知能力和目標(biāo)搜索能力進(jìn)行評估。有許多方法可用于描述和計算作戰(zhàn)能力，例如，武器裝備性能指數(shù)方法［7］和徐瑞恩提出的AHP方法是普遍接受的方法，趙青松和其他相關(guān)學(xué)者［8］提出的武器裝備系統(tǒng)控制能力空間中還有“層次性、協(xié)作性、松耦合性、多目標(biāo)性和涌現(xiàn)性”的五個特征。加權(quán)Voronoi圖的圖像生成過程比較復(fù)雜，節(jié)點(diǎn)越多，其生成的Delaunay剖分三角網(wǎng)就越多，結(jié)構(gòu)越復(fù)雜［9～10］。

3 飛行區(qū)域威脅能力劃分

3.1 威脅能力指數(shù)

在實(shí)際飛行區(qū)域能力分析時，不同的能力指數(shù)根據(jù)目標(biāo)對應(yīng)屬性有相應(yīng)的計算方式，有基于云模型推理的方法、基于模糊的MODM方法、基于TOPSIS的方法、基于灰靶理論的方法等，不同的方式方法有不同的側(cè)重點(diǎn)，一般采用多種方式計算而后進(jìn)行一致性檢驗來評估威脅值。在下文中，每個飛行臨近區(qū)域的威脅能力值用作Voronoi圖的加權(quán)系數(shù)。由徐瑞恩提出的冪指數(shù)方法用于表示某種向量Y=（Y1，Y2，L，yi，L，YN），其單個節(jié)點(diǎn)的N個指標(biāo)的表現(xiàn)，用I來表示單個區(qū)域威脅的效益指數(shù)，有I=Q（Y），其中，Q（Y）的具體形式為

式中：wi為冪指數(shù)；yi為影響飛行半徑的環(huán)境因素或性能指標(biāo)；K為調(diào)整因子，在比較不同型號飛行器，或計數(shù)與多個不同環(huán)境參考下的能力指數(shù)形成威脅邊界之間的能力關(guān)系，這種方法相當(dāng)于對不同偏好影響進(jìn)行了指數(shù)的歸一化，使不同的能力指數(shù)的生成處于能力評估的同一框架內(nèi)，因此將其稱為對無人機(jī)威脅能力一致性的調(diào)整系數(shù)。

等權(quán)條件下生成的威脅邊界如圖2所示，紅色部分為飛行器在限制條件下的威脅范圍，綠色部分為環(huán)境因素對威脅區(qū)域的控制包絡(luò)。本文用Matlab隨機(jī)生成15個區(qū)域節(jié)點(diǎn)和若干個環(huán)境限制點(diǎn)作為需要進(jìn)行威脅區(qū)域劃分的對象，分析在不同偏好權(quán)值的條件下組成的最大威脅范圍。根據(jù)不同型號及其環(huán)境限制因素設(shè)定不同的威脅能力權(quán)值生成加權(quán)Voronoi圖，如圖3所示，其中各區(qū)域?qū)?yīng)的能力指數(shù)轉(zhuǎn)化成權(quán)值，一般采用標(biāo)準(zhǔn)計算法如下：

圖2 相同威脅能力指數(shù)對應(yīng)的威脅邊界示意圖

圖3 不同威脅能力指數(shù)對應(yīng)的威脅邊界示意圖

圖4 對無人機(jī)探測區(qū)域的地形進(jìn)行加權(quán)化生成的Voronoi控制邊界示意圖

在確定如何設(shè)定飛行路徑對探測區(qū)域全覆蓋問題上，則可以導(dǎo)入附帶探測屬性和指標(biāo)能力的Voronoi圖。在對于部分無需探測的區(qū)域或者已探知后對覆蓋區(qū)域的影響，則可以通過刪除節(jié)點(diǎn)或者降低節(jié)點(diǎn)權(quán)重系數(shù)的方式來呈現(xiàn)威脅覆蓋邊界，分析需要如何重新規(guī)劃路徑來彌補(bǔ)探測覆蓋區(qū)。在不增加新路徑的情況下可以通過移動鄰近無人機(jī)位置來彌補(bǔ)該區(qū)域探測能力缺失。

圖形的能力重構(gòu)受到各武器節(jié)點(diǎn)加權(quán)距離最大的限制和區(qū)域環(huán)境因素的限定，從力學(xué)角度上可以看成加權(quán)Voronoi圖中各節(jié)點(diǎn)之間具有保持最佳作用力與反作用力的性能。在加權(quán)Voronoi圖中的動力傳播機(jī)制就是各節(jié)點(diǎn)設(shè)定的加權(quán)值，并且這里分析的例子是屬于相對均勻網(wǎng)絡(luò)模型，不存在連接不相鄰節(jié)點(diǎn)之間的鏈接關(guān)系或者是權(quán)值極大的關(guān)鍵節(jié)點(diǎn)。

3.2 無人機(jī)配置區(qū)域復(fù)雜度分析

無人機(jī)布置考慮的環(huán)境因素不僅僅包含了地形限制，同時需要考慮該區(qū)域敵我人員和裝備等流動個體的影響，通過模型的建立可以分析圖形的聚集密度、區(qū)域復(fù)雜度、鄰近點(diǎn)指數(shù)等數(shù)據(jù)，從而來輔助宏觀上的態(tài)勢分析和戰(zhàn)術(shù)布局，例如圖5就是以環(huán)境影響和目標(biāo)流動因素為因子構(gòu)建的無人機(jī)群布點(diǎn)復(fù)雜度示意圖。圖中利用GIS工具提取了大量地圖中可供分析的節(jié)點(diǎn)和線段，仍采用Delaunay三角剖分法對該區(qū)域進(jìn)行復(fù)雜程度分析。通過構(gòu)建后的圖形呈現(xiàn)，可以根據(jù)情況適當(dāng)合理地調(diào)整無人機(jī)部署，以及管理區(qū)域內(nèi)與武器控制有關(guān)的資源。

圖5 加入部分影響因子的無人機(jī)配置區(qū)域復(fù)雜度示意圖

在更大分析要素中，各個武器裝備節(jié)點(diǎn)類型屬性不同，機(jī)動能力各不相同，因此，復(fù)雜度區(qū)域劃分要考慮到可移動單位速度、目標(biāo)類型甚至天氣情況等。例如，移動速度權(quán)值設(shè)定上可以采用公式：

式中：Wi為目標(biāo)速度權(quán)系數(shù)；Ti，Tj為不同機(jī)動能力的無人機(jī)通過該片區(qū)的時間，T為所有武器在該區(qū)域單元所停留的時間。若需要布置無人機(jī)對沿岸地域搜索，則需要考慮風(fēng)力、降雨量、浪高等因素，通過數(shù)據(jù)歸一化結(jié)合比重系數(shù)來計算該區(qū)域的權(quán)系數(shù)，其中加權(quán)Voronoi圖的發(fā)生元可以設(shè)定為表示沿岸的線段和灘涂島礁，或者自行添加參考點(diǎn)作為發(fā)生元，其權(quán)系數(shù)計算公式為

式中：Wk海域海況和天氣權(quán)系數(shù)；Ai為風(fēng)力、降雨量、浪高等數(shù)據(jù)處理后的權(quán)系數(shù)值；Ti為不同海域和天氣情況下無人機(jī)正常通過指定區(qū)域所用時間；T為飛行器平均穿越指定區(qū)域所用的時間。因此，不同偏好的復(fù)雜情況分析就可以采用該復(fù)雜度對應(yīng)的加權(quán)值帶入發(fā)生元用以生成相應(yīng)的加權(quán)Voronoi圖。另外，假設(shè)我們只考慮4種復(fù)雜因子：i，j，k，l。那么在數(shù)據(jù)分析中，區(qū)域綜合的復(fù)雜度計算可采用公式：

TC=Wi+Wj+Wk+Wl

在圖5中我們可以比較直觀地看出1區(qū)目標(biāo)的復(fù)雜度較高、CV值大、因此該區(qū)域無人機(jī)群探測打擊的威脅能力較高、地域人員裝備情況也較為復(fù)雜。而2區(qū)相對復(fù)雜度低、能力分布較平均、地域人員裝備情況較為簡單。因此可推測在一般情況下，CV值和TC值是成正比的，也就是說復(fù)雜度越高的區(qū)域，其威脅能力分布也呈現(xiàn)出較為集中的特點(diǎn)。因此在無人機(jī)飛行規(guī)劃的部署配置以及區(qū)域管控上，可以綜合分析需要重點(diǎn)布置的范圍和人員裝備調(diào)整區(qū)域，使其在資源利用控制上更為合理高效。

4 結(jié)語

本文以無人機(jī)探測威脅能力為例，提出將作戰(zhàn)武器能力和環(huán)境信息要素進(jìn)行融合，利用Voronoi圖將武器控制區(qū)域劃分為有限個單元，根據(jù)不同的任務(wù)需求，將偏好的能力系數(shù)轉(zhuǎn)換成相應(yīng)的加權(quán)值，然后通過生成的Delaunay幾何圖形進(jìn)行仿真分析。在無人機(jī)區(qū)域威脅分析中提出統(tǒng)計復(fù)雜度，將區(qū)域中飛行器平均穿越時間和其它戰(zhàn)場態(tài)勢信息生成復(fù)雜度權(quán)值用于生成Voronoi圖，呈現(xiàn)效果較好，便于相關(guān)人員進(jìn)行有針對性的研究分析。