趙 明，趙玲玲，蘇小紅，馬培軍，張彥航（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱）

一種三維多UAV協(xié)同航跡規(guī)劃的空間模糊文化算法

趙 明，趙玲玲，蘇小紅，馬培軍，張彥航
（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001哈爾濱）

針對(duì)多無(wú)人機(jī)在三維環(huán)境下航跡規(guī)劃搜索空間大、多機(jī)協(xié)同困難等問(wèn)題，提出一種基于空間模糊表示和差分進(jìn)化相結(jié)合的文化算法.該方法首先用模糊集合表示三維空間網(wǎng)格點(diǎn)，提高關(guān)鍵路徑點(diǎn)的被關(guān)注度；然后組合空間模糊信息、歷史信息和協(xié)同信息成為文化算法的信念空間，用以剪枝規(guī)劃的搜索空間；在文化算法的種群空間則利用差分進(jìn)化生成滿足多機(jī)協(xié)同約束的優(yōu)解，并用差分獲得的未知領(lǐng)域知識(shí)擴(kuò)展信念空間，保證進(jìn)化種群的多樣性；最后，通過(guò)共享信息促進(jìn)知識(shí)的積累和修正搜索的方向.仿真實(shí)驗(yàn)表明，該方法提高了關(guān)鍵路徑點(diǎn)選取的效率，能夠探索空間中更多的未知區(qū)域，避免求解陷入局部最優(yōu)，更符合多機(jī)協(xié)同的需求，有助于快速規(guī)劃出多條可行的協(xié)同航跡.

多無(wú)人機(jī)；空間模糊；文化算法；協(xié)同航跡規(guī)劃；差分進(jìn)化

隨著無(wú)人機(jī)（unmanned aerial vehicle，UAV）技術(shù)的不斷發(fā)展，UAV系統(tǒng)具有更高的自主能力和協(xié)同性能，能夠以更低風(fēng)險(xiǎn)和更廉價(jià)的費(fèi)用完成多種復(fù)雜的作戰(zhàn)任務(wù)，并避免危險(xiǎn)導(dǎo)致的人員傷亡［1］.多機(jī)協(xié)同航跡規(guī)劃問(wèn)題是指在給定已知、部分已知或未知信息的環(huán)境中，規(guī)劃從起始點(diǎn)到達(dá)目標(biāo)點(diǎn)，可以繞過(guò)威脅區(qū)和障礙物且同時(shí)滿足各種約束條件和協(xié)同關(guān)系的多條可行飛行航跡［2］.該問(wèn)題是一個(gè)NP完全問(wèn)題，求解難度較大，是無(wú)人機(jī)任務(wù)規(guī)劃系統(tǒng)研究的難點(diǎn)之一.

當(dāng)前關(guān)于多機(jī)協(xié)同航跡規(guī)劃的研究有很多，如基于概率圖的規(guī)劃方法將規(guī)劃空間表示成簡(jiǎn)單的網(wǎng)絡(luò)圖，在網(wǎng)絡(luò)圖上搜索最短航跡，常用的概率圖有隨機(jī)路線圖［3］、Voronoi圖［4］等.啟發(fā)式A?算法也是常用的航跡規(guī)劃方法，該方法用啟發(fā)函數(shù)估算最優(yōu)節(jié)點(diǎn)，并基于靜態(tài)路網(wǎng)擴(kuò)展當(dāng)前位置快速搜索航跡［5－6］.此外，仿效力的作用形成空間力場(chǎng)進(jìn)行規(guī)劃的人工勢(shì)場(chǎng)法［7］也是有效進(jìn)行航跡規(guī)劃的方法.近年來(lái)群智能算法獲得了廣泛的關(guān)注，例如遺傳算法利用物種遺傳機(jī)制尋優(yōu)，通常將備選航跡表示成進(jìn)化個(gè)體，通過(guò)迭代搜索最優(yōu)航跡［8－9］.粒子群算法則利用粒子的記憶和相互間的學(xué)習(xí)，在空間中向著最優(yōu)解方向飛行獲得最佳航跡［10］.此外，將差分進(jìn)化應(yīng)用于多機(jī)航跡規(guī)劃也逐漸獲得興起，且獲得了較好的效果［11］.

為有效解決三維戰(zhàn)場(chǎng)環(huán)境下的多機(jī)協(xié)同航跡規(guī)劃問(wèn)題，本文首先提出一種三維空間模糊表示方法，利用空間點(diǎn)的模糊信息表示其被關(guān)注程度，以優(yōu)選關(guān)鍵路徑點(diǎn)；接著利用文化算法對(duì)問(wèn)題進(jìn)行建模，將空間點(diǎn)的模糊信息、歷史信息和協(xié)同信息組合成算法的信念空間，用以剪枝搜索的三維環(huán)境，為之后的進(jìn)化操作提供領(lǐng)域知識(shí)；在算法的種群空間，則利用基于關(guān)鍵路徑點(diǎn)的差分進(jìn)化算法規(guī)劃協(xié)同航跡，在求解的同時(shí)探索新的未知空間，并用未知空間的知識(shí)豐富原有信念空間，使規(guī)劃的航跡是多機(jī)協(xié)同的優(yōu)解組合.

1 基于空間模糊的文化算法框架

利用模糊集合表示UAV的規(guī)劃空間，可以獲得不同空間點(diǎn)的可飛性的隸屬程度.基于該隸屬程度進(jìn)行搜索，能夠凸顯有價(jià)值的點(diǎn)，快速篩選航跡的關(guān)鍵路徑點(diǎn)，有效約減空間搜索范圍.因此，分析三維空間中的點(diǎn)與規(guī)劃問(wèn)題之間的模糊關(guān)系，用模糊集合表示UAV飛行的三維空間，是有效可行的空間表示方法.

文化算法［12－14］利用領(lǐng)域知識(shí)來(lái)指導(dǎo)搜索過(guò)程以提高群體演化的性能.文化算法中的“文化”通常指群體演化過(guò)程中逐漸積淀的各種知識(shí)、經(jīng)驗(yàn)、信念、價(jià)值等行為習(xí)慣的總和.該算法同時(shí)維持兩個(gè)搜索空間：種群空間表示基于進(jìn)化原則的種群演化；信念空間表示演化種群中存在的文化成分.種群空間和信念空間并行進(jìn)化，通過(guò)通信協(xié)議相互影響，指導(dǎo)種群的快速演化.

采用文化算法求解多機(jī)協(xié)同航跡規(guī)劃問(wèn)題，可將模糊化的三維空間網(wǎng)格點(diǎn)作為環(huán)境知識(shí)，利用空間點(diǎn)的隸屬度篩選關(guān)鍵路徑點(diǎn)，影響種群空間中個(gè)體的生成；在種群空間通過(guò)差分進(jìn)化探索空間中的未知領(lǐng)域；同時(shí)將新個(gè)體的模糊信息和協(xié)同信息更新到信念空間，用以指導(dǎo)之后的演化，其框架如圖1所示.

圖1 空間模糊的文化算法框架

在圖1中，三維環(huán)境空間是系統(tǒng)的輸入，依據(jù)這些信息可以構(gòu)建出規(guī)劃的任務(wù)集.信念空間用來(lái)維護(hù)各種知識(shí)體系，用模糊集形成環(huán)境知識(shí)，在求解過(guò)程中更新種群空間產(chǎn)生的協(xié)同知識(shí)和歷史知識(shí).在種群空間中，差分進(jìn)化搜索滿足協(xié)同約束條件的新子代個(gè)體.信念空間和種群空間通過(guò)兩個(gè)通信協(xié)議進(jìn)行聯(lián)系，影響協(xié)議綜合信念空間中的知識(shí)以指導(dǎo)進(jìn)化種群的更新；接受協(xié)議則將進(jìn)化產(chǎn)生的優(yōu)解信息、協(xié)同信息傳播到信念空間，充實(shí)和完善信念知識(shí)庫(kù)，為之后的進(jìn)化迭代提供依據(jù).

2 基于模糊集的信念空間構(gòu)成

2.1 模糊隸屬度函數(shù)

三維空間中任一點(diǎn)P（x，y，z）是否適合作為航跡的關(guān)鍵路徑點(diǎn)，可由點(diǎn)P與UAV起始點(diǎn)和目標(biāo)點(diǎn)之間的三角距離關(guān)系、點(diǎn)P與威脅區(qū)域的距離關(guān)系，以及點(diǎn)P與地形的距離關(guān)系體現(xiàn)出來(lái).因此，對(duì)于柵格上可飛的點(diǎn)，可設(shè)定綜合的模糊隸屬度函數(shù).

2.1.1 最短航程關(guān)系隸屬度

UAV執(zhí)行任務(wù)的最短航程是從出發(fā)點(diǎn)到目標(biāo)點(diǎn)之間的直線距離，而空間中某點(diǎn)與出發(fā)點(diǎn)和目標(biāo)點(diǎn)的距離之和接近最短航程時(shí)，該點(diǎn)適于作為關(guān)鍵路徑點(diǎn)，其隸屬度較大，否則較小，最短航程隸屬度表示為

式中：x為空間中的某個(gè)點(diǎn)；s為UAV的出發(fā)點(diǎn)；t為執(zhí)行任務(wù)的目標(biāo)點(diǎn)；d為距離.同時(shí)設(shè)定x與s和t的距離之和大于最短航程距離10倍時(shí)，該點(diǎn)的隸屬度為0.

2.1.2 多雷達(dá)威脅和禁飛區(qū)隸屬度

在UAV執(zhí)行任務(wù)的區(qū)域通常存在多個(gè)探測(cè)雷達(dá)和禁飛區(qū).某點(diǎn)與各個(gè)雷達(dá)威脅和禁飛區(qū)關(guān)系的隸屬度，可用該點(diǎn)到威脅中心的距離與威脅半徑的關(guān)系計(jì)算.對(duì)多個(gè)威脅，可將隸屬度加權(quán)平均，其隸屬度函數(shù)為

式中：θ為威脅中心；d（x，θ）為點(diǎn)x到該威脅中心的距離；rθ為威脅半徑；n為雷達(dá)和禁飛區(qū)的個(gè)數(shù).

2.1.3 地形隸屬度

三維環(huán)境下執(zhí)行任務(wù)時(shí)要求UAV不能撞到地面造成毀傷，空間中某點(diǎn)與地形的關(guān)系可以轉(zhuǎn)換成該點(diǎn)在坐標(biāo)x、y、z方向上離地面最近的距離與安全距離的關(guān)系，因此地形隸屬度表示為

式中：di、dj、dk分別為點(diǎn)x在坐標(biāo)系x、y、z方向上與地面之間的距離；dm為UAV到地面的安全距離.以上3種模糊隸屬度的函數(shù)變化曲線如圖2所示.

綜合以上3種隸屬關(guān)系的隸屬度函數(shù)，獲得實(shí)際問(wèn)題求解的綜合隸屬度為

圖2 模糊隸屬度函數(shù)曲線

2.2 模糊信念空間的構(gòu)成

信念空間可以理解為求解問(wèn)題的知識(shí)倉(cāng)庫(kù)，存儲(chǔ)著種群中個(gè)體的習(xí)慣模式，通常由多種知識(shí)源構(gòu)成.

1）環(huán)境知識(shí)，即是求解問(wèn)題的較優(yōu)解集合.可以表示為一系列由關(guān)鍵路徑點(diǎn)組成的飛行備選航跡：

式中：Pks為s個(gè)組成備選航跡的關(guān)鍵路徑點(diǎn)；n為種群中航跡個(gè)體的數(shù)量.

2）歷史知識(shí).源于進(jìn)化迭代對(duì)較優(yōu)解的積累，將進(jìn)化產(chǎn)生的部分較優(yōu)解存儲(chǔ)到信念空間構(gòu)成歷史知識(shí).

式中：Pold為歷代已經(jīng)保留下來(lái)的個(gè)體；Presult為當(dāng)前代差分操作后獲得的結(jié)果種群；s%為個(gè)體保留的比例.選擇個(gè)體的概率可由個(gè)體的適應(yīng)度函數(shù)獲得

3）協(xié)同知識(shí).為有效提高多機(jī)作戰(zhàn)的協(xié)同性能，可用該點(diǎn)執(zhí)行當(dāng)前任務(wù)與執(zhí)行其他不同任務(wù)的隸屬度差異來(lái)進(jìn)行比較.

英國(guó)肉用家畜委員會(huì)下屬有25%以上的豬場(chǎng)應(yīng)用液體飼料飼喂。英國(guó)Wheyfeed有限公司每年向整個(gè)英國(guó)銷售運(yùn)輸超過(guò)20萬(wàn)噸液體副產(chǎn)品。荷蘭小麥淀粉、土豆皮、乳清粉和酵母濃縮蛋白質(zhì)等高水分副產(chǎn)品年產(chǎn)量約575萬(wàn)噸，不宜遠(yuǎn)距離運(yùn)輸，主要用在豬飼料上。荷蘭約60%的規(guī)?；i場(chǎng)使用液體飼喂技術(shù)[2]。隨著乙醇工業(yè)的發(fā)展，加拿大安大略省約有20%的生長(zhǎng)育肥豬飼喂含玉米酒糟和濃縮浸出水溶物配制的液體飼料[3]。

3 多機(jī)協(xié)同航跡規(guī)劃的文化算法

3.1 基于影響協(xié)議的種群生成

將空間柵格分解成一組在x或y軸方向上垂直于地平面的面，則從UAV出發(fā)點(diǎn)到目標(biāo)點(diǎn)之間的每一個(gè)柵格面上，利用輪盤賭法篩選出一個(gè)關(guān)鍵路徑點(diǎn)，基于模糊隸屬度選擇的概率為

式中Pi為柵格面上某點(diǎn)的選中概率.因此隸屬度較高的點(diǎn)，被選中的機(jī)會(huì)較大.通過(guò)輪盤賭法在不同的柵格面上選擇關(guān)鍵路徑點(diǎn)，然后將這些關(guān)鍵點(diǎn)連接起來(lái)，就形成了一條初始航跡個(gè)體.

基于以上的個(gè)體生成方法，可在空間柵格上產(chǎn)生n條備選的航跡，組成基于環(huán)境知識(shí)的種群Penviro.同時(shí)，通過(guò)知識(shí)積累逐漸形成基于歷史知識(shí)的種群Phistory.因此基于影響協(xié)議的種群生成可表示為

式中：（g／Gen）為當(dāng)前代數(shù)占總代數(shù)的比例，隨著進(jìn)化過(guò)程不斷的增長(zhǎng)，歷史知識(shí)積累可以加快算法的收斂；Pory為在種群生成時(shí)必須包含在歷史知識(shí)中的當(dāng)前最優(yōu)解，以防止進(jìn)化算法重復(fù)搜索到次優(yōu)的位置.

3.2 基于接受協(xié)議的信念更新

可通過(guò)接受協(xié)議更新信念空間，根據(jù)信念空間的知識(shí)來(lái)源，其更新操作如下.

1）環(huán)境動(dòng)態(tài)更新.為了盡可能全面的覆蓋航跡的搜索空間，在進(jìn)化過(guò)程中，可通過(guò)改變柵格的整體位置和柵格的空間結(jié)構(gòu)來(lái)生成新的種群，擴(kuò)大空間的覆蓋范圍.柵格的表示方法為

式中：U、L分別為x、y、z分量上的取值范圍；n為網(wǎng)格的數(shù)量.為避免結(jié)構(gòu)不斷改變?cè)斐傻拇罅坑?jì)算，設(shè)定環(huán)境更新的閾值λ，使種群進(jìn)化λ代數(shù)后再執(zhí)行更新.網(wǎng)格更新可表示為

式中：g為當(dāng)前進(jìn)化的代數(shù)，當(dāng)進(jìn)化的代數(shù)與閾值的余數(shù)為0時(shí)，更新初始坐標(biāo)位置和柵格的數(shù)量；ε、δ、γ分別為坐標(biāo)更新的分量；n為一個(gè)大于2，且小于網(wǎng)格上限U的整數(shù).

2）歷史選擇更新.歷史選擇更新包括隨機(jī)個(gè)體保留和最優(yōu)解保留兩個(gè)方面，分別可表示為

式中：phistory為歷史信息種群，記錄不同進(jìn)化代中的部分個(gè)體；pbest為當(dāng)前最優(yōu)解.

3）協(xié)同信息更新.當(dāng)差分進(jìn)化生成新個(gè)體時(shí)，要計(jì)算新個(gè)體的協(xié)同值并加入到適應(yīng)度函數(shù)中，以便和種群中的父代個(gè)體進(jìn)行比較.在更新協(xié)同信息時(shí)，保存已有個(gè)體的協(xié)同值，僅計(jì)算新個(gè)體的協(xié)同值即可.

3.3 種群空間的差分協(xié)同航跡規(guī)劃

差分進(jìn)化是基于實(shí)數(shù)編碼的并行搜索算法，非常適合基于路徑點(diǎn)坐標(biāo)的航跡個(gè)體進(jìn)化操作，因此，本文在文獻(xiàn)［11，15－16］的基礎(chǔ)上，根據(jù)三維空間中點(diǎn)的坐標(biāo)值將差分進(jìn)化的差分操作擴(kuò)展如下

式中：m為航跡個(gè)體關(guān)鍵路徑點(diǎn)的個(gè)數(shù)；i、j、k分別為點(diǎn)在三維坐標(biāo)軸上的分量；F為交叉率，一般取在［0，1］范圍內(nèi)的值；如果新位置產(chǎn)生的個(gè)體具有更好的適應(yīng)度，則可以通過(guò)選擇操作加以保留，如

式中：g為當(dāng)前種群的迭代次數(shù)，f（x）為適應(yīng)度函數(shù).

為了利用文化空間的模糊和協(xié)同信息來(lái)引導(dǎo)搜索，本文采用的適應(yīng)度函數(shù)為

式中：fcost（x）為UAV自身的飛行代價(jià)，包括最大航程、總飛行時(shí)間、燃油指標(biāo)約束等因素；μ～（x）為當(dāng)前航跡上關(guān)鍵路徑點(diǎn)的隸屬度；σ（x）為當(dāng)前航跡上關(guān)鍵路徑點(diǎn)的協(xié)同值；α、β分別為比例因子，協(xié)調(diào)三者的量級(jí).

4 結(jié)果與分析

本文將文獻(xiàn)［16］的實(shí)驗(yàn)結(jié)果作為輸入.在此前提下，在奔騰雙核3.20 GHz、8 GB內(nèi)存的PC機(jī)上，利用Matlab（R2011b）仿真軟件環(huán)境進(jìn)行實(shí)驗(yàn)，驗(yàn)證算法的可行性和有效性，并與標(biāo)準(zhǔn)文化算法進(jìn)行了比較.

4.1 航跡規(guī)劃可行性實(shí)驗(yàn)（實(shí)驗(yàn)1）

設(shè)定實(shí)驗(yàn)的環(huán)境參數(shù)如表1所示，UAV與目標(biāo)的關(guān)系來(lái)自于目標(biāo)分配的結(jié)果.同時(shí)設(shè)定實(shí)驗(yàn)群體空間中差分進(jìn)化的參數(shù)為：種群大?。≒op＝20）、進(jìn)化代數(shù)（Gen＝500）、交叉率（F＝0.7）、比例因子（α＝200）、比例因子（β＝150）、歷史保留率（s%＝10%）.實(shí)驗(yàn)結(jié)果如圖3、4所示，其中：圖3（a）為仿真實(shí)驗(yàn)規(guī)劃的結(jié)果；圖3（b）為單條航跡規(guī)劃的收斂曲線.圖4（a）～（c）為隱藏地形和威脅區(qū)后，在不同視角上航跡的顯示結(jié)果.

從圖3獲得的結(jié)果可以看出，改進(jìn)后的算法能夠有效的生成多架UAV可行的飛行航跡.同時(shí)，算法的收斂性能較強(qiáng)，后期不會(huì)輕易陷入局部最優(yōu).從圖4中不同視角顯示的結(jié)果可以看出，規(guī)劃后的航跡具有較好的協(xié)同避碰性能，航跡與航跡之間幾乎沒(méi)有交叉點(diǎn)的存在，因此改進(jìn)的算法具有較好的協(xié)同能力.

表1 實(shí)驗(yàn)的環(huán)境參數(shù)

圖3 協(xié)同航跡仿真實(shí)驗(yàn)結(jié)果和算法收斂曲線

圖4 不同視角的航跡協(xié)同效果

圖5 DE與標(biāo)準(zhǔn)文化算法收斂曲線比較

4.2 與其他文化算法的對(duì)比分析（實(shí)驗(yàn)2）

標(biāo)準(zhǔn)文化算法是基于GA算法維持種群空間進(jìn)化尋優(yōu)的，因此本文還與標(biāo)準(zhǔn)文化算法和非模糊空間下的標(biāo)準(zhǔn)文化算法進(jìn)行了對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖5和表2所示.

從圖5可以看出，標(biāo)準(zhǔn)文化算法也能夠有效利用信念空間中的知識(shí)指導(dǎo)搜索的深入，然而算法的收斂存在早熟現(xiàn)象，因此搜索性能較基于DE算法的文化算法差很多.從表2可以看出，非模糊空間的標(biāo)準(zhǔn)文化算法存在個(gè)別任務(wù)失效，這是由于隨機(jī)搜索依賴于更好的初始化表示和更多的迭代次數(shù).

表2 規(guī)劃算法的任務(wù)代價(jià)和執(zhí)行時(shí)間比較

5 結(jié) 論

1）采用文化算法對(duì)航跡規(guī)劃問(wèn)題進(jìn)行整體建模，用空間模糊信息、歷史信息和協(xié)同信息共同組成算法的信念空間，剪枝航跡規(guī)劃的搜索空間、保證種群多樣性、并為深入搜索提供了全局信息.

2）在種群空間中改進(jìn)差分進(jìn)化算法，使其適用于求解航跡規(guī)劃問(wèn)題，并將獲得的新個(gè)體按比例輸入歷史信息庫(kù)，為之后的搜索積累更豐富的環(huán)境知識(shí)和協(xié)同知識(shí)，降低搜索的盲目性.

3）本文針對(duì)多機(jī)協(xié)同避碰問(wèn)題，在適應(yīng)度函數(shù)中加入?yún)f(xié)同信息量，提高了航跡個(gè)體處理協(xié)同避碰的能力.實(shí)驗(yàn)結(jié)果證明了本文方法的有效性.

［1］SHIN H S，LEBOUCHER C，TSOURDOS A.Resource allocation with cooperative path planning for multiple UAVs［C］／／Proceedings of the 2012 UKACC International Conference on Control.Cardiff：IEEE，2012：298－303.

［2］葉媛媛，閔春平.多無(wú)人機(jī)協(xié)同航路規(guī)劃的共同進(jìn)化方法［J］.計(jì)算機(jī)仿真，2007，24（5）：37－39，149.

［3］YANG K，SUKKARIEH S.Real?time continuous curvature path planning of UAVs in cluttered environments［C］／／Proceedings of the ISMA08 5th International Symposium on Mechatronics and Its Applications.Amman，Jordan：IEEE，2008：1－6.

［4］PEHLIVANOGLU Y V.A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV［J］.Aerospace Science and Technology，2012，16（1）：47－55.

［5］MENG Bobo，GAO Xiaoguang.UAV path planning based on bidirectional sparse A?search algorithm［C］／／Proceedings of 2010 International Conference on Intelligent Computation Technology and Automation.Changsha：IEEE，2010：1106－1109.

［6］MITSUTAKE K，HIGASHINO S I.An A??EC hybrid path planning method for waypoint traveling problem considering terrain［C］／／Proceedings of AIAA Guidance Navigation and Control Conference and Exhibit.Honolulu，Hawaii：AIAA，2008，7133：1－14.

［7］DAILYR，BEVLY D M.Harmonic potential field path planning for high speed vehicles［C］／／Proceedings of American Control Conference.Seattle，WA：IEEE，2008：4609－4614.

［8］NIKOLOS I K，VALAVANIS K P，TSOURVELOUDIS N C，et al.Evolutionary algorithm based offline／online path planner for UAV navigation［J］.IEEE Transactions on Systems，Man，and Cybernetics，2003，33（6）：898－912.

［9］ALLAIRE F C J，TARBOUCHI M，LABONTéG，et al. FPGA implementation of genetic algorithm for UAV real?time path planning［M］.Springer Netherlands：Unmanned Aircraft Systems，2009：495－510.

［10］FOO J L，KNUTZON J，KALIVARAPU V，et al.Path planning of unmanned aerial vehicles using B?splines and particle swarm optimization［J］.Journal of Aerospace Computing，Information，and Communication，2009，6（4）：271－290.

［11］RAKSHIT P，KONAR A，BHOWMIK P，et al.Realization of an Adaptive Memetic Algorithm Using Differential Evolution and Q?Learning：A Case Study in Multirobot Path Planning［J］.IEEE Transactions on Systems，Man，and Cybernetics：Systems，2013，43（4）：814－831.

［12］ENGELBRECHT A P.Computational intelligence：an introduction［M］.2nd ed.John Wiley＆Sons，2009.

［13］REYNOLDSR G.An introduction to cultural algorithms［C］／／Proceedings of the Third Annual Conference on Evolutionary programming.San Diego，CA：IEEE，1994：131－139.

［14］SUN Yang，ZHANG Lingbo，GU Xingsheng.A hybrid co?evolutionary cultural algorithm based on particle swarm optimization for solving global optimization problems［J］. Neurocomputing，2012，98：76－89.

［15］ONWUBOLU G，DAVENDRA D.Differential evolution for permutation?based combinatorial problems［M］.Berlin Heidelberg：Springer，2009.

［16］趙明，蘇小紅，馬培軍，等.復(fù)雜多約束UAVs協(xié)同目標(biāo)分配的一種統(tǒng)一建模方法［J］.自動(dòng)化學(xué)報(bào)，2012，38（12）：2038－2048.

（編輯 張 紅）

A cultural algorithm with spatial Fuzzy set to solve Multi?UAVs cooperative path planning in a three dimensional environment

ZHAO Ming，ZHAO Lingling，SU Xiaohong，MA Peijun，ZHANG Yanhang
（School of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China）

The Multi?UAVs cooperative path planning has a complex search space in 3D environment，while the cooperative of Multi?UAVs is very hard to deal with.So a novel cultural algorithm based on spatial fuzzy set and differential evolution is proposed in this paper.The proposed approach uses fuzzy set to present spatial grid points in 3D，so that the key way?points on path should be paid more attention.Then the spatial fuzzy knowledge，history knowledge and cooperative knowledge that contained in the belief space of cultural algorithm prune the search space of Multi?UAVs path planning.Moreover，this approach uses differential evolution as the population space of cultural algorithm to generate the optimal solution，while it satisfies the constraints ofmulti?UAVs cooperative.The differential also extends the belief space with the unknown information of spatial to ensure the population diversity.In addition，the cultural algorithm exchanges the shared information，so that it accumulates the knowledge and revises the searching direction.The simulation results show that the spatial grid points based on fuzzy set enhance the efficiency of key way?points selected，and the culturalalgorithm could explore more unknown space out ofspatial grid such that it avoids the search fall into local optimization.Cooperative knowledge is also introduced to satisfy the requirements of Multi?UAVs cooperative to planning feasible paths for Multi?UAVs cooperative quickly.

Multi?UAVs；spatial fuzzy；cultural algorithm；cooperative path planning；differential evolution

TP242.6

A

0367－6234（2015）10－0029－06

10.11918／j.issn.0367?6234.2015.10.006

2014－06－06.

國(guó)家自然科學(xué)基金（61175027，61305023）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（HIT.NSRIF.2015069）.

趙 明（1979—），男，博士研究生；蘇小紅（1966—），女，教授，博士生導(dǎo)師；馬培軍（1963—），男，教授，博士生導(dǎo)師.

蘇小紅，sxh＠hit.edu.cn.