啟發(fā)式前后向鏈條優(yōu)化組合在軌多目標觀測規(guī)劃算法

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

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

0 引 言

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

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

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

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

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

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

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

1 多目標觀測問題描述

1.1 問題描述

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

圖1 目標沿衛(wèi)星航跡分布示意圖

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

1.2 任務(wù)模型

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

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

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

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

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

1.3 規(guī)劃模型

通過對于衛(wèi)星在一次過境中對于多目標的觀測收益進行總和計算,對前后向鏈條優(yōu)化組合的規(guī)劃收益進行評價。目標收益函數(shù):

(1)

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

1.4 約束條件

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

滾動方向約束:

?θn,|θn|≤θmax

(2)

俯仰方向約束:

?φn,|φn|≤φmax

(3)

姿態(tài)機動速度約束實際約束的是角度機動所花費的時間。

滾動方向機動時間約束:

(4)

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

俯仰方向機動時間約束:

(5)

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

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

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

2.1 算法設(shè)計

前后向鏈條優(yōu)化組合方法的目標是充分發(fā)揮衛(wèi)星的姿態(tài)機動能力,獲得最大化的目標收益?；谝陨夏繕?設(shè)計了啟發(fā)式算法運行的基本規(guī)則。

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

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

(6)

在本文的仿真場景中,Δθmax=90°,Δφmax=120°。k最大為1,代表衛(wèi)星在兩個方向上都要改變?yōu)橥耆喾吹姆较?姿態(tài)開銷最大。k最小為0,代表不用改變姿態(tài)就能觀測下一點,姿態(tài)開銷最小。前向鏈條與衛(wèi)星運動方向相反,則k值較大,結(jié)合姿態(tài)機動時間形成總的鏈接開銷。完成組鏈后鏈條方向確定,則下一次迭代依據(jù)此方向延伸組合鏈條。

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

2.2 算法步驟

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

步驟 1初始化設(shè)置,獲取多目標的經(jīng)緯度信息、觀測權(quán)重及觀測開始點信息、衛(wèi)星的姿態(tài)機動能力、每個點目標觀測收益,作為任務(wù)規(guī)劃的輸入條件。

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

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

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

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

步驟 6輸出觀測序列。

圖4 前后向鏈條優(yōu)化組合方法規(guī)劃流程

2.3 算法時間復雜度分析

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

3 仿真校驗

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

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

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

圖5 低機動能力下觀測序列規(guī)劃結(jié)果

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

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

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

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

圖6 高機動能力下觀測序列規(guī)劃結(jié)果

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

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

3.2 打靶分析

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

圖7 鏈條組合分析

3.3 觀測時間對鏈條的影響

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

圖8 觀測時長分析

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

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

4 結(jié) 論

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

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