鐘澤南, 權申明,2, 晁 濤, 王松艷,*, 楊 明

(1. 哈爾濱工業(yè)大學控制與仿真中心, 黑龍江 哈爾濱 150080;2. 上海機電工程研究所, 上海 201109)

0 引 言

航天器由于退役、故障、損壞等原因成為空間碎片,不僅占據(jù)寶貴的空間軌道資源,還影響其他在軌航天器正常運行,對人類航天活動造成不利影響[1]。目前,國內(nèi)外應對空間碎片主要傾向于采用3種策略,即監(jiān)測預警、減緩和主動移除[2]。其中,主動移除技術包括附著式移除技術和非接觸遙操作移除技術,附著式移除因具有針對特定空間碎片清除的特點而受到關注。

盡管附著移除技術有多種具體實施手段,但將功能性載荷投送到目標碎片附近的需求是明確且必要的,目前有天基平臺投送和地基平臺投送兩種投送方式。地基平臺直接上升式清除方式,具有載荷在軌工作時間短、響應速度快、不涉及大量空間目標避碰規(guī)劃且地面條件易保障等優(yōu)點[3-4]。采用運載器搭載多載荷的方式則可進一步降低成本,尤其是節(jié)省發(fā)射資源。運載器一次投送可清除多個碎片目標,不失為一種快速清除大規(guī)?？臻g碎片目標的有效方法。通過對現(xiàn)有技術進行調(diào)研發(fā)現(xiàn),對地基清除碎片目標任務各組成要素(發(fā)射點、運載器、載荷和碎片目標)的進行合理規(guī)劃與控制,能夠顯著提升任務的效費比[5]。因此,多發(fā)射點-多運載器-多載荷-多目標任務規(guī)劃問題應作為重點展開研究。

多發(fā)射點-多運載器-多載荷-多目標任務規(guī)劃問題,涉及運載器軌跡及載荷軌道設計、運載器-載荷-目標分配等內(nèi)容,難以找到直接有效的求解方法。目前,此類相似任務規(guī)劃的研究主要集中在“發(fā)射點-運載器-載荷-目標”彈道設計與優(yōu)化,所考慮的背景多為一對一[3],適用于目標過頂?shù)奶厥馇樾蝃6],且考慮的約束較少。相比運載器軌跡及載荷軌道優(yōu)化設計,考慮初始條件及約束條件的發(fā)射窗口計算更為重要[7]。在窗口計算方面,文獻[4]針對低軌目標快速攔截的發(fā)射窗口規(guī)劃問題,提出了基于上升軌跡可達范圍分析的發(fā)射窗口初篩及精確求解算法。文獻[8]研究在目標軌道、目標區(qū)域和發(fā)射車機動區(qū)域內(nèi)公路信息確定的情況下,機動發(fā)射點位和發(fā)射窗口的一體解析規(guī)劃方法。文獻[9]分析各種約束對交會對接發(fā)射窗口的影響,得出各種約束條件下交會對接發(fā)射窗口分布的規(guī)律。本文在任務規(guī)劃時需要考慮到實際物理限制下的多種約束,如飛行時長、變軌沖量約束、運載器搭載載荷數(shù)量約束、因載荷傳感器工作所需的場景約束等。目前針對多類型目標,多物理約束[10]及多階段運動過程的窗口推算研究相對較少。

與武器-目標分配問題類似[11],運載器耗費量最少問題也是優(yōu)化問題[12],性能指標是優(yōu)化問題的關鍵要素,與實際任務需求有關。文獻[13]針對多彈頭在軌武器平臺目標分配優(yōu)化,考慮到武器平臺長期在軌服務需求,考慮以能量耗費作為最優(yōu)指標;部分場景下由于任務中包含不確定性,則關注成功概率最大化問題[14]。隨著研究場景的復雜性逐漸增加,性能指標由單性能指標向多性能指標轉(zhuǎn)變[15-16]。一枚運載器的制造維護成本更高,占用發(fā)射資源更多,因此本文將運載器耗費量最少作為性能指標進行重點研究。目標分配問題屬于典型的指派問題,針對各類指派問題的有效求解方法有匈牙利算法、分支定界法、反點算法和粒子群算法等,其中匈牙利算法具有求解耗時短、結(jié)果穩(wěn)定等優(yōu)勢[17-19],通過改進匈牙利算法對多陣地協(xié)同攔截多目標問題類似“發(fā)射點-運載器-載荷-目標”的匹配問題,可通過改進匈牙利算法進行求解[20]。在本文“多發(fā)射點-多運載器-多載荷-多目標”指派問題中,運載器搭載載荷數(shù)量受限,且求解規(guī)模與任務時長有關,屬于受約束的非平衡指派問題。匈牙利算法被認為是多項式時間內(nèi)求解指派問題的有效方法,可適應大規(guī)模的計算需求[21]。因此本文將考慮采用匈牙利算法以適應文中各種規(guī)模目標的分配問題。

本文針對大規(guī)模碎片目標清除背景下的“多發(fā)射點-多運載器-多載荷-多目標”任務規(guī)劃中最小化運載器耗費量問題,首先設計考慮多約束多過程的目標窗口推算方案以解決“發(fā)射點-運載器-載荷-目標”單匹配問題,在此基礎上生成可發(fā)射矩陣,用以描述“多發(fā)射點-多運載器-多載荷-多目標”可行性,考慮以最少運載器耗費量為最優(yōu)性能指標,通過可發(fā)射矩陣動態(tài)調(diào)整策略,基于匈牙利算法,最終實現(xiàn)“多發(fā)射點-多運載器-多載荷-多目標”任務規(guī)劃求解。

1 問題描述

1.1 任務描述

圖1 多階段任務過程描述Fig.1 Description of multi-phase mission process

1.2 問題建模

與文獻[16]描述方式類似,本文的目標清除任務規(guī)劃問題可用三元組來描述:LS為發(fā)射點集合,LS={L1,L2,L3,…,Lm},其中m為發(fā)射點數(shù)量;TS為目標碎片集合,TS={T1,T2,…,Tn},n表示目標數(shù)量;CS表示任務規(guī)劃中的約束,包括運載器-載荷動力運動學約束、任務時長約束、數(shù)量約束,這些約束將會在建模中詳細討論。

任務規(guī)劃的本質(zhì)是一個優(yōu)化問題,包含設計變量、任務約束和評價指標3個關鍵因素,本文研究問題的關鍵要素如下:

(1) 設計變量

(1)

(2) 評價指標

所需運載器數(shù)量越少,完成任務的成本越小,節(jié)省的發(fā)射資源越多,即有

J=VD

(2)

(3) 任務約束

在整個任務規(guī)劃過程中,需要考慮任務約束CS={C1,C2,C3,C4,C5,C6},各約束分別為:

C1:運載器-載荷等實際飛行過程中的動力學、運動學約束[22];

C3:載荷變軌滑行最大沖量ΔVMax;

C5:載荷傳感器正常工作所需滿足約束,如光照角、交會角、交會速度等[23];

C6:運載器-載荷分配受可發(fā)射矩陣MI約束,稱為匹配約束。

1.3 任務規(guī)劃模型

綜上,本文研究的目標清除任務規(guī)劃問題,可表示為如下優(yōu)化模型:

(3)

式中:C1～C6描述了任務所需滿足的約束,其余兩個約束則用于保證所有目標均被清除且同一目標不能由多個運載器搭載的載荷清除?；谠撊蝿漳Ｐ?問題難點如下:

(1) 任務涉及多個階段,約束類型多、數(shù)量多;

(2) 任務指派基于MI信息,但MI不可知;

(3)MI與目標數(shù)量及任務時長相關,維數(shù)大。

2 模型求解

2.1 求解框架

在三元組中,運載器及載荷等并未直接給出,因此后續(xù)根據(jù)諸元虛擬運載器及載荷進行規(guī)劃。根據(jù)任務要求,問題求解框架劃分為窗口推算、可發(fā)射矩陣生成及基于可發(fā)射矩陣的問題求解等3個子問題。

圖2 問題求解框架Fig.2 Solution framework of problem

2.2 目標窗口推算方法

窗口推算求取采用如表1所示的參數(shù),解決“發(fā)射點-運載器-載荷-目標”諸元匹配問題。

表1 發(fā)射點-運載器-載荷-目標匹配參數(shù)

本文采用離散化方法以提高問題求解快速性,離散化主要體現(xiàn)在主動段關機點參數(shù)離散及窗口離散兩個方面,同時離散化有利于計算機工作。

由于主動段工作時間短且固定,因此在發(fā)射系下通過幾種典型的彈道設計方案,即通過彈道積分得到發(fā)射系下的關機點參數(shù)[24-25]。通過典型彈道設計,主動段可達域由三維空間離散化為射面內(nèi)關機點參數(shù),減少了計算量,提高了計算效率。典型彈道對應關機點集合,在需要時通過坐標變換將關機點參數(shù)由發(fā)射系轉(zhuǎn)化為慣性系下即可。典型彈道設計方法則不在文中敘述。在后續(xù)一對多匹配中,多個載荷的主動段關機點參數(shù)需要一致,因此離散關機點參數(shù)有利于實現(xiàn)一對多匹配。

為兼顧不同類型目標的窗口推算需求,本文采用通用的遍歷任務時間區(qū)間的方法,即通過判斷任務時間區(qū)間內(nèi)的每一個時刻是否為窗口,進而求取任務時間內(nèi)的全部窗口。該方法需要選取窗口推算步長,以兼顧窗口推算的快速性與實用性。

算法1給出了判斷某一時刻tI是否為窗口的判斷方法,圖3是該算法的實現(xiàn)流程圖。通過以時間步長δtI遍歷任務時間區(qū)間,循環(huán)調(diào)用算法1,即可得到發(fā)射點對目標的所有窗口。進而,遍歷發(fā)射點及目標,可以得到所有m個發(fā)射點對n個目標的窗口。實際使用時通過并行計算提高求解速度。

算法 1 時間窗口判斷:判斷時刻tI是否為發(fā)射點p對目標Tk的窗口(1) 輸入時刻tI;(2) 預報tI時刻目標Tk的狀態(tài);(3) CS中僅與目標狀態(tài)相關的約束判斷(如地影):若不滿足某個約束,則說明該時刻不屬于窗口,判斷結(jié)束;滿足約束則繼續(xù);(4) 依據(jù)飛行時間約束,求取發(fā)射時刻tL的范圍[tMinL,tMaxL],初始化發(fā)射時刻tL=tMinL;(5) 聯(lián)合tL、tI時刻下目標經(jīng)緯與發(fā)射點經(jīng)緯計算射向sD,根據(jù)發(fā)射點p參數(shù)及射向建立發(fā)射系;(6) 初始化關機點sp;(7) 通過坐標變換得到關機點參數(shù);(8) 初始化滑行時間tG;(9) 推算滑行結(jié)束時刻的載荷狀態(tài);(10) 求取變軌轉(zhuǎn)移時長tT=tI-tL-tG-tS;(11) 采用固定時間蘭伯特變軌計算變軌初速度,計算變軌沖量ΔV;(12) 變軌沖量約束判斷;若不滿足變軌沖量約束,轉(zhuǎn)至步驟(14);滿足沖量約束則繼續(xù);(13) CS中其他約束判斷,若均滿足,則是窗口,判斷結(jié)束;否則,轉(zhuǎn)至步驟(14);(14) 按滑行時間步長δtG更新滑行時間tG,轉(zhuǎn)至步驟(9);若tG無法繼續(xù)更新,轉(zhuǎn)至步驟(15);(15) 更新關機點sp,轉(zhuǎn)至步驟(7);若關機點參數(shù)無法繼續(xù)更新,轉(zhuǎn)至步驟(16);(16) 按發(fā)射時刻步長δtL更新發(fā)射時刻tL,轉(zhuǎn)至步驟(5);若發(fā)射時刻無法繼續(xù)更新,轉(zhuǎn)至步驟(17);(17) 時刻tI不是窗口,判斷結(jié)束。

圖3 算法1流程圖Fig.3 Flowchart for Algorithm 1

2.3 可發(fā)射矩陣生成

表2 原始信息表

續(xù)表2

表3 缺省信息表

缺省有兩種情況。發(fā)射時刻缺省表明該時刻下不可發(fā)射運載器;發(fā)射陣地缺省表明在該時刻下該陣地不可發(fā)射運載器。

表2與表3的主要區(qū)別僅在于表3只需要更少的存儲空間,表3的每一行可生成可發(fā)射矩陣MI的每一行。由此可知,矩陣MI的規(guī)模會隨著任務時長、窗口推算步長、目標數(shù)量變化。

2.4 最少運載器耗費量求解方法

在匈牙利算法中,一個任務只能由一個對象完成,且一個對象只能完成一個任務,對象與任務之間具有一一對應關系。如果一個運載器只搭載一個載荷,一個載荷只清除一個目標,則運載器與目標之間具有一一對應關系,在這種對應關系下,基于可發(fā)射矩陣MI,可以直接采用匈牙利算法進行求解?？紤]到一個運載器可以搭載多個載荷,且當搭載數(shù)量受限制時,基于MI無法采用匈牙利算法直接進行求解。

經(jīng)分析可知,之所以不能求解一個運載器對多個目標的分配情況,是因為在算法求解過程中,MI對應的行被去掉,因此這枚運載器將不再被考慮繼續(xù)搭載載荷。在實際應用中,由于這枚運載器可以搭載多個載荷,其所在的行可以繼續(xù)放到可發(fā)射矩陣中,這種方法可得到一個新的可發(fā)射矩陣。由于新的可發(fā)射矩陣是在原MI的基礎上擴展而來的,因此可將其稱為可發(fā)射矩陣擴展。

(3) 由于目標必須被清除,當目標只可以被一枚虛擬運載器清除時,這枚運載器必須被指派;假設目標可以被2枚虛擬運載器清除,則在這2枚運載器中,至少有一枚必須被指派;依此類推,必須發(fā)射的運載器盡可能多地清除目標,則有利于減少所需運載器的數(shù)量。對于可發(fā)射矩陣MI,其行元素之和越小,重要性越大;其列元素之和越大,其重要性也越大。

算法 2 一對多可發(fā)射矩陣拓展方法(1) 行數(shù)拓展:設NA^為擴展矩陣^MI的行數(shù),可發(fā)射矩陣MI第i行的列元素之和為si-,當si->VMaxZ時,si-=VMaxZ;其余情況下s^i_=si-;NA^=∑NLVi=1s^i_;(2) 列數(shù)不變:矩陣^MI的列數(shù)仍然為NT;(3) 建立映射:MI行第k行映射為擴展可發(fā)射矩陣^MI的第∑k-1i=1s^(i-1)_+1至∑ki=1s^(i-1)_+1行,其中s^0_=0;(4) 調(diào)整權重:^MI的第i行所有列元素之和為si-,^mIi,j=Rr-mIi,jsi-;^MI的第j列所有行元素之和為s-j,^mIi,j=mIi,j(Cc-s-j);其中,mIi,j、^mIi,j分別表示^MI調(diào)整前后的第i行第j列元素,Rr、Cc分別為較大的參數(shù)。

算法 3 最少運載器耗費量NL的求解步驟(1) 從表3生成原始可發(fā)射矩陣MI,進而求解虛擬運載器數(shù)量NLV和需清除的目標數(shù)量NT,初始化SdD、SdX,其中集合SdD為使用的運載器的集合,SdX表示已經(jīng)被分配的目標集合,初始化效費值C為較大的數(shù);(2) 獲取不屬于集合SdD的虛擬運載器并將其進行排序,獲取不屬于集合SdX的目標并將其進行排序;得到可用運載器的數(shù)量NM和分配的目標的數(shù)量NT;(3) 根據(jù)NT和NM生成可發(fā)射矩陣MI;(4) 依據(jù)算法2生成擴展矩陣^MI;(5) 調(diào)用匈牙利算法,返回效費值C,得到分配情況;若目標被分配完畢或效費值C不再減小,則結(jié)束;輸出集合SdD和SdX,集合SdD的勢即為最少運載器耗費量;否則繼續(xù);將清除VMaxZ個碎片的運載器壓入集合SdD,將被分配目標壓入集合SdX,返回步驟(2)。

綜合以上描述,任務規(guī)劃流程如圖4所示。

圖4 任務規(guī)劃算法流程Fig.4 Flowchart of mission planning algorithm

3 仿真驗證

3.1 最少運載器求解算法驗證

為說明以MI為基礎的最少運載器耗費量求解方法的有效性,考慮20個運載器清除18個目標的任務場景,仿真考慮A、B兩種MI情形。兩種情形均假設一枚運載器最多可清除6個目標,A情形中,設定第1、2、3枚運載器能清除所有目標,B情形中設定第6、8、10枚運載器能清除所有目標。因此,針對18個目標的理論最少運載器耗費量均為3,該問題有最優(yōu)解。采用可視化方法展示MI,如圖5～圖6所示,圖中對MI中非0元素進行有色展示,用綠色圖塊指示了A、B兩種情形下的可行解,并用箭頭進行指示。針對所列出的A、B兩種情形,分別采用遺傳算法和本文提出的算法3對問題進行求解。

在采用遺傳算法求解時,對同一初始條件求解50次,并將最優(yōu)結(jié)果繼續(xù)迭代優(yōu)化10次,以保證算法求解結(jié)果的最優(yōu)性。對圖5所示的MI的求解結(jié)果如圖7所示,對圖6所示的MI的求解結(jié)果如圖8所示。圖7和圖8中,o表示采用遺傳算法求解50次的結(jié)果,即為循環(huán)迭代的初值,☆表示循壞迭代10次后的結(jié)果。從圖中可以看出,盡管在最優(yōu)值的基礎上進行迭代優(yōu)化,運載器耗費量最少為5枚,達不到理論最優(yōu)解3枚,且50次求解結(jié)果并不相同,求解耗時長。

圖5 MI可視化圖(A)Fig.5 Visualization diagram of MI(A)

圖6 MI可視化圖(B)Fig.6 Visualization of MI(B)

圖7 遺傳算法求解結(jié)果(A)Fig.7 Result solved by genetic algorithm (A)

圖8 遺傳算法求解結(jié)果(B)Fig.8 Result solved by genetic algorithm (B)

采用算法3進行最少運載器求解的結(jié)果如下:針對圖5所示的MI,指派運載器序號為1、2、3,最少運載器耗費量為3,其中為運載器1分配目標1～6,為運載器2分配目標7～12,為運載器3分配目標13～18;針對圖6所示的MI,指派運載器序號為1、4、6,最少運載器耗費量為3,其中為運載器1分配目標1、3、6、9、10、13,為運載器4分配目標5、11、12、14、16、17,為運載器6分配目標2、4、7、8、15、18。算法求解速度快,每一次求解的結(jié)果均相同。

3.2 任務規(guī)劃仿真驗證

設任務起始儒略日為2 458 929.839,任務規(guī)劃結(jié)束儒略日為2 458 930.839,任務時長為24 h。共有4個發(fā)射點和30個目標的任務場景。其中發(fā)射點信息如表4所示,目標數(shù)量為30個,其軌道半長軸分布范圍為[6 681.718,7 596.97]km,軌道偏心率分布范圍為[0.002 216,0.196 9],軌道傾角分布范圍為[53.055 81,87.900 37]°,升交點赤經(jīng)分布范圍為[4.106 102,349.473 3]°,近地點幅角分布范圍為[35.574 42,280.822 6]°,目標歷元時刻與任務起始時刻相同,采用二體運動預報目標狀態(tài)。運載器主動段時間為210 s,載荷滑行時間為85～980 s,最大變軌沖量為1 100 m·s-1,最大飛行時間為3 800 s,每個運載器上最多允許搭載6枚功能性載荷。主動段發(fā)射系下的離散關機點參數(shù)如圖9、圖10所示,窗口推算步長為120 s。硬件信息為Intel(R) Xeon(R) W-2255 CPU @3.70 GHz,內(nèi)存為64.0 G,操作系統(tǒng)為Windows 10,編譯環(huán)境為Microsoft Visual Studio 2010。

表4 發(fā)射點信息

每個發(fā)射點對所有目標均存在“發(fā)射點-運載器-載荷-目標”匹配關系,根據(jù)窗口信息生成的可發(fā)射矩陣維度為53 583×30,因矩陣較大在此不做展示。為驗證任務規(guī)劃方法對大規(guī)模目標任務的規(guī)劃能力,分別考慮24 h內(nèi)4個發(fā)射點對數(shù)量分別為100、300和500等不同規(guī)模碎片目標的任務規(guī)劃情況。由于目標數(shù)量較多,只展示最終的運載器耗費量,統(tǒng)計求解結(jié)果列于表5。算法耗時包括窗口推算時間、信息矩陣提取時間及目標分配時間,其中窗口推算耗時最多。隨著目標規(guī)模增多,能一次清除6個目標的運載器數(shù)量在不斷增加,一個運載器只搭載一個載荷、清除一個目標的情況較少,這體現(xiàn)了本文方法“一對多”任務規(guī)劃的有效性。

圖9 運載器發(fā)射系下離散化關機點參數(shù)Fig.9 Shutdown sample parameters of launch vehicle in launch coordinate system

表5 不同規(guī)模目標求解結(jié)果

4 結(jié) 論

本文針對地基大規(guī)?？臻g碎片清除背景下“多發(fā)射點-多運載器-多載荷-多目標”任務規(guī)劃中最少運載器耗費量問題,設計考慮多約束多階段的目標窗口推算方法,基于離散化關機點參數(shù)實現(xiàn)“發(fā)射點-運載器-載荷-目標”的諸元匹配問題,并通過諸元匹配信息生成可發(fā)射矩陣?；诳砂l(fā)射矩陣,針對受載荷數(shù)量約束下的非平衡指派問題,采用動態(tài)調(diào)整策略,基于匈牙利算法,使其能求解一對多目標分配問題。仿真結(jié)果表明,該任務規(guī)劃方法能以少于目標數(shù)量的運載器數(shù)量實現(xiàn)對所有任務目標的清除。