敏捷成像衛星自主規劃模型與算法*

劉　嵩，陳英武

(1.國防科技大學 信息系統與管理學院， 湖南 長沙　410073；

2. 駐沈陽鐵路局長春軍事代表辦事處， 吉林 長春　130051)

?

敏捷成像衛星自主規劃模型與算法*

劉嵩1,2，陳英武1

(1.國防科技大學 信息系統與管理學院， 湖南 長沙410073；

2. 駐沈陽鐵路局長春軍事代表辦事處， 吉林 長春130051)

摘要：針對敏捷成像衛星自主規劃問題，將規劃、決策、執行和信息反饋相結合，提出星上自主規劃框架，并介紹框架結構和模塊功能。在分析主要約束條件的基礎上，建立基于時間線約束網絡的問題模型。通過將各種衛星動作前后銜接，組合成能夠完成不同任務的動作序列，提出一種面向衛星動作序列的啟發式算法。該算法分為規劃和決策兩個部分，并在衛星執行每一個動作序列的同時基于多種啟發式規則進行規劃，在動作序列執行結束時進行決策。實驗結果表明了自主規劃框架和模型的合理性以及算法的有效性。

關鍵詞：敏捷成像衛星；自主規劃；時間線約束網絡；衛星動作序列；啟發式

敏捷成像衛星與傳統衛星相比具有俯仰、側擺、偏航等姿態機動能力，具有更大的觀測范圍和更強的觀測能力，因此已經成為航天大國競相研制的對象[1-2]。但是在傳統管控模式下，衛星系統所依賴的指揮控制指令都是由地面測控系統發出的，由于測控限制、通信延遲以及受限的通信帶寬和時間窗口等因素存在，即便是敏捷成像衛星也無法在較短的時間內對觀測需求的動態變化做出快速響應。另外，地面控制中心必須通過預測衛星狀態的方式進行任務規劃，所以根本無法避免星上資源的浪費。為解決上述問題且充分發揮敏捷成像衛星的觀測效能，最有效的方式就是減少人的干預，并賦予衛星更多的“智能”，使其能夠根據觀測需求和衛星狀態進行自主規劃[3-4]。

文獻[5-6]對星上自主規劃的可行性進行研究，提出反應慎思型自主規劃結構，設計了一種迭代式隨機貪婪算法，但是沒有考慮任務執行結果對自主規劃過程造成的影響。文獻[7-11]針對EO-1衛星自主規劃問題進行深入研究，但是規劃方法耗時較長，所以應急響應能力較弱。文獻[12]利用迭代修復的方法進行自主規劃，但衛星狀態實時變化，修復時機很難把握，而且每一次規劃的持續時間無法確定。文獻[13]提出了逆向動態規劃方法，但是問題模型比較簡單，沒有考慮衛星動作。

1問題描述與自主規劃框架

星上工作環境隨時間動態變化，主要體現在任務和衛星狀態兩個方面。任務分為觀測任務和數據回傳任務，任務的動態變化是由用戶需求和天氣情況造成的，如用戶隨時可能提出新的任務需求，又或者由于云層遮擋等天氣原因使得某個任務被臨時取消。衛星狀態的動態變化是指衛星每執行一個任務都會對固存、電量等資源造成一定的影響，但影響程度在任務完成之前是無法準確預測的。因此敏捷成像衛星自主規劃問題可以描述為：面對星上動態工作環境，衛星在不需要或較少依靠地面人員干預的情況下，自主為任務指定觀測或回傳時段，并生成衛星可以執行的動作序列指令，在滿足各種約束條件的同時，實現以盡可能少的資源消耗獲得盡可能大的觀測收益。

在星上使用傳統的規劃方式，比如文獻[2]和文獻[14-18]中所使用的方法，將無法解決敏捷成像衛星自主規劃問題。因為這些方法要求衛星必須嚴格執行每一個長周期下的規劃方案，不考慮星上動態環境以及任務執行效果。自主規劃框架能夠實現規劃與執行之間的交叉，邊規劃邊執行，是一種在星上將決策、規劃、執行與信息反饋相結合的設計，該框架由4個功能模塊構成，如圖1所示。決策模塊：負責確定規劃過程結束的時間，并觸發規劃模塊，選擇規劃結果中的部分動作作為決策結果。根據決策觸發時機可以分為普通決策和應急決策。普通決策是指每次產生決策結果之后所觸發的決策。應急決策是指當任務發生變化，或是由于衛星狀態發生變化而導致決策結果無法執行時所觸發的決策。應急決策被觸發時，如果正在進行普通決策，那么普通決策將會被終止，從而進行應急決策。

圖1　自主規劃框架Fig.1　Framework of automatic planning

規劃模塊：負責根據用戶需求、衛星狀態和各種約束條件針對規劃周期內的衛星動作進行規劃。

狀態檢測模塊：負責實時檢測和提供當前衛星狀態信息，如果決策結果不滿足當前星上約束條件，將觸發應急決策；如果滿足，則將決策結果轉換成硬件可執行的動作指令。

執行模塊：負責根據動作指令控制硬件執行，并及時反饋執行結果和參數信息。

2CNT模型

應用CNT建模方法對敏捷成像衛星自主規劃問題進行建模。CNT建模方法是一種基于約束網絡的建模方法，能夠針對離散事件動態系統進行建模，文獻[19-20]對該方法進行了詳細闡述。模型構建考慮了9種敏捷成像衛星動作和5種約束[2]。9種動作分別是觀測、數據回傳、姿態轉換、對日定向、對地定向、相機開機、相機關機、天線開機和天線關機。5種約束分別是時間窗口約束、固存約束、姿態轉換時間約束、星上載荷約束和能量約束。模型描述主要用到以下符號：

1)實驗模擬的開始時間和結束時間分別表示為STA和END；

2)衛星最大固存容量表示為MMmax，電量的上限和下限分別表示為ENmax和ENmin，單位時間充電量表示為Psun，衛星運行、觀測和數據回傳時單位時間耗電量分別表示為Psat，Pob，Pdl，姿態轉換速度表示為MS；

3)待觀測任務集合表示為OB，每個觀測任務o∈OB，占用固存大小表示為SZo，收益值表示為Po，即任務的優先級，觀測和數據回傳時所需要的持續時間分別表示為DOo和DDOo，可用觀測時間窗口數量表示為NOo，每個時間窗口的開始和結束時間分別表示為SOo,k和EOo,k，k∈[1,NOo]，衛星姿態角度表示為ORo，待回傳任務集合表示為DL；

4)衛星可用的數據回傳時間窗口數量表示為ND，每個時間窗口的開始和結束時間分別表示為SDk和EDk，k∈[1，ND]；

5)衛星處于陽照區的時間窗口數量表示為NS，每個時間窗口的開始和結束時間分別表示為SSk和ESk，k∈[1，NS]；

衛星必須依次執行各種動作，動作之間不能重疊，動作在執行過程中必須滿足電量和固存約束，而且任何動作都不能永遠處于執行狀態，衛星的不同狀態會對星上電量造成不同程度的影響：

?i∈[2，h-1],tr∈{obon,ob,oboff,dlon,dl,

dloff,sp,ge,sw}

(tri=1)→((tri+1=0)∧

gei+swi=1)∧(tii=Str)∧(tii+1=Etr)∧

(mmi=mmi-1)∧(0≤mmi≤MMmax)∧

(0≤mmi+1≤MMmax)∧

(eni=eni-1-(tii-tii-1)·Psat)∧

(eni+1=(tii+1-tii)·(spi·Psun-obi·Pob-Psat))∧

(ENmin≤eni≤ENmax)∧

(ENmin≤eni+1≤ENmax))

(1)

觀測動作的開始和結束時間必須在某個觀測任務的某個觀測時間窗口內，動作的持續時間等于該觀測任務所需要的觀測持續時間，動作開始時衛星固存減少：

(2)

數據回傳動作的開始和結束時間必須在某個數據回傳時間窗口內，動作的持續時間等于被回傳任務所需要的數據回傳持續時間，動作結束時衛星固存增加：

(3)

對地定向動作可以在模擬周期內的任意時刻進行，動作執行期間衛星固存不變：

(4)

對日定向動作的開始和結束時間必須在某個陽照區時間窗口內，動作執行期間衛星固存不變：

(5)

姿態轉換動作必須在觀測、數據回傳、對日定向、對地定向這4種動作中的任何一種動作之后連續執行，動作的開始和結束時間由這4種動作的開始時間確定，動作執行期間衛星固存不變：

?i∈[3，h-3],tr∈{ob,dl,sp,ge},

(swi=1)→((swi+1=0)∧

(tri+2=1)∧(tri+3=0)∧(Esw=tri+2-1)∧

(6)

相機(天線)開機動作必須在姿態轉換動作、觀測(數據回傳)動作之前連續執行，相機(天線)開機動作的開始和結束時間由姿態轉換動作的開始時間確定，動作執行期間衛星固存不變：

(7)

相機(天線)關機動作必須在觀測(數據回傳)動作之后連續執行，相機(天線)關機動作的開始和結束時間由觀測(數據回傳)動作的結束時間確定，動作執行期間衛星固存不變：

(8)

觀測(數據回傳)動作之后可能連續執行姿態轉換、觀測(數據回傳)動作，或者相機(天線)關機、相機(天線)開機動作，或者相機(天線)關機、天線(相機)開機動作，或者相機(天線)關機、姿態轉換動作和對日定向動作，或者相機(天線)關機、姿態轉換和對地定向動作：

?i∈[2，h-7],tr∈{ob,dl},

tr′∈{ob,dl}-{tr},tr″∈{sp,ge},

((tri=1)∧(tri+1=0))→(((swi+2=1)∧(swi+3=0)∧

(tr″i+6=1)∧(tr″i+7=0)))

(9)

如果觀測(數據回傳)動作和姿態轉換動作連續執行，說明觀測(數據回傳)動作結束時間與姿態轉換動作的開始時間之間的時間較短而且姿態轉換動作之后將連續執行觀測(數據回傳)動作：

(10)

如果相機(天線)關機動作和相機(天線)開機動作連續執行，說明觀測(數據回傳)動作、相機(天線)關機動作、相機(天線)開機動作、姿態轉換動作和觀測(數據回傳)動作連續執行，而且前一次觀測(數據回傳)動作結束時間與姿態轉換動作的開始時間之間的時間較長：

(11)

對日(對地)定向動作之后可能連續執行姿態轉換、對日定向動作，或者姿態轉換、對地定向動作，或者相機開機動作，或者天線開機動作：

(12)

3算法設計

根據CNT模型可知，衛星動作之間并不是任意銜接的，前一個動作決定了后一個動作。因此本算法將9種衛星動作組合成為4種動作序列，分別是數據回傳動作序列、觀測動作序列、對日定向動作序列和對地定向動作序列。每個動作序列可能包含的衛星動作如表1所示。算法分為規劃和決策兩個階段，規劃結果是由若干個動作序列構成的動作序列組合，而決策結果是指規劃結果中的第一個動作序列，也是本算法的輸出結果，即衛星下一個將要執行的動作序列。每當衛星開始執行一個動作序列時，將啟動算法對下一個規劃周期內的動作序列進行規劃和決策，從而實現執行與規劃同時進行。

表1　動作序列表

為確保衛星每次出地影時都能夠有足夠的電量，算法的規劃周期被設定為從當前正在執行的動作序列的結束時刻至最近一次地影區時間窗口的結束時刻，優化目標為觀測并回傳的任務收益最大化。考慮星上有限的計算能力，求解速度顯得格外重要，因此提出一種基于規則的啟發式算法，算法流程如圖2所示。求解過程分為4個步驟，分別為選擇動作序列、選擇動作、選擇任務和確定動作時間。規劃周期內，算法進行迭代規劃，最終的規劃結果是收益最高的動作序列組合。

步驟1：選擇動作序列。每次以概率p選擇優先級最高的動作序列，這意味著選擇低優先級動作序列的概率為1-p。數據回傳動作序列、觀測動作序列、對日定向動作序列和對地定向動作序列的優先級由前至后，由高至低。

步驟2：選擇動作。選擇動作序列之后，根據前一個動作序列的結束動作和CNT模型約束條件，依據表1確定所包含的具體動作。

圖2　算法流程圖Fig.2　Process of algorithm

步驟3：選擇任務。如果是回傳動作序列將選擇回傳任務，如果是觀測動作序列將選擇觀測任務。選擇回傳任務時，依據概率在兩種規則中選擇一種規則進行任務選擇：一種是按優先級選擇任務，優先選擇高優先級的任務進行回傳，概率為r；另一種是隨機選擇任務進行回傳，概率為1-r。選擇觀測任務時，依據概率在三種規則中選擇一種規則進行任務選擇：一種是按優先級選擇任務，優先選擇高優先級的任務進行觀測，概率為g；第二種是按時間窗口先后順序選擇，優先選擇時間窗口靠前的任務進行觀測，概率為f；第三種是隨機選擇觀測任務進行觀測，概率為1-g-f。步驟4：確定動作時間。如果選擇的是數據回傳任務，選擇當前最早可以使用的回傳時間窗口的開始時間作為動作的開始時間，并根據任務的持續回傳時間確定動作的結束時間。如果選擇的是觀測任務，那么選擇當前最早可以使用的觀測時間窗口的開始時間作為動作的開始時間，并根據任務的持續觀測時間確定動作的結束時間。根據觀測動作或者回傳動作的開始和結束時間可以確定動作序列中其他動作的開始和結束時間。如果選擇的是對日定向或對地定向動作，那么根據前一個動作序列的結束時間可以從前至后依次確定動作序列中各動作的開始和結束時間。對日定向和對地定向動作的持續時間隨機生成。如果無法確定每個動作的開始和結束時間，或者無法滿足模型約束，那么會按照優先級由高至低的順序選擇下一個動作序列。

4實驗結果

本實驗中采用的數據是參照敏捷衛星IKONOS的軌道和姿態性能，由衛星工具箱(Satellite Tool Kit，STK)軟件仿真得到。共設置了6組不同規模的仿真實驗，每組實驗由10個相同規模的仿真實驗構成，采用每組實驗結果的平均值作為最終的實驗結果。實驗模擬24h內的衛星自主規劃情況，期間任務與衛星狀態動態變化，任務收益范圍為1～10。經過反復嘗試，將概率參數p設為0.8，r設為0.8，g設為0.6，f設為0.3較為合理。任務完成率表示觀測并回傳的任務占任務總數的百分比。回傳帶寬資源利用率表示用于回傳數據的時間占全部可用回傳時間窗口總時長的百分比。實驗還將本算法與文獻[2]中的前瞻啟發式算法(Look Ahead algorithm,LA)算法進行對比，對比結果中規劃一次平均耗時表示規劃過程中每迭代一次的平均計算時間。實驗結果如表2所示。

表2　實驗結果

從實驗結果可以看出，雖然隨著任務數量的遞增，任務完成率逐漸下降，但是不同任務規模的任務完成率均能保持在70%以上。之所以會出現下降趨勢，主要是由于任務數量增加的同時加大了任務之間的沖突，而星上資源有限，只能完成部分任務。回傳帶寬資源利用率保持在80%以上，這說明本算法能夠很好地利用回傳帶寬資源，從而減少了資源浪費。之所以沒有達到100%的利用率，主要是由于在規劃過程中觀測、數據回傳、對日定向、對地定向動作交替考慮，所以數據回傳時間窗口不能被整體利用。本算法與LA算法的平均耗時是有明顯差異的。LA算法是針對地面上靜態任務規劃問題而設計的，目的是規劃出一個近似最優解，所以算法規則比較復雜，耗時較長。但當星上環境突然變化時，即便求得近似最優解，也很可能瞬間變為無效解。因此，針對動態環境和較弱的星上計算能力，能夠快速求得一個可行解才是最合適的方式。本算法沒有像LA算法那樣面向動作進行規劃，而是面向動作序列進行規劃，搜索空間被大大減少，且省略了對任務進行規劃的環節，直接規劃動作序列，從而再一次提高了求解效率，因此大大縮短了規劃耗時。

5結論

針對動態環境下的敏捷成像衛星自主規劃問題展開研究，提出星上自主規劃框架和一種與之相適應的啟發式算法，并取得了以下成果：

1)星上自主規劃框架將規劃、決策、執行和信息反饋結合考慮，在控制流程上實現了真正的閉環。因此衛星能夠實時根據任務和衛星狀態進行規劃，充分、合理地利用星上資源。

2)問題的CNT模型能夠更加清晰地描述衛星動作之間的約束關系，為動作與動作序列之間的轉換工作創造了條件。通過對模型的分析，詳細總結每一種動作序列中各種動作的組合情況，并在此基礎上提出面向動作序列的啟發式算法。算法基于多種啟發式規則，能夠在動態環境下快速求得可行解，并及時調整規劃方案。

3)實驗驗證自主規劃框架和模型的有效性，并將算法與LA算法進行比較。實驗結果表明，該啟發式算法不但具有更快的求解速度，而且在不同任務數量的情況下均能表現出較高的性能，從而滿足敏捷成像衛星自主規劃的需求。

參考文獻(References)

[1]郝會成, 姜維, 李一軍, 等. 基于 Multi-Agent 敏捷衛星動態任務規劃問題[J]. 國防科技大學學報, 2013,35(1): 53-59.

HAO Huicheng, JIANG Wei, LI Yijun, et al. Research on agile satellite dynamic mission planning based on multi-agent[J]. Journal of National University of Defense Technology, 2013,35(1): 53-59. (in Chinese)

[2]孫凱, 白國慶, 陳英武, 等. 面向動作序列的敏捷衛星任務規劃問題[J]. 國防科技大學學報, 2012, 34(6): 141-147.

SUN Kai, BAI Guoqing, CHEN Yingwu, et al. Action planning for agile earth-observing satellite mission planning problem[J]. Journal of National University of Defense Technology, 2012, 34(6): 141-147. (in Chinese)

[3]姚敏, 趙敏. 基于模糊神經網絡的小衛星任務自主調度設計[J]. 宇航學報, 2007, 28(2): 385-388.

YAO Min, ZHAO Min. Small satellite task autonomous scheduling design method based on fuzzy neural network[J].Journal of Astronautics, 2007, 28(2): 385-388. (in Chinese)

[4]陳浩, 景寧, 李軍, 等. 基于外包合同網的自治電磁探測衛星群任務規劃[J]. 宇航學報, 2009, 30(6): 2285-2291.

CHEN Hao, JING Ning, LI Jun, et al. An approach for autonomous electromagnetic detection satellite constellation scheduling based on outsourcing contract net[J].Journal of Astronautics, 2009, 30(6): 2285-2291. (in Chinese)

[5]Beaumet G, Verfaillie G, Charmeau M C. Feasibility of autonomous decision making on board an agile earth-observing satellite[J]. Computational Intelligence, 2011, 27(1): 123-139.

[6]Beaumet G, Verfaillie G, Charmeau M C. Decision-making on-board an autonomous agile earth-observing satellite[C]//Proceedings of the 8th International Conference on Automated Planning and Scheduling, Australia, 2008.

[7]Abramson M, Carr F, Carter D, et al. Robust planning for the earth observing-1 (EO-1) mission[C]//Proceedings of AIAA Infotech@ Aerospace Conference, 2009.

[8]Rabideau G, Tran D, Chien S, et al. Mission operations of earth observing-1 with on board autonomy[C]//Proceedings of the 2nd IEEE International Conference on Space Mission Challenges for Information Technology, 2006: 367-373.

[9]Sherwood R L, Chien S, Davies A, et al. Real-time decision making on EO-1 using on board science analysis[C]//Proceedings of the 4th International Asia-Pacific Environmental Remote Sensing Symposium, 2005: 47-55.

[10]Chien S, Sherwood R, Tran D, et al. The EO-1 autonomous science agent[C]//Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, 2004: 420-427.

[11]Sherwood R, Chien S, Tran D, et al. Intelligent systems in space: the EO-1 autonomous sciencecraft [C]//Proceedings of the Infotech@ Aerospace Conference, 2005.

[12]Chien S, Knight R, Stechert A, et al. Using iterative repair to improve the responsiveness of planning and scheduling[C]//Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling, 2000: 300-307.

[13]Verfaillie G, Bornschlegl E. Designing and evaluating an on-line on-board autonomous earth observation satellite scheduling system[C]// Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space, 2000: 122-127.

[14]Grasset-Bourdel R. Interaction between action and motion planning for an agile earth-observing satellite[R]. ONERA, 2009.

[15]Rabideau G, Knight R, Chien S, et al. Iterative repair planning for spacecraft operations using the ASPEN system[C]//Proceedings of Artificial Intelligence, Robotics and Automation in Space,1999, 440: 99.

[16]Grasset R, Verfaillie G, Flipo A. Building a really executable plan for a constellation of agile earth observation satellites[C]//Proceedings of International Workshop on Planning and Scheduling for Space, Germany, 2011.

[17]龐秀麗, 于渤, 姜維. 成像衛星任務周規劃模型與算法[J]. 國防科技大學學報, 2013, 35(5): 44-51.

PANG Xiuli, YU Bo, JIANG Wei. The weekly task scheduling model and solving algorithm of imagining satellites[J]. Journal of National University of Defense Technology, 2013, 35(5): 44-51. (in Chinese)

[18]劉剛, 王建江, 李志猛. 衛星對地觀測任務全周期規劃模型[J]. 國防科技大學學報, 2013, 35(4): 62-66.

LIU Gang, WANG Jianjiang, LI Zhimeng. The model of whole cycle mission planning for satellite observation[J]. Journal of National University of Defense Technology, 2013, 35(4): 62-66. (in Chinese)

[19]Verfaillie G, Pralet C. How to model planning and scheduling problems using timelines[C]// Proceedings of the 18th International Conference on Automated Planning and Scheduling,Australia, 2008.

[20]Pralet C, Verfaillie G. Using constraint networks on timelines to model and solve planning and scheduling problems[C]//Proceedings of the International Conference on Artificial Intelligence Planning and Scheduling, 2008: 272-279.

http://journal.nudt.edu.cn

Model and algorithm of automatic planning for agile imaging satellite

LIUSong1,2,CHENYingwu1

(1. College of Information System and Management, National University of Defense Technology, Changsha 410073, China；

2. The Military Representative Office Stationed in Changchun， Changchun 130051， China)

Abstract：Aiming at the problem of automatic planning for agile imaging satellite, the architecture of automatic planning combined with planning, decision making and information feedback was presented. The architecture, components and functions of automatic planning were introduced. The model based on constraint network on timelines was constructed according to the satellite physical constrains and operational constrains. The activity sequences were constructed through connecting various activities. And a heuristic algorithm based on activity sequences was presented. The algorithm was composed of two parts: planning and decision making. The algorithm could plan based on heuristic rules when satellite was performing every activity sequence, and make decision when the activity sequence was completed. Finally, satisfactory results are obtained through experiments, which show that the architecture of automatic planning and the model are reasonable, and the algorithm is efficient.

Key words：agile imaging satellite; automatic planning; constraint network on timelines; satellite activity sequence; heuristic

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-2486(2015)06-096-07

作者簡介：劉嵩(1980—)，男，吉林吉林人，博士研究生，E-mail：liusongnudt@sina.com；陳英武(通信作者)，男，教授，博士，博士生導師，E-mail：ywchen@nudt.edu.cn

基金項目：國家自然科學基金資助項目(71331008，61203180)；高分辨率對地觀測青年基金資助項目(04060103-5-18)

收稿日期：*2015-01-12

doi:10.11887/j.cn.201506019