張琪新 孫富春 許斌 劉華平

（1海軍航空工程學院，煙臺264001）

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

1 引言

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

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

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

2 任務分配模型

2.1 任務場景

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

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

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

2.2 數(shù)學模型

（1）決策變量

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

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

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

（2）飛行器消耗最小指標

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

（3）目標飛行器價值收益最大指標

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

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

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

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

（5）約束條件

服務飛行器任務分配應滿足以下約束條件：

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

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

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

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

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

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]。由于標準的粒子群算法具有連續(xù)本質(zhì)，不太適宜于求解離散問題。為了將其用于服務飛行器協(xié)同目標分配問題的求解，根據(jù)該問題的特點，在分析多約束基礎上，設計了自然數(shù)編碼的離散粒子群算法，建立了粒子與實際問題的對應關系，并且對標準粒子群算法作了相應的改進[17]。

3.1 離散粒子群編碼方式

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

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

圖3 粒子編碼Fig.3 Particle code

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

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

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

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

圖4 目標置換操作Fig.4 Target replacement

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

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

4 仿真試驗

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

兩種算例的時間約束為50min，任務要求準時與目標飛行器交會，實施在軌服務。

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

（1）5個服務飛行器對3個目標飛行器服務

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

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

表1 算例1服務飛行器和目標飛行器初始軌道要素Tab.1 Initial orbital elements in example 1

表2 算例2服務飛行器和目標飛行器初始軌道要素Tab.2 Initial orbital elements in example 2

表3 服務器剩余服務能力和目標價值Tab.3 Surplus capacity and target value in spacecrafts

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

表5 仿真結果Tab.5 The simulation results

（2）5個服務飛行器對10個目標飛行器服務

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

在算例中，兩種算法在迭代30次過程中的最優(yōu)、平均、最差解的變化曲線及比較結果如圖6～圖8和表6所示。大規(guī)模的任務分配能夠體現(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

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

5 結束語

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

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

[2]崔乃剛，王平，郭繼峰，等.空間在軌服務技術發(fā)展綜述 [J].宇航學報，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ī)劃的在軌服務任務指派問題研究 [J].裝備指揮技術學院學報，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é)同控制中的任務分配模型及算法 [J].國防科技大學學報，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é)同目標分配算法研究[J].系統(tǒng)工程與電子技術，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遺傳算法工具箱及應用 [M].西安：西安電子科技大學出版社，2005：128-130.