基于交叉熵優(yōu)化的多飛行器在線協(xié)同目標(biāo)分配方法

高 磊，劉也墨，尚 騰，何靚文

（北京航天自動(dòng)控制研究所，北京，100854）

0 引 言

隨著集群智能的快速發(fā)展，多飛行器自主協(xié)同作戰(zhàn)受到各軍事強(qiáng)國(guó)的高度重視，目前已成為研究的熱點(diǎn)。飛行器自主協(xié)同作戰(zhàn)技術(shù)涉及感知、規(guī)劃、控制等多個(gè)領(lǐng)域，主要通過(guò)精準(zhǔn)高效協(xié)同消解空間、時(shí)間、頻率、任務(wù)、效果等多維度矛盾和沖突，最大限度發(fā)揮多飛行器的整體作戰(zhàn)效能。在線協(xié)同目標(biāo)分配技術(shù)是支撐多飛行器自主協(xié)同作戰(zhàn)的關(guān)鍵，是綜合考慮飛行器性能、戰(zhàn)場(chǎng)環(huán)境和任務(wù)要求等多種約束條件，按照某種特定的優(yōu)化準(zhǔn)則，在飛行中實(shí)時(shí)計(jì)算求解各飛行器最優(yōu)打擊目標(biāo)分配策略的一類共性技術(shù)，被規(guī)約為具有強(qiáng)實(shí)時(shí)、多約束、多目標(biāo)、非線性特點(diǎn)的武器-目標(biāo)分配（Weapon-target Assignment，WTA）問(wèn)題[1]，其算法設(shè)計(jì)的實(shí)時(shí)性、最優(yōu)性、有效性將直接對(duì)未來(lái)飛行器的協(xié)同作戰(zhàn)能力產(chǎn)生決定性影響。

在線協(xié)同目標(biāo)分配是一類NP-hard問(wèn)題[1]，其特點(diǎn)是隨著問(wèn)題計(jì)算規(guī)模的擴(kuò)大，解空間將出現(xiàn)“組合爆炸”情況，同時(shí)其最優(yōu)解計(jì)算的時(shí)間代價(jià)也將呈指數(shù)級(jí)增加。目前學(xué)者大多采用匈牙利算法、蒙特卡洛樹搜索（Monte Carlo Tree Search，MCST）、改進(jìn)窮舉法以及遺傳算法（Genetic Algorithm，GA）、粒子群優(yōu)化（Particle Swarm Optimization，PSO）等現(xiàn)代優(yōu)化算法或其改進(jìn)算法解決[2～6]。但由于飛行控制對(duì)待打擊目標(biāo)參數(shù)的在線計(jì)算速度要求較高，特別是飛行器和目標(biāo)組合規(guī)模較大時(shí)，目前算法的計(jì)算實(shí)時(shí)性將很難滿足實(shí)際工程應(yīng)用需要，亟需對(duì)此進(jìn)一步開展研究。近年來(lái)，有學(xué)者對(duì)交叉熵（Cross-entropy，CE）算法的優(yōu)化效率進(jìn)行了對(duì)比研究，證明了CE算法相較于MCST、GA、PSO等傳統(tǒng)算法，在計(jì)算性能和解的全局最優(yōu)性上有顯著優(yōu)勢(shì)，或?qū)⒊蔀槲磥?lái)的一個(gè)研究趨勢(shì)[7,8]。因此，本文提出了一種基于交叉熵優(yōu)化的多飛行器在線協(xié)同目標(biāo)分配模型，首先結(jié)合飛行控制特點(diǎn)對(duì)多飛行器在線協(xié)同目標(biāo)分配問(wèn)題進(jìn)行了數(shù)學(xué)建模，隨后基于交叉熵理論設(shè)計(jì)了在線優(yōu)化求解算法，并針對(duì)不同計(jì)算規(guī)模的問(wèn)題開展了數(shù)學(xué)仿真分析和驗(yàn)證。

1 問(wèn)題建模

多飛行器在線協(xié)同目標(biāo)分配問(wèn)題模型主要由飛行器和目標(biāo)的先驗(yàn)條件、約束模型、指標(biāo)評(píng)估函數(shù)3個(gè)部分組成。該問(wèn)題相關(guān)要素可以抽象為一個(gè)三元組{ P ,C ,G}，其中，P表示飛行器和目標(biāo)的先驗(yàn)條件集合，C表示目標(biāo)分配的約束集合，G表示指標(biāo)評(píng)估函數(shù)。

1.1 飛行器和目標(biāo)的先驗(yàn)條件P

設(shè)定M架飛行器打擊N個(gè)目標(biāo)。已知飛行器i的位置 li= [ lxi,lyi,lzi]T，以及對(duì)目標(biāo)j的打靶命中概率pij∈[ 0,1]、飛行器的剩余最大航程 Di；已知目標(biāo)j的位置 qj=[ qxj,qyj,qzj]T，以及給定了目標(biāo)價(jià)值 Vj∈ [ 0,1]。

1.2 目標(biāo)分配的約束條件C

目標(biāo)分配約束規(guī)定了解的形式和解的可行域 X*。本文采用分配策略矩陣描述問(wèn)題的可行解，設(shè)在線協(xié)同目標(biāo)分配的決策變量為X，記為：

式中 xij={0,1}。當(dāng)將第i架飛行器分配第j個(gè)目標(biāo)時(shí)，xij=1；當(dāng)不將第i架飛行器分配第j個(gè)目標(biāo)時(shí)，xij=0。同時(shí)，還需滿足以下約束條件：

a）目標(biāo)的分配數(shù)量約束：同一時(shí)刻，一個(gè)飛行器選擇瞄準(zhǔn)的目標(biāo)數(shù)量不超過(guò)1個(gè)。

b）飛行器完全分配約束：在滿足分配約束的前提下，所有飛行器均選擇了瞄準(zhǔn)目標(biāo)。

c）剩余飛行能力約束：各飛行器距離所選瞄準(zhǔn)目標(biāo)的剩余航程估計(jì)值，需要滿足在其最大可達(dá)航程的覆蓋范圍內(nèi)。

1.3 指標(biāo)評(píng)估函數(shù)G

為了對(duì)多飛行器在線協(xié)同目標(biāo)分配策略的整體效能進(jìn)行量化評(píng)估，從任務(wù)成本和任務(wù)收益兩個(gè)方面構(gòu)建指標(biāo)評(píng)估函數(shù)。任務(wù)成本主要考慮多飛行器綜合航程代價(jià)最小，以避免目標(biāo)分配后可能面臨的多飛行器航跡交叉問(wèn)題；任務(wù)收益主要從最大綜合命中概率和最大價(jià)值收益角度考慮，實(shí)現(xiàn)多飛行器協(xié)同作戰(zhàn)整體效能的最優(yōu)化。

a）任務(wù)成本cf。對(duì)于整個(gè)多飛行器而言，所分配的飛行總體航程越小，各飛行器越傾向于就近選擇瞄準(zhǔn)目標(biāo)，可在一定程度上防止分配后航跡交叉現(xiàn)象的出現(xiàn)[9]。同時(shí)，執(zhí)行任務(wù)所需的飛行航程總距離越小，其任務(wù)執(zhí)行時(shí)間越短，途中面臨戰(zhàn)損的可能性越小。航程代價(jià)成本cf可按如下公式計(jì)算：

b）任務(wù)收益rf。認(rèn)為各飛行器命中目標(biāo)概率之間相互獨(dú)立，那么對(duì)于目標(biāo)j，其綜合命中概率 jp為

瞄準(zhǔn)該目標(biāo)的任務(wù)收益rjf可以記為

那么該分配策略的綜合收益rf為

綜上，指標(biāo)評(píng)估函數(shù)的設(shè)計(jì)實(shí)質(zhì)上是一個(gè)多目標(biāo)優(yōu)化過(guò)程，是為了使任務(wù)成本最低的同時(shí)，保證任務(wù)的收益最大。多目標(biāo)優(yōu)化整體收益f可以記為

對(duì)于上述指標(biāo)的求解等價(jià)于求解多目標(biāo)優(yōu)化問(wèn)題的Pareto最優(yōu)解。由于上述評(píng)價(jià)指標(biāo)間存在潛在沖突，難以同時(shí)達(dá)到最優(yōu)值，采用加權(quán)方式對(duì)目標(biāo)分配策略進(jìn)行綜合評(píng)價(jià)，計(jì)算公式如下：

式中 權(quán)重w1+w2=1， w1, w2∈ [ 0,1]。

綜合考慮約束條件和指標(biāo)評(píng)估，構(gòu)建如下在線協(xié)同目標(biāo)分配WTA模型：

2 在線優(yōu)化算法設(shè)計(jì)

交叉熵算法解決組合優(yōu)化問(wèn)題最早由Rubinstein提出，在解決許多典型的NP-hard問(wèn)題方面，被證實(shí)了具有很好的時(shí)效性。近年來(lái)年有學(xué)者以WTA問(wèn)題為背景，對(duì)CE算法的性能進(jìn)行了系統(tǒng)對(duì)比分析，證明了CE相比GE和MCST等算法在計(jì)算時(shí)間和解的最優(yōu)性上具有更優(yōu)的性能，特別是在收斂速度上優(yōu)勢(shì)明顯[9]。為此，針對(duì)本文提出的在線協(xié)同目標(biāo)分配模型，考慮到在線決策算法需要在有限時(shí)間內(nèi)快速生成決策結(jié)果，基于CE設(shè)計(jì)優(yōu)化求解算法。

針對(duì)上述非線性0-1整數(shù)規(guī)劃問(wèn)題，可以將其目標(biāo)函數(shù)可等效建模為如下形式：假定S為定義在χ上的實(shí)值函數(shù)，χ為可行策略集，也稱為決策空間。對(duì)規(guī)劃模型的求解實(shí)質(zhì)上是在滿足約束條件的所有可行解中，找到目標(biāo)函數(shù)S （X）的全局最小值γ*，此時(shí)對(duì)應(yīng)的最優(yōu)目標(biāo)分配策略記為 X*。優(yōu)化模型為[10]

上述問(wèn)題的一組可行解X可視為一組由0、1構(gòu)成的離散隨機(jī)變量概率分布。基于上述思想，CE算法的思路是將該規(guī)劃問(wèn)題的最優(yōu)解視為一個(gè)關(guān)于原始參數(shù)β的最優(yōu)概率分布f （·,β），f （·,β）隨著原始參數(shù)β的變化而改變。此時(shí)，優(yōu)化過(guò)程的目標(biāo)就是不斷估計(jì)這個(gè)最優(yōu)概率分布的過(guò)程，以使得當(dāng)前的目標(biāo)分配估計(jì)策略與理論最優(yōu)策略的差異最小。選取交叉熵作為兩個(gè)概率分布之間差異的測(cè)度。對(duì)于任意概率分布p，其相對(duì)概率分布q的交叉熵D （ p ||q）的計(jì)算公式為

那么對(duì)于上文中提到的S （X）最小值問(wèn)題，求解過(guò)程是不斷求解更優(yōu)的估計(jì)γ來(lái)逼近*γ，這樣就將優(yōu)化問(wèn)題轉(zhuǎn)化為一個(gè)估計(jì)問(wèn)題?（γ） 。?（γ） 可以表示如下[10]：

根據(jù)上式可以得到[8]：

綜上，可以設(shè)計(jì)如下在線協(xié)同目標(biāo)分配的CE優(yōu)化算法：

a）初始化原始估計(jì)參數(shù)?β為均勻概率分布種子：

b）設(shè)置采樣門限閾值θ∈[ 0,1]；

c）根據(jù)?β隨機(jī)生成滿足分配約束的K組目標(biāo)分配策略樣本 X1,X2,… ,XK，并根據(jù)指標(biāo)函數(shù)f計(jì)算（Xi）,i =1,2,…,K；

e）根據(jù)篩選出的樣本，按照下式更新原始估計(jì)參數(shù)?β：

重復(fù)步驟c～e直至?β收斂至最優(yōu)參數(shù)β，判定依據(jù)為指標(biāo)函數(shù)值連續(xù)5次不變。

3 仿真分析

為驗(yàn)證交叉熵優(yōu)化算法解決在線協(xié)同目標(biāo)分配問(wèn)題的有效性，采用C++作為算法開發(fā)語(yǔ)言，分別實(shí)現(xiàn)了6架飛行器打擊3個(gè)目標(biāo)、12架飛行器打擊3個(gè)目標(biāo)、12架飛行器打擊6個(gè)目標(biāo)、24架飛行器打擊6個(gè)目標(biāo)、24架飛行器打擊12個(gè)目標(biāo)、48架飛行器打擊12個(gè)目標(biāo)6種場(chǎng)景的仿真，在不同的計(jì)算規(guī)模下對(duì)算法性能進(jìn)行系統(tǒng)分析和驗(yàn)證。仿真初始參數(shù)的設(shè)置如下：目標(biāo)價(jià)值 jV= 1，命中概率 ijp= 0.8，剩余航程能力 Di= 250 km，指標(biāo)分配權(quán)重w1=w2= 0.5，樣本容量N=200，采樣門限閾值θ=0.1，最大迭代次數(shù)nItermax=50，算法終止的判定次數(shù) Ncheckmax=5，收斂精度peps=0.0001。仿真結(jié)果見圖1。

圖1 在線協(xié)同目標(biāo)分配策略仿真結(jié)果 Fig.1 Simulation Results of Real-time Cooperative Target Allocation Strategy

圖2為在線協(xié)同目標(biāo)分配優(yōu)化過(guò)程。

圖2 在線協(xié)同目標(biāo)分配優(yōu)化過(guò)程 Fig.2 Optimization Process of Real-time Cooperative Target Allocation

由圖1、圖2可以看出，在不同計(jì)算規(guī)模下，對(duì)于本文提出的多約束、非線性0-1整數(shù)規(guī)劃模型，基于CE的在線協(xié)同目標(biāo)分配優(yōu)化算法能夠在接近20次左右的迭代中快速收斂，并且從綜合航程代價(jià)、協(xié)同突防命中等角度給出合理的目標(biāo)分配結(jié)果。從表1可以看出，CE算法在各種計(jì)算規(guī)模下的平均求解時(shí)間在毫秒級(jí)，典型6架飛行器打3個(gè)目標(biāo)情況下一次在線決策時(shí)間僅需8.7 ms，在最大計(jì)算規(guī)模場(chǎng)景下的在線優(yōu)化時(shí)間僅需140.9 ms，能夠很好地滿足工程應(yīng)用需求。

表1 在線協(xié)同目標(biāo)分配性能分析 Tab.1 Performance Analysis of Real-time Cooperative Target Assignment

4 結(jié)束語(yǔ)

多飛行器在線協(xié)同目標(biāo)分配問(wèn)題是一個(gè)具有多約束、強(qiáng)實(shí)時(shí)限制條件的復(fù)雜0-1整數(shù)規(guī)劃問(wèn)題，除了考慮分配策略求解的全局最優(yōu)性，還需要兼顧其在線計(jì)算的實(shí)時(shí)性要求，以便為飛行控制提供實(shí)時(shí)的目標(biāo)指引信息，提升飛行控制效率。本文基于交叉熵優(yōu)化提出了一種多飛行在線協(xié)同目標(biāo)分配的建模及優(yōu)化方法，經(jīng)設(shè)計(jì)并通過(guò)數(shù)學(xué)仿真驗(yàn)證了本文算法的有效性，可為未來(lái)多飛行器自主協(xié)同作戰(zhàn)的實(shí)現(xiàn)提供技術(shù)支撐。