基于離散粒子群算法的多飛行器在軌服務(wù)任務(wù)分配

張琪新 孫富春 許斌 劉華平

（1海軍航空工程學(xué)院，煙臺264001）

（2清華大學(xué)，北京100084） （3智能技術(shù)與系統(tǒng)國家重點實驗室，北京100084）

1 引言

飛行器在軌服務(wù)（On-orbit Service，OOS）是指在空間通過人、機(jī)器人或兩者協(xié)同完成涉及延長各種飛行器壽命、提升執(zhí)行任務(wù)能力的一類空間操作[1-2]。

目前，國內(nèi)外對在軌服務(wù)任務(wù)分配已開展了相關(guān)的研究，但針對服務(wù)飛行器的協(xié)同任務(wù)分配研究較少。文獻(xiàn)[3]對圓軌道上一顆服務(wù)飛行器執(zhí)行多項任務(wù)的在軌服務(wù)規(guī)劃問題進(jìn)行了研究，但沒有考慮服務(wù)飛行器的服務(wù)時間；文獻(xiàn)[4]對同步軌道上一顆服務(wù)飛行器執(zhí)行多項任務(wù)的最優(yōu)服務(wù)策略進(jìn)行了研究，但不能夠解決協(xié)同多個服務(wù)飛行器之間的問題；文獻(xiàn)[5]建立了雙沖量遠(yuǎn)程交會的能量時間模型，但僅考慮飛行器能量消耗和時間兩項因素，討論也僅限于單個飛行器；文獻(xiàn)[6]采用整數(shù)規(guī)劃方法通過設(shè)計決策變量和形式化各種約束，較好地解決了任務(wù)指派問題，但是并沒有綜合考慮飛行器在整個服務(wù)過程中自身的損耗；文獻(xiàn)[7]以對目標(biāo)的毀傷最大和自身消耗最小為任務(wù)分配的目標(biāo)函數(shù)，但沒有考慮執(zhí)行任務(wù)的消耗時間這一重要因素，而完成任務(wù)的時間是反映效能的關(guān)鍵指標(biāo)之一。文獻(xiàn)[8]針對分布式協(xié)同控制，采用基于投標(biāo)、競標(biāo)等市場機(jī)制的合同網(wǎng)方法，協(xié)調(diào)多個飛行器間的任務(wù)，具有通信量少、魯棒性能好等優(yōu)點，但各飛行器對自身收益和代價的評價局限于任務(wù)的平衡，沒有考慮到自身指標(biāo)。使用線性規(guī)劃、動態(tài)網(wǎng)絡(luò)流等方法對多任務(wù)分配問題進(jìn)行建模[9-11]，雖然這些模型簡單、易于實現(xiàn)，但目標(biāo)函數(shù)過于簡單，不能完全描述關(guān)鍵指標(biāo)。服務(wù)飛行器協(xié)同任務(wù)分配中，各飛行器的控制必須相互協(xié)調(diào)，采用基于動力學(xué)方法建立雙脈沖優(yōu)化制導(dǎo)模型，綜合考慮飛行器消耗、提供服務(wù)所獲收益最大、軌道轉(zhuǎn)移所需能量以及消耗時間關(guān)鍵指標(biāo)，協(xié)同多飛行器進(jìn)行任務(wù)分配。

本文針對在軌服務(wù)飛行器任務(wù)分配問題的特點，設(shè)計了新的離散粒子群位置與速度更新公式，提出了一種新的在多約束條件下，基于離散粒子群算法的多服務(wù)飛行器目標(biāo)分配方法。

2 任務(wù)分配模型

2.1 任務(wù)場景

空間在軌服務(wù)飛行器得到指令后，需要從準(zhǔn)備軌道轉(zhuǎn)移至靠近目標(biāo)衛(wèi)星的服務(wù)軌道。其中，服務(wù)飛行器是主動的，而需要服務(wù)的目標(biāo)飛行器是被動的，軌道轉(zhuǎn)移過程可用圖1簡單描述。服務(wù)飛行器運行在低軌道上，在綜合考慮自身性能和周圍環(huán)境等約束條件下，根據(jù)任務(wù)分配的結(jié)果合理地實施Lambert雙脈沖軌道轉(zhuǎn)移至目標(biāo)衛(wèi)星的高軌道上，在交會初始時刻施加第一次脈沖，在靠近目標(biāo)衛(wèi)星施加第二次脈沖，單圈Lambert變軌示意圖見圖2。在整個在軌服務(wù)任務(wù)過程中，服務(wù)飛行器始終保持在目標(biāo)衛(wèi)星的軌道上。

圖1 空間在軌服務(wù)示意Fig.1 Space on-orbit servicing

圖2 單圈Lambert變軌示意Fig.2 Lap Lambert maneuver

2.2 數(shù)學(xué)模型

（1）決策變量

設(shè)有U顆在軌部署的服務(wù)飛行器，在某刻有T顆具有不同任務(wù)優(yōu)先級的目標(biāo)飛行器等待服務(wù)，根據(jù)該規(guī)劃問題的特點，決策變量可以定義為

式中u＝1，2，…，U；t＝1，2，…，T。

服務(wù)飛行器目標(biāo)分配是以整個編隊的整體收益最優(yōu)作為目標(biāo)的，而目標(biāo)飛行器價值、服務(wù)飛行器消耗以及能量時間消耗是評價效能主要指標(biāo)[12-13]。

（2）飛行器消耗最小指標(biāo)

執(zhí)行任務(wù)往往在規(guī)定的時間內(nèi)，選擇最容易服務(wù)的飛行器，設(shè)計相應(yīng)的軌道，從而達(dá)到降低飛行器損耗的目的。設(shè)aut為服務(wù)飛行器對目標(biāo)飛行器服務(wù)后的消耗，如可能出現(xiàn)的部件失效、軟硬件故障以及零部件的磨損。對服務(wù)飛行器進(jìn)行任務(wù)分配，使得所有服務(wù)飛行器消耗之和最小，即

（3）目標(biāo)飛行器價值收益最大指標(biāo)

目標(biāo)價值收益最大指標(biāo)通過對服務(wù)飛行器執(zhí)行任務(wù)時所獲取目標(biāo)價值的評估，來引導(dǎo)目標(biāo)分配的優(yōu)化和決策向著服務(wù)效能最大化的方向進(jìn)行。該指標(biāo)使服務(wù)飛行器趨向于服務(wù)最優(yōu)價值的目標(biāo)。綜合考慮目標(biāo)價值V、確認(rèn)概率Pc、剩余服務(wù)能力1-aut，則服務(wù)飛行器U服務(wù)目標(biāo)飛行器T時，收益為Vut＝V·Pc·（1-aut）。其中，Pc表示服務(wù)飛行器準(zhǔn)確到達(dá)任務(wù)區(qū)域、發(fā)現(xiàn)目標(biāo)并且正確識別出目標(biāo)的概率，為每個服務(wù)飛行器分配任務(wù)，使得總的收益最大，即

（4）能量時間最優(yōu)模型

在得到既定任務(wù)后需要對在軌服務(wù)飛行器進(jìn)行軌道機(jī)動，自主、快速、精確和大范圍軌道機(jī)動技術(shù)為各種應(yīng)用提供了可靠的保證。遠(yuǎn)程導(dǎo)引變軌在整個任務(wù)分配活動中起著非常重要的作用，合理的導(dǎo)引變軌還能夠節(jié)省能量以及所需時間。同時考慮燃料消耗和轉(zhuǎn)移時間，建立性能指標(biāo)，使得能量時間消耗最小，即

式中 Δv1為交會初始時刻所需的速度增量；Δv2為交會末時刻所需的速度增量；t為交會變軌所要求的時間；0≤k≤1為比例系數(shù)。根據(jù)交會變軌時間t就能求出Lambert雙脈沖變軌所需的能量消耗，尋找最佳交會時間，使得變軌能量消耗也最小。

（5）約束條件

服務(wù)飛行器任務(wù)分配應(yīng)滿足以下約束條件：

2）對于每個目標(biāo)，無論采取什么方式的服務(wù)，對目標(biāo)價值收益不大于該目標(biāo)的自身價值：

3）Δv1＋Δv2≤Δv，Δv表示服務(wù)飛行器所能提供的速度增量，即服務(wù)飛行器執(zhí)行任務(wù)需要的速度增量必須小于其所能提供的速度增量。

綜上所述，服務(wù)飛行器任務(wù)分配的性能指標(biāo)函數(shù)可以表示為

式中ω1、ω2、ω3為權(quán)系數(shù)，反映了每個子目標(biāo)的重要程度。

任務(wù)分配問題的特點是隨著問題規(guī)模的增大，決策變量的個數(shù)和決策向量的維數(shù)將大為增加，難點是怎樣在滿足各種約束條件的基礎(chǔ)上，綜合考慮各項指標(biāo)組成的目標(biāo)最優(yōu)值，若仍用傳統(tǒng)的最優(yōu)算法求解這個組合優(yōu)化問題時，計算量將非常大，從而導(dǎo)致求解困難，甚至無法求解。針對這一情況以及服務(wù)飛行器協(xié)同目標(biāo)分配問題特點，設(shè)計了一種新的離散粒子群目標(biāo)分配算法。

3 離散粒子群算法

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是Kennedy和Eberhart于1995年提出的，有著個體數(shù)目少、計算簡單、魯棒性好等優(yōu)點。PSO算法中，每個粒子就是一個備選解，多個粒子共存、合作尋優(yōu)。每個粒子根據(jù)自身和粒子群的經(jīng)驗，在問題空間中向更好的位置 “飛行”，搜索最優(yōu)解。粒子本身找到的最優(yōu)解稱為個體最優(yōu)值pbest，就是每個粒子在飛行過程所經(jīng)歷過的最優(yōu)位置。整個群體目前找到的最優(yōu)解稱為全局最優(yōu)值gbest，就是整個群體所經(jīng)歷過的最優(yōu)位置[14-16]。由于標(biāo)準(zhǔn)的粒子群算法具有連續(xù)本質(zhì)，不太適宜于求解離散問題。為了將其用于服務(wù)飛行器協(xié)同目標(biāo)分配問題的求解，根據(jù)該問題的特點，在分析多約束基礎(chǔ)上，設(shè)計了自然數(shù)編碼的離散粒子群算法，建立了粒子與實際問題的對應(yīng)關(guān)系，并且對標(biāo)準(zhǔn)粒子群算法作了相應(yīng)的改進(jìn)[17]。

3.1 離散粒子群編碼方式

服務(wù)飛行器協(xié)同目標(biāo)分配的決策關(guān)鍵在于確定任務(wù)目標(biāo)由哪個飛行器來執(zhí)行。因此，這里采用自然數(shù)編碼方式來表達(dá)，每個粒子長度等于目標(biāo)總數(shù)，粒子由按目標(biāo)編號順序排列的服務(wù)飛行器分配編號組成，表示一種可能的分配方案。例如，目標(biāo)飛行器數(shù)目n取3，目標(biāo)數(shù)目m取4，如圖3所示，表示第2個服務(wù)飛行器服務(wù)第1個目標(biāo)，第3

個服務(wù)飛行器服務(wù)第2個目標(biāo)，第1個服務(wù)飛行器同時對第3個目標(biāo)和第4個目標(biāo)進(jìn)行服務(wù)。保證約束條件中對每一個目標(biāo)必須分配一個服務(wù)飛行器的限制，單位粒子取值范圍為[1，n]。

圖3 粒子編碼Fig.3 Particle code

3.2 離散粒子群算法的位置和速度更新公式

粒子的新位置是粒子的速度、個體極值和全局極值相互作用的結(jié)果。根據(jù)服務(wù)飛行器協(xié)同目標(biāo)分配問題的實際特點，對粒子群算法的位置和速度更新公式進(jìn)行重新定義，即

式中Xi＝（xi1，xi2，…，xim）為粒子i在迭代中的位置；pi＝（pi1，pi2，…，pim）為粒子i的個體極值；pg＝（pg1，pg2，…，pgm）為全局極值；ω為慣性權(quán)重；c1是認(rèn)知系數(shù)，調(diào)節(jié)向pi的飛行步長；c2是社會系數(shù)，調(diào)節(jié)向pg的飛行步長。F1[Xi（t）]是關(guān)于粒子Xi（t）的函數(shù)，其作用是考慮粒子本 身 速 度 對 其 位 置 變 化 的 影 響；F2[Xi（t），pi（t）]為Xi（t） 對pi（t） 的 學(xué) 習(xí) 操 作；F3[Xi（t），pg（t）]為Xi（t）對pg（t）的學(xué)習(xí)操作。位置更新公式由三部分構(gòu)成，設(shè)Ψi為臨時變量：

這是粒子的“慣性”部分，表示粒子對自身飛行速度的思考。其中ω?F1[Xi（t）]表示粒子的速度，即為一個概率為ω的目標(biāo)置換操作，它的實現(xiàn)方法為：由rand（）產(chǎn)生一個區(qū)間[0，1]上的隨機(jī)數(shù)r，如果r＜ω，將對粒子進(jìn)行置換操作Ψi（t）＝F1[Xi（t）]，即產(chǎn)生兩個在 [1，m]之間不同的隨機(jī)數(shù)a和b，然后將粒子位置矢量的第a個數(shù)值與第b個數(shù)值互換，也就是將服務(wù)第a個目標(biāo)的服務(wù)飛行器與服務(wù)第b個目標(biāo)的服務(wù)飛行器進(jìn)行互換，如圖4所示；如果r≥ω，則Ψi（t）＝Xi（t）。

圖4 目標(biāo)置換操作Fig.4 Target replacement

離散粒子群算法的流程圖如圖5所示。

圖5 離散粒子群算法流程Fig.5 Flow chart of DPSO

4 仿真試驗

假設(shè)在同一軌道上部署了5個服務(wù)飛行器，它們具有不同的服務(wù)和機(jī)動能力，但一個飛行器只能對一顆目標(biāo)飛行器提供在軌服務(wù)?，F(xiàn)有處于不同軌道上的目標(biāo)飛行器，要求在規(guī)定的交會時間內(nèi)完成對目標(biāo)飛行器的在軌服務(wù)，使整體效能達(dá)到最佳。算例1和算例2的初始軌道要素如表1和表2所示。

兩種算例的時間約束為50min，任務(wù)要求準(zhǔn)時與目標(biāo)飛行器交會，實施在軌服務(wù)。

服務(wù)飛行器實施遠(yuǎn)程軌道機(jī)動的交會時間設(shè)定在1 000～3 000s之間，通過搜索某一時刻對應(yīng)速度增量，能夠找出最小能量消耗，將其代入任務(wù)分配模型中，結(jié)合假設(shè)求解如下兩種算例。

（1）5個服務(wù)飛行器對3個目標(biāo)飛行器服務(wù)

假設(shè)有5個服務(wù)飛行器和3個目標(biāo)飛行器，pc＝1。為便于與文獻(xiàn)[18]中的模型和算法相比較，目標(biāo)的價值、剩余服務(wù)能力都采用文獻(xiàn)[18]中的數(shù)據(jù)，如表3所示（剩余服務(wù)能力和目標(biāo)價值均是根據(jù)飛行器軌道參數(shù)進(jìn)行的假設(shè)）。

在算例中，分別采用遺傳算法和離散粒子群算法對上述問題進(jìn)行仿真，并將迭代30次后兩種算法的最優(yōu)、平均、最差解進(jìn)行了對比，得出最終的服務(wù)飛行器任務(wù)分配的結(jié)果如表4所示。通過表4的數(shù)據(jù)可以知道，在服務(wù)飛行器和目標(biāo)飛行器規(guī)模不大的情況下，兩種算法得到的最優(yōu)解和任務(wù)分配的結(jié)果是一致的，最優(yōu)方案及對應(yīng)時間的最小速度增量如表5所示。在小規(guī)模的任務(wù)分配中，雖也能夠得到最優(yōu)的分配結(jié)果，但兩種算法的優(yōu)劣性差別不大。后面大規(guī)模任務(wù)分配算例中，將會體現(xiàn)出離散粒子群算法的優(yōu)越性。

表1 算例1服務(wù)飛行器和目標(biāo)飛行器初始軌道要素Tab.1 Initial orbital elements in example 1

表2 算例2服務(wù)飛行器和目標(biāo)飛行器初始軌道要素Tab.2 Initial orbital elements in example 2

表3 服務(wù)器剩余服務(wù)能力和目標(biāo)價值Tab.3 Surplus capacity and target value in spacecrafts

表4 兩種算法的性能比較Tab.4 Performance comparison of two algorithms

表5 仿真結(jié)果Tab.5 The simulation results

（2）5個服務(wù)飛行器對10個目標(biāo)飛行器服務(wù)

假設(shè)有5個服務(wù)飛行器和10個目標(biāo)衛(wèi)星，pc＝1。為便于與文獻(xiàn)[19]中的模型和算法相比較，目標(biāo)的價值、剩余服務(wù)能力都采用文獻(xiàn)[19]中的數(shù)據(jù)。

在算例中，兩種算法在迭代30次過程中的最優(yōu)、平均、最差解的變化曲線及比較結(jié)果如圖6～圖8和表6所示。大規(guī)模的任務(wù)分配能夠體現(xiàn)出兩種算法的差異：從圖8中可以看出，離散粒子群算法比遺傳算法收斂特性要好，能夠比較快速地找到最優(yōu)解，而且在離散粒子群平均解的變化曲線也可以看出，即使在迭代的后期，也不會出現(xiàn)粒子趨同的現(xiàn)象，說明該算法具有較強的尋優(yōu)能力。

圖6 遺傳算法收斂曲線Fig.6 GA convergence curve

圖7 離散粒子群算法收斂曲線Fig.7 DPSO convergence curve

圖8 兩種算法性能比較Fig.8 Performance comparison of two algorithms

表6 不同迭代次數(shù)下兩種算法性能比較Tab.6 Performance Comparison of Two Algorithms under different iteration

由計算結(jié)果可知，該任務(wù)分配方案可使服務(wù)飛行器在指定的任務(wù)完成時間內(nèi)，以最大的效益完成服務(wù)任務(wù)，且滿足各項約束條件，保證了軌道機(jī)動過程中能量消耗最少，從而較好地解決了在軌服務(wù)任務(wù)分配問題。

5 結(jié)束語

本文根據(jù)在軌服務(wù)飛行器協(xié)同任務(wù)分配問題的特點，設(shè)計了新的離散粒子群位置與速度更新公式，提出了一種基于離散粒子群算法的多服務(wù)飛行器目標(biāo)分配方法。仿真結(jié)果表明，改進(jìn)的粒子群算法能夠快速穩(wěn)定地找到最優(yōu)分配方案，有效地解決多約束條件下的服務(wù)飛行器任務(wù)分配問題。在本文的靜態(tài)研究基礎(chǔ)上可以進(jìn)一步分析任務(wù)狀態(tài)變化的情況，以及這些變化過程中的不確定性，另外，還可以考慮當(dāng)服務(wù)飛行器所帶燃料有限時如何進(jìn)行任務(wù)分配的問題。本文的研究工作為研究動態(tài)分配問題提供了較好的基礎(chǔ)。

[1]DONALD M WALTZ.On-orbit servicing of space system [M].Krieger Publishing Company，Malabar，F(xiàn)lorida，1993.

[2]崔乃剛，王平，郭繼峰，等.空間在軌服務(wù)技術(shù)發(fā)展綜述 [J].宇航學(xué)報，2007，28（4）：33-39.CUI NAIGANG，WANG PING，GUO JIFENG，et al.A review of on-orbit servicing [J].Journal of Astronautics，2007，28（4）：33-39.

[3]SHEN HAIJUN.Optimal scheduling for satellite refuelling in circular orbits [D].Georgia：Georgia Institute of Technology，2003.

[4]CHENG CHEUGCHUUG，SMITHSF.Appling constraint satisfaction techniques to job shop scheduling[R].Pittsburgh：Carnegie Mellon University，1995.

[5]HU LAIHONG，SUN FUCHUN，XU BIN，et al.On-orbit long-range maneuver transfer via EDAs[C].IEEE World Congress on Computational Intelligence，2008：2343-2347.

[6]任仙海，楊樂平，朱彥偉.基于整數(shù)規(guī)劃的在軌服務(wù)任務(wù)指派問題研究 [J].裝備指揮技術(shù)學(xué)院學(xué)報，2008，19（2）：52-56.REN XIANHAI，YANG LEPING，ZHU YANWEI.Research on the on-orbit servicing mission assignment based on integer programming [J].Journal of the Academy of Equipment Command and Technology，2008，19（2）：52-56.

[7]CURZJ B，JR C，CHEN G.Particle swarm optimization for resource allocation in UAV cooperative control[C].AIAA Guidance，Navigation，and Control Conference，Rhode Island，2004：16-19.

[8]LEMAIRE T，ALAMI R，LACROIX S.A distributed tasks allocation scheme in multi-UAV context[C].2004IEEE International Lonference on Robotics and Automation，2004：3622-3627.

[9]SPENCER D B，KIN Y H.Optimal spacecraft rendezvous using genetic algorithm [J].Journal of Spacecraft and Rockets，2002，39（6）：859-865.

[10]NYGARD K E，CHANDLER P R，PACHTER M.Dynamic network optimization models for air vehicle resource allocation[C].American Control Conference，Arlington，VA，2001：1853-1858.

[11]霍霄華，陳巖，朱華勇，等.多UCAV協(xié)同控制中的任務(wù)分配模型及算法 [J].國防科技大學(xué)學(xué)報，2006，28（3）：83-88.HUO XIAOHUA，CHEN YAN，ZHU HUAYONG，et al.Study on task allocation model and algorithm for multi-UCAV cooperative control[J].Journal of National University of Defense Technology，2006，28（3）：83-88.

[12]FAN CHUNXIA，WAN YOUHONG.An adaptive simple particle swarm optimization algorithm [C].Control and Decision Conference，2008：3067-3072.

[13]PAN Q K，TASGETIREN M F，LIANG Y C.A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem with makespan criterion [C]／／ Proceeding of the Int Workshop，UK Planning and Scheduling Special Interest Group，2005：31-41.

[14]VENTER G.Particle swarm optimization [C].43rd AIAA／ASME／ASCE／AHS／ASC Structures，Structural Dynamics，and Materials Conference，Denver，2002.

[15]BERGH F，ENGELBRECH A P.A cooperative approach to particle swarm optimization[J].IEEE Transactions on Evolutionary Computation，2004，8 （3）：255-239.

[16]JI C L，YUAN P.Particle swarm optimization for mobile Ad Hoc networks clustering [C].Proc.2004 IEEE International Conference on Networking，Sensing＆Control，Taipei，Taiwan，2004（3）：225-239.

[17]葉文，朱愛紅，潘長鵬，等.多UCAV協(xié)同目標(biāo)分配算法研究[J].系統(tǒng)工程與電子技術(shù)，2010，32（1）：104-108.YE WEN，ZHU AIHONG，PAN CHANGPENG，et al.Cooperation mission assignment algorithm for multi-UCAV[J].Systems Engineering and Electronics.2010，32（1）：104-108.

[18]CURZ J B，JR C，CHEN G.Particle swarm optimization for resource allocation in UAV cooperative control[C].AIAA Guidance，Navigation，and Control Conference and Exhibit，Rhode Island，2004：16-19.

[19]雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用 [M].西安：西安電子科技大學(xué)出版社，2005：128-130.