采用注意力模型的多星交會序列優化方法

嚴冰，張 進，羅亞中，朱閱訸

（1.國防科技大學空天科學學院，長沙 410073；2.空天任務智能規劃與仿真湖南省重點實驗室，長沙 410073）

0 引言

多目標交會任務要求航天器連續訪問多個目標，在主動碎片清除［1-3］、在軌燃料加注［4-6］等任務中具有廣闊的應用前景。基于智能進化算法的單航天器對多目標交會任務能夠獲得較優的序列解，但缺點是計算時間較長，不適合作為多航天器對多目標交會序列問題的底層支撐，亟需發展一種從隨機次序輸入到最優序列輸出的快速估計方法。

大規模多星交會任務優化含有三層優化子問題，分別是上層的多對多分組指派優化、中層的單對多序列優化以及底層的單對單軌跡優化［7］。每層優化都可基于智能進化算法獲得較優解，但當相鄰兩層或三層均采用計算量較大的全局優化算法時，這種嵌套的優化會使得整體計算效率極低。

中層的多星交會序列優化是時間相關的旅行商問題（Traveling salesman problem，TSP），離散序列變量和連續時間變量引入的混合整數特性增加了優化難度。蒙特卡洛樹搜索［8］和波束搜索［9］等啟發式搜索方法在深空多小行星探測任務優化中取得較好效果。Zhang 等［10］采用混合遺傳算法求解近地空間LEO目標的在軌加注優化問題。朱閱訸［7］將蟻群算法（Ant colony optimization，ACO）的信息素矩陣擴展成帶時間信息的4 維張量，先全局優化獲得較優的序列和時刻后，再通過局部搜索方法進一步優化連續時間變量。黃岸毅等［11］建立的多星多約束遍歷交會的混合整數規劃模型，獲得了性能指標優于第9屆國際空間軌道設計大賽［12］（GTOC9）冠軍結果的方案。然而現有方法尚未解決分組與序列的嵌套優化，只能在分組指派時借助啟發式規則貪婪地獲取組內序列，并進行局部修剪［13］。

事實上，具有“離線訓練、在線決策”特點的強化學習方法已廣泛應用于僅含有離散變量的組合優化問題（Combinatorial optimization problem，COP）中，這是因為強化學習的動作策略選擇特點符合COP 的離散決策特性［14］。因此借助神經網絡對多星交會問題進行最優序列估計，可以與上層優化實現解耦，進而搜索到更加全局的分組結果。

自然語言處理問題中的序列映射模型（Sequence-to-sequence，Seq2Seq）能夠將輸入文本序列轉換成新的文本序列。Vinyals 等［15］提出了指針網絡（Pointer network，Ptr-Net），通過輸出指向原序列位置的概率將Seq2Seq 模型應用到序列規劃任務中，隨后使用監督學習對獲得局部最優標簽值的數據進行學習，但訓練結果往往受限于標簽值的精度。因此后續學者均采用強化學習（Reinforcement learning，RL）中 的REINFORCE 算 法［16］對Ptr-Net進行訓練，所得解的精度優于多種進化算法，且在不少COP 場景中都接近專業求解器［17-18］。傳統Seq2Seq 模型基于循環神經網絡（Recurrent neutral network，RNN）描述文本之間的時序相關性，在編碼過程中文本參數只能被RNN 單元依次讀取并生成隱含狀態，這種遞歸結構使得數據無法并行計算，計算效率較低。為此，Vaswani 等［19］提出自注意力機制，僅使用注意力模型描述文本之間的時序關系，實現了輸入文本數據的并行處理。這種采用自注意力機制的Seq2Seq 模型，也稱為Transformer 模型。Kool等［20］對其進行改進，在TSP、車輛路徑問題等任務中的性能表現均超越了基于RNN的Ptr-Net。

目前基于強化學習的多星交會序列優化研究仍處于起步階段。為此本文搭建了面向多星交會問題的強化學習框架，引入Seq2Seq 模型構成交會序列的策略網絡，最后采用基于回合更新的帶基線的REINFORCE 算法對網絡參數進行更新。多星交會馬爾可夫鏈、策略網絡和REINFORCE 算法之間的關系如圖1所示。

圖1 基于強化學習的多星交會基本架構Fig.1 Basic structure of multi-target rendezvous based on RL

1 面向多星交會的強化學習建模

多星序列優化問題在考慮時間維度的前提下，其離散決策屬性仍然十分鮮明，即以目標數量n為航天器（智能體）的執行總步長，每次只訪問一個目標。智能體在第t步中包含5個要素，分別是狀態空間st、動作空間at、即時獎勵rt、折扣因子γ和狀態更新方程。所有決策過程符合馬爾可夫特性，即智能體在下一步的狀態只與上一步的狀態有關，與其他步的狀態無關。

1.1 狀態空間

航天器在交會時刻與目標的狀態保持一致，因此每一步的狀態空間s（tt=1，2，…，n）即為訪問目標在對應時刻的位置速度或軌道根數。

1.2 動作空間

智能體的動作既有離散變量（訪問目標），又有連續變量（訪問時刻），不利于策略網絡的學習。可將任務總時長Tmax均勻分成m段，讓智能體在不同時間節點下的目標之間進行決策。因此每一步的動作空間at包含訪問目標的序號It以及交會時刻的網格序號Tt，表達式為

由于每步決策時動作維度不變，即（m+1）×n，因此需要借助掩碼約束，確保目標It未被訪問，且前后交會時刻和剩余目標的時間滿足基本任務需求，約束表達式為

1.3 即時獎勵

在多星交會序列問題中，三維空間的歐式距離無法準確衡量航天器的轉移代價，需要借助兩兩目標之間轉移的最優速度增量Δv進行描述。然而，通過軌跡優化獲取最優Δv需要較高的計算成本，可采用精度較高的轉移成本估計方法。已有研究從軌道動力學模型出發，基于Edelbaum 公式和軌道根數差對二體與攝動條件下的轉移成本進行估計［21-23］。此外，利用機器學習方法將成本估計建模成監督學習中的回歸問題也是一種有效手段，一般需要結合軌道領域知識提高解的精度［24-25］。為了提高學習效率，攝動條件下的多脈沖最優解可采用文獻［22］的方法進行估計。需要注意的是，在論證學習方法的性能優劣時，必須確保其他序列優化方法也采用相同的底層估計算法。

經典TSP 問題采用的REINFORCE 方法是基于回合更新的，因此單步決策沒有即時獎勵，直接以完整序列的總路徑長度為期望（折扣因子γ=1），因此最后一步的獎勵rt設為總的轉移速度增量。rt表達式為

由于估計算法得到的成本值與考慮了初始和終端脈沖時刻自由的多脈沖軌跡優化結果十分接近，因此動作空間at無需引入航天器完成在軌駐留后的出發時刻。當到達時刻固定時，出發時刻越早，脈沖時刻的搜索范圍越大，越有可能得到高質量的速度增量。

1.4 狀態更新

智能體的狀態轉移過程不存在隨機性，在更新狀態空間st時，要將交會目標It的軌道根數外推至Tt時刻。目標在近地空間除了受到地球引力外，還需要考慮J2長期項攝動影響，軌道動力學方程為

式中：［a，e，i，Ω，ω，M］為平均軌道根數，表示目標的半長軸、偏心率、傾角、升交點赤經、近地點幅角和平近點角。更新完st要將bIt從0置為1。

綜上，多星交會任務中的強化學習要素如圖2所示，s0為航天器初始狀態，通過at可以選擇交會目標，并將狀態外推至對應時刻，直到最后一步決策對所有的速度增量進行累加作為即時獎勵rn。

圖2 多星交會任務中的強化學習要素Fig.2 Elements of RL in multi-target rendezvous task

2 基于注意力模型的策略網絡搭建

基于Seq2Seq 模型的策略網絡π（θat|s）t用于序列輸出，在每一步中生成所有候選目標的概率分布并進行隨機采樣得到當前目標和時刻索引，即為動作at。其流程可分解為編碼和解碼，θ代指所有的神經網絡參數。編碼器負責對原始輸入數據進行高維映射，轉換成隱含狀態。解碼器則在每一步中結合隱含狀態和歷史決策選出當前目標，步步推進即可確定一條完整序列。在組合優化問題中，由于輸入序列是隨機的，注意力模型體現在解碼過程中。

2.1 編碼器

在機器翻譯問題中輸入文本的序列會影響輸出詞匯的序列，因此編碼器要將輸入文本之間的序列相關性表達出來。而在傳統TSP等路徑規劃問題中，輸入序列是隨機的，編碼器只需要充當嵌入層，將輸入參數投影到高維空間。記n個目標的狀態向量為x，通過線性映射將其轉換為隱含狀態h：

式中：x∈Rn×6；神經網絡參數Wx∈R6×dh，bx∈Rdh；dh為特征維度。

多星交會問題的決策空間既包含目標也包含時間，要讓策略函數選出帶時間信息的目標，只有在編碼時將所有離散時刻的目標狀態都作為輸入，才可以讓πθ在同一個目標的不同時刻之間作選擇，此時x∈Rn×（m+1）×6，h∈Rn×（m+1）×dh。

2.2 解碼器

解碼器采用自回歸模型，每一步解碼都會對所有時刻的目標產生注意力，從而輸出一個目標It和相應的到達時刻Tt，共執行n步。考慮到Transformer模型在應用于機器翻譯問題時，編碼器和解碼器需要分別使用自注意力機制描述輸入和輸出序列之間的相關性，而在路徑規劃問題中編碼器無需采用該機制，因此將應用于此類問題的Transformer 模型稱為注意力模型。

2.2.1 拓展時間維度的注意力模型

在注意力模型中需要設計一個包含上下文信息的隱含狀態hc，由隱含狀態h關于所有時刻的目標的平均值，第一步決策的T1時刻的目標以及上一步決策的Tt-1時刻的目標組成［20］。hc的表達式為

用Q與K的內積表示每一步的解碼輸入hc與編碼輸出h之間的兼容性，并對不滿足約束的目標和時刻的兼容性進行懲罰，使得解碼時對該時刻的目標的注意力為0。

式中：uj，k，l表示第l個頭的解碼輸入與目標j在時刻k的兼容性；j=1，2，…，n；k=0，1，…，m；l=1，2，…，L。將j和k取代式中的It和Tt，即可確定滿足掩碼約束的取值范圍。

將兼容性經過歸一化指數函數（softmax）處理后得到權重張量，即相對于某個目標和時刻的注意力程度。其中第l個頭的目標j在時刻k的權重為

2.2.2 結合啟發因子的概率分布

在多星交會任務中時間網格是稀疏的，注意力難以集中在關鍵的交會時刻上，從而使得策略網絡陷入局部最優，因此需要設計啟發因子輔助注意力有側重地分布在不同的交會時刻。

在第t步解碼中，計算Tt-1時刻的交會目標It-1到未訪問目標j在可行時間區間內的任意時刻k的速度增量，則啟發式因子ηj，k的表達式為

式中：Δvmax為所有可行速度增量的最大值。將其與式的兼容性進行加權求和，經過softmax 函數后得到解碼器相對于前t-1步的條件概率：

式中：β為啟發因子ηj，k相對于兼容性的權重。

2.3 策略網絡架構與決策流程

不同于常規的順序串聯多個全連接層的神經網絡架構，結合注意力機制的策略網絡往往需要拆開這種順序關系，并對多個僅經過一次線性映射后的向量進行單獨處理。此外，不同步長下的掩碼約束對策略網絡πθ的輸出也至關重要。綜上，πθ的網絡架構與決策流程如圖3所示。

圖3 基于注意力模型的策略網絡架構和決策流程Fig.3 Architecture and deciding process of policy network based on the attention model

圖中，最上方為二維掩碼矩陣，行向量為時刻，列向量為目標，白色表示當前時刻的目標滿足掩碼約束，淺灰色則相反，深灰色表示上一步解碼的位置；中間則是解碼的輸入輸出，一直循環直至所有目標都被選出；下方為πθ的神經網絡架構，總共有6個線性全連接層，每次解碼時hc都會更新，使得右側參數一直變化，而左側參數保持不變。

3 基于REINFORCE算法的參數更新

隨機策略函數的選擇概率p（θπ）可利用鏈式法則拆解成每一步條件概率的累乘：

基于p（θπ）可以確定一組序列和時刻，進而得到回合總獎勵R（π），目標函數為R（π）的期望值：

式中：期望值為遍歷交會的速度增量之和，期望越小交會序列越好，因此需要利用梯度下降對其進行尋優。

帶基線的REINFORCE 算法目前是強化學習解決TSP等路徑規劃問題的高效算法［14］。該方法通過整個回合的采樣值代替收益評價指標，因此參數是基于回合更新的。通過引入一個不依賴于策略網絡的基線函數fbl作為實際獎勵的期望值，在不影響目標期望值的同時降低其方差，從而增強網絡的泛化能力。期望值的梯度為

式中：d為采樣樣本數。通過鏈式法則將選擇概率的對數lnp（θπ）替換成每一步決策的條件概率的對數之和，然后基于蒙特卡洛采樣近似獲得目標函數J對參數θ的梯度值。fbl可根據文獻［20］提出的貪婪rollout 策略進行擬合，如果當前訓練回合下隨機采樣的策略網絡πθ得到的完整序列獎勵優于貪婪采樣的基線函數網絡πθbl，且經過單邊配對t 檢驗得到的值小于置信度α，則用θ更新一次θbl。訓練回合數越大，基線函數越接近實際獎勵值R。算法共涉及兩層循環，具體流程如圖4所示。

圖4 基于REINFORCE算法的參數更新流程圖Fig.4 Flow chart of parameter updating based on REINFORCE algorithm

4 仿真試驗

多星交會任務通常以軌道高度和傾角差異較小的碎片云或衛星集群為對象，并且在上層多對多分組優化中軌道異面度比較集中的目標會被分到一組，以提高單個航天器交會目標的數量。因此，單對多序列優化的空間目標分布于半長軸a、傾角i和升交點赤經Ω 分布差異較小的近圓軌道上。此外，由于多星交會問題沒有理論最優解，為了驗證學習方法在不同目標數量下的精度與泛化能力，通過應用于GTOC9 的改進蟻群算法［7］提供較優解，并將學習結果與之進行對比驗證。

4.1 訓練配置

4.1.1 數據集

通過限定軌道根數取值范圍構造強化學習的數據集，軌道參數的取值范圍見表1，符合碎片云或衛星集群的基本特征。在參數訓練過程中，數據的隨機采樣服從均勻分布。

表1 訓練數據的軌道根數分布范圍Table 1 Range of orbital elements for training

在J2長期項攝動影響下，目標的軌道根數中半長軸a、偏心率e和傾角i不變，升交點赤經Ω 和近地點幅角ω緩慢漂移，而相位M則呈周期性變化。仿照TSP問題提取目標城市的位置坐標作為神經網絡的輸入，多星交會問題也可將軌道根數轉成位置和速度作為輸入張量x。

4.1.2 任務場景參數

以單航天器在20 天內交會10 個目標為基本訓練場景，兩兩目標之間的最大轉移時間設為8天，包含最少駐留時間ΔTstay=0.5 天。由于沒有太陽光照等與星歷相關的約束條件，因此對初始歷元沒有要求。航天器的初始位置設定參考GTOC9，即與第一個交會目標重合，沒有額外設計航天器的初始部署軌道。

考慮到交會序列成本隨時間的變化呈現出多峰性，若網格數m設太大則注意力過于分散造成學習效果不理想，而m設太小則會使得解的質量偏低。因此m設為80，每個時間網格為0.25天。

4.1.3 超參數

超參數是搭建、訓練神經網絡的基本參數，可能會影響訓練結果但無法進行尋優，最終通過人為經驗加上小范圍調試給定。這些超參數主要跟網絡模型以及訓練參數相關，相關數值見表2。

表2 超參數配置Table 2 Configuration of hyperparameters

表中，樣本數B是指一次性放入GPU 中進行批量計算的數據量，為了提高訓練效果且受顯存大小限制需要分批次對樣本進行訓練；學習衰減率ldecay表示在訓練中網絡參數θ會隨著訓練代數g的增加而衰減，學習率的表達式為

4.2 結果分析

4.2.1 訓練結果

訓練總輪數設為200 代，每代分批訓練25 次，因此累計迭代次數為5 000 次。在每回合的批量樣本的平均獎勵值（實質上是懲罰）指標越小，意味著模型θ的訓練效果和泛化能力越好。在10 星交會任務中的這兩類指標數值隨回合數和迭代次數的增加而變化的情況分別見圖5。

圖5 10目標交會的訓練結果Fig.5 Training results of 10-target rendezvous

從圖中可以看到，隨著訓練次數的增加，樣本集的平均速度增量在逐漸下降，并且帶基線的目標函數值也在0 處附近振蕩，說明策略網絡到達了局部最優，整個訓練過程也趨于穩定。

在顯卡配置為GTX1050Ti 的4G 顯存中，10 目標交會場景每訓練1 代需要約42 s，200 代累計訓練約2.3 h。因為解碼流程是串行的，所以目標序列越長，訓練時間越長。而其余參數，如時間網格m、特征維度dh等，都不會隨著取值的小范圍波動而對訓練時間造成顯著影響。

4.2.2 與ACO對比分析

文獻［7］在改進蟻群算法時將信息素矩陣拓展了時間維度，應用于本問題中的時間間隔與網格數m一致，底層采用相同的成本估計算法，其余參數配置為：螞蟻數為35，進化代數為200，啟發式權重參數為2.0，衰減系數為0.9。隨機選擇50 組算例，RL方法與ACO 算法的序列成本的絕對和相對誤差見圖6。

圖6 基于RL與ACO的10目標交會成本對比Fig.6 Comparisons of costs of 10-target rendezvous by RL and ACO

圖中，ACO 算法得到的50 組樣本的序列成本均值為2 170 m∕s，RL 方法估計的序列成本均值為2 379 m∕s。以ACO 算法的優化結果為真值，則RL方法估計成本的平均相對誤差為9.7%，平均絕對誤差為208.8 m∕s。50 組樣本中有13 組的估計值優于ACO算法。

以單個序列為例，RL 方法與ACO 算法分別得到的序列、時間和成本情況見表3。

表3 單個算例的優化結果對比Table 3 Comparison of optimization results of the proposed method and ACO in a single example

表中，序列1 的成本相對誤差為3.6%，序列重合度為40%，任務時長為408 h；序列2的成本相對誤差為-4.3%，序列重合度為60%，任務時長為456 h。這說明軌道面分布差異較小的序列成本隨時間變化的局部極值點較多，存在多組序列和時間不盡相同的解，其轉移成本是相近的。

其次對RL 方法與ACO 算法在計算時間上的差異進行比較。在CPU 進程數為28的計算機上，ACO算法對10 目標交會的單個算例的平均優化時間為3.8 min，50 組算例累計約3.2 h。而經過預訓練的RL 方法測試這些算例的時間約50 ms，加上2.3 h的預訓練時間，總時間仍短于ACO 的優化時間。因此基于強化學習的多星交會序列估計方法在滿足一定精度的同時可大大提升計算效率。

4.2.3 不同交會目標對比

為了測試訓練網絡在不同交會目標下的泛化能力，將訓練10目標交會的網絡直接對8和12目標的50 組算例進行估計，其余條件不變，同樣與ACO算法得到的結果進行對比，2 種情況的序列相對誤差分布見圖7。

圖7 基于RL與ACO的8和12目標交會成本對比Fig.7 Comparisons of costs of 8-target and 12-target rendezvous by RL and ACO

從圖中可以看出，由10目標訓練得到的網絡參數一定程度上也能適用其余目標的交會場景，對8和12目標的估計成本相對誤差為15.1%和11.0%。當目標數量越少，ACO 算法的尋優效果更好，RL 方法的泛化誤差相對變大，且沒有得到比ACO 更好的解；而數量越多，RL方法的適應性優于ACO，估計精度相對穩定，且能夠得到比ACO更好的序列解。

4.2.4 不同訓練場景對比

此外，交會目標數據集的軌道根數分布程度也會影響訓練結果。當進一步擴大目標集的半長軸a、傾角i和升交點赤經Ω 的分布范圍，將其上限調整為7 300 km、102°和70°，則RL 方法的估計精度會有所降低，但訓練時間不受影響，與ACO 算法的結果對比如圖8所示。

圖8 基于RL與ACO的10目標交會成本對比Fig.8 Comparisons of costs of 10-target rendezvous by RL and ACO

圖中，ACO 算法得到的50 組樣本的序列成本均值為2 918 m∕s，RL 方法估計的序列成本均值為3 340 m∕s。以ACO 算法的優化結果為真值，則RL方法估計成本的平均相對誤差為12.2%，平均絕對誤差為421.5 m∕s。50 組樣本中有6 組的估計值優于ACO 算法。當目標分布更分散時，序列成本隨時間變化的多峰性增強，導致學習效果降低。

5 結論

針對多星交會序列的端對端優化提出了基于注意力模型的強化學習方法，將時間維度引入注意力模型中，并以速度增量為啟發因子，對學習方法的策略網絡進行引導，使其能夠對不同時刻下的目標進行決策。將所提方法應用于多星交會序列場景中，并與蟻群算法的優化結果進行對比。在對軌道分布較為集中的10目標交會場景中，強化學習方法與蟻群算法對50 組算例的序列成本的平均相對誤差為9.7%，且前者的估計時間遠小于后者。當交會目標在10附近波動時，神經網絡也有較好的估計精度。此外，進一步擴大訓練集的軌道根數分布范圍，學習方法的估計精度會有所降低。

本文所提方法能夠在上層分組打包問題中對單對多訪問序列和時間進行快速估計并得到精度尚可的轉移成本，從而輔助指派算法更好地搜索全局解。