王龍寶，欒茵琪，徐亮，曾昕，張帥，徐淑芳*

基于動(dòng)態(tài)簇粒子群優(yōu)化的無(wú)人機(jī)集群路徑規(guī)劃方法

王龍寶1，2，欒茵琪1，徐亮3，曾昕3，張帥4，徐淑芳1，2*

（1.河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，南京 211000； 2.水利部水利大數(shù)據(jù)技術(shù)重點(diǎn)實(shí)驗(yàn)室（河海大學(xué)），南京 211000； 3.長(zhǎng)江生態(tài)環(huán)保集團(tuán)有限公司，武漢 430014； 4.中國(guó)電建集團(tuán)昆明勘測(cè)設(shè)計(jì)研究院有限公司，昆明 650051）（ ? 通信作者電子郵箱xushufang@hhu.edu.cn）

路徑規(guī)劃對(duì)于無(wú)人機(jī)（UAV）集群的任務(wù)執(zhí)行十分重要，而且高維場(chǎng)景中的計(jì)算通常很復(fù)雜。群體智能為解決該問(wèn)題提供了較好的解決思路。粒子群優(yōu)化（PSO）算法具有參數(shù)少、收斂速度快、操作簡(jiǎn)單等優(yōu)點(diǎn)，尤其適用于路徑規(guī)劃問(wèn)題，但它在應(yīng)用時(shí)存在全局搜索能力差、容易陷入局部最優(yōu)的問(wèn)題。為了解決上述問(wèn)題以提升無(wú)人機(jī)集群路徑規(guī)劃的效果，提出了動(dòng)態(tài)簇粒子群優(yōu)化（DCPSO）算法。首先，利用人工勢(shì)場(chǎng)法和滾動(dòng)時(shí)域控制原理建模UAV集群路徑規(guī)劃問(wèn)題的任務(wù)場(chǎng)景；其次，引入Tent混沌映射和動(dòng)態(tài)簇機(jī)制進(jìn)一步提升全局搜索能力和搜索精度；最后，使用DCPSO算法優(yōu)化模型的目標(biāo)函數(shù)，以獲得UAV集群的每個(gè)軌跡點(diǎn)的選擇。在單峰/多峰、低維/高維不同組合的10種基準(zhǔn)測(cè)試函數(shù)下的仿真實(shí)驗(yàn)結(jié)果表明，與PSO、鴿子啟發(fā)優(yōu)化（PIO）、麻雀搜索算法（SSA）和混沌擾動(dòng)鴿群優(yōu)化（CDPIO）算法相比，DCPSO算法具有更好的計(jì)算最優(yōu)值、均值和方差，搜索精度更佳，穩(wěn)定性更強(qiáng)。此外，UAV集群路徑規(guī)劃應(yīng)用實(shí)例仿真結(jié)果也驗(yàn)證了DCPSO算法的性能與效果。

粒子群優(yōu)化；動(dòng)態(tài)簇機(jī)制；無(wú)人機(jī)集群；路徑規(guī)劃；滾動(dòng)時(shí)域控制

0 引言

無(wú)人機(jī)（Unmanned Aerial Vehicle， UAV）路徑規(guī)劃是無(wú)人機(jī)各項(xiàng)任務(wù)中涉及的關(guān)鍵問(wèn)題。無(wú)人機(jī)在到達(dá)目標(biāo)點(diǎn)執(zhí)行特定任務(wù)之前，必須規(guī)劃從起點(diǎn)到下一個(gè)任務(wù)點(diǎn)的合理路徑，并成功避開(kāi)障礙物；但實(shí)際場(chǎng)景中的任務(wù)一般非常復(fù)雜，單架無(wú)人機(jī)存在效率低、響應(yīng)慢、有時(shí)無(wú)法完成復(fù)雜任務(wù)的問(wèn)題。無(wú)人機(jī)集群可以解決單架無(wú)人機(jī)效率低等問(wèn)題，通過(guò)集群內(nèi)的相互感知和信息交換，無(wú)人機(jī)集群可以在敵對(duì)的復(fù)雜環(huán)境中以較低的成本完成復(fù)雜的任務(wù)，這就要求無(wú)人機(jī)集群能夠安全高效地完成路徑規(guī)劃工作。

近年來(lái)，無(wú)人機(jī)集群路徑規(guī)劃主要有兩個(gè)研究方向：一種是經(jīng)典路徑規(guī)劃算法，如梯度下降法［1］和圖論法［2］；另一種是群體智能優(yōu)化算法，如麻雀搜索算法（Sparrow Search Algorithm， SSA）［3］和鴿子啟發(fā)優(yōu)化（Pigeon-Inspired Optimization， PIO）［4］。但經(jīng)典算法通常伴隨著各種各樣的問(wèn)題，例如，梯度下降法需要大量的迭代計(jì)算，不能保證優(yōu)化效果。群體智能優(yōu)化算法是一種模仿生物集群行為產(chǎn)生的算法，擅長(zhǎng)處理復(fù)雜的多約束優(yōu)化問(wèn)題［5］。

粒子群優(yōu)化（Particle Swarm Optimization， PSO）［6］是經(jīng)典的群體智能優(yōu)化算法，具有參數(shù)少、計(jì)算簡(jiǎn)單、收斂快等優(yōu)點(diǎn)，適合解決無(wú)人機(jī)集群復(fù)雜路徑規(guī)劃問(wèn)題；但PSO本身也存在精度低、易陷入局部最優(yōu)的問(wèn)題。文獻(xiàn)［7］中提出了一種結(jié)合PSO的自適應(yīng)差分進(jìn)化算法，它的核心思想是根據(jù)粒子偏離全局最優(yōu)解的程度分配不同的搜索模式，并將所提出的算法應(yīng)用于無(wú)人機(jī)集群路徑規(guī)劃中，取得了良好的效果；文獻(xiàn)［8］中利用時(shí)變自適應(yīng)慣性權(quán)重的思想，提出了一種具有較高種群多樣性的改進(jìn)PSO算法，并成功應(yīng)用于無(wú)人機(jī)集群路徑規(guī)劃；文獻(xiàn)［9］中將遺傳算法和PSO有機(jī)結(jié)合，成功應(yīng)用于無(wú)人機(jī)集群路徑規(guī)劃。

由于PSO容易陷入局部最優(yōu)，所以改進(jìn)PSO意義巨大。文獻(xiàn)［10］中在局部最優(yōu)解附近添加混沌擾動(dòng)算子，使它具有突跳能力，進(jìn)而提高全局搜索能力；文獻(xiàn)［11］中使用Tent混沌映射進(jìn)行混沌填充，增強(qiáng)初始化階段的種群多樣性，有利于種群在早期演化階段遍歷整個(gè)可行解域?；煦缬成渫ǔ１挥脕?lái)解決在初始化種群時(shí)快速陷入局部最優(yōu)的問(wèn)題，本文利用Tent混沌映射具有的隨機(jī)性和遍歷性，改善PSO在初始化種群時(shí)快速陷入局部最優(yōu)的問(wèn)題；然而，種群在移動(dòng)過(guò)程中仍會(huì)出現(xiàn)容易陷入局部最優(yōu)的問(wèn)題，因此，本文引入了動(dòng)態(tài)簇機(jī)制。

本文針對(duì)全局搜索能力弱的共性問(wèn)題進(jìn)行了改進(jìn)，針對(duì)它在高維復(fù)雜環(huán)境中路徑規(guī)劃的應(yīng)用，提出了動(dòng)態(tài)簇PSO（Dynamic Cluster Particle Swarm Optimization， DCPSO）算法，采用Tent混沌映射和動(dòng)態(tài)簇機(jī)制進(jìn)行改進(jìn)。通過(guò)實(shí)驗(yàn)充分驗(yàn)證了DCPSO在復(fù)雜任務(wù)場(chǎng)景下無(wú)人機(jī)集群路徑規(guī)劃中的有效性。本文還揭示了生物群體智能應(yīng)用于無(wú)人機(jī)集群路徑規(guī)劃的一般規(guī)律，為生物群體智能優(yōu)化算法和無(wú)人機(jī)集群智能提供理論依據(jù)和應(yīng)用參考。

1 相關(guān)工作

1.1　問(wèn)題描述

假設(shè)無(wú)人機(jī)集群從基地出發(fā)，飛向任務(wù)地點(diǎn)，協(xié)同執(zhí)行特定任務(wù)。要求無(wú)人機(jī)集群合理規(guī)劃飛行路徑，到達(dá)任務(wù)位置執(zhí)行后續(xù)任務(wù)，同時(shí)避開(kāi)途中障礙物。假設(shè)一組具有相同配置的攜帶傳感器檢測(cè)設(shè)備的無(wú)人機(jī)集群，且規(guī)定每個(gè)無(wú)人機(jī)可以相互通信。在巡航任務(wù)期間，無(wú)人機(jī)集群通常在規(guī)定的高度飛行且高度不變。任務(wù)區(qū)設(shè)置為矩形區(qū)域，無(wú)人機(jī)集群從起飛區(qū)域出發(fā)，按照規(guī)劃路徑避開(kāi)多個(gè)障礙物到達(dá)任務(wù)點(diǎn)。為了在路徑規(guī)劃中合理地描述無(wú)人機(jī)集群的狀態(tài)，需要設(shè)計(jì)一個(gè)高效的模型構(gòu)建任務(wù)場(chǎng)景。

本文使用人工勢(shì)場(chǎng)的方法構(gòu)建任務(wù)場(chǎng)景。人工勢(shì)場(chǎng)法是由Khatib［12］提出的一種虛擬力方法，常用于機(jī)器人路徑規(guī)劃。該方法將環(huán)境抽象地模擬為一個(gè)力場(chǎng)，通過(guò)作用在物體上的重力和排斥力實(shí)現(xiàn)路徑規(guī)劃。通常，無(wú)人機(jī)朝向的目標(biāo)點(diǎn)會(huì)對(duì)物體產(chǎn)生重力，而需要避開(kāi)的障礙物會(huì)對(duì)物體產(chǎn)生排斥力，從而使物體可以避開(kāi)環(huán)境中的障礙物到達(dá)目標(biāo)點(diǎn)，最終實(shí)現(xiàn)合理的路徑規(guī)劃。

本文將無(wú)人機(jī)集群路徑規(guī)劃問(wèn)題轉(zhuǎn)化為多約束優(yōu)化問(wèn)題。以無(wú)人機(jī)為例，使用式（2）優(yōu)化上述問(wèn)題：

圖1　無(wú)人機(jī)集群路徑規(guī)劃模型的結(jié)構(gòu)

1.2　無(wú)人機(jī)集群相應(yīng)規(guī)則

為了便于研究，本文簡(jiǎn)化了無(wú)人機(jī)集群運(yùn)動(dòng)規(guī)則和環(huán)境模型。無(wú)人機(jī)集群的高度在仿真模型中是固定的，因?yàn)樗趯?shí)際巡航任務(wù)中通常變化很小，從而將實(shí)際問(wèn)題轉(zhuǎn)化為二維場(chǎng)景，飛行環(huán)境也轉(zhuǎn)化為二維平面；此外，將無(wú)人機(jī)集群視為一組粒子并限制飛行過(guò)程中的最大偏航角。對(duì)于無(wú)人機(jī)集群飛行環(huán)境進(jìn)行離散網(wǎng)格處理，其中每個(gè)網(wǎng)格中心都有代表整個(gè)網(wǎng)格的信息值。

1.2.1人工勢(shì)場(chǎng)法

根據(jù)問(wèn)題描述，可知任務(wù)場(chǎng)景中只有一個(gè)目標(biāo)點(diǎn)，所以在終點(diǎn)給出一個(gè)低勢(shì)能，為無(wú)人機(jī)提供更大的牽引力。將任務(wù)場(chǎng)景設(shè)置為矩形區(qū)域，并構(gòu)建笛卡爾坐標(biāo)系。使用式（3）在目標(biāo)點(diǎn)處布置了一個(gè)山谷型勢(shì)場(chǎng)［3］。

對(duì)于任務(wù)場(chǎng)景中的障礙物，使用式（4）構(gòu)建山勢(shì)場(chǎng)：

取兩個(gè)局部勢(shì)場(chǎng)中較高的兩個(gè)值相加作為總勢(shì)場(chǎng)，得到無(wú)人機(jī)集群路徑規(guī)劃的人工勢(shì)場(chǎng)，如式（5）所示：

1.2.2滾動(dòng)時(shí)域控制

使用滾動(dòng)時(shí)域控制策略對(duì)無(wú)人機(jī)集群路徑規(guī)劃進(jìn)行離散處理。以無(wú)人機(jī)為例，無(wú)人機(jī)每個(gè)時(shí)刻都覆蓋一個(gè)滾動(dòng)時(shí)域窗口，隨著時(shí)間推移向前移動(dòng)［13］。由于無(wú)人機(jī)集群路徑規(guī)劃的長(zhǎng)度是不確定的，且在實(shí)際場(chǎng)景中通常很長(zhǎng)，如果將整個(gè)無(wú)人機(jī)集群的路徑作為優(yōu)化問(wèn)題的輸出，要優(yōu)化的函數(shù)在高維上會(huì)變得非常復(fù)雜，因此，本文采用滾動(dòng)時(shí)域控制策略解決這個(gè)問(wèn)題。

圖2　滾動(dòng)時(shí)域控制策略示意圖

2 算法提出

2.1　算法基礎(chǔ)

2.1.1PSO算法

PSO是一種受鳥(niǎo)類覓食機(jī)制啟發(fā)，基于一種速度和位置搜索模型的群體智能優(yōu)化算法。這種算法是一種并行算法，具有實(shí)現(xiàn)簡(jiǎn)單、精度高、收斂快等優(yōu)點(diǎn)，對(duì)于解決實(shí)際問(wèn)題存在重要意義。與大多數(shù)群體智能優(yōu)化算法一樣，整個(gè)種群是問(wèn)題的輸入和待優(yōu)化的輸出，每一個(gè)個(gè)體都是一個(gè)候選解。

粒子群算法的迭代公式如式（9）所示：

式（10）中的社會(huì)機(jī)制為算法提供了牽引力，但也制約了算法的全局搜索能力。

2.1.2Tent混沌映射

混沌映射是非線性系統(tǒng)中一種特別非周期性的現(xiàn)象，它普遍存在，具有隨機(jī)性、遍歷性和規(guī)律性等特點(diǎn)。使用混沌映射初始化種群，可以有效增加初始種群的多樣性，提高初始解的質(zhì)量和全局優(yōu)化能力，有效避免陷入局部最優(yōu)的情況。Tent映射［14］是典型的混沌系統(tǒng)，因它的函數(shù)圖像類似帳篷又被稱為帳篷映射，呈現(xiàn)比較均勻的分布密度，在遍歷性、均勻性和迭代速度方面具有相當(dāng)?shù)膬?yōu)勢(shì)。迭代更新公式如式（11）所示：

2.2　DCPSO算法

2.2.1動(dòng)態(tài)簇機(jī)制

從式（9）（10）可以看出，標(biāo)準(zhǔn)PSO的迭代更新過(guò)于依賴社會(huì)部分，一旦記錄下的整個(gè)種群的最優(yōu)位置趨向局部最優(yōu)，整個(gè)粒子群就會(huì)被牽引，進(jìn)而陷入局部最優(yōu)。為此，本文改進(jìn)了這種機(jī)制，并生成了一種新的動(dòng)態(tài)簇機(jī)制。實(shí)驗(yàn)結(jié)果表示，粒子群更趨于在最優(yōu)位置點(diǎn)附近聚集。本文在PSO中引入了動(dòng)態(tài)簇機(jī)制，形成一種新的DCPSO算法，以減少粒子之間不必要的通信并擴(kuò)展全局搜索能力。動(dòng)態(tài)簇機(jī)制是一種從自身機(jī)制角度提高PSO性能的自適應(yīng)策略。隨著粒子群的不斷迭代和更新，算法根據(jù)密度對(duì)粒子群進(jìn)行動(dòng)態(tài)分類。與靜態(tài)簇相比，動(dòng)態(tài)簇機(jī)制可能具有更高的復(fù)雜度，但相應(yīng)地，算法性能的整體增益也更大。

動(dòng)態(tài)簇機(jī)制［15］有4個(gè)過(guò)程：選擇簇頭、聚類、迭代計(jì)算和合并以準(zhǔn)備下一次聚類。首先，選擇每個(gè)時(shí)刻最密集位置的個(gè)體作為第一個(gè)簇的簇頭1；其次，種群中距離簇頭1最近的一半個(gè)體被包含在簇1中，其余的個(gè)體全部被包含在簇2中，兩個(gè)簇共享簇內(nèi)的資源并在簇之間沒(méi)有交互的情況下進(jìn)行迭代；最后，合并兩個(gè)簇，為下一次循環(huán)做準(zhǔn)備。

如圖3（a）所示，由于社會(huì)機(jī)制的存在，粒子群中的個(gè)體會(huì)受群體中處于最佳位置的個(gè)體的牽引。例如，粒子0被粒子1拖向局部最優(yōu)1，算法很可能陷入局部最優(yōu)。如圖3（b）所示，通過(guò)添加連接機(jī)制，這種情況得到改善。根據(jù)粒子群的運(yùn)動(dòng)機(jī)制，可以判斷最密集位置的粒子接近的某個(gè)最優(yōu)值；因此，將最密集位置的一半粒子群作為簇1，其余的作為簇2進(jìn)行不連續(xù)迭代。通過(guò)這種方式，簇1跟隨最優(yōu)粒子1到局部最優(yōu)1，簇2跟隨最優(yōu)粒子0到全局最優(yōu)0。一次迭代后，將簇合并，依此類推，最終整個(gè)種群將被引導(dǎo)至全局最優(yōu)。這樣既可以保留簇1原有的PSO趨勢(shì)，又可以獲得由簇2提供的全局搜索能力。

圖3　PSO和DCPSO算法的粒子運(yùn)動(dòng)對(duì)比

2.2.2DCPSO算法

針對(duì)PSO在求解復(fù)雜高維問(wèn)題時(shí)存在的搜索精度低、易陷入局部最優(yōu)、魯棒性差等缺點(diǎn)，DCPSO算法首先使用Tent混沌映射初始化種群，以提高初始種群的多樣性；其次，在整個(gè)算法過(guò)程中采用動(dòng)態(tài)簇機(jī)制，進(jìn)一步提高算法的全局搜索能力和搜索精度。

具體實(shí)現(xiàn)步驟如算法1所示。

算法1 DCPSO框架。

輸入 最大迭代次數(shù)，迭代次數(shù)，粒子群大?。?/p>

輸出 最優(yōu)解位置，最優(yōu)適應(yīng)度值。

1） 根據(jù)式（7）和式（11）初始化具有個(gè)粒子的粒子群

2） 根據(jù)不同需求設(shè)計(jì)目標(biāo)函數(shù)

3） for= 0 to

4） 使用動(dòng)態(tài)簇機(jī)制將粒子群分為簇1和簇2

5） 分別通過(guò)PSO更新簇1和簇2

6） 將兩個(gè)簇合并成一個(gè)完整的粒子群

7） 得到當(dāng)前全局最優(yōu)值

8） 如果全局最優(yōu)值優(yōu)于先前全局最優(yōu)值，更新全局最優(yōu)值

9）=+ 1

10） end for

11） return，

2.3　路徑規(guī)劃

在上述建模過(guò)程中利用人工勢(shì)場(chǎng)法和滾動(dòng)時(shí)域控制這兩個(gè)優(yōu)化策略可以得到待優(yōu)化的目標(biāo)函數(shù)，將無(wú)人機(jī)集群路徑規(guī)劃的問(wèn)題轉(zhuǎn)化為求解目標(biāo)函數(shù)最優(yōu)解的問(wèn)題。根據(jù)DCPSO算法構(gòu)建相應(yīng)的求解思路并給出算法優(yōu)化過(guò)程，從而實(shí)現(xiàn)三維空間的無(wú)人機(jī)集群路徑規(guī)劃，具體流程如圖4所示，詳細(xì)過(guò)程如算法2所示。

圖4　基于DCPSO的無(wú)人機(jī)集群路徑規(guī)劃流程

算法2 基于DCPSO的無(wú)人機(jī)集群路徑規(guī)劃步驟。

輸入 無(wú)人機(jī)集群起飛點(diǎn)，障礙物坐標(biāo)，飛行終點(diǎn)；

輸出 無(wú)人機(jī)集群飛行路徑。

1） 根據(jù)輸入，和構(gòu)建人工勢(shì)場(chǎng)

2） While 飛行軌跡不包含

3） 使用式（6）建立當(dāng)前時(shí)間的目標(biāo)函數(shù)

4） 使用DCPSO優(yōu)化當(dāng)前時(shí)間目標(biāo)函數(shù)，獲得最優(yōu)解位置

5） 根據(jù)獲取當(dāng)前時(shí)間路徑點(diǎn)，并將它置于內(nèi)

6） end while

7） return

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1　仿真環(huán)境及參數(shù)

3.1.1基準(zhǔn)函數(shù)

本文使用了單峰低維、單峰高維、多峰低維和多峰高維（http：//www.sfu.ca/～ssurjano/optimization.html）這4種類型的測(cè)試函數(shù)測(cè)試算法的性能。此外，為了避免單次優(yōu)化的偏差，仿真實(shí)驗(yàn)采用了蒙特卡羅模擬方法。每個(gè)測(cè)試函數(shù)運(yùn)行30次，得到最優(yōu)值、平均值、標(biāo)準(zhǔn)差和平均時(shí)間，最后與標(biāo)準(zhǔn)PSO［6］、鴿子啟發(fā)優(yōu)化（PIO）［4］、麻雀搜索算法（SSA）［3］和混沌擾動(dòng)鴿群優(yōu)化（Chaotic Disturbance Pigeon-inspired Optimization， CDPIO）算法［16］進(jìn)行比較。

3.1.2算法參數(shù)

PSO、PSO、SSA和DCPSO算法的參數(shù)設(shè)置如表1所示。

表1PSO、PIO、SSA和DCPSO算法的參數(shù)

Tab.1　Parameters for PSO， PIO， SSA and DCPSO algorithms

在相同測(cè)試函數(shù)的條件下，優(yōu)化結(jié)果的最優(yōu)值可以衡量?jī)?yōu)化精度；平均值和標(biāo)準(zhǔn)差可以衡量算法的穩(wěn)定性和魯棒性，平均耗時(shí)則可以反映算法的收斂速度。

實(shí)驗(yàn)環(huán)境：2.30 GHz Intel I5處理器和4 GB內(nèi)存；Python 3.8.0。

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

在DCPSO算法的基礎(chǔ)上，本文進(jìn)一步考慮了算法對(duì)不同類型函數(shù)的優(yōu)化能力。

單峰低維測(cè)試函數(shù)只有一個(gè)全局最優(yōu)且維數(shù)較低，可以測(cè)試算法在簡(jiǎn)單情況下的局部搜索能力和搜索精度。單峰高維測(cè)試函數(shù)只有一個(gè)全局最優(yōu)但維數(shù)高，可以測(cè)試算法在較復(fù)雜情況下的局部搜索能力和搜索精度；多峰低維測(cè)試函數(shù)具有多個(gè)全局最優(yōu)但維數(shù)較低，可以測(cè)試算法在比較復(fù)雜的情況下的全局搜索能力；多峰高維測(cè)試函數(shù)具有多個(gè)全局最優(yōu)且維數(shù)高，可以測(cè)試算法在較復(fù)雜的情況下的局部和全局搜索能力。

PSO、PIO、SSAhe DCPSO算法在4種類型的測(cè)試函數(shù)上經(jīng)過(guò)30次獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果與CDPIO算法實(shí)驗(yàn)結(jié)果如表2～5所示。

表2單峰低維函數(shù)的測(cè)試結(jié)果

Tab.2　Test results of unimodal low-dimensional functions

表3單峰高維函數(shù)的測(cè)試結(jié)果

Tab.3　Test results of unimodal high-dimensional functions

表2中，DCPSO算法無(wú)法找到Easom函數(shù)的全局最優(yōu)解，但對(duì)Matyas函數(shù)的優(yōu)化精度較高，且對(duì)Easom函數(shù)和Matyas函數(shù)都具有較高的魯棒性，它的優(yōu)化耗時(shí)稍長(zhǎng)于其他對(duì)比算法。DCPSO算法在優(yōu)化單峰低維測(cè)試函數(shù)時(shí)是不穩(wěn)定的，有時(shí)DCPSO可以準(zhǔn)確快速地找到全局最優(yōu)解，在搜索精度和穩(wěn)定性上具有相當(dāng)優(yōu)勢(shì)，有時(shí)性能比其他對(duì)比算法差。

表3中，DCPSO可以為Sumsquares函數(shù)和Sphere函數(shù)找到全局最優(yōu)值，與PSO和PIO相比表現(xiàn)優(yōu)秀；并且DCPSO得到的平均值和標(biāo)準(zhǔn)偏差最小，標(biāo)準(zhǔn)偏差為0，這意味著DCPSO在穩(wěn)定性和魯棒性方面表現(xiàn)優(yōu)秀。DCPSO算法在優(yōu)化單峰高維測(cè)試函數(shù)時(shí)能夠準(zhǔn)確找到全局最優(yōu)解，在搜索精度和穩(wěn)定性方面表現(xiàn)優(yōu)秀。

表4中，DCPSO算法可以找到4個(gè)多峰低維測(cè)試函數(shù)的全局最優(yōu)值。特別地，與PSO相比，DCPSO具有較大的優(yōu)勢(shì)。DCPSO與CDPIO算法得到的平均值和標(biāo)準(zhǔn)偏差最小，標(biāo)準(zhǔn)偏差為0，這意味著DCPSO與CDPIO算法在穩(wěn)定性和魯棒性方面優(yōu)于其他對(duì)比算法。

表5中，DCPSO算法可以準(zhǔn)確地找到Rastrigin函數(shù)的全局最優(yōu)值，但是4種算法都不能找到Ackley函數(shù)的全局最優(yōu)值。其中，DCPSO和SSA具有最高的搜索精度，并且DCPSO得到的平均值和標(biāo)準(zhǔn)偏差最小，標(biāo)準(zhǔn)偏差為0，這意味著DCPSO在穩(wěn)定性和魯棒性方面具有絕對(duì)優(yōu)勢(shì)。DCPSO的缺點(diǎn)在處理復(fù)雜函數(shù)時(shí)并不明顯，因?yàn)樗兴惴ǘ夹枰^長(zhǎng)時(shí)間。DCPSO算法在處理多峰高維復(fù)函數(shù)時(shí)，在搜索精度和穩(wěn)定性方面表現(xiàn)優(yōu)秀。

表4多峰低維函數(shù)的測(cè)試結(jié)果

Tab.4　Test results of multimodal low-dimensional functions

表5多峰高維函數(shù)的測(cè)試結(jié)果

Tab.5　Test results of multimodal high-dimensional functions

綜上所述，除處理簡(jiǎn)單的單峰低維函數(shù)情況外，與PSO、PIO、SSA和CDPIO算法相比，DCPSO算法具有高搜索精度和穩(wěn)定性，但在計(jì)算耗時(shí)方面有所犧牲，如在優(yōu)化Rastrigin時(shí)，DCPSO算法相較于PSO算法耗時(shí)增加了約19 s，但總體而言屬于同一數(shù)量級(jí)，可以借助高性能服務(wù)器端彌補(bǔ)耗時(shí)問(wèn)題。對(duì)于全域路徑規(guī)劃，DCPSO算法具有相當(dāng)?shù)膬?yōu)勢(shì)和競(jìng)爭(zhēng)力。

4 在無(wú)人機(jī)集群路徑規(guī)劃中的應(yīng)用

上一章給出了DCPSO與PSO、PIO、SSA、CDPIO算法對(duì)比結(jié)果，結(jié)果表明DCPSO在搜索精度和穩(wěn)定性方面優(yōu)于其他四類算法?；诖?，在無(wú)人機(jī)集群路徑規(guī)劃任務(wù)中優(yōu)選DCPSO進(jìn)行應(yīng)用并仿真展示其效果。

4.1　實(shí)驗(yàn)參數(shù)設(shè)置

相關(guān)仿真實(shí)驗(yàn)參數(shù)在表6中列出。仿真實(shí)驗(yàn)場(chǎng)景如圖5、6所示。圖5中，無(wú)人機(jī)起點(diǎn)、終點(diǎn)和障礙物分別用不同深淺色圓圈標(biāo)注。圖6（a）中，三維圖中的軸數(shù)值大小表示電位場(chǎng)強(qiáng)度的高低，數(shù)值越大，電位場(chǎng)強(qiáng)度越高，圖6（b）中，二維圖中與原點(diǎn)的距離表示電位場(chǎng)強(qiáng)度的高低，即距離原點(diǎn)近表示電位場(chǎng)強(qiáng)度高，距離原點(diǎn)遠(yuǎn)則表示電位場(chǎng)強(qiáng)度低。

表6實(shí)驗(yàn)參數(shù)設(shè)置

Tab.6　Experimental parameter setting

圖5　無(wú)人機(jī)集群、障礙物和軌跡終點(diǎn)分布圖

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

本文在具有挑戰(zhàn)性的環(huán)境中進(jìn)行了一系列實(shí)驗(yàn)，以驗(yàn)證所提出的DCPSO算法在3D環(huán)境下的無(wú)人機(jī)集群路徑規(guī)劃應(yīng)用中的性能。首先利用人工勢(shì)場(chǎng)法對(duì)任務(wù)場(chǎng)景進(jìn)行建模，然后利用滾動(dòng)時(shí)域控制策略不斷更新下一個(gè)最優(yōu)路徑點(diǎn)，最終得到最優(yōu)飛行路徑。實(shí)驗(yàn)中采用蒙特卡羅方法獨(dú)立使用DCPSO算法運(yùn)行30次，獲得軌跡的平均值和標(biāo)準(zhǔn)偏差，進(jìn)一步驗(yàn)證DCPSO算法的穩(wěn)定性和有效性。

圖6　人工勢(shì)場(chǎng)圖

4.2.1可行性

使用DCPSO算法優(yōu)化無(wú)人機(jī)集群路徑規(guī)劃過(guò)程，圖7顯示了一項(xiàng)模擬實(shí)驗(yàn)的結(jié)果。

圖7　DCPSO算法的路徑規(guī)劃

圖8則直觀地展示了DCPSO優(yōu)化后的無(wú)人機(jī)集群路徑規(guī)劃，從中可以看出路徑真實(shí)，無(wú)人機(jī)集群轉(zhuǎn)彎角度不大。更重要的是，規(guī)劃的路徑可以避開(kāi)障礙物，保證無(wú)人機(jī)集群在飛行過(guò)程中不會(huì)撞到障礙物，極大地保證了無(wú)人機(jī)集群在實(shí)際飛行路徑規(guī)劃過(guò)程中的安全。同時(shí)，從圖8中可以看出，DCPSO的整體搜索效率函數(shù)值在初始階段（大約0～8次迭代）迅速下降。然后，隨著迭代次數(shù)的增加，搜索效率函數(shù)的值最終收斂到257.940。

從圖7、8可以看出，DCPSO算法可以使搜索效率函數(shù)快速收斂，縮短無(wú)人機(jī)集群的飛行距離，有效避開(kāi)障礙物，在最短的時(shí)間內(nèi)到達(dá)終點(diǎn)。在收斂速度方面，DCPSO算法是該問(wèn)題的有效優(yōu)化方法。

圖8　DCPSO算法的收斂曲線

4.2.2有效性

為了驗(yàn)證基于DCPSO的無(wú)人機(jī)集群路徑規(guī)劃在復(fù)雜環(huán)境下的有效性，本文在4.2.1節(jié)的基礎(chǔ)上增加了障礙物的數(shù)量。整個(gè)飛行區(qū)域布置了5個(gè)障礙物，坐標(biāo)如下：（35，40，15）、（50，50，15）、（50，35，15）、（60，70，15）和（68，52，15），其他參數(shù)同上。仿真結(jié)果如圖9所示。從圖9可以看出，無(wú)人機(jī)集群在復(fù)雜的環(huán)境中仍然可以使用DCPSO算法準(zhǔn)確地避開(kāi)障礙物并到達(dá)終點(diǎn)。飛行道路平坦，沒(méi)有太大的彎道，短且沒(méi)有長(zhǎng)彎路。

圖9　多障礙環(huán)境下DCPSO算法的路徑規(guī)劃

4.2.3穩(wěn)定性

采用蒙特卡羅方法獨(dú)立運(yùn)行30次，得到可行路徑長(zhǎng)度的平均值和標(biāo)準(zhǔn)差，進(jìn)一步驗(yàn)證DCPSO算法在解決無(wú)人機(jī)集群路徑規(guī)劃中的穩(wěn)定性和有效性。實(shí)驗(yàn)結(jié)果如表7所示。

通過(guò)分析表7中的仿真結(jié)果，經(jīng)DCPSO優(yōu)化的軌道長(zhǎng)度在30次獨(dú)立重復(fù)實(shí)驗(yàn)中的平均值、標(biāo)準(zhǔn)偏差、最優(yōu)值和最差值分別為108.984 6、0.384 1、108.234 5和109.855 8?？梢钥闯?，DCPSO算法優(yōu)化后的無(wú)人機(jī)集群路徑規(guī)劃結(jié)果波動(dòng)小，穩(wěn)定性高，驗(yàn)證了DCPSO算法在實(shí)際應(yīng)用中的穩(wěn)定性和魯棒性。

表7　DCPSO算法進(jìn)行30次獨(dú)立重復(fù)實(shí)驗(yàn)的結(jié)果

5 結(jié)語(yǔ)

針對(duì)PSO局部精度不高、易陷入局部最優(yōu)的問(wèn)題，綜合動(dòng)態(tài)簇機(jī)制和混沌初始化思想，提出一種動(dòng)態(tài)簇粒子群優(yōu)化（DCPSO）算法，并根據(jù)實(shí)際應(yīng)用場(chǎng)景，將DCPSO應(yīng)用于無(wú)人機(jī)集群路徑規(guī)劃問(wèn)題，以提高無(wú)人機(jī)集群的執(zhí)行效率。

與標(biāo)準(zhǔn)的PSO算法相比，DCPSO算法在保留PSO算法原有優(yōu)勢(shì)的基礎(chǔ)上，對(duì)它們?nèi)炙阉髂芰汪敯粜赃M(jìn)行優(yōu)化，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了它是一種很有潛力的群體智能優(yōu)化算法。

在復(fù)雜的三維仿真環(huán)境中，DCPSO算法在無(wú)人機(jī)集群路徑規(guī)劃問(wèn)題上被證明是可行和有效的，進(jìn)一步驗(yàn)證了算法具有很高的適應(yīng)性和穩(wěn)定性。

綜上所述，DCPSO算法具有較大的競(jìng)爭(zhēng)優(yōu)勢(shì)和應(yīng)用前景。未來(lái)，各種應(yīng)用場(chǎng)景將需要無(wú)人機(jī)集群在更復(fù)雜多樣的飛行環(huán)境中運(yùn)行，自適應(yīng)穩(wěn)定的無(wú)人機(jī)集群路徑規(guī)劃是一個(gè)重要的研究方向。

[1] LYU H， YIN Y. Fast path planning for autonomous ships in restricted waters［J］. Applied Sciences， 2018， 8（12）： No.2592.

[2] VOLKAN PEHLIVANOGLU Y. 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.

[3] XUE J， SHEN B. A novel swarm intelligence optimization approach： sparrow search algorithm［J］. Systems Science and Control Engineering， 2020， 8（1）： 22-34.

[4] DUAN H， QIAO P. Pigeon-inspired optimization： a new swarm intelligence optimizer for air robot path planning［J］. International Journal of Intelligent Computing and Cybernetics， 2014， 7（1）： 24-37.

[5] BHARNE P K， GULHANE V S， YEWALE S K. Data clustering algorithms based on swarm intelligence［C］// Proceedings of the 3rd International Conference on Electronics Computer Technology. Piscataway： IEEE， 2011： 407-411.

[6] KENNEDY J， EBERHART R. Particle swarm optimization［C］// Proceedings of the 1995 International Conference on Neural Networks — Volume 4. Piscataway： IEEE， 1995： 1942-1948.

[7] 魯亮亮，代冀陽(yáng)，應(yīng)進(jìn)，等. 基于APSODE-MS算法的無(wú)人機(jī)航跡規(guī)劃［J］. 控制與決策， 2022， 37（7）：1695-1704.（LU L L， DAI J Y， YING J， et al. UAV trajectory planning based on APSODE-MS algorithm［J］. Control and Decision， 2022， 37（7）： 1695-1704.）

[8] NAYEEM G M， FAN M， AKHTER Y. A time-varying adaptive inertia weight based modified PSO algorithm for UAV path planning［C］// Proceedings of the 2nd International Conference on Robotics， Electrical and Signal Processing Techniques. Piscataway： IEEE， 2021： 573-576.

[9] LI X， ZHAO Y， ZHANG J， et al. A hybrid PSO algorithm based flight path optimization for multiple agricultural UAVs［C］// Proceedings of the IEEE 28th International Conference on Tools with Artificial Intelligence. Piscataway： IEEE， 2016： 691-697.

[10] 田興華，張紀(jì)會(huì)，李陽(yáng). 基于混沌映射的自適應(yīng)退火型粒子群算法［J］. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)， 2020， 17（1）：45-54.（TIAN X H， ZHANG J H， LI Y. An adaptive annealing particle swarm optimization based on chaotic mapping ［J］. Complex Systems and Complexity Science， 2020， 17（1）： 45-54.）

[11] ZHANG R， SUN M， PAN C. Micro-nano satellite resource allocation algorithm based on chaos-filled PSO ［C］// Proceedings of the 6th International Symposium on Computer and Information Processing Technology. Piscataway： IEEE， 2021： 204-208.

[12] KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots ［J］. The International Journal of Robotics Research， 1986， 5（1）： 90-98.

[13] 段海濱，楊之元. 基于柯西變異鴿群優(yōu)化的大型民用飛機(jī)滾動(dòng)時(shí)域控制［J］. 中國(guó)科學(xué)：技術(shù)科學(xué)， 2018， 48（3）：277-288.（DUAN H B， ZHANG Z Y. Large civil aircraft receding horizon control based on Cauthy mutation pigeon inspired optimization ［J］. SCIENTIA SINICA Technologica， 2018， 48（3）： 277-288.）

[14] LIANG X， WANG D， HUANG M. Improved grey wolf optimizer and their applications［C］// Proceedings of the IEEE 7th International Conference on Computer Science and Network Technology. Piscataway： IEEE， 2019： 107-110.

[15] XU S， XU D， MAO Y， et al. A cooperative dynamic cluster in multitasking mobile networks ［J］. Intelligent Automation and Soft Computing， 2017， 23（4）： 567-572.

[16] LI L， XU S， NIE H， et al. Collaborative target search algorithm for UAV based on chaotic disturbance pigeon-inspired optimization［J］. Applied Sciences， 2021， 11（16）： No.7358.

Route planning method of UAV swarm based on dynamic cluster particle swarm optimization

WANG Longbao1，2， LUAN Yinqi1， XU Liang3， ZENG Xin3， ZHANG Shuai4， XU Shufang1，2*

（1，，211100，；2（），211100，；3，430014，；4，650051，）

Route planning is very important for the task execution of Unmanned Aerial Vehicle （UAV） swarm， and the computation is usually complex in high dimensional scenarios. Swarm intelligence has provided a good solution for this problem. Particle Swarm Optimization （PSO） algorithm is especially suitable for route planning problem because of its advantages such as few parameters， fast convergence and simple operation. However， PSO algorithm has poor global search ability and is easy to fall into local optimum when applied to route planning. In order to solve the problems above and improve the effect of UAV swarm route planning， a Dynamic Cluster Particle Swarm Optimization （DCPSO） algorithm was proposed.Firstly， artificial potential field method and receding horizon control principle were used to model the task scenario of route planning problem of UAV swarm. Secondly， Tent chaotic map and dynamic cluster mechanism were introduced to further improve the global search ability and search accuracy. Finally， DCPSO algorithm was used to optimize the objective function of the model to obtain each trajectory point selection of UAV swarm. On 10 benchmark functions with different combinations of unimodal/multimodal and low-dimension/high-dimension， simulation experiments were carried out. The results show that compared with PSO algorithm， Pigeon-Inspired Optimization （PIO）， Sparrow Search Algorithm （SSA） and Chaotic Disturbance Pigeon-Inspired Optimization （CDPIO） algorithm， DCPSO algorithm has better optimal value， mean value and variance， better search accuracy and stronger stability. Besides， the performance and effect of DCPSO algorithm were demonstrated in the route planning application instances of UAV swarm simulation experiments.

Particle Swarm Optimization (PSO); dynamic cluster mechanism; Unmanned Aerial Vehicle (UAV) swarm; route planning; receding horizon control

This work is partially supported by Major Science and Technology Special Program of Yunnan Province Science and Technology Department （202202AF080003）， Scientific Research Project of Yangtze Ecology and Environment Company Limited （HBZB2022005）.

WANG Longbao， born in 1977， Ph. D.， senior engineer. His research interests include domain software， intelligent computing.

LUAN Yinqi， born in 2000， M. S. candidate. Her research interests include intelligent computing.

XU Liang， born in 1980， senior engineer. His research interests include construction management of ecological and environmental protection projects.

ZENG Xin， born in 1990， engineer. His research interests include construction and management of ecological and environmental protection projects.

ZHANG Shuai， born in 1988， senior engineer. His research interests include information fusion.

XU Shufang， born in 1981， Ph. D.， associate professor. Her research interests include wireless communication network， information fusion.

TP391.9

A

1001-9081（2023）12-3816-08

10.11772/j.issn.1001-9081.2022111763

2022?11?28；

2023?03?26；

2023?03?30。

云南省科技廳重大科技專項(xiàng)計(jì)劃項(xiàng)目（202202AF080003）；長(zhǎng)江生態(tài)環(huán)保集團(tuán)有限公司科研項(xiàng)目（HBZB2022005）。

王龍寶（1977—），男，江蘇鹽城人，高級(jí)工程師，博士，CCF會(huì)員，主要研究方向：領(lǐng)域軟件、智能計(jì)算；欒茵琪（2000—），女，山東菏澤人，碩士研究生，主要研究方向：智能計(jì)算；徐亮（1980—），男，江西九江人，高級(jí)工程師，主要研究方向：生態(tài)環(huán)保工程建設(shè)管理；曾昕（1990—），男，湖北十堰人，工程師，主要研究方向：生態(tài)環(huán)保工程建設(shè)管理；張帥（1988—），男，云南昆明人，高級(jí)工程師，主要研究方向：信息融合；徐淑芳（1981—），女，安徽青陽(yáng)人，副教授，博士，主要研究方向：無(wú)線通信網(wǎng)絡(luò)、信息融合。