王 歆1,2? 陸 昊1,3 趙海斌1,3 李 彬1,3 夏 炎1,3

(1中國科學(xué)院紫金山天文臺南京210008) (2中國科學(xué)院空間目標與碎片觀測重點實驗室南京210008) (3中國科學(xué)院行星科學(xué)重點實驗室南京210008)

基于0-1線性規(guī)劃的近地天體望遠鏡巡天調(diào)度優(yōu)化?

王 歆1,2? 陸 昊1,3 趙海斌1,3 李 彬1,3 夏 炎1,3

(1中國科學(xué)院紫金山天文臺南京210008) (2中國科學(xué)院空間目標與碎片觀測重點實驗室南京210008) (3中國科學(xué)院行星科學(xué)重點實驗室南京210008)

針對近地天體望遠鏡巡天觀測的特點,將調(diào)度優(yōu)化問題轉(zhuǎn)化為約束優(yōu)化問題.通過引入0-1變量,實現(xiàn)了目標函數(shù)和約束條件的線性化表達,建立了0-1線性規(guī)劃模型.優(yōu)化調(diào)度中不僅考慮了觀測價值的最大化,同時也考慮了觀測資源的消耗.仿真表明,通過模型優(yōu)化可簡便地考慮更多的因素,充分發(fā)揮望遠鏡運行效率.

望遠鏡,方法:實測

1 引言

近地天體望遠鏡是目前我國在國際小行星預(yù)警網(wǎng)絡(luò)(IAWN,International Asteroid Warning Network)中唯一的觀測設(shè)備,采用了1.0 m/1.2 m口徑的施密特光學(xué)系統(tǒng),焦距1.8 m,視場3.14?,主要開展大視場小行星巡天觀測.由于極其出色的觀測探測能力,近地天體望遠鏡投入運行以來也開展了許多其他類型的觀測[1-3],并建立了觀測圖像數(shù)據(jù)庫[4-5].其中大多數(shù)觀測僅僅需要對特定源在比較寬松的時間范圍內(nèi)進行少數(shù)幾次觀測的任務(wù),都安排在巡天任務(wù)間隙共同執(zhí)行.為了提高探測能力,近地天體望遠鏡的探測終端升級成了目前最大的單芯片的CCD相機,盡管讀出速度提高,但由于靶面增大,讀出時間仍然變長.相機在圖像采集中采用了連續(xù)工作模式,一次采集將連續(xù)獲取多張圖像,而終止和啟動這樣的采集過程都有額外的較長時間消耗.如何更好地調(diào)度近地天體望遠鏡的巡天觀測以及和其他觀測需求有機結(jié)合在一起,減少不必要的觀測時間消耗就成為提高近地天體望遠鏡運行效率的關(guān)鍵問題.

長期以來在觀測實踐中,為了節(jié)約觀測時間,近地天體望遠鏡利用相機讀出時間進行望遠鏡擺位,并升級了控制軟件系統(tǒng),實現(xiàn)了全自動的調(diào)度[6],但巡天觀測計劃由于主要依賴工作人員的定性選擇,缺少定量的理論依據(jù),因此無法實現(xiàn)計劃的自動輸入.為了簡化,目前總是選擇相鄰并可循環(huán)連接的天區(qū).同時為了滿足一些其他觀測需求,觀測中常常是終止常規(guī)的巡天計劃,用巡天組間間隙,人工重新將望遠鏡擺位到指定天區(qū)后拍攝圖像,完成觀測任務(wù)后再重新啟動后續(xù)巡天計劃.執(zhí)行時間完全依據(jù)觀測員經(jīng)驗和習(xí)慣.

合理的優(yōu)化調(diào)度是望遠鏡良好運行的前提條件,特別是隨著設(shè)備自動化程度的提高,對調(diào)度優(yōu)化也提出了新的要求,采用數(shù)學(xué)方法對觀測計劃調(diào)度進行優(yōu)化也成為許多國際上大型望遠鏡的常規(guī)研究內(nèi)容.

Palomar Transient Factory(PTF)采用了自動隊列調(diào)度系統(tǒng)(Automated Queue Scheduler),采用鄰視策略(Shortsighted strategy)進行觀測的實時調(diào)度,由于不是優(yōu)化整晚的觀測隊列，這種方法比較適用于對后續(xù)觀測條件以及觀測資源消耗關(guān)注度較小的設(shè)備[7].

而對于哈勃空間望遠鏡(HST,Hubble Space Telescope)和甚大望遠鏡(VLT,Very Large Telescope)等設(shè)備,它們不僅需要最大程度地獲得天文觀測數(shù)據(jù),還需要考慮觀測資源的消耗,因此將調(diào)度問題考慮為一個具有多重約束的復(fù)雜調(diào)度問題.HST首先采用了基于神經(jīng)網(wǎng)絡(luò)的優(yōu)化算法[8],Space Telescope Science Institute在為HST的優(yōu)化調(diào)度軟件開發(fā)中,形成了一個框架系統(tǒng)—Spike planning and scheduling software,并成功應(yīng)用于Chandra Advanced X-Ray Astrophysics Facility(AXAF)、Space InfraRed Telescope Facility(SIRTF)、VLT、VLBI Space Observatory Program(VSOP)以及Subaru Telescope等[9-16].

開源的RTS2(Remote Telescope System 2nd Edition)系統(tǒng)原先采用一個簡單的價值函數(shù)對計劃進行優(yōu)選,后也改進為采用遺傳算法進行優(yōu)化調(diào)度[17].

望遠鏡調(diào)度優(yōu)化被認為是一個NP-Hard(Non-deterministic Polynomial Hard)問題,因此啟發(fā)式算法在望遠鏡調(diào)度中有很廣泛的應(yīng)用,例如鄰域搜索法(Neighbourhood Search Method)和遺傳算法[18].

望遠鏡調(diào)度優(yōu)化勢必與其運行的具體情況密切相關(guān),上述工作也都針對具體應(yīng)用的觀測模式和設(shè)備運行狀態(tài)進行了特別的研究.本文針對近地天體望遠鏡巡天觀測模式下的調(diào)度優(yōu)化問題做了初步探索,采用0-1線性規(guī)劃刻畫了巡天調(diào)度的數(shù)學(xué)模型,實現(xiàn)了適合近地天體望遠鏡運行實際情況的優(yōu)化策略,模型求解則可通過成熟的整數(shù)線性規(guī)劃算法以及軟件包實現(xiàn).

2 巡天模式

近地天體望遠鏡根據(jù)望遠鏡的視場將全天以天球赤道坐標(α,δ)為索引分為4 772個固定天區(qū),巡天觀測時對于任何觀測時間選擇觀測源所在的固定天區(qū)實施觀測.

對于小行星巡天,與傳統(tǒng)觀測略有區(qū)別,它需要通過對同一個天區(qū)的一定間隔的重復(fù)觀測來識別移動的小行星.近地天體望遠鏡目前采用了3次重復(fù)天區(qū)的方式,即對同一個天區(qū)以固定時間間隔重復(fù)觀測3次,通過3幅觀測圖像的比對找出候選小行星.觀測中,在得到一張觀測圖像后,利用CCD相機的讀出時間,望遠鏡擺位到下一個觀測天區(qū),對于目前采用的CCD相機,望遠鏡擺位時間必須在26 s內(nèi),因此相鄰時間的觀測天區(qū)跨度不能太大.

為了便于人工排列計劃,目前多數(shù)采用了1組約20個天區(qū)的觀測方式,曝光時間60 s,對20個天區(qū)循環(huán)3次,為了使得相鄰觀測天區(qū)跨度符合擺位要求,只能選擇相互循環(huán)相連的整片天區(qū).

事實上,每個天區(qū)的觀測價值不同,每個天區(qū)地平方位和高度坐標(A,h)隨時間在變化,導(dǎo)致觀測效果不同,以及不同相位角區(qū)域理想的重復(fù)時間也不同.這些因素如完全依賴人工調(diào)度,難以考慮,從而使得設(shè)備的效率發(fā)揮尚不充分.

對于只需對特定源進行觀測的任務(wù),由于觀測時間以及重復(fù)性沒有特殊要求.目前近地天體望遠鏡在巡天組間進行這類觀測,主要是為了不破壞人工排列的巡天計劃,但從設(shè)備運行角度,總希望這樣的觀測和巡天計劃可有機融合,在巡天過程中能直接執(zhí)行這些觀測,從而減少望遠鏡附加移動和CCD相機的重新啟動,節(jié)約觀測時間.

3 數(shù)學(xué)模型

觀測調(diào)度是一個典型的約束優(yōu)化問題,滿足各類條件情況下,如何獲得最佳的觀測方案.通過上述分析,近地天體望遠鏡巡天任務(wù)和傳統(tǒng)天文觀測任務(wù)有所區(qū)別,對于一個天區(qū),需要完成若干次觀測,科學(xué)價值只有完成全部圖像采集后才能發(fā)揮;考慮到CCD相機的工作模式,相鄰天區(qū)的距離必須小于讀出時間內(nèi)望遠鏡的移動距離,因此望遠鏡的移動距離不能作為優(yōu)化變量考慮,而必須是對可行域的約束.

對于觀測計劃而言,首要考慮的是觀測科學(xué)價值最大化.各個天區(qū)的觀測價值一般用適應(yīng)度( fi tness)來表示,適應(yīng)度越大表示觀測價值越高,換言之在調(diào)度中被優(yōu)先實施.各天區(qū)的適應(yīng)度和許多因素相關(guān),包括:觀測時的地平高度、與黃道面的距離、天光背景情況(主要和月光相關(guān))、歷史觀測情況以及觀測任務(wù)的重要程度等,這些量中有些是天區(qū)固有的屬性,有些是與時間相關(guān)的,天區(qū)的適應(yīng)度取值可根據(jù)經(jīng)驗和具體觀測需求確定,但時間確定后,天區(qū)適應(yīng)度都是確定的.

定義總的天區(qū)集合為S={si,i=1,2,···,N},觀測的時間窗口集合為T={ti,i= 1,2,···,NT},共NT個窗口,ti按時間順序排列.各窗口的開始時刻定義為W(t),是已知的.適應(yīng)度為天區(qū)s和時間窗口t的函數(shù)F(t,s).對于巡天觀測而言,需要確定的是每個可觀測的時間窗口觀測哪個天區(qū).巡天優(yōu)化調(diào)度轉(zhuǎn)換為指派問題,可直觀表達為圖1的形式.圖中每1列對應(yīng)1個時間窗口,每1行對應(yīng)1個天區(qū),每個格子中的數(shù)值代表該格子的價值.調(diào)度就是在圖中按照一定規(guī)則選格子,每列至多選擇1個格子,每行選擇3個格子或者不選擇;相鄰兩列選擇的格子距離不能太遠,每行選擇的各個格子之間距離也要滿足一定要求,例如圖1中灰色格子就構(gòu)成了1個可行的調(diào)度方案.這樣的可行選擇有很多,評判選擇優(yōu)劣的標準是選中的格子數(shù)值和最大,優(yōu)化目標就是找到最優(yōu)的調(diào)度方案.

將上述問題轉(zhuǎn)換為數(shù)學(xué)模型,為了便于建立線性條件,定義決策變量dtofk∈{0,1},其中t∈T,o∈S,f∈S,k∈{1,2,···,NK}.k用于表示小行星巡天輪次,NK是需要的輪次,對于近地天體望遠鏡NK=3.例如d1361=1表示在t1時間窗口觀測s3天區(qū),是該天區(qū)的首輪觀測,下一個時間窗口,即t2觀測s6.

令當晚巡天的候選天區(qū)集合為Ss,非巡天觀測任務(wù)所需天區(qū)為So,Ss∩So=?.同時引入天區(qū)集合S0,該集合中只有一個元素即0號天區(qū)s0,這個天區(qū)是一個虛擬的天區(qū),觀測s0表示該時段空閑.對于調(diào)度而言總的可觀測天區(qū)為Sa=So∪Ss∪S0.

圖1 調(diào)度問題的示意圖Fig.1 The sketch of the scheduling problem

根據(jù)上述變量定義,可以建立巡天調(diào)度的數(shù)學(xué)模型,目標函數(shù)為最大化觀測總適應(yīng)度:

根據(jù)前面分析的巡天觀測模式逐一建立約束條件.由于引入了虛擬的s0天區(qū),每個時間窗口必須觀測1個天區(qū),有:

其中s.t.為subject to的縮寫,表示該式為約束條件.此外,決策變量中包含了下一個時間窗口的觀測天區(qū),必須約束:

其中Sub表示取下標,t′是按時間順序t的下一個元素.對于巡天天區(qū)在每個輪次至多觀測1次,有:

巡天天區(qū)只有觀測NK次才能發(fā)揮有效作用,安排少幾次則沒有意義,因此要么安排NK次,或者完全不安排,有:

NK輪巡天中后面的輪次必須在前面輪次之后觀測,有:

考慮到對于巡天天區(qū)重復(fù)間隔時間有一定要求,時間太短移動目標不足以區(qū)分,對于每個天區(qū),令重復(fù)時間必須在[(L(s),U(s)],s∈Ss,上述約束條件(6)式可直接變?yōu)?

和

至此,關(guān)于巡天天區(qū)的約束條件均已建立.對于其他天區(qū),沒有輪次問題,約束:

以及非巡天天區(qū)一般限制觀測不超過約定上限M(o),有:

由于望遠鏡運動速度有限,相鄰兩次觀測的天區(qū)跨度不能太大,定義L(so,sf)為兩個天區(qū)之間的距離,so∈S,sf∈S,顯然有L(so,sf)=L(sf,so).根據(jù)望遠鏡移動速度和相機讀出時間可以求得相鄰天區(qū)的最大間隔Lm.

特別約定s0和任意天區(qū)都是可以往返的,因此上述約束條件對s0并無限制.最后為了保持一致性,約束最后時刻觀測的下一個觀測天區(qū)為s0:

至此已給出了所有的約束條件,最大化(1)式即可得到觀測適應(yīng)度最好的觀測方案.

在獲得觀測適應(yīng)度最好的觀測方案后,可進一步優(yōu)化得到望遠鏡移動距離最小的觀測方案,此時將(1)式作為約束條件,不難得到新的目標函數(shù):

近地天體望遠鏡巡天觀測已全部轉(zhuǎn)換為數(shù)學(xué)模型,模型中較全面地考慮了各種因素,特別是一些在人工排列中難以考慮從而簡化的因素,都被完整地考慮進模型.在觀測實踐中總會遇到對時間有一定要求的觀測需求,通過對dtofk的約束很容易將這類需求引入模型之中.事實上只需要對F(t,s)取值合理也可達到同樣目的,例如對于不能夠?qū)嵤┯^測的時間–天區(qū)對,可設(shè)置其對應(yīng)的適應(yīng)度F＜F(t,s0),這樣上述模型不需任何變化即可滿足需求.

從所有的數(shù)學(xué)條件不難看出,所有的條件均為線性條件,沒有決策變量的高階項,因此可行域是凸的,便于大規(guī)模問題的求解.同時決策變量d∈{0,1},通過0-1變量的使用,將望遠鏡在相鄰時間窗口的移動距離等非線性量都轉(zhuǎn)化為了線性表達.因此本文建立的模型為0-1線性規(guī)劃模型.

4 仿真試驗

為了驗證本文提出的模型,進行了仿真試驗.考慮3輪巡天,共有連續(xù)的30個時間窗口.候選天區(qū)為:S0={0},So={1},Ss={2,4,6,8,10,12,14,16};對各天區(qū)F取了定值,F(t,0)=?1,F(t,1)=1,?t;F(t,s)=2,?t,s∈Ss;時間窗口為等長,取W(ti)=i;仿真中只有一個非巡天天區(qū),取M(1)=2.各天區(qū)之間的距離L取值見表1.表中m,n分別表示起止天區(qū)編號.L(0,0)＜L(0,n),n?=0以及L(0,0)?=0是為了在優(yōu)化過程中可以使得s0天區(qū)盡可能連續(xù),減少間斷次數(shù).優(yōu)化中約定望遠鏡只能擺位到距離為1的天區(qū), LM=1.

由于采用了0-1線性規(guī)劃模型,模型可通過標準的數(shù)學(xué)規(guī)劃語言表達,并通過求解軟件求解.在仿真試驗中,采用GLPK1http://www.gnu.org/software/glpk/(GNU Linear Programming Kit)軟件包定義的MathProg語言編寫了模型,并通過該軟件包將模型轉(zhuǎn)化為線性規(guī)劃標準的MPS (Mathematical Programming System)格式.求解采用了Gurobi2http://www.gurobi.com(版本5.6.3)軟件的免費學(xué)術(shù)版.

巡天的重復(fù)時間間隔在仿真中做了統(tǒng)一約定,模擬了兩種情況.當重復(fù)時間比較寬松,[(L(s),U(s)]取[7,15]時,經(jīng)兩步優(yōu)化得到的觀測適應(yīng)度為46,最短路徑為55,具體結(jié)果為:

經(jīng)直觀驗證可知該結(jié)果為最優(yōu)結(jié)果,符合預(yù)期.說明模型表達正確有效.優(yōu)化結(jié)果中s0都連續(xù)排列在最后,這和之前L取值時的考慮完全吻合.

表1 各天區(qū)的距離表Table 1 The distances between each two sky areas

當重復(fù)時間選取較小,[(L(s),U(s)]取[7,9]時,優(yōu)化結(jié)果為:

觀測適應(yīng)度仍為46,最短路徑也為55.

仿真表明通過數(shù)學(xué)模型表達,當一些條件發(fā)生變化時,只需要對模型參數(shù)進行調(diào)整即可繼續(xù)求得最優(yōu)解,十分便捷,也適合自動處理.當約束條件發(fā)生變化時,通過數(shù)學(xué)求解往往可以克服各種約束條件的限制,使得調(diào)度效益可以和弱約束甚至無約束情況下保持一致.

5 討論與展望

本文將近地天體望遠鏡巡天調(diào)度處理為約束優(yōu)化問題,通過選擇決策變量為0-1變量,使得約束條件和目標函數(shù)均為線性條件.0-1線性規(guī)劃模型作為一種經(jīng)典的模型,有許多成熟的求解算法和軟件包,極大地方便了在望遠鏡運行中的應(yīng)用.優(yōu)化著眼于觀測的整體情況,符合小行星巡天的任務(wù)特點.

本文只是對近地天體望遠鏡巡天策略進行了初步探索,近地天體望遠鏡還開展了多樣的觀測任務(wù),例如小行星的光變曲線觀測、反銀心方向巡天等,如何將這些觀測需求和巡天任務(wù)相互融合還有待進一步探索.

此外,隨著時域天文的興起,ToO(Target of Opportunity)觀測在近地天體望遠鏡觀測中越來越多,和巡天觀測快速融合實現(xiàn)實時調(diào)度也是重要的方向.

采用數(shù)學(xué)方法進行望遠鏡調(diào)度,不僅有利于充分利用望遠鏡觀測資源,發(fā)揮設(shè)備效率,也能更好地支持無人值守的全自動觀測.隨著望遠鏡機電能力的提高,以及觀測任務(wù)的多樣性與實時性要求的提高,優(yōu)化調(diào)度勢必發(fā)揮更大的作用.

參考文獻

[1]李彬,趙海斌.天文學(xué)報,2012,53:240

[2]Li B,Zhao H B.ChA&A,2013,37:97

[3]葉嘉暉,趙海斌,李彬.天文學(xué)報,2015,56:243

[4]王歆.天文學(xué)報,2013,54:382

[5]Wang X.ChA&A,2014,38:211

[6]王歆,趙海斌,夏炎,等.天文學(xué)報,2015,56:178

[7]Cenko S B,Fox D B,Moon D S,et al.PASP,2006,118:1396

[8]Josnston M D,Adorf H M.Computers and Operations Research,1992,19:209

[9]Johnston M,Miller G.Intelligent Scheduling.San Francisco:Morgan-Kaufmann,1994:391

[10]Miller G,Bose A.ASP Conference Series,adass V,1996,101:467

[11]Giuliano M.ASP Conference Series,adass VII,1998,145:271

[12]Foor L Z,Asson D J.Spike:A Dynamic Interactive Component in a Human-Computer Long-range Planning System.3rd International NASA Workshop on Planning and Scheduling for Space,Houston, October 27-29,2002

[13]Chavan A M,Giannone G,Silva D,et al.ASP Conference Series,adass VII,1998,145:255

[14]Giannone G,Chavan A M,Silva D R,et al.ASP Conference Series,adass IX,2000,216:111

[15]Meier D L,Fomalont E B.AdSpR,2000,26:629

[16]Sasaki T,Kosugi G,Kawai J A,et al.Proceedings of SPIE,2000,4009:350

[17]Kubanek P.Genetic Algorithm for Robotic Telescope Scheduling.Granada:Universidad de Granada, 2008

[18]G′omez de Castro A I,Y′a?nez J.A&A,2003,403:357

0-1 Linear Programming for CNEOST Survey Scheduling

WANG Xin1,2LU Hao1,3ZHAO Hai-bin1,3LI Bin1,3XIA Yan1,3
(1 Purple Mountain Observatory,Chinese Academy of Sciences,Nanjing 210008) (2 Key Laboratory for Space Object and Debris Observation,Purple Mountain Observatory,Chinese Academy of Sciences,Nanjing 210008) (3 Key Laboratory of Planetary Sciences,Purple Mountain Observatory,Chinese Academy of Sciences,Nanjing 210008)

Survey scheduling of the CNEOST(China Near Earth Object Survey Telescope)is studied as a constrained optimization problem.Employing the 0-1 variables,both the objective functions and constraints in the model are linearized,and the 0-1 linear programming model is constructed.For the optimization,not only the scienti fi c productivity of the observation but also the consume of observing resources are considered.Simulations show that with the model,more factors can be dealt with conveniently,and the observation efficiency will be improved.

telescopes,methods:observational

P111;

:A

2014-11-21收到原稿,2014-12-30收到修改稿

?國家自然科學(xué)基金項目(11373072,11273067)、江蘇省自然科學(xué)基金項目(BK2011890)和小行星基金會資助

?wangxin@pmo.ac.cn

10.15940/j.cnki.0001-5245.2015.04.009