李文廣，李建增，胡永江，李永科，趙月飛

（陸軍工程大學(xué)石家莊校區(qū)，石家莊 050003）

0 引言

現(xiàn)階段，根據(jù)無人機(jī)偵察對象的不同，多無人機(jī)協(xié)同偵察問題可分為“點對點”協(xié)同偵察［2］和“點對面”協(xié)同偵察兩個方面［3］。

“點對點”協(xié)同偵察即偵察對象為點目標(biāo)群，要求無人機(jī)以最小的時間代價完成偵察任務(wù)。如文獻(xiàn)［4］將多無人機(jī)偵察點目標(biāo)群的航跡規(guī)劃問題先轉(zhuǎn)化為多旅行商問題，然后利用遺傳算法求解得到各任務(wù)航跡。但該算法僅限于點目標(biāo)群規(guī)模較小的情況。為解決大規(guī)模點目標(biāo)群的偵察問題，文獻(xiàn)［5］首先對點目標(biāo)群使用K-means 聚類算法，將多旅行商問題分解為單旅行商問題，然后利用優(yōu)化后的遺傳算法對問題進(jìn)行求解。

“點對面”協(xié)同偵察即偵察對象為廣域面目標(biāo)，需要無人機(jī)能夠?qū)υ撊蝿?wù)區(qū)域進(jìn)行全覆蓋偵察，常用的覆蓋方式有掃描線法［6-7］、柵格法［8］等。如文獻(xiàn)［9］在保證區(qū)域全覆蓋和滿足無人機(jī)動力學(xué)約束的前提下，對無人機(jī)編隊的轉(zhuǎn)彎時機(jī)和轉(zhuǎn)彎位置進(jìn)行調(diào)整，完成了區(qū)域覆蓋搜索任務(wù)。文獻(xiàn)［10-11］根據(jù)無人機(jī)的性能，將任務(wù)區(qū)域分解為多個子任務(wù)區(qū)域，然后將子任務(wù)區(qū)域分配給各個無人機(jī)，由各個無人機(jī)使用掃描線法進(jìn)行區(qū)域覆蓋搜索，最終實現(xiàn)以最少的轉(zhuǎn)彎次數(shù)完成偵察任務(wù)。

對于上述兩種目標(biāo)類型的航跡規(guī)劃問題已有了較為成熟的研究成果，但是以鐵路、公路等線目標(biāo)為偵察對象的多無人機(jī)航跡規(guī)劃問題，相關(guān)文獻(xiàn)較少。針對偵察線目標(biāo)的多無人機(jī)協(xié)同航跡規(guī)劃問題，結(jié)合目標(biāo)屬性及最小時間代價要求，提出了一種基于集中一體化遺傳算法的協(xié)同航跡規(guī)劃方法。通過建立基于時間代價的航跡模型和采用集中一體化式遺傳算法對模型進(jìn)行求解，可得到具有最小時間代價的任務(wù)航跡。

1 基于時間代價的航跡模型

問題描述：利用m 架無人機(jī)對任務(wù)區(qū)域內(nèi)的N條河流和道路進(jìn)行偵察，每個目標(biāo)均能被偵察到，且不能重復(fù)偵察并要求整體任務(wù)時間代價最小。

設(shè)L={L1，L2，…，LN}為待被偵察的線目標(biāo)集合，V={V1，V2，…，Vm}為各無人機(jī)對應(yīng)的巡航速度集合。第i 架無人機(jī)的位置為（xi，yi），其偵察的線目標(biāo)數(shù)量為ni，且第j 個線目標(biāo)的端點坐標(biāo)（xj1，yj1）、（xj2，yj2），滿足1≤i≤m，1≤j≤N。則第i 架無人機(jī)的航跡時間代價可表示為：

其中，li1表示無人機(jī)從起飛點飛向所分配到的第一

個線目標(biāo)進(jìn)入點的路徑長度，li2表示各線目標(biāo)之間

的路徑長度，即從上一線目標(biāo)飛出點到下一線目標(biāo)進(jìn)入點的路徑長度，li3表示偵察各線目標(biāo)時，在其上空飛過的路徑長度，一般與線目標(biāo)長度近似相等，li4表示從最后一個線目標(biāo)飛出點返回?zé)o人機(jī)起飛點的路徑長度。d（a，b）表示點a 和點b 之間的幾何距離，dj表示第j 個線目標(biāo)的長度。

則各個無人機(jī)偵察航跡的時間代價可以用T=（t1，t2，…，tm）表示。

基于時間代價的航跡模型其目標(biāo)函數(shù)即為：

表示此次偵察任務(wù)的整體時間代價由花費時間最長的無人機(jī)所決定。

航跡模型的約束條件則為：

其表示所有線目標(biāo)均被偵察，且無重復(fù)偵察。

2 集中一體化遺傳算法

對于多無人機(jī)協(xié)同航跡規(guī)劃問題的求解方法主要有分層解耦法和集中一體化法。后者是將初始生成的航跡長度當(dāng)作任務(wù)分配代價函數(shù)的一個自變量，在任務(wù)分配的同時得到偵察航跡，通過不斷迭代，來尋找最優(yōu)解［12］。而分層解耦法則無法得到最優(yōu)解或次優(yōu)解。

針對偵察線目標(biāo)的多無人機(jī)協(xié)同航跡規(guī)劃問題，引入集中一體化方法并結(jié)合改進(jìn)的遺傳算法進(jìn)行求解。但遺傳算法存在收斂性較差且易陷入局部最優(yōu)的問題［13］。所以在標(biāo)準(zhǔn)遺傳算法的編碼、染色體交叉和變異環(huán)節(jié)進(jìn)行了合理優(yōu)化，來彌補(bǔ)標(biāo)準(zhǔn)遺傳算法的易早熟和收斂性差等缺點。

2.1 染色體編碼

采用集中一體化求解的思想，即可在染色體編碼階段，使得每條染色體上所有基因可對應(yīng)表示線目標(biāo)的分配結(jié)果，以及各無人機(jī)的偵察序列等信息。染色體編碼按以下步驟進(jìn)行。

步驟1：產(chǎn)生一個行數(shù)為3，列數(shù)為N 的空矩陣E；

步驟2：第1 行的矩陣元素由區(qū)間［1，m］中的m個整數(shù)隨機(jī)填入；

步驟3：第2 行的矩陣元素由區(qū)間［1，N］中的N個整數(shù)隨機(jī)填入，要求整數(shù)無重復(fù)；

步驟4：第3 行的矩陣元素由整數(shù)1 或2 隨機(jī)填入，最終形成矩陣E'。

以上是多類型基因編碼方式，染色體的基因數(shù)由線目標(biāo)數(shù)量所確定，每個染色體包含多個基因，每個基因由無人機(jī)編號、線目標(biāo)編號和進(jìn)入點編號構(gòu)成。圖1 即染色體編碼的示意圖。

圖1 染色體編碼示意圖

其表示4 架無人機(jī)偵察6 個線目標(biāo)，其中無人機(jī)1 的偵察序列為從起飛點起飛，然后從線目標(biāo)3的右側(cè)端點進(jìn)入，再從線目標(biāo)5 的左側(cè)端點進(jìn)入，最后返回起飛點，以此類推。

相關(guān)說明：定義無人機(jī)偵察線目標(biāo)時，均從線目標(biāo)的1 個端點進(jìn)入，另1 個端點飛出；1 表示從線目標(biāo)左側(cè)端點進(jìn)入，2 則表示從右側(cè)端點進(jìn)入。

2.2 適應(yīng)度求解與優(yōu)選

染色體的選擇采用經(jīng)典的輪盤賭法來對種群中的染色體進(jìn)行優(yōu)選，形成父代染色體種群，且染色體適應(yīng)度越小，被優(yōu)選的概率越大。

第s 條染色體對應(yīng)的適應(yīng)度為：

式中，Ts表示第s 條染色體其對應(yīng)偵察序列下的各無人機(jī)時間代價的集合。

則整個種群最佳的適應(yīng)度為：

式中，k 為遺傳代數(shù)，k=1，2，…，r，fks表示第k 代中第s 條染色體對應(yīng)的適應(yīng)度。

2.3 染色體交叉

通過對兩個染色體進(jìn)行交叉操作，使得被選擇的兩個染色體之間交叉互換若干部分基因，達(dá)到遺傳繁衍產(chǎn)生子代的作用。集中一體化式遺傳算法對染色體進(jìn)行交叉操作后，能夠進(jìn)一步使得種群向適應(yīng)度值更優(yōu)的方向進(jìn)行迭代，也可以提高算法收斂速度。

首先，對父代染色體種群進(jìn)行適應(yīng)度求解及優(yōu)選，選取父染色體A 和B。然后，隨機(jī)產(chǎn)生兩個不相等整數(shù)p 和q（p、q∈［1，N］），將父染色體A 中的第p 和q 個基因與B 中的第p 和q 個基因?qū)?yīng)相互交換。為了保證每個目標(biāo)都被偵察到且最多被偵察到一次，還需進(jìn)行目標(biāo)編號沖突檢測。完成沖突檢測后，再分別將染色體A'和B'中第p-q 之間的基因片段反轉(zhuǎn)，即得到交叉操作后的子染色體C 和D。

相關(guān)說明：由于每個線目標(biāo)要求至多被偵察一次，所以要對線目標(biāo)的編號進(jìn)行沖突檢測。

2.4 染色體變異

為了防止種群陷入局部最優(yōu)，還需對子染色體進(jìn)行變異操作。針對染色體編碼的特點，設(shè)計了3種變異方式：即無人機(jī)編號變異、目標(biāo)編號變異、進(jìn)入點編號變異。

圖2 染色體交叉操作示意圖

1）無人機(jī)編號變異

隨機(jī)產(chǎn)生變異基因，將其對應(yīng)的無人機(jī)編號隨機(jī)突變?yōu)槠渌麩o人機(jī)編號。如圖3 所示，無人機(jī)變異基因為3，對應(yīng)的無人機(jī)編號為3，將其突變?yōu)榫幪枮? 的無人機(jī)。

圖3 無人機(jī)編號變異示意圖

2）目標(biāo)編號變異

隨機(jī)產(chǎn)生變異基因，將其對應(yīng)的目標(biāo)編號隨機(jī)突變?yōu)槠渌哪繕?biāo)編號，同時檢測目標(biāo)編號沖突。如圖4 所示，無人機(jī)變異基因為4，對應(yīng)的目標(biāo)編號為5，將其突變?yōu)榫幪枮? 的目標(biāo)，此時，該基因的目標(biāo)編號與基因6 的目標(biāo)編號沖突，將基因6 的目標(biāo)編號4 修改為基因4 變異前的目標(biāo)編號5。

圖4 目標(biāo)編號變異示意圖

3）進(jìn)入點編號變異

隨機(jī)產(chǎn)生變異基因位，將其對應(yīng)的進(jìn)入點編號隨機(jī)突變?yōu)榱硪粋€進(jìn)入點編號。如圖5 所示，進(jìn)入點變異基因為5，對應(yīng)的進(jìn)入點編號為1，將其突變?yōu)榱硪粋€進(jìn)入點2。

圖5 進(jìn)入點編號變異示意圖

2.5 算法收斂性

標(biāo)準(zhǔn)遺傳算法是在經(jīng)過交叉、變異兩個環(huán)節(jié)之后才會進(jìn)行適應(yīng)度的求解和優(yōu)選，但染色體在經(jīng)過交叉操作后有可能已經(jīng)是最優(yōu)解了，這將導(dǎo)致算法收斂速度變慢，也可能陷入局部最優(yōu)解。

集中一體化遺傳算法對染色體交叉、變異操作進(jìn)行了優(yōu)化，同時要求經(jīng)過每次染色體交叉或變異操作后，都要對前后每個染色體的適應(yīng)度進(jìn)行計算并優(yōu)選，以有效保證每次迭代后，算法可有效收斂并得到最優(yōu)解。

3 仿真驗證

仿真平臺為Inter（R）Core（TM）i5-5200UCPU，4 GB 內(nèi)存，64 位Win7 操作系統(tǒng)的戴爾筆記本。編程工具為Matlab-R2016a（64 位）。

為了驗證本文方法的有效性，采用以下驗證方案：現(xiàn)有3 架無人機(jī)，無人機(jī)的巡航速度均為10 m/s，各無人機(jī)起飛點坐標(biāo)分別為（0，0）、（100，0）和（80，80），任務(wù)要求對8 個線目標(biāo)進(jìn)行快速協(xié)同偵察。線目標(biāo)端點坐標(biāo)參數(shù)如表1 所示，各無人機(jī)和線目標(biāo)的位置關(guān)系如圖6 所示。

表1 待偵察的線目標(biāo)坐標(biāo)

圖6 無人機(jī)和目標(biāo)位置示意圖

經(jīng)過對3 架無人機(jī)偵察航跡的求解，算法最終迭代的輸出結(jié)果如圖7 所示。

圖7 最佳染色體

現(xiàn)將實驗結(jié)果分析如下：

1）根據(jù)最終迭代輸出的染色體，對應(yīng)編碼規(guī)則可解譯得到各無人機(jī)的偵察序列及各個線目標(biāo)的進(jìn)入點編號，如表2 所示。

表2 各無人機(jī)偵察序列及時間代價（min）

2）該方法可有效求解得到各無人機(jī)的任務(wù)航跡，各偵察航跡的時間代價分別為3.295 min、2.747 min和2.945 min，且航跡之間無交叉、無沖突，如圖8所示。

圖8 航跡規(guī)劃結(jié)果

3）集中一體化式遺傳算法在第101 代已達(dá)到收斂，而標(biāo)準(zhǔn)遺傳算法在第613 代才收斂，且前者達(dá)到收斂的時間優(yōu)于標(biāo)準(zhǔn)遺傳算法達(dá)到收斂的時間。即集中一體化式遺傳算法與標(biāo)準(zhǔn)遺傳算法相比，不僅收斂速度快，算法求解效率也更高。

圖9 收斂性分析

4 結(jié)論

本文針對偵察線目標(biāo)的多無人機(jī)協(xié)同航跡規(guī)劃問題進(jìn)行了研究，并提出了相應(yīng)的航跡規(guī)劃方法。

1）該方法適用于多無人機(jī)協(xié)同偵察鐵路、河流等線目標(biāo)，可求解得到各無人機(jī)的偵察序列及航跡。

2）對染色體交叉、變異操作的改進(jìn)，有效彌補(bǔ)了標(biāo)準(zhǔn)遺傳算法的易早熟和收斂性差等缺點，為其他啟發(fā)性算法的優(yōu)化提供了思路。

3）集中一體化式遺傳算法在求解效率及算法收斂性上，均具有一定的優(yōu)越性。

4）下一步可在多無人機(jī)協(xié)同偵察航跡規(guī)劃問題中引入更加復(fù)雜的任務(wù)背景和任務(wù)要求，來提高算法的實用性。