啟發式前后向鏈條優化組合在軌多目標觀測規劃算法

張晟宇, 孫煜坤, 朱振才, 胡海鷹

(1. 中國科學院微小衛星創新研究院, 上海 201203; 2. 上海微小衛星工程中心, 上海 201203;3. 中國科學院大學, 北京 100039)

0 引 言

隨著敏捷衛星的發展,其姿態機動能力逐步增強,面對突發事件可以通過快速姿態機動完成特定區域指向,以及對多個待觀測點的快速切換[1-4]。衛星在軌可以通過接收其他衛星或者地面注入的先驗引導信息來完成事件驅動的在軌任務實時響應[5-6]。如在山火蔓延時,大幅寬衛星可以獲得多個疑似火點,并將火點信息傳輸到后方敏捷衛星,引導其進行詳查。敏捷衛星一般視場較小,若火點較多,想要在一次過境過程中對多個火點開展有效探測,Liu[7]提出了任務合并的方法，同時需要在軌實時開展觀測序列任務規劃[8-10],并充分合理地調度衛星姿態機動等資源實現較高觀測收益[11-12]。敏捷遙感衛星姿態機動能力提升后,面臨著在軌自主能力不足,無法充分利用姿態機動能力提升觀測能力的問題。高效自主快速的任務規劃方法[13-15],能有效地提升敏捷遙感衛星在軌資源利用效率,增強在軌應用能力。

現在的敏捷衛星具備俯仰、滾動兩個維度的機動能力。在軌接收應急任務時,一次過境有限時間窗口內可以對多個點目標進行觀測。在軌任務規劃應具備:① 實時響應能力,規劃求解方法應在較短時間內獲得滿足任務要求的規劃結果;② 充分利用衛星姿態機動能力達到觀測效益最大化。

敏捷成像衛星任務規劃問題是NP難問題,難以求解。任務規劃問題的指數爆炸特征十分明顯。賀仁杰[16]總結了主要的遙感衛星規劃模型及動態規劃、樹搜索、智能優化、貪婪算法等主要的求解算法,分析了任務規劃求解的特點。其結論是難以建立通用的遙感衛星規劃模型,具體問題需要專門的模型及求解方法。

在規劃算法的實時響應能力方面。陳書劍[17]針對應急規劃問題提出了由自適應免疫算法(adaptive immune algorithm, AIA)和前向動態規劃算法(forward dynamic programming algorithm, FDPA)相結合的分解優化策略進行求解的方法,獲得了較好的時間響應特性,但總體耗時依然較長。孫凱[18]提出了一種基于專家知識的多種啟發式規則,以一種前瞻啟發式算法(look-ahead algorithm,LA)在較短的時間內獲得局部效果最優的規劃效果,但該算法主要解決超過1天的長周期規劃任務序列排序問題,時間響應程度不高。伍國威[19]提出了一種面向在軌實時引導成像的多星自主任務規劃方法,可實時地通過高收益目標替代低收益目標的方式提高整個規劃方案的成像收益,但該方法主要解決多目標向多星系統的分配問題,沒有考慮對于單個衛星姿態機動能力的充分挖掘。姜維[20]提出算法協同進化模型求解技術,引入啟發式信息的遺傳禁忌求解算法,但是同樣存在求解時間較長,規劃目標數量較少的問題。

在充分利用星上資源方面。Han[21]建立了一個敏捷衛星觀測多目標(點目標)的物理模型,基于任務收益的評價和能源及姿態機動的約束,提出基因算法進行觀測序列求解的方法,獲得了較好的收益效果,但可規劃的目標數量較少,同時是以較少的能源消耗作為優化方向的。Mok[22]針對兩個自由度機動能力的衛星,開展對于多個點目標的觀測序列規劃,其主要方法是通過將待觀測目標分類、選擇,并設計一種基于優先級的任務評價函數結合所有觀測時間窗口的沖突消解來進行觀測序列規劃與優化,由于需要計算所有潛在的窗口并多次迭代,算法只能適應不超過10個目標的觀測序列規劃,不適用數量較大的目標規劃。張科科[23]也提出過在分布式衛星任務規劃中將待規劃目標編成序列的方法,也未考慮充分發揮衛星機動能力的設計。何磊[24]在提出的云層遮擋時間窗口的計算方法中增加了預判和二分法推進環節,有效提高了算法的求解效率,但主要是針對無云窗口的組合問題求解。陳金勇[25]構建了多星協同任務規劃組合優化模型,并且建立超啟發式算法求解問題框架,具有一定的面向資源利用模型設計上的啟發性,但主要開展的是多種智能算法的比較,不具備問題針對性。Guo[26]提出了面向姿態、數傳等資源約束的在軌應急求解算法,具有較好的星上可實現性,但只解決了星上不同任務模式的排序組合問題。孫立遠[27]設計了針對導彈目標的基于動態優先級的啟發式算法,能夠克服群體智能算法在模型適配性和實時性方面的缺陷,但存在適配目標較少的問題。

結合以上方法的分析可以看出,對于敏捷遙感衛星的任務規劃算法的研究體現出了非常明顯的問題導向趨勢,不同的具體問題需要相對應的任務規劃策略,不同的時效性要求和優化效益評估也決定了求解方法的選用。針對在軌一次過境多目標的觀測序列規劃問題,沒有針對性的研究。

本文面向具備兩維姿態自由度的敏捷衛星一次過境對100個目標進行觀測序列規劃,提出一種基于啟發式前后鏈條優化組合的點目標觀測路徑序列規劃算法,結合衛星兩維自由度提出了前向鏈條和后向鏈條的鏈條生成策略,再通過鏈條間組合所產生的姿態機動代價決定鏈條間的組合選擇,并在此過程中有選擇地進行鏈條上目標數量的調整。該算法時效性好,星上計算開銷小,有較好的工程可實現性。

1 多目標觀測問題描述

1.1 問題描述

本文主要研究敏捷衛星在軌對大量待觀測目標進行觀測序列規劃的問題。典型場景中寬幅載荷獲得大范圍內多個待觀測的點目標的位置信息和優先級,如圖1所示。后續飛越的敏捷衛星接收這些點目標的位置信息及狀態評估信息,在過境的有效時間內通過在軌規劃,充分利用衛星姿態機動能力實現觀測收益的最大化。

圖1 目標沿衛星航跡分布示意圖

根據敏捷衛星的機動能力,驗證對于目標數量在30～100個之間的觀測路徑規劃能力。目標在分布上應該考慮到其合并情況,即如果兩個目標之間的沿跡向與切跡向的距離,小于目標在此觀測角度的視場的寬度與長度,則可將2個點目標進行合并,以二者連線的點為指向點后,作為一個目標進行規劃。

1.2 任務模型

在該問題中,敏捷衛星的姿態機動能力被定義為具備滾動軸與俯仰軸兩軸的自由度。如果只考慮滾動軸一維的姿態機動能力即一維自由度,則衛星飛越待觀測區域的過程中主要采取的觀測模式只有左右兩側的正側視觀測模式。如圖2所示,一旦衛星飛越目標則衛星不具備對目標的觀測可能性。二維自由度的目標觀測模式下,如圖3所示衛星不但具備滾動向的姿態機動能力,同時具備俯仰軸的機動能力,因此衛星具備在未飛達目標時對目標進行前向觀測,以及在飛越目標之后對目標進行后向觀測的能力,使得衛星擁有更為靈活的觀測模式。

圖2 一維自由度的目標觀測模式

圖3 兩維自由度的目標觀測模式

具備兩個軸向姿態機動自由度的敏捷衛星,不但可以觀測更大的區域,也可延長對同一目標的觀測窗口,因此自主任務規劃可以有效提升兩維自由度敏捷衛星在軌工作的靈活性,滿足更為復雜的任務要求。

本文主要考慮兩個軸向的機動能力來實現前向觀測與后向觀測的在觀測過程中的結合,從而提出本文的主要求解方法:前后向鏈條優化組合方法。該方法在前向觀測時采用連續幾個處于前向觀測的目標組合成為前向的觀測序列,同理將同次后向觀測的目標組合成為后向觀測序列,最后再綜合考慮前后向鏈條的組合,從而形成過境期間的完整觀測序列。

1.3 規劃模型

通過對于衛星在一次過境中對于多目標的觀測收益進行總和計算,對前后向鏈條優化組合的規劃收益進行評價。目標收益函數:

(1)

式中,PI為本次衛星過境的全部目標觀測的總收益;Cn為第n個觀測目標觀測收益;wn為第n個觀測目標的權重,其與觀測收益的乘積作為第n個觀測目標的實際觀測收益;tθ,n為向第n個觀測目標機動花費的滾動向機動時間;tφ,n為向第n個觀測目標機動花費的俯仰向機動時間;k為姿態機動時間消耗權重。該目標收益函數主要的優化方向是盡量優先對于高優先級的目標進行觀測,同時將對向該目標進行姿態機動作為主要的約束條件。

1.4 約束條件

在本文中主要考慮的約束包含敏捷遙感衛星的姿態機動范圍,也就是滾動軸和俯仰軸向上的最大機動角,該約束實際約束了敏捷遙感衛星可以組成觀測鏈條的前后向范圍。

滾動方向約束:

?θn,|θn|≤θmax

(2)

俯仰方向約束:

?φn,|φn|≤φmax

(3)

姿態機動速度約束實際約束的是角度機動所花費的時間。

滾動方向機動時間約束:

(4)

式中,Ωθ,n為滾動向的姿態機動速度;Ωθ,n-max為衛星可以達到的最大滾動向姿態機動速度。

俯仰方向機動時間約束:

(5)

式中,Ωφ,n為俯仰向的姿態機動速度;Ωφ,n-max為衛星可以達到的最大俯仰向姿態機動速度。

為了將問題簡化,將重點用于任務規劃,故這里Ωθ,n,Ωφ,n為平均的滾動向與俯仰向姿態機動速度,不考慮實際在軌過程中的加減速過程。采用較大的姿態機動速度可以獲得較短的姿態機動時間,最短為tθ,n-min與tφ,n-min。最大的姿態機動速度會消耗較大的衛星姿態機動資源,獲得較低的姿態機動時間消耗權重k。在該問題中,主要考慮以衛星本體進行姿態機動的情況,最大的姿態機動速度不超過4° /s;以及以轉臺為指向的情況,角度機動范圍為5°/s～8°/s。

2 前后向鏈條多目標觀測序列規劃算法

2.1 算法設計

前后向鏈條優化組合方法的目標是充分發揮衛星的姿態機動能力,獲得最大化的目標收益。基于以上目標,設計了啟發式算法運行的基本規則。

原則 1優先選取高權重目標原則。wn為第n個觀測目標的權重,最高為1,最低為0,劃分為10個等級。相關權重矩陣默認為星上任務規劃前的前置輸入。該規則下優先安排觀測任務定義價值高的目標。

原則 2鏈條合成的啟發式原則。鏈條的組合以鏈條觀測點收益最大與衛星姿態機動角最小為規則,選擇合成方案。觀測點收益由目標權重決定,鏈條的觀測開銷由觀測鏈條的長度和方向決定。tθ,n為向第n個觀測目標機動花費的滾動向機動時間;tφ,n為向第n個觀測目標機動花費的俯仰向機動時間。兩者定義了兩相鄰觀測點間姿態機動的所需時間。姿態機動的權重k由向第n個觀測目標機動與當前姿態機動方向的比較決定，表達式為

(6)

在本文的仿真場景中,Δθmax=90°,Δφmax=120°。k最大為1,代表衛星在兩個方向上都要改變為完全相反的方向,姿態開銷最大。k最小為0,代表不用改變姿態就能觀測下一點,姿態開銷最小。前向鏈條與衛星運動方向相反,則k值較大,結合姿態機動時間形成總的鏈接開銷。完成組鏈后鏈條方向確定,則下一次迭代依據此方向延伸組合鏈條。

原則3鏈條邊緣點丟棄原則。區域鏈條組合完成后,分別計算兩端各丟棄1點與丟棄2點,返回組鏈后收益最高的組合,形成最終觀測序列。

2.2 算法步驟

算法的流程如圖4所示,具體步驟如下。

步驟 1初始化設置,獲取多目標的經緯度信息、觀測權重及觀測開始點信息、衛星的姿態機動能力、每個點目標觀測收益,作為任務規劃的輸入條件。

步驟 2進行初始鏈條組鏈,選擇本一級觀測權重的目標通過最小自動開銷計算形成包含2個觀測點的元鏈條。

步驟 3元鏈條的兩端搜索最近的鏈條或者孤點,以整鏈收益最高的原則組成新鏈條,若同一鏈條為多組鏈條所選,則選擇收益最高組鏈,如果組成鏈條節點相同,以收益高的方向組鏈條。

步驟 4組鏈后判斷鏈條是否達到局部最優,及是否達到該方向組鏈長度的上限。滿足任意一項則形成局部單條鏈條,準備開始全局鏈條組合。如局部收益不是最優，判斷是否達到上限,如未達上限,則鏈條繼續增長。

步驟 5進行長鏈條組合,如最近鏈接端,姿態開銷較大,收益較低鏈條以丟棄最末節點來組鏈條,計算丟棄1點與丟棄2點,選組合后最大收益完成組鏈。返回收益最大鏈條,如果未超過最大姿態約束則輸出鏈條,如超過,則丟棄兩端代價較大點。

步驟 6輸出觀測序列。

圖4 前后向鏈條優化組合方法規劃流程

2.3 算法時間復雜度分析

假設有n候選觀測目標,每個目標最壞情況下需要嘗試m種鏈條組合方式才能建立鏈接。對于每個點根據組合鏈條的規則進行鏈條組合符合性的計算,計算m次,時間復雜度為O(log2m)。而針對n個候選目標的時間復雜度,需要完整地循環n次,則總的時間復雜度為O(n·log2m)。由此可見,候選觀測目標數量n是影響算法時間復雜度的主要因素,鏈條組合的嘗試次數也對整體的復雜度有影響。

3 仿真校驗

3.1 不同機動能力下觀測路徑分析

仿真衛星軌道高度為800 km,滾動向機動范圍θmax=±45°;俯仰向機動范圍φmax=±60°。

以不同的機動能力設置了不同數量的待觀測目標場景。在場景1中,設置沿星下點航跡兩側500 km內,衛星飛越1 000 km內隨機分布30個目標。以低速姿態機動1°/s,2°/s,3°/s,4°/s為輸入,進行觀測序列路徑的規劃,結果如圖5所示。

圖5 低機動能力下觀測序列規劃結果

以上結果中,紅色的圈點為被選入觀測序列的目標點,藍色圈點為未被選入的觀測點。綠色線條為最終組成的完整鏈條即觀測序列?？v坐標的中心0為星下點的軌跡。

針對同一觀測場景的觀測結果中,在衛星的姿態機動能力較低的情況下,如圖5(a)中衛星具備1°/s的姿態機動能力,在30個待觀測點的情況下,僅完成對10個左右目標的觀測。且觀測目標基本分布在衛星側擺的同一側。從鏈條方向上看,主要為前向鏈條,唯一的后向鏈條只包含2個觀測點。結果表明,衛星在姿態能力較低的情況下,姿態機動能力更適應與飛行方向一致的前向鏈條。

隨著姿態機動能力的增強,在圖5(b)和圖5(c)中,鏈條分布于衛星飛行軌跡的兩側。后向鏈條較少較短。在圖5(d)中開始出現包含3個以上觀測目標點的后向鏈條。表明在衛星姿態機動能力到達4 °/s后可以開展更為靈活的成像觀測任務。同時可以看到在圖5(d)觀測路徑幾乎覆蓋了全部的待觀測目標點,只遺留5個目標點未被觀測。

考慮基于轉臺,具備更高姿態機動能力情況下可以應對目標量更高的場景。因此,設置包含100個目標的場景2進行仿真。在場景2中,設置沿星下點航跡兩側800 km內隨機分布的100個目標。以高速姿態機動為假設場景,分別對姿態機動能力5 °/s,6 °/s,7 °/s,8 °/s輸入對目標進行觀測序列路徑的規劃,結果如圖6所示。圖6(a)和圖6(b),在規劃覆蓋的目標數量上區別較小。姿態機動能力提高之后,鏈條在衛星軌跡兩側的分布更為平均。圖6(c)和圖6(d)中都可見有較多后向長鏈條。其結果與圖5(d)呈現的趨勢是一致的。后向鏈條的增加有助于提高整體觀測序列的觀測收益。

圖6 高機動能力下觀測序列規劃結果

為提高算法的時效性,在仿真中對鏈條的長度進行了約束,如場景1與場景2中都設置了不大于7跳的鏈條長度約束。計算開銷方面30個目標規劃仿真平均規劃計算時間約為50 ms,100個目標規劃仿真平均規劃計算時間約為200 ms。

采用7跳的鏈條長度約束造成一些較佳鏈條未被選擇,如一些分布較為集中的目標。因此,采用打靶的方法對不同的鏈條選擇原則進行了優化。

3.2 打靶分析

場景1與場景2的仿真中采用單一的鏈條長度約束設置,仿真結果中出現了一些比較集中分布的觀測點未被納入觀測序列的情況,基于場景2進行了不同鏈條長度約束下的打靶分析。每種約束下,對于不同的觀測駐留時間,各進行1 000次隨機分布目標的觀測收益計算。鏈條組合打靶分析結果如圖7所示。經過打靶分析,在駐留時間較短的場景下,前向和后向鏈條長度接近的組合方式可獲得高的觀測收益。隨著觀測時間的增加,后向鏈條的長度增加有助于提高觀測效能,效果在增加3～5跳時最為明顯，如圖7中最頂部分所示。在前向鏈條與后向鏈條的長度約束都設置到15次時,觀測收益已呈現出下降趨勢。依據仿真結果,前向鏈條的長度在6～9跳之間,后向鏈條的長度在7～13跳之間組合可以獲得較好的組合收益。鏈條較短時容易遺漏密集分布的觀測目標點。在鏈條較長時,由于最后組鏈時只使用丟棄1點和丟棄2點原則,造成已形成的鏈條難以進一步丟棄影響收益的觀測點。最后,計算開銷方面100個目標規劃仿真平均規劃計算時間約為200 ms,最大不超過300 ms。

圖7 鏈條組合分析

3.3 觀測時間對鏈條的影響

對于不同凝視時間下的鏈條長度的置信度進行分析,分析結果如圖8所示。

圖8 觀測時長分析

圖8(a)中在凝視時間為0.5 s時,結果分布在優于85%的置信區間內,30個目標,選用的鏈條長度應小于7跳;40個目標,選用的鏈條長度應小于10跳;50個目標,選用的鏈條長度應小于11跳。

圖8(b)～圖8(d)中,隨著對于同一個目標點的觀測駐留時間的增加,不同目標數量下的鏈條選用長度都進一步縮減。觀測模式中增加目標凝視模式,適用的鏈條長度縮短。

4 結 論

本文從工程應用出發,針對具備兩個軸向自由度的敏捷遙感衛星在一次過境對多目標的觀測,提出了一種以其姿態機動能力為約束的前后向鏈條優化組合方法。

本文建立了問題模型與目標函數,并完成了前后向鏈條優化組合方法的算法設計。經過仿真表明算法有效,可以依據在軌條件實現實時的觀測路徑規劃。同時在固定鏈條長度約束下,任務規劃方法會導致一些較佳鏈條未被選擇的情況。因此，對鏈條長度進行優化,得出了特定場景下的前后向鏈條長度的選擇區間。最后，考慮了在不同凝視情況下對鏈條長度的選擇影響情況。綜上,前后向鏈條優化組合方法有效,計算開銷在星上條件下都小于1 s,可應用于敏捷衛星面向大量點目標的在軌自主任務規劃應用。未來工作中,需要在鏈條針對目標分布的自適應選擇方面開展進一步的研究。