張琪新 孫富春 許斌 劉華平
(1海軍航空工程學(xué)院,煙臺(tái)264001)
(2清華大學(xué),北京100084) (3智能技術(shù)與系統(tǒng)國家重點(diǎn)實(shí)驗(yàn)室,北京100084)
飛行器在軌服務(wù)(On-orbit Service,OOS)是指在空間通過人、機(jī)器人或兩者協(xié)同完成涉及延長各種飛行器壽命、提升執(zhí)行任務(wù)能力的一類空間操作[1-2]。
目前,國內(nèi)外對(duì)在軌服務(wù)任務(wù)分配已開展了相關(guān)的研究,但針對(duì)服務(wù)飛行器的協(xié)同任務(wù)分配研究較少。文獻(xiàn)[3]對(duì)圓軌道上一顆服務(wù)飛行器執(zhí)行多項(xiàng)任務(wù)的在軌服務(wù)規(guī)劃問題進(jìn)行了研究,但沒有考慮服務(wù)飛行器的服務(wù)時(shí)間;文獻(xiàn)[4]對(duì)同步軌道上一顆服務(wù)飛行器執(zhí)行多項(xiàng)任務(wù)的最優(yōu)服務(wù)策略進(jìn)行了研究,但不能夠解決協(xié)同多個(gè)服務(wù)飛行器之間的問題;文獻(xiàn)[5]建立了雙沖量遠(yuǎn)程交會(huì)的能量時(shí)間模型,但僅考慮飛行器能量消耗和時(shí)間兩項(xiàng)因素,討論也僅限于單個(gè)飛行器;文獻(xiàn)[6]采用整數(shù)規(guī)劃方法通過設(shè)計(jì)決策變量和形式化各種約束,較好地解決了任務(wù)指派問題,但是并沒有綜合考慮飛行器在整個(gè)服務(wù)過程中自身的損耗;文獻(xiàn)[7]以對(duì)目標(biāo)的毀傷最大和自身消耗最小為任務(wù)分配的目標(biāo)函數(shù),但沒有考慮執(zhí)行任務(wù)的消耗時(shí)間這一重要因素,而完成任務(wù)的時(shí)間是反映效能的關(guān)鍵指標(biāo)之一。文獻(xiàn)[8]針對(duì)分布式協(xié)同控制,采用基于投標(biāo)、競標(biāo)等市場機(jī)制的合同網(wǎng)方法,協(xié)調(diào)多個(gè)飛行器間的任務(wù),具有通信量少、魯棒性能好等優(yōu)點(diǎn),但各飛行器對(duì)自身收益和代價(jià)的評(píng)價(jià)局限于任務(wù)的平衡,沒有考慮到自身指標(biāo)。使用線性規(guī)劃、動(dòng)態(tài)網(wǎng)絡(luò)流等方法對(duì)多任務(wù)分配問題進(jìn)行建模[9-11],雖然這些模型簡單、易于實(shí)現(xiàn),但目標(biāo)函數(shù)過于簡單,不能完全描述關(guān)鍵指標(biāo)。服務(wù)飛行器協(xié)同任務(wù)分配中,各飛行器的控制必須相互協(xié)調(diào),采用基于動(dòng)力學(xué)方法建立雙脈沖優(yōu)化制導(dǎo)模型,綜合考慮飛行器消耗、提供服務(wù)所獲收益最大、軌道轉(zhuǎn)移所需能量以及消耗時(shí)間關(guān)鍵指標(biāo),協(xié)同多飛行器進(jìn)行任務(wù)分配。
本文針對(duì)在軌服務(wù)飛行器任務(wù)分配問題的特點(diǎn),設(shè)計(jì)了新的離散粒子群位置與速度更新公式,提出了一種新的在多約束條件下,基于離散粒子群算法的多服務(wù)飛行器目標(biāo)分配方法。
空間在軌服務(wù)飛行器得到指令后,需要從準(zhǔn)備軌道轉(zhuǎn)移至靠近目標(biāo)衛(wèi)星的服務(wù)軌道。其中,服務(wù)飛行器是主動(dòng)的,而需要服務(wù)的目標(biāo)飛行器是被動(dòng)的,軌道轉(zhuǎn)移過程可用圖1簡單描述。服務(wù)飛行器運(yùn)行在低軌道上,在綜合考慮自身性能和周圍環(huán)境等約束條件下,根據(jù)任務(wù)分配的結(jié)果合理地實(shí)施Lambert雙脈沖軌道轉(zhuǎn)移至目標(biāo)衛(wèi)星的高軌道上,在交會(huì)初始時(shí)刻施加第一次脈沖,在靠近目標(biāo)衛(wèi)星施加第二次脈沖,單圈Lambert變軌示意圖見圖2。在整個(gè)在軌服務(wù)任務(wù)過程中,服務(wù)飛行器始終保持在目標(biāo)衛(wèi)星的軌道上。
圖1 空間在軌服務(wù)示意Fig.1 Space on-orbit servicing
圖2 單圈Lambert變軌示意Fig.2 Lap Lambert maneuver
(1)決策變量
設(shè)有U顆在軌部署的服務(wù)飛行器,在某刻有T顆具有不同任務(wù)優(yōu)先級(jí)的目標(biāo)飛行器等待服務(wù),根據(jù)該規(guī)劃問題的特點(diǎn),決策變量可以定義為
式中u=1,2,…,U;t=1,2,…,T。
服務(wù)飛行器目標(biāo)分配是以整個(gè)編隊(duì)的整體收益最優(yōu)作為目標(biāo)的,而目標(biāo)飛行器價(jià)值、服務(wù)飛行器消耗以及能量時(shí)間消耗是評(píng)價(jià)效能主要指標(biāo)[12-13]。
(2)飛行器消耗最小指標(biāo)
執(zhí)行任務(wù)往往在規(guī)定的時(shí)間內(nèi),選擇最容易服務(wù)的飛行器,設(shè)計(jì)相應(yīng)的軌道,從而達(dá)到降低飛行器損耗的目的。設(shè)aut為服務(wù)飛行器對(duì)目標(biāo)飛行器服務(wù)后的消耗,如可能出現(xiàn)的部件失效、軟硬件故障以及零部件的磨損。對(duì)服務(wù)飛行器進(jìn)行任務(wù)分配,使得所有服務(wù)飛行器消耗之和最小,即
(3)目標(biāo)飛行器價(jià)值收益最大指標(biāo)
目標(biāo)價(jià)值收益最大指標(biāo)通過對(duì)服務(wù)飛行器執(zhí)行任務(wù)時(shí)所獲取目標(biāo)價(jià)值的評(píng)估,來引導(dǎo)目標(biāo)分配的優(yōu)化和決策向著服務(wù)效能最大化的方向進(jìn)行。該指標(biāo)使服務(wù)飛行器趨向于服務(wù)最優(yōu)價(jià)值的目標(biāo)。綜合考慮目標(biāo)價(jià)值V、確認(rèn)概率Pc、剩余服務(wù)能力1-aut,則服務(wù)飛行器U服務(wù)目標(biāo)飛行器T時(shí),收益為Vut=V·Pc·(1-aut)。其中,Pc表示服務(wù)飛行器準(zhǔn)確到達(dá)任務(wù)區(qū)域、發(fā)現(xiàn)目標(biāo)并且正確識(shí)別出目標(biāo)的概率,為每個(gè)服務(wù)飛行器分配任務(wù),使得總的收益最大,即
(4)能量時(shí)間最優(yōu)模型
在得到既定任務(wù)后需要對(duì)在軌服務(wù)飛行器進(jìn)行軌道機(jī)動(dòng),自主、快速、精確和大范圍軌道機(jī)動(dòng)技術(shù)為各種應(yīng)用提供了可靠的保證。遠(yuǎn)程導(dǎo)引變軌在整個(gè)任務(wù)分配活動(dòng)中起著非常重要的作用,合理的導(dǎo)引變軌還能夠節(jié)省能量以及所需時(shí)間。同時(shí)考慮燃料消耗和轉(zhuǎn)移時(shí)間,建立性能指標(biāo),使得能量時(shí)間消耗最小,即
式中 Δv1為交會(huì)初始時(shí)刻所需的速度增量;Δv2為交會(huì)末時(shí)刻所需的速度增量;t為交會(huì)變軌所要求的時(shí)間;0≤k≤1為比例系數(shù)。根據(jù)交會(huì)變軌時(shí)間t就能求出Lambert雙脈沖變軌所需的能量消耗,尋找最佳交會(huì)時(shí)間,使得變軌能量消耗也最小。
(5)約束條件
服務(wù)飛行器任務(wù)分配應(yīng)滿足以下約束條件:
2)對(duì)于每個(gè)目標(biāo),無論采取什么方式的服務(wù),對(duì)目標(biāo)價(jià)值收益不大于該目標(biāo)的自身價(jià)值:
3)Δv1+Δv2≤Δv,Δv表示服務(wù)飛行器所能提供的速度增量,即服務(wù)飛行器執(zhí)行任務(wù)需要的速度增量必須小于其所能提供的速度增量。
綜上所述,服務(wù)飛行器任務(wù)分配的性能指標(biāo)函數(shù)可以表示為
式中ω1、ω2、ω3為權(quán)系數(shù),反映了每個(gè)子目標(biāo)的重要程度。
任務(wù)分配問題的特點(diǎn)是隨著問題規(guī)模的增大,決策變量的個(gè)數(shù)和決策向量的維數(shù)將大為增加,難點(diǎn)是怎樣在滿足各種約束條件的基礎(chǔ)上,綜合考慮各項(xiàng)指標(biāo)組成的目標(biāo)最優(yōu)值,若仍用傳統(tǒng)的最優(yōu)算法求解這個(gè)組合優(yōu)化問題時(shí),計(jì)算量將非常大,從而導(dǎo)致求解困難,甚至無法求解。針對(duì)這一情況以及服務(wù)飛行器協(xié)同目標(biāo)分配問題特點(diǎn),設(shè)計(jì)了一種新的離散粒子群目標(biāo)分配算法。
粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是Kennedy和Eberhart于1995年提出的,有著個(gè)體數(shù)目少、計(jì)算簡單、魯棒性好等優(yōu)點(diǎn)。PSO算法中,每個(gè)粒子就是一個(gè)備選解,多個(gè)粒子共存、合作尋優(yōu)。每個(gè)粒子根據(jù)自身和粒子群的經(jīng)驗(yàn),在問題空間中向更好的位置 “飛行”,搜索最優(yōu)解。粒子本身找到的最優(yōu)解稱為個(gè)體最優(yōu)值pbest,就是每個(gè)粒子在飛行過程所經(jīng)歷過的最優(yōu)位置。整個(gè)群體目前找到的最優(yōu)解稱為全局最優(yōu)值gbest,就是整個(gè)群體所經(jīng)歷過的最優(yōu)位置[14-16]。由于標(biāo)準(zhǔn)的粒子群算法具有連續(xù)本質(zhì),不太適宜于求解離散問題。為了將其用于服務(wù)飛行器協(xié)同目標(biāo)分配問題的求解,根據(jù)該問題的特點(diǎn),在分析多約束基礎(chǔ)上,設(shè)計(jì)了自然數(shù)編碼的離散粒子群算法,建立了粒子與實(shí)際問題的對(duì)應(yīng)關(guān)系,并且對(duì)標(biāo)準(zhǔn)粒子群算法作了相應(yīng)的改進(jìn)[17]。
服務(wù)飛行器協(xié)同目標(biāo)分配的決策關(guān)鍵在于確定任務(wù)目標(biāo)由哪個(gè)飛行器來執(zhí)行。因此,這里采用自然數(shù)編碼方式來表達(dá),每個(gè)粒子長度等于目標(biāo)總數(shù),粒子由按目標(biāo)編號(hào)順序排列的服務(wù)飛行器分配編號(hào)組成,表示一種可能的分配方案。例如,目標(biāo)飛行器數(shù)目n取3,目標(biāo)數(shù)目m取4,如圖3所示,表示第2個(gè)服務(wù)飛行器服務(wù)第1個(gè)目標(biāo),第3
個(gè)服務(wù)飛行器服務(wù)第2個(gè)目標(biāo),第1個(gè)服務(wù)飛行器同時(shí)對(duì)第3個(gè)目標(biāo)和第4個(gè)目標(biāo)進(jìn)行服務(wù)。保證約束條件中對(duì)每一個(gè)目標(biāo)必須分配一個(gè)服務(wù)飛行器的限制,單位粒子取值范圍為[1,n]。
圖3 粒子編碼Fig.3 Particle code
粒子的新位置是粒子的速度、個(gè)體極值和全局極值相互作用的結(jié)果。根據(jù)服務(wù)飛行器協(xié)同目標(biāo)分配問題的實(shí)際特點(diǎn),對(duì)粒子群算法的位置和速度更新公式進(jìn)行重新定義,即
式中Xi=(xi1,xi2,…,xim)為粒子i在迭代中的位置;pi=(pi1,pi2,…,pim)為粒子i的個(gè)體極值;pg=(pg1,pg2,…,pgm)為全局極值;ω為慣性權(quán)重;c1是認(rèn)知系數(shù),調(diào)節(jié)向pi的飛行步長;c2是社會(huì)系數(shù),調(diào)節(jié)向pg的飛行步長。F1[Xi(t)]是關(guān)于粒子Xi(t)的函數(shù),其作用是考慮粒子本 身 速 度 對(duì) 其 位 置 變 化 的 影 響;F2[Xi(t),pi(t)]為Xi(t) 對(duì)pi(t) 的 學(xué) 習(xí) 操 作;F3[Xi(t),pg(t)]為Xi(t)對(duì)pg(t)的學(xué)習(xí)操作。位置更新公式由三部分構(gòu)成,設(shè)Ψi為臨時(shí)變量:
這是粒子的“慣性”部分,表示粒子對(duì)自身飛行速度的思考。其中ω?F1[Xi(t)]表示粒子的速度,即為一個(gè)概率為ω的目標(biāo)置換操作,它的實(shí)現(xiàn)方法為:由rand()產(chǎn)生一個(gè)區(qū)間[0,1]上的隨機(jī)數(shù)r,如果r<ω,將對(duì)粒子進(jìn)行置換操作Ψi(t)=F1[Xi(t)],即產(chǎn)生兩個(gè)在 [1,m]之間不同的隨機(jī)數(shù)a和b,然后將粒子位置矢量的第a個(gè)數(shù)值與第b個(gè)數(shù)值互換,也就是將服務(wù)第a個(gè)目標(biāo)的服務(wù)飛行器與服務(wù)第b個(gè)目標(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
假設(shè)在同一軌道上部署了5個(gè)服務(wù)飛行器,它們具有不同的服務(wù)和機(jī)動(dòng)能力,但一個(gè)飛行器只能對(duì)一顆目標(biāo)飛行器提供在軌服務(wù)?,F(xiàn)有處于不同軌道上的目標(biāo)飛行器,要求在規(guī)定的交會(huì)時(shí)間內(nèi)完成對(duì)目標(biāo)飛行器的在軌服務(wù),使整體效能達(dá)到最佳。算例1和算例2的初始軌道要素如表1和表2所示。
兩種算例的時(shí)間約束為50min,任務(wù)要求準(zhǔn)時(shí)與目標(biāo)飛行器交會(huì),實(shí)施在軌服務(wù)。
服務(wù)飛行器實(shí)施遠(yuǎn)程軌道機(jī)動(dòng)的交會(huì)時(shí)間設(shè)定在1 000~3 000s之間,通過搜索某一時(shí)刻對(duì)應(yīng)速度增量,能夠找出最小能量消耗,將其代入任務(wù)分配模型中,結(jié)合假設(shè)求解如下兩種算例。
假設(shè)有5個(gè)服務(wù)飛行器和3個(gè)目標(biāo)飛行器,pc=1。為便于與文獻(xiàn)[18]中的模型和算法相比較,目標(biāo)的價(jià)值、剩余服務(wù)能力都采用文獻(xiàn)[18]中的數(shù)據(jù),如表3所示(剩余服務(wù)能力和目標(biāo)價(jià)值均是根據(jù)飛行器軌道參數(shù)進(jìn)行的假設(shè))。
在算例中,分別采用遺傳算法和離散粒子群算法對(duì)上述問題進(jìn)行仿真,并將迭代30次后兩種算法的最優(yōu)、平均、最差解進(jìn)行了對(duì)比,得出最終的服務(wù)飛行器任務(wù)分配的結(jié)果如表4所示。通過表4的數(shù)據(jù)可以知道,在服務(wù)飛行器和目標(biāo)飛行器規(guī)模不大的情況下,兩種算法得到的最優(yōu)解和任務(wù)分配的結(jié)果是一致的,最優(yōu)方案及對(duì)應(yīng)時(shí)間的最小速度增量如表5所示。在小規(guī)模的任務(wù)分配中,雖也能夠得到最優(yōu)的分配結(jié)果,但兩種算法的優(yōu)劣性差別不大。后面大規(guī)模任務(wù)分配算例中,將會(huì)體現(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)價(jià)值Tab.3 Surplus capacity and target value in spacecrafts
表4 兩種算法的性能比較Tab.4 Performance comparison of two algorithms
表5 仿真結(jié)果Tab.5 The simulation results
假設(shè)有5個(gè)服務(wù)飛行器和10個(gè)目標(biāo)衛(wèi)星,pc=1。為便于與文獻(xiàn)[19]中的模型和算法相比較,目標(biāo)的價(jià)值、剩余服務(wù)能力都采用文獻(xiàn)[19]中的數(shù)據(jù)。
在算例中,兩種算法在迭代30次過程中的最優(yōu)、平均、最差解的變化曲線及比較結(jié)果如圖6~圖8和表6所示。大規(guī)模的任務(wù)分配能夠體現(xiàn)出兩種算法的差異:從圖8中可以看出,離散粒子群算法比遺傳算法收斂特性要好,能夠比較快速地找到最優(yōu)解,而且在離散粒子群平均解的變化曲線也可以看出,即使在迭代的后期,也不會(huì)出現(xiàn)粒子趨同的現(xiàn)象,說明該算法具有較強(qiáng)的尋優(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
由計(jì)算結(jié)果可知,該任務(wù)分配方案可使服務(wù)飛行器在指定的任務(wù)完成時(shí)間內(nèi),以最大的效益完成服務(wù)任務(wù),且滿足各項(xiàng)約束條件,保證了軌道機(jī)動(dòng)過程中能量消耗最少,從而較好地解決了在軌服務(wù)任務(wù)分配問題。
本文根據(jù)在軌服務(wù)飛行器協(xié)同任務(wù)分配問題的特點(diǎn),設(shè)計(jì)了新的離散粒子群位置與速度更新公式,提出了一種基于離散粒子群算法的多服務(wù)飛行器目標(biāo)分配方法。仿真結(jié)果表明,改進(jìn)的粒子群算法能夠快速穩(wěn)定地找到最優(yōu)分配方案,有效地解決多約束條件下的服務(wù)飛行器任務(wù)分配問題。在本文的靜態(tài)研究基礎(chǔ)上可以進(jìn)一步分析任務(wù)狀態(tài)變化的情況,以及這些變化過程中的不確定性,另外,還可以考慮當(dāng)服務(wù)飛行器所帶燃料有限時(shí)如何進(jìn)行任務(wù)分配的問題。本文的研究工作為研究動(dòng)態(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é)報(bào),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é)報(bào),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é)報(bào),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.