基于深度強化學習算法的空間站任務重規劃方法

史兼郡，張 進，羅亞中，郭 帥，李智遠，李大鵬

（1.國防科技大學空天科學學院，長沙410073；2.中國西安衛星測控中心，西安710043）

1 引言

近年來隨著中國載人航天事業及空間站技術的快速發展，空間站任務規劃技術的研究也受到越來越多關注［1］。空間站任務規劃涵蓋對象廣、涉及時間周期長，工作繁重、難度大。

目前國際空間站已在軌運行多年，開發出多套相關任務規劃系統。例如美國約翰遜中心開發的集成規劃系統（Integrated Planning System，IPS）［2］，該系統可以根據使用者定義的約束對設備資源和在軌飛行任務序列進行規劃；歐空局針對空間站運營艙段開發了（Operations Preparation and Planning System，OPPS）［3］運營準備與規劃系統，該系統主要有任務長期規劃、短期規劃和實時重規劃等功能模塊；俄羅斯針對空間站運營艙段開發了（TheAutomated International Space Station Russian Segment Planning System，APS）自動任務規劃系統［4］。在上述文獻及國外公開的文獻資料中主要是針對國際空間站軟件系統的功能架構進行介紹，少有針對空間站任務規劃的具體模型和方法的研究論述。

國內在空間站任務規劃方面的研究已有初步成果。羅亞中等［5］從頂層設計層面對中國空間站任務規劃關鍵技術提出了發展建議；李志海［6］、卜慧蛟［7-8］等對空間站任務規劃模型及長期、短期任務規劃進行了研究；邱冬陽等［9-10］基于啟發式約束化解的智能優化算法對空間站運營任務層規劃的建模與規劃技術進行了研究；牟帥等［11］對空間站任務快速地重新規劃問題進行了研究，提出了基于啟發式規則的沖突化解策略。上述研究中主要是利用基于啟發式約束化解策略的智能優化算法對規劃問題進行求解，在求解過程事先需求人對問題進行分析提出針對性的啟發式約束化解策略，求解過程缺乏智能性；同時最終結果受到啟發性規則的約束，其結果有很大提升空間。

近年來，人工智能快速發展。谷歌公司的人工智能研究團隊DeepMind創新性地將具有感知能力的深度學習（Deep learning，DL）和具有決策能力的強化學習（Reinforcement learning，RL）相結合，提出深度強化學習［12］（Deep Reinforcement learning，DRL）方法，在高緯度決策問題中有巨大的優勢，已在游戲、機器控制、參數優化、機器視覺等領域中得到廣泛的應用。其中深度確定性策略梯度（Deep Deterministic Policy Gradient，DDPG）算法是Silver等提出的一種改進的策略梯度方法［12-13］，該算法通過雙網絡和經驗回放機制，可以有效解決連續動作空間上深度強化學習問題。針對空間站任務重規劃問題，該算法可以從數據中學習經驗，自主化解約束沖突，有效取得問題的近似最優解。

本文針對空間站任務重規劃時效性強、包含活動多、約束復雜的特點，結合深度強化學習DDPG在智能學習和決策上的優勢，將其引入空間站任務重規劃問題，以編排任務的總體獎勵為強化學習信號，實現空間站任務規劃問題的近似最優求解。

2 任務規劃模型

2.1 問題描述

規劃問題需要在滿足各種條件約束（主要指時間約束和資源約束）的情況下，調整每個活動的具體執行時間，使得期望目標值盡可能高。空間站任務規劃是指在給定的任務周期內規劃空間站的在軌運行事件及其所含活動的編排方案，為航天員合理安排該任務周期內的工作生活提供參考依據［9］。在規劃過程中需要考慮空間站平臺維護、航天員工作條件約束、空間站載荷約束等多種不同類型的任務需求間的平衡；同時，每個在軌事件一般包含不止一項活動，各活動間可能需要考慮邏輯關系約束。

空間站任務重規劃［11］是指空間站在原有計劃執行期間，由于設備故障、人員操作、外部環境改變等突發情況的出現，對一定時間內的任務計劃進行重新規劃，以便于突發情況的處理。空間站任務重規劃主要出現于空間站短期任務規劃中，其主要有規劃周期短、實時性約束多、約束傳播復雜的特點，規劃過程難以提出普適高效的約束沖突化解策略。該問題可看作需快速求解的約束滿足問題，其目的是在短時間內找出滿足突發條件約束的新的任務計劃，同時保持原有執行計劃的相對穩定，其操作流程如圖1所示。

圖1 任務重規劃示意圖Fig.1 Illustration ofm ission re-planning

2.2 規劃模型概念描述

空間站任務層規劃問題的本質是一個約束滿足問題（Constraint Satisfaction Problem，CSP）［10］，針對此類問題，文獻［9-11］已建立起完整的模型。現對本文中使用的任務重規劃模型概念描述如式（1）～（5）：

（1）任務

式中，M代表在軌執行任務；IM代表任務編號；NM.代表任務名稱；tM.E.S.代表任務執行窗口中最早開始時間；tM.L.E.代表任務執行窗口中最晚結束時間；EM.P.代表任務優先級，設定范圍［0，100］；EM.L.代表任務收益性指標，設定范圍［0%，100%］；OM.I.代表其他特殊任務信息要求；A代表任務包含活動集合，即任務完成需要執行一系列的活動。

（2）活動

式中，A代表在軌執行任務所包含活動；IA.代表活動編號；DA.代表活動持續時間；tA.S.代表活動開始時間；OA.I.代表活動其他特殊信息；SA.R.代表先驗關系信息，表示活動間邏輯關系約束，ve表示與基準活動同時完成，vb表示必須在基準活動開始前一定時間完成，va表示必須在基準活動技術后一定時間開始；R代表消耗資源集合；d代表使用設備集合。

（3）資源

式中，R代表在軌執行活動使用資源；IR.代表資源編號；NR.代表資源名稱；UR.代表資源使用量；UR.max.代表資源在軌庫存量；OR.I.代表資源其他信息；SR.C.代表資源類型，0表示連續消耗，1表示離散消耗。

（4）設備

式中，d代表在軌執行活動使用設備；Id.代表設備編號；Nd.代表設備名稱；Cd.Max.代表設備最大負載。

2.3 規劃模型變量及指標

2.3.1 規劃變量集

按照任務重規劃問題的描述，把需要進行重規劃的任務集合（包括原有計劃任務和突發任務）稱為待規劃任務集合。將待規劃任務集合中每個任務事件的第一個活動開始時間作為規劃設計變量，多活動事件的后續活動開始時間按照活動先驗關系進行賦值。得到規劃變量集合如式（6）：

式中，X為設計變量；ti為第i個重規劃任務開始時刻；為由ti和先驗約束確定的第i個重規劃任務結束時刻；tM.ST（i）.和tM.ET（i）.分別是第i個重規劃任務最早開始時間和最晚結束時間；n為待規劃任務總數。

2.3.2 約束集

考慮空間站實際工程背景，規劃結果中要確保每一時刻，所有執行活動要滿足空間站額定功耗、散熱、數據傳輸帶寬、資源額定容量的約束。具體描述如式（7）：

式中，t為規劃時刻；nw為時刻的正在執行的活動總數；為t時刻第i個正在執行活動的實際功耗； 為t時刻空間站的額定功耗；（i）為t時刻第i個正在執行活動的實際散熱；為t時刻空間站的額定散熱；（i）為t時刻第i個正在執行活動的實際占用傳輸帶寬；為t時刻空間站的額定傳輸帶寬；（i）為t時刻第i個正在執行活動的設備資源占用量；為t時刻空間站的對應設備資源總量（如有多種設備每種設備單獨判斷約束）。

2.3.3 目標函數集

由于空間站任務的目的差異，空間站任務規劃目標函數有多種形式。本文主要考慮空間站運營的安全性與穩定性，應在優先安排好突發任務的前提下，盡量減少對原有計劃的影響，設計目標函數如式（8）：

式中，n為最終任務計劃中被安排任務總數；Mi.Priority為任務計劃中第i個任務的優先級；δt（i）為任務計劃中第i個任務的時間改變量，計算方式為新規劃時間tr（i）相對于原有計劃時間t（i）的改變量與該任務最大允許改變量Δtmax之間的比值，取值范圍［0.0，1.0］。

3 空間站任務重規劃方法

3.1 深度強化學習DDPG算法

DDPG算法主要包括基于策略的神經網絡（Actor）和基于價值的神經網絡（Critic），Actor網絡輸入是狀態，輸出是動作，Critic網絡輸入是狀態和行動，輸出為Q值［14］，Actor網絡靠Critic網絡輸出優化每個狀態上選取的動作，達到最終收益最高的目的。其具體流程如圖2。

圖2 DDPG算法Fig.2 DDPG Algorithm

3.2 基于DDPG算法的任務規劃程序

利用DDPG算法求解問題需要對問題狀態空間、動作空間和獎懲規則進行定義。結合第1節中空間站任務規劃模型，定義如下：

3.2.1 狀態編碼

在空間站任務重規劃中，每個任務事件的主要特征包括原任務計劃時間、任務的最早開始時間、任務的最晚結束時間、任務的優先級四個特征，任務的資源消耗主要用于約束的判斷，本文在獎懲規則中進行考慮。由此，采用如式（10）所示狀態編碼：

式中，i為待規劃任務序號，t（i）為第i個待規劃任務原計劃開始時間，ti.E.S為第i個待規劃任務執行窗口中最早開始時間，ti.L.E為第i個待規劃任務執行窗口中最晚結束時間，Ei.P為第i個待規劃任務收益性指標。

3.2.2 動作編碼

考慮1.3節規劃變量集合，選取當前狀態下的任務待規劃開始時間tr（i）為動作編碼，即式（11）：

該動作空間為一維連續空間。

3.2.3 獎懲規則

利用DDPG算法最終目的是找出每個狀態下的最優動作，在本文中就是找出每個待規劃任務的最佳開始時間。而在學習過程中在算法選出動作后需要一個對應的獎懲值引導算法朝著目標方向進化。綜合考慮空間站任務重規劃問題的約束集與目標函數集，定義獎懲規則如下：①算法從第一個待規劃任務（i=1）開始啟動，輸入狀態，做出動作（輸出該任務開始時間），進行約束判斷給出對應的獎懲值，算法進入下一個（i=i+1）任務的規劃；②進行約束判斷時，按照1.3節給出的約束規則進行判斷，若該條計劃加入已規劃任務集后滿足所有約束，返回獎懲值ri=Mi.Priority×（1-δt（i））， 若不滿足全部約束，將該任務從已規劃任務集中剔除，放入規劃失敗任務集，返回獎懲值ri=0；③無論規劃的任務是否滿足所有約束，算法都會進入下個狀態，直到規劃完最后一個待規劃任務，退出當前學習過程，重新開始另一個學習過程。案例具體函數如式（12）：

3.2.4 規劃程序實現

基于Python3.5.4，使用TensorFlow實現DDPG算法的構造與任務規劃模型的實現，其中DDPG算法主要參數設置如表1。

表1 DDPG算法主要參數設置Table 1 M ain parameters of DDPG algorithm

按照2.1節中DDPG算法流程，文章規劃程序實現的具體求解過程為：

1）初始化狀態S1，設置總學習次數（episode），本文案例設置為1000次，設置樣本緩存空間大小10 000條，第一次學習開始。

2）Actor根據當前狀態Si輸出該狀態下做出的動作ai（當前任務的規劃開始時間）。

3）將動作ai，與狀態Si代入約束模型進行判斷，獲得獎勵值ri，到達下一狀態Si+1，產生一條學習樣本（Si，ai，ri，Si+1），放入樣本緩存，當緩存區樣本記錄達到10 000，自動刪除第一條記錄。

4）Critic從樣本緩存中隨機抽取一定量的樣本記錄進行學習，輸入狀態Si和獎勵ri，進行網絡參數θQ的更新，輸出時序差分誤差。

5）Actor獲取時序差分誤差，使用梯度下降法調整參數θμ。若時序差分信號大于0，則表明當前實際采取的行為比估計好，從而使網絡參數的修正方向與誤差信號一致；反之，則使參數的修正方向與誤差信號相反。

6）判斷是否最后一個任務已規劃結束（i≤n），若結束則完成一次學習，統計該次學習過程中的總收益記錄總收益與對應的規劃時間序列。

7）初始化狀態S1，返回流程b，進行下一次學習，直到學習次數達到設定最大值。輸出最大總收益與對應的規劃時間序列，為最終任務規劃結果。

完整流程如圖3所示。

圖3 DDPG算法流程Fig.3 Flow chart of DDPG algorithm

4 算例仿真及結果分析

4.1 算例配置

為驗證本文算法的有效性，應用一個想定的空間站三天內執行任務案例進行分析。算例包括49個原始任務和2個突發任務，共包含104個原始執行活動和3個新增在軌執行活動，涉及模型中4項資源的約束判斷，主要包含通信帶寬約束、能耗約束、散熱功耗約束、設備約束，為使算例貼近實際設置通信帶寬約束為時變約束，每個任務活動均包含四項約束的消耗。原始任務總時間段為［0，4680］min，任務突發時刻1680 min，在此之前已結束的任務不需要進行重規劃。重規劃任務時間段為［1680，4680］min。程序運行環境如表2。

圖4 原始在軌執行任務詳單Fig.4 Originalm ission list

圖4中每個任務ID號表示一項完整任務，同一任務中的不同顏色表示該任務內的不同活動。在圖4（b）原始在軌執行任務詳單2中任務ID9001與9002表示突發的兩項任務。

4.2 結果分析

在上述配置情況下，進行仿真實驗，每一次學習過程結束時進行一次目標函數值的統計，整個學習過程中目標函數值隨學習進程的變化如圖5。其中前350次，主要是算法隨機探索積累學習樣本的階段，對應得到的目標函數值較低，生成的計劃中大部分任務無法完成。隨著學習過程的進行DDPG算法逐漸總結出規劃模型的特點，得到較高的目標函數值回報。在學習進行到800次后，算法基本收斂，目標函數值基本穩定于130上下。

圖5 目標函數變化曲線Fig.5 Variation curve of objective function

獲取學習過程中得到的最優規劃結果，其重規劃部分任務執行詳單如圖6。與原始任務執行詳單對比可以發現，重規劃過程對突發任務時刻附近的任務進行了重新規劃，其他時刻任務執行情況與原計劃基本一致。

對兩次任務計劃表的約束滿足情況進行分析如圖7～9。圖中，綠線（標記Rated）表示額定約束，藍線（標記Actual）表示重規劃之前，原始執行計劃資源消耗情況，紅色虛線（標記Replan Actual）表示重規劃后執行計劃資源消耗情況。可以發現，在原始執行計劃中，由于突發任務的加入其在通信帶寬上超出額定值，不滿足實際需求。而重新規劃之后，化解了突發任務時刻的資源約束沖突，同時維持了原有計劃的穩定性，驗證了本文重規劃方法的有效性。

為便于了解算法的具體性能，利用本文提出的重規劃方法與文獻［11］中提出的基于啟發式規則的智能優化算法分別對該重規劃算例進行處理，多次運行，平均主要結果數據如表3所示。分析表中數據，本文提出的規劃方法通過合理調整任務的開始時間，得到更高的任務完成率與目標值重規劃結果，但需要消耗更多的時間學習進化完成這一調整過程。

圖6 重規劃任務執行詳單Fig.6 Re-planned m ission list

圖7 任務計劃通信帶寬使用情況Fig.7 Communication bandw idth usage of m ission p lanning

表3 本文方法與文獻［11］中方法對比結果Table 3 Com parison results between themethods in this paper and those in literature［11］

圖8 任務計劃功耗使用情況Fig.8 Power consum ption ofm ission p lanning

圖9 任務計劃散熱功率使用情況Fig.9 Heat dissipation power usage in m ission planning

5 結論

本文通過對空間站任務重規劃問題的研究，結合深度強化學習在智能學習和決策上的優勢，首次實現了基于DDPG算法進行空間站任務重規劃的方法。仿真結果驗證了該方法的有效性，相比于以往結合啟發式規則的智能優化方法，該方法有更強的適應性與智能性。