張開元, 夏小云, 張先超, 江海, 劉靜, 廖偉志
(1. 江西理工大學理學院, 贛州 341000; 2. 嘉興學院信息科學與工程學院, 嘉興 314001;3. 嘉興學院信息網絡與智能研究院, 嘉興 314001; 4. 中國科學院國家天文臺, 北京 100012)
1957年10月蘇聯將第一顆人造衛(wèi)星“Sputnik 1” 送入太空, 在過去的六十六年時間里, 由于人類各種空間活動產生了數以億計的空間碎片, 這些碎片主要包括完成任務的火箭、 衛(wèi)星、探測器、 載人飛船的殘骸以及空間物體碰撞產生的碎片等, 是空間環(huán)境的主要污染源, 如圖1 所示。 根據美國國家航空航天局(NASA) 約翰遜航天中心軌道碎片項目辦公室 (Orbital Debris Program Office) 的統(tǒng)計數據顯示[1], 截至2023年2月3日, 地球軌道上的太空碎片, 從1966年的大約2000 個上升到2023年的近27000 個, 如圖2所示。 大量空間碎片的存在增加了撞擊甚至摧毀正常在軌衛(wèi)星的概率, 而且不同碎片的高速碰撞將產生大量新的空間碎片, 對人類和航天器將產生巨大的威脅。 當前太空碎片還在不斷增加, 倘若不采取有效措施, 太空碎片將布滿整個軌道。減緩空間碎片的增長速度, 清理已有的太空碎片, 是全球各國共同面臨的挑戰(zhàn)和難題[2]。
圖1 空間碎片Fig.1 Space debris
圖2 地球軌道上各類空間碎片數量統(tǒng)計Fig.2 Number of cataloged objects in Earth orbit by object type as of 03 February 2023
當前聯合國、 IADC、 ESA 等國際組織相繼制定各項太空行為準則, 對各國的太空活動進行約束和規(guī)范, 避免人為原因產生更多的碎片。 我們國家也設立了專門的“空間碎片行動計劃”, 成立了太空碎片協(xié)調組和專家組, 全面開展空間碎片研究工作, 不斷加強太空碎片的監(jiān)測。 當前應對空間碎片的主要措施包括主動清除、 離軌和棄置策略、 監(jiān)測和預警以及碰撞規(guī)避和防護。 對空間碎片進行觀測、 跟蹤和編目, 從而進行碰撞預警是降低空間碎片撞擊風險的關鍵。 太空望遠鏡觀測是一種典型的空間碎片觀測跟蹤方法。
為了更好地利用好已有望遠鏡觀測資源, 減少望遠鏡的觀測時間和成本, 最大程度提升望遠鏡使用效率, 望遠鏡的觀測調度就成為了關鍵。望遠鏡的觀測調度是將觀測任務和觀測資源進行合理安排的過程。 望遠鏡的調度問題實際上就是資源調度問題, 需要考慮多方面的因素。 在實際的望遠鏡觀測中, 觀測目標的可見性, 觀測目標的優(yōu)先級, 都是望遠鏡調度需要考慮的問題。 合理的望遠鏡調度能夠充分利用觀測時間, 獲得較好的觀測質量, 提升觀測效率。
目前空間碎片監(jiān)測網絡定期跟蹤、 編目的碎片超過3.1 萬個, 毫米級以上空間碎片總數達到上億個, 地球軌道人造物體的總質量超過了9000t。 鑒于空間碎片對航天器運行安全的危害以及近地天體對地球可能造成的撞擊威脅, 各國對空間碎片監(jiān)測預警需求不斷提高[3-5]。 為了滿足空間觀測的需求, 世界各國不斷建造空間觀測設備[6-8]。 2016年, 我國自主建設的世界上最大最靈敏的單口徑射電望遠鏡 (Five-hundred-meter Aperture Spherical radio Telescope, FAST) 全面建成投入使用, 研究人員將問題建模為最小成本最大流量問題, 設計了一種基于最大匹配邊緣檢測的方法來減小問題規(guī)模, 并提出了一種回溯算法最小化最優(yōu)調度的轉換成本[8]。 相比于單個望遠鏡, 望遠鏡陣列通過將多個望遠鏡同步使用, 使得觀測精度與距離大大提高。 2019年, 平方公里射電陣(Square Kilometre Array, SKA) 已全面投入使用, 是目前世界上最大規(guī)模的最復雜的射電望遠鏡陣列, 其對望遠鏡調度算法的性能需求也更高[9-10]。
太空望遠鏡調度問題具有多約束、 多目標等特點, 其相當于使用m臺望遠鏡對n個獨立觀測目標進行觀測處理, 等價于作業(yè)車間調度問題[11], 也被視為一類NP 難問題。 當觀測的目標數較大, 望遠鏡的分配方式數量也非常大, 問題求解時間往往呈指數級增長。 當前望遠鏡調度問題求解方法主要分為確定性方法和近似方法。 確定性方法主要包括線性規(guī)劃、 二次規(guī)劃和動態(tài)規(guī)劃方法, 適合于求解問題規(guī)模比較小的情形。 近似算法主要包括局部搜索、 貪心算法和啟發(fā)式優(yōu)化算法等, 適用于求解問題規(guī)模較大的情形, 通常考慮在合理的計算時間內找到滿意的調度方案。
針對空間碎片和近地小行星編目的不同觀測范圍、 精度、 時效等要求, 研究望遠鏡陣列調度模型與算法, 形成適用于具體應用場景的調度策略是也是當前研究熱點。 對于大規(guī)模的望遠鏡陣列, 如何設計合理的調度分配方案來調度空間望遠鏡陣列中的單個望遠鏡分別完成觀測, 從而得到連續(xù)性更好的觀測數據, 更進一步地提升對空間碎片的觀測性能同樣是一個重要的研究任務。
太空望遠鏡的調度過程是一個非常復雜的過程。 在不同的應用場景下如觀測設備的不同、 觀測需求的不同, 就會衍生出不同的調度問題。 此外, 望遠鏡觀測的良好運行離不開算法合理的優(yōu)化調度。 隨著觀測設備的自動化程度不斷提高,設備對調度優(yōu)化算法的性能需求也隨之增加, 采用不同算法優(yōu)化觀測計劃也是學界研究的熱點[12]。 望遠鏡的調度優(yōu)化依賴于實際的應用場景執(zhí)行。 針對不同的觀測模式和觀測設備, 國內外學者也提出了不同的望遠鏡觀測調度模型。 望遠鏡調度問題本質是一個帶有約束的組合優(yōu)化問題, 總體的目標是要提升望遠鏡觀測利用率, 使得望遠鏡觀測效率最大化。 本章節(jié)圍繞望遠鏡調度的單目標優(yōu)化、 多目標優(yōu)化以及觀測模式不同, 給出了幾個常見的望遠鏡調度模型以及求解該類型問題的常用算法。 對應不同問題的求解,望遠鏡調度算法大致分為三類: 一類是確定性算法, 包括線性規(guī)劃和整數規(guī)劃等; 第二類是啟發(fā)式算法; 第三類是基于機器學習的求解方法。
線性規(guī)劃是一種在線性約束條件下, 求解線性目標函數極值的常用的數學方法, 屬于確定性算法。 線性規(guī)劃方法在望遠鏡觀測調度問題求解上也獲得了廣泛應用。 與求解許多組合優(yōu)化問題相同, 研究人員將望遠鏡觀測調度問題抽象為一個整數線性規(guī)劃模型, 將該模型輸入求解軟件中使用優(yōu)化器求解[12-16]。
2015年, 王歆等人針對近地天體望遠鏡巡天觀測問題建立了0 -1 線性規(guī)劃模型[12]。 該模型以觀測科學價值最大化為目標, 通過引入0 -1 變量實現了目標函數和約束條件的線性表達。
定義天區(qū)集合為S ={si,i =1,2,3...N} ,觀測時間窗口集合為T ={ti,i =1,2,3...Nt} ,共Nt個窗口,ti按時間順序排列, 已知窗口的開始時刻為w(t) 。 由天區(qū)s和時間窗口t可計算得到適應值函數F(t,s) 。
定義決策變量dtofk∈{0,1} , 其中t ∈T、o∈S、f∈S,k∈{1,2,... ,Nk} 。k用于表示小行星巡天輪次,NK是需要的輪次。 近地天體望遠鏡巡天需要3 輪。d1361=1 表示為: 在t1時間窗口觀測s3天區(qū), 下一個時間窗口t2觀測s6天區(qū)。 巡天的候選天區(qū)集合為Ss, 非巡天觀測任務所需天區(qū)為So,Ss∩So = ?。 引入虛擬天區(qū)S0, 觀測S0表示該時段空閑。
根據上述變量的定義, 建立巡天調度的數學模型, 最大化科學觀測價值的目標函數如下:
模型的約束條件如下:
1) 由于引入了虛擬天區(qū), 每個時間窗口都要有天區(qū)被觀測, 下一個時間窗口的觀測天區(qū)由決策變量決定。
2) 每個輪次至多觀測一個巡天天區(qū)一次,巡天天區(qū)只有觀測NK次才有效, 后面的巡天輪次必須在前面的巡天輪次之后觀測, 對非巡天天區(qū)無輪次約束。
3) 非巡天天區(qū)一般限制觀測不超過約定上限。
4) 由于望遠鏡運動速度有限, 兩天區(qū)間的跨度不能太大。
5) 最后為了保持一致性, 約束最后時刻觀測的下一個觀測天區(qū)為S0。
最大化觀測科學價值的同時, 進一步優(yōu)化使切換天區(qū)時距離最小, 此時將式作為約束條件,不難得到新的目標函數:
在實現了問題的線性化表達后, 王歆等人采用GLPKl (GNU Linear Programming Kit) 軟件包定義的MathProg 語言編寫了模型, 并通過該軟件包將模型轉化為線性規(guī)劃標準的MPS (Mathematical Programming System) 格式, 并采用Gurobi2 軟件進行求解。 試驗結果表明當模型中一些約束條件發(fā)生變化時, 通過數學方法仍可以獲得最優(yōu)解。
為了清晰的介紹上文目標函數的計算過程在此引用文獻[12] 中的例子。 巡天觀測需要確定每個可觀測的時間窗口觀測哪個天區(qū), 即將巡天優(yōu)化調度轉換為指派問題。 如圖3 所示。
圖3 調度問題的示意圖Fig.3 The sketch of the scheduling problem
圖中每1 行對應1 個天區(qū), 每1 列對應1 個時間窗口, 每個格子中的數值代表該格子的觀測價值。 調度就是按照特定規(guī)則在圖中選取格子,每列至多選擇1 個格子, 每行選擇3 個格子或者不選擇; 相鄰兩列選擇的格子距離不能太遠, 每行選擇的各個格子之間距離也要滿足一定要求,例如圖3 中灰色格子就構成了1 個可行的調度方案。 這樣的可行調度方案有很多, 可行調度方案選中的格子數值之和越大, 調度方案越優(yōu)秀。 問題的優(yōu)化目標為找到最優(yōu)的調度方案。
根據圖3 中的問題實例和調度方案, 函數的總觀測價值等于將所有灰色格子中的值相加。 具體過程如下:
1) 根據調度方案得到每一時刻觀測的天區(qū)和其對應的觀測價值。t1時刻觀測s4天區(qū)觀測價值為1;t2時刻觀測s2天區(qū)觀測價值為2;t3時刻觀測s1天區(qū)觀測價值為3;t4時刻觀測s4天區(qū)觀測價值為4;t5時刻觀測s2天區(qū)觀測價值為2;t6時刻觀測s1天區(qū)觀測價值為4;t7時刻觀測s2天區(qū)觀測價值為2;t8時刻觀測s4天區(qū)觀測價值為4;t9時刻觀測s1天區(qū)觀測價值為4。
2) 將上述觀測價值相加總和即為總觀測價值。 即總觀測價值為1+2+3+4+2+4+2+
4+4=26 。
3) 調度過程中望遠鏡的移動距離, 根據各天區(qū)間的距離表計算。 假設各個天區(qū)間的距離如表1 所示。
表1 各天區(qū)距離表Table 1 The distances between each two sky areas
望遠鏡移動路徑為s4→s2→s1→s4→s2→s1→s2→s4→s1, 得到對應路徑之和為2+1+2+2+1+1+2+2=13 。
Sabol、 Alimo 和Kamangar 等人[14]研究了一種混合整數線性規(guī)劃方法用于求解美國國家航空航天局(NASA) 的深空網絡(Deep Space Network,DSN) 調度問題, 他們通過DSN 數據實驗驗證了算法的有效性。 在該工作的基礎上, Claudet、Alimo 和Goh 等人[15]提出了一種改進版的混合整數線性規(guī)劃方法Δ -MILP, 他們通過引入新的約束集來提供滿足DSN 需求且更加可行的調度方案, 同時能夠優(yōu)先考慮特殊的調度任務。 實驗結果表明所提的Δ-MILP 方法能夠較好地滿足調度需求。
戴偉等人[16]將射電望遠鏡短期觀測編排問題建模為混合整數線性規(guī)劃問題, 并以望遠鏡尋址時間最小化作為問題的目標函數。 通過使用Gurobi9.1 求解器進行問題求解, 試驗結果表明能夠較好地滿足射電望遠鏡的短期觀測編排需求。
線性規(guī)劃方法使用方便, 只需將問題抽象為整數線性規(guī)劃模型, 能夠在小規(guī)模問題上快速求得最優(yōu)解。 但隨著問題規(guī)模的增大, 計算量也隨之增加, 使用線性規(guī)劃求解就變得更困難。
望遠鏡觀測空間碎片的調度過程中, 實際上需要考慮多個目標的同時優(yōu)化。 傳統(tǒng)的做法是對不同的優(yōu)化目標通過加權的方式轉化為單個目標優(yōu)化問題。 然而, 這種方法最大的問題在于各個目標權重的確定。 由于各個目標之間存在不一致性, 目標本身之間就存在矛盾, 不具備可比性,權重的設置具有較大的主觀性。 單目標優(yōu)化求得的解是唯一的, 而多目標優(yōu)化得到的是由許多Pareto 最優(yōu)解構成的解集。 這些Pareto 解集包含了許多有用的信息, 可以獲得不同目標之間的相關性, 對模型提供更多的解釋, 也方便給用戶提供個性化偏好的調度決策。
不失一般性, 多目標優(yōu)化問題(Multi-objective Optimization Problems, MOPs) 的數學模型可以描述如下。
其中x =(x1,x2,…,xn) ∈S為n維決策向量,S為n維決策空間;f(x) ∈?m為具有m個優(yōu)化目標的目標向量, 其中fi(x) 為目標函數f(x)的第i個目標分量;gi(x) ≤0,(i =1,2,…,p) 定義了p個不等式約束,hj(x)=0,(j =1,2,…,q)定義了q個等式約束。
根據上述定義, 望遠鏡調度問題就是在滿足所有約束條件的前提下, 在變量定義范圍內, 同時優(yōu)化m個不同的目標。 望遠鏡調度多目標優(yōu)化的目標向量要根據實際情況和需求進行設置, 如觀測目標的觀測時長盡可能長, 高等級的觀測目標優(yōu)先觀測, 望遠鏡等待的時間盡可能短等, 總體是要使得望遠鏡觀測效率最大化。
望遠鏡觀測調度執(zhí)行過程中, 需要滿足各類不同的約束條件, 這些約束條件可分為硬約束和軟約束。 硬約束是指在望遠鏡調度過程中不能違背的約束條件, 比如一個望遠鏡在同一時刻只能觀測一個目標就是硬約束, 一般用來衡量調度方案的可行性。 軟約束是指在調度過程中盡可能去滿足但不是一定要滿足的約束條件, 比如觀測目標的觀測時間盡可能要長就是軟約束, 一般用來衡量調度方案的優(yōu)劣。
鑒于望遠鏡調度問題的NP 難解性, 確定性算法的求解時間會隨問題規(guī)模增加而呈指數級增加, 導致用戶無法接受。 啟發(fā)式算法是求解NP難問題時常用的一種方法。 該方法首先產生問題的一個初始解, 然后通過啟發(fā)式規(guī)則進行求解迭代不斷改進現有解, 在合理的時間范圍內獲得優(yōu)化問題的可接受解。 啟發(fā)式算法作為求解組合優(yōu)化問題的熱點, 在望遠鏡觀測調度問題中也被廣泛應用[17-22]。
Giuliano 和Johnston[22]研究了詹姆斯·韋伯太空望遠鏡的調度問題, 并將該問題建模為最小化調度時間間隔、 最小化望遠鏡角動量累積和最小化未被觀測的目標數量等三目標優(yōu)化問題, 同時考慮了觀測時間窗和優(yōu)先級等約束條件。 設計并開發(fā)了多目標進化算法用于詹姆斯·韋伯太空望遠鏡的調度, 實驗結果驗證了算法的有效性。
Liu 等人[23]為了解決使用聚類方法提高空間碎片觀測效率的過程中引起可用觀測設備之間的沖突, 增加調度復雜性的問題, 提出了基于模擬退火的沖突避免算法。 Song 等人[24]使用改進粒子群算法求解空間碎片觀測最優(yōu)資源調度問題, 在粒子群算法中引入約束因子, 結合權重因子和學習因子控制粒子的飛行速度, 以獲得更好的收斂效果和全局近似最優(yōu)解。 此外, 還將改進后的算法與傳統(tǒng)粒子群算法和標準粒子群算法進行了對比測試, 證明改進后的算法在空間碎片監(jiān)測資源分配方面能達到令人滿意的效果。 Zhao 等人[25]提出自適應遺傳算法解決空間碎片觀測設備的優(yōu)化調度問題。 在算法的執(zhí)行過程中引入精英策略對選擇算子進行改進。 改進后的算法與傳統(tǒng)算法相比, 能更好地解決局部收斂問題, 并顯著加快收斂速度。 隨后, Zhao 等人[25]通過各種實驗和對比分析驗證了改進算法的有效性。
Gómez de Castro 和Yá?ez[17]研究了關于鄰域搜索算法和遺傳算法的望遠鏡調度優(yōu)化求解方法, 他們分析了調度過程中不同調度策略對于調度結果的敏感性。 劉琪等人[18]針對2.4m 望遠鏡時間分配問題, 在經典的哈勃空間望遠鏡Spike系統(tǒng)框架下, 使用混合式啟發(fā)算法對望遠鏡調度問題進行求解優(yōu)化。 首先, 通過遺傳算法在初始解搜索階段找出具有最大科學價值的時間分配方案。 隨后, 采用模擬退火算法有效地避免陷入局部最優(yōu)。 經2.4m 望遠鏡工作數據測試, 與傳統(tǒng)的Spike 模型相比, 無論是構造最大科學價值方案, 還是用戶觀測連續(xù)性的優(yōu)化, 混合啟發(fā)式算法都表現出更好的效果。 這也推動學者們在望遠鏡調度問題研究上融合不同啟發(fā)式算法。
尹樹成等人[19]以望遠鏡利用率、 用戶獲得觀測時間的公平性、 望遠鏡觀測的科學價值為優(yōu)化目標提出了一種混合啟發(fā)式算法。 在問題求解過程中使用模糊邏輯計算每個目標函數下次迭代在適應值函數中所占的權值。 該算法先是在構造初始種群時采用貪心策略, 使高優(yōu)先級的申請優(yōu)先分配到沖突值較小的時間片上。 同時, 采用了一種權重隨機策略, 將所有待分配的申請構造成一個權重隨機隊列, 用每個申請的科學價值作為隊列的優(yōu)先權重, 申請出現在隊列靠前位置的概率跟它所具有的權重有關。 隨后使用遺傳算法求解問題, 采用爬山算法處理問題沖突。
Hengameh 等人[20]在INO340 天文望遠鏡的調度問題上, 以最大限度地減少INO340 天文望遠鏡的空閑時間, 降低其機械運動的成本, 同時獲得最佳質量的圖像結果為優(yōu)化目標, 提出了一種遺傳算法求解。 該算法求解過程中考慮了可預測的影響觀測因素如: 環(huán)境條件、 地球自轉、 地球軌道、 調度策略、 觀測策略。 經過測試在實際工作中該算法能夠滿足INO340 天文望遠鏡的調度需求。
Wei 等人[21]為了解決云南40m 射電望遠鏡的短期觀測調度需求提出了一種多目標遺傳算法。該算法的適應值函數包括最小化轉換時間之和與最大化觀測科學價值。 在實際測試中簡單地考慮了一些約束條件, 例如天氣、 接收器和目標的不同優(yōu)先級, 同時研究發(fā)現在該問題上很難得到參數化建模。
啟發(fā)式算法能夠在可接受時間內得到較優(yōu)解, 然而望遠鏡觀測調度問題作為NP 難問題,啟發(fā)式算法求解的質量沒法得到保證。 此外,啟發(fā)式算法依賴研究人員根據問題性質手工設計啟發(fā)式規(guī)則, 當望遠鏡觀測調度問題求解目標和約束發(fā)生變化時, 算法的編碼方式、 適應值函數、 啟發(fā)式規(guī)則都需要研究人員重新進行設計。 因此, 啟發(fā)式算法求解望遠鏡調度問題不能確保獲得算法的全局最優(yōu)解, 算法的求解性能取決于具體的調度問題和算法設計人員的經驗。
望遠鏡設備的發(fā)展有兩種趨勢, 一種是建設大型獨立的望遠鏡, 另一種是建立望遠鏡陣列網絡, 以利用天文臺的不同位置的望遠鏡協(xié)同完成觀測任務。 López-Casado 等人于2022年提出了一種多臺望遠鏡組成的望遠鏡網絡模型 (GLORIA), GLORIA 網絡由分布在四大洲的18 臺望遠鏡組成[26], 基于三層結構的GLORIA 調度器架構如圖4 所示。
圖4 GLORIA 調度器架構Fig.4 GLORIA scheduler architecture
如圖4 所示, GLORIA 調度器的上層由一個獨特的中心節(jié)點組成, 負責接收用戶提出的所有觀測請求, 并對其進行初步分析, 評估請求中的時間和硬約束是否符合規(guī)定。 在評估后, 中心節(jié)點就會與本地節(jié)點進行通信。 這些節(jié)點構成了結構的中間層, 節(jié)點直接與網絡中的每臺望遠鏡相關聯。 它們的主要功能是進行可見性分析, 以檢查請求中的可見性約束。 可見性約束的分析結果被送回中心節(jié)點, 并通過上述三個約束條件的分析結果創(chuàng)建一個可用望遠鏡的列表。 隨后, 中心節(jié)點在該列表中選擇將提供觀測的望遠鏡。 觀測望遠鏡由基于不同特征的望遠鏡調度算法選出。選出執(zhí)行觀測的望遠鏡后, 中心節(jié)點就將決定傳達給該望遠鏡的本地節(jié)點。 這個本地節(jié)點與望遠鏡的本地調度器建立直接通信, 將請求引入望遠鏡的夜間觀測計劃中。 GLORIA 調度器架構的下層由具體執(zhí)行觀測的望遠鏡本地調度器構成。
GLORIA 網絡與其它望遠鏡網絡不同的一點是觀測時間在望遠鏡所有者和GLORIA 網絡之間共享, 所有者通常會為GLORIA 用戶分配一段觀測時間。 GLORIA 網絡的模型中的需要分析的參數是網絡的整體接受率, 整體接受率取決于以下三類輸入參數: ①觀測點位置的條件。 包含天氣預報參數和天文能見度參數。 ②目標質量, 通過目標過境高度來測量目標質量信息。 ③望遠鏡網絡反饋, 通過用戶反饋得知。
GLORIA 調度程序接收觀測請求并將其發(fā)送到特定的望遠鏡。 請求具體發(fā)送到哪臺望遠鏡是通過決策算法決定的。 此外, 該模型根據觀測請求定義望遠鏡是否可用, 即滿足用戶指定的所有約束條件的望遠鏡為可用望遠鏡。 該功能通過兩個均勻分布的隨機變量實現: 第一個變量為可用望遠鏡的數量, 第二個變量為每個望遠鏡的標識符。
為了分析望遠鏡決策算法如何影響網絡接受率, 網絡中的每個望遠鏡都接收觀測請求, 并決定是否執(zhí)行。 有多重因素影響觀測請求是否被接受, 但最重要的因素是望遠鏡所在地的天氣。 如果天氣狀況不適合觀測, 望遠鏡控制系統(tǒng)將保持圓頂關閉, 觀測請求不會執(zhí)行。
GLORIA 網絡使用了廣義線性回歸模型構建了響應變量和一個或多個預測因子之間的關系,其中響應變量是指數分布族中的一個特定分布。在望遠鏡接受請求時, 設響應變量代表決策, 且服從伯努利分布,y∈{0,1} , 望遠鏡所在地的天氣是決定望遠鏡是否可用的主要因素, 模型將只使用這個變量作為預測因子。 定義如式(4):
其中,μ是對天氣預報的平均響應變量,α表示望遠鏡所在地,a和b被估算的廣義線性回歸模型參數。 由于響應變量服從伯努利分布, 將平均響應與觀測請求結果1 出現的概率相匹配。 對于接收觀測請求與其執(zhí)行或拒絕之間花費的平均時間。 該信息直接從網絡日志中獲得, 并被計算為所有望遠鏡請求中的平均時間。
綜上所述, 將問題轉換一個由目標觀測函數和成本函數定義的多目標優(yōu)化問題, 優(yōu)化目標為最大化完成的觀測請求數量和最小化重新分配過程中的步驟數。 給定一組觀測請求
{O1,O2,... ,ON} 和重新分配的最大步驟數S目標觀測函數定義為式(5)。
M為={O1,O2,... ,ON} 的重新分配步驟最大值。
隨著天文學的發(fā)展, 望遠鏡觀測需求增多,僅使用單點觀測模式已經逐漸不能滿足觀測需求, 多望遠鏡協(xié)同組成的望遠鏡陣列對適應觀測需求的復雜化更具有優(yōu)勢。 望遠鏡調度未來將會是多望遠鏡協(xié)同觀測和單點觀測協(xié)同發(fā)展, 新的觀測模式將會被引入, 在減少調度時間的同時增加應對觀測中產生突發(fā)事件的能力。
最近, Zhang、 Yu 和Sun 等人[27]針對更大的觀測區(qū)域和更高的全時空監(jiān)測頻率要求, 提出了一種分布式時域大面積巡天望遠鏡陣列的多級調度框架。 通過優(yōu)化策略自協(xié)調地對時變觀測條件的貢獻進行加權, 從而從全局角度保持均勻覆蓋和有效的時間利用。 實驗結果表明, 在同時考慮調度時間分配效率和觀測區(qū)域的覆蓋均勻性方面, 該望遠鏡調度框架能夠提供滿意的解決方案。
在望遠鏡觀測調度過程中, 除了靜態(tài)的任務需求之外, 動態(tài)望遠鏡觀測調度也成為當前研究人員關注的熱點。 在實際任務規(guī)劃時, 會出現需求變化、 任務中斷或者不可預見的突發(fā)情況。 在執(zhí)行任務調度時, 可能會出現任務增加或取消的情況, 也存在望遠鏡出現故障等情況。 這些不確定性因素給望遠鏡觀測調度增加了新的難度, 對調度模型建立提出了更高的要求。
由于望遠鏡網絡問題的復雜性使得具備優(yōu)秀表達能力的深度強化學習方法在這一領域廣泛使用。 強化學習是通過智能體與環(huán)境交互進行計算的一種機器學習方法, 智能體根據環(huán)境狀態(tài)選擇動作策略, 環(huán)境狀態(tài)根據智能體的動作進行改變并給智能體反饋。 當狀態(tài)和動作數量非常大時就需要使用函數擬合方法, 由于神經網絡具有強大的表達能力因此常用神經網絡表示函數。 深度強化學習方法是將深度學習的感知和強化學習的決策能力相結合的一種方法, 在眾多組合優(yōu)化問題求解中獲得了較好的效果, 也是當前學界研究的熱點[28]。
Jia 等人[29]將幾臺廣角小口徑望遠鏡組成觀測陣列, 用以觀測連續(xù)天體。 由于需要觀測的目標較多, 為此提出了一種最大化科學價值的強化學習算法。 該算法用深度神經網絡存儲望遠鏡陣列的觀測策略, 通過智能體與環(huán)境的交互不斷學習觀測策略, 在訓練過程中使用經驗回放機制將訓練后的數據存儲在緩沖區(qū)中, 用于隨后的隨機采樣訓練。 實驗證明深度強化學習方法在望遠鏡觀測調度問題上能夠取得良好的性能, 且具有很強的泛化能力。
地面光學望遠鏡陣列的觀測能力往往受到云、 衛(wèi)星和天空背景等各種動態(tài)因素的制約,需要充分利用已有的遙測數據, 并合理安排望遠鏡陣列調度。 然而, 望遠鏡陣列比較復雜而且成本較高, 直接使用物理望遠鏡陣列設備來測試算法代價太高。 基于此, 研究人員提出了一個模擬望遠鏡陣列的框架[30], 并采用一種基于分布式強化學習框架的調度策略來優(yōu)化望遠鏡陣列觀測策略。 實驗結果表明所提方法能夠有效提升望遠鏡陣列觀測效率。
綜上, 求解望遠鏡調度的幾種典型方法如表2 所示。
當前較多文獻使用啟發(fā)式算法求解望遠鏡觀測調度問題, 這類方法往往針對解決某一特定問題提出, 需要研究人員手工設計啟發(fā)式規(guī)則。 與傳統(tǒng)的優(yōu)化技術相比深度強化學習方法具有更強的泛化性, 隨著深度強化學習方法研究的不斷深入, 未來基于深度強化學習求解該類問題將成為一個熱門的研究方向。
國外較早開始了望遠鏡調度系統(tǒng)的研究, 最有代表性的是用于哈勃空間望遠鏡HST (Hubble Space Telescope) 調度的Spike 系統(tǒng)[31]。 該系統(tǒng)由美國國家航空和宇宙航行局研究開發(fā), 從1990開始投入使用, 系統(tǒng)采用的核心算法是迭代修正搜索算法。 Spike 調度程序是為哈勃太空望遠鏡開發(fā)的, 但設計時考慮到了通用性和靈活性。 此后, Spike 也被用于解決一些其他天文調度問題,以及與天文學無關的問題。 HST 的調度過程使用互聯網以電子方式接收申請, 通過一個提案數據庫進行處理。 轉換系統(tǒng)會將天文學家的觀測計劃轉換為一系列任務來進行調度。 Spike 負責進行長期調度, 并將調度任務以周為單位劃分交給負責短期調度和儀器指令的科學規(guī)劃調度系統(tǒng)。 Spike系統(tǒng)的軟件界面如圖5 所示。
圖5 Spike 系統(tǒng)的軟件界面Fig.5 Software interface of Spike system
第一臺完全由計算機控制的光學望遠鏡是1975年建成的英澳望遠鏡, 由此形成了望遠鏡控制系統(tǒng)的概念[32]。 自此, 使用望遠鏡進行天文觀測從傳統(tǒng)的天文臺運作模式逐步向隊列調度模式發(fā)展, 望遠鏡調度系統(tǒng)也隨著相關技術的進步得到了飛速的發(fā)展[33]。 望遠鏡調度系統(tǒng)為天文觀測研究帶來了極大的便利, 不僅節(jié)約了時間和費用, 也減少了研究人員的工作量, 提高了望遠鏡觀測的效率。
哈勃望遠鏡、 ROSAT 天文衛(wèi)星、 甚大天線陣列(Very Large Array) 較早的使用了望遠鏡調度系統(tǒng)。 在2007年, 哈勃望遠鏡的調度系統(tǒng)因為技術的限制仍存在很多需要解決的問題如[33]: 望遠鏡調度系統(tǒng)還不能自動檢查程序完成情況; 研究人員不能直接向隊列添加目標或從隊列中刪除目標等。 2009年位于智利帕瑞納天文臺的可見光和紅外巡天望遠鏡(Visible and Infrared Survey Telescope for Astronomy, VISTA) 開光(開始運行),VISTA 望遠鏡控制軟件主體部分使用了ESOVLT控制軟件, 高層控制軟件并不直接控制硬件, 而是將命令發(fā)送給實際控制硬件的本地控制單元[34]。 VISTA 望遠鏡的控制軟件主體復用了ESO VLT 控制軟件, 采用與VLT 控制界面類似的界面和使用感受, 以便望遠鏡操作員可以輕松地在VLT 和VISTA 之間切換。 該軟件主要用C++編寫, 在標準Linux PC 上運行。 高級控制軟件不直接控制硬件, 而是通過向實際控制硬件的本地控制單元(Local Control Unit, LCU) 發(fā)送指令來實現各種功能。 LCU 是運行VXWorks 實時操作系統(tǒng), 采用C 語言編程的小型磁盤計算機。 每個運動軸或子系統(tǒng)都有一個獨立的LCU。 VISTA 望遠鏡總共有11 個LCU。
(Gravitational-wave Optical Transient Observer,GOTO) 引力波光學瞬態(tài)觀測儀原型儀器于2017年7月在加那利群島的拉帕爾馬落成[35]。 拉帕爾馬的GOTO 原型儀器如圖6 所示[35]。
圖6 拉帕爾馬的GOTO 原型儀器Fig.6 The GOTO prototype instrument on La Palma
GOTO 的望遠鏡調度系統(tǒng)由多個獨立的控制進程組成, 由一個名為‘pilot’ 的主控負責監(jiān)督其他進程。 觀察由即時調度程序決定, 該調度程序指示‘pilot’ 實時觀察的目標, 并提供瞬時事件的快速跟進[35]。 GLORIA 望遠鏡網絡的調度程序以最大化總網絡接受率和最小化觀測提交與結果之間的耗時為目標設計了3 種算法[26]: 第一種算法僅基于望遠鏡位置的天氣預報; 第二種算法基于使用不同輸入參數的模糊邏輯; 第三種算法基于對每個望遠鏡接受觀測的條件概率的預測。此后, GLORIA 的研究人員將在新的機器學習方法上進行探索, 如神經網絡、 支持向量機等, 將這些方法與上述的三種算法進行比較[26]。
阿爾及利亞的奧勒斯國家天文臺(National Aures Observatory, NAO) 中使用了預測類型的調度程序, 該程序使用基于NSGA-II 和帕累托最優(yōu)的遺傳算法求解調度問題[36]。 伊朗國家天文臺的INO340 望遠鏡以最大限度地減少望遠鏡的空閑時間并降低其機械運動的成本, 同時獲得最佳質量的圖像結果為目標, 采用遺傳算法考慮影響觀測條件的可預測因素并獲得最優(yōu)調度方案[20]。
2019年, 目前世界上最大規(guī)模的最復雜的射電望遠鏡陣列平方公里射電陣(Square Kilometre Array, SKA) 已全面投入使用是目前世界上最大規(guī)模的最復雜的射電望遠鏡陣列[9]。 澳大利亞平方公里陣列探路者 (Australian Square Kilometre Array Pathfinder, ASKAP) 是SKA 的前身, 通過ASKAP 的建設研究人員得到了幾條重要經驗。 在設備建設過程中需將硬件、 軟件和軟件開發(fā)相互關聯, 并盡早整合子系統(tǒng)。 一些早期的設計需要根據實際經驗進行修改, 因此需要盡快開始科學導向的測試觀測。 新射電望遠鏡的調試工作從子系統(tǒng)測試開始, 到整個系統(tǒng)全部運行結束。 自動化系統(tǒng)在望遠鏡從調試到運行的過程中發(fā)揮了關鍵作用, 并在ASKAP 的未來運行中至關重要。 在ASKAP 的建設和使用中, 自動化系統(tǒng)可以幫助研究人員發(fā)現問題, 并在條件允許的情況下對問題進行修復。 當遇到系統(tǒng)無法修復的問題時, 系統(tǒng)也可以執(zhí)行有效的變通方法。
國內的望遠鏡調度系統(tǒng)較國外起步稍晚, 國內的天文工作者通過參與國外的相關項目積累經驗為國內望遠鏡調度系統(tǒng)的建設奠定了基礎[37]。2012年3月, 中國第一臺專業(yè)級程控自主望遠鏡BOOTES-4 在云南麗江觀測站落成[32]。 BOOTES-4程序控制系統(tǒng)結構圖如圖7 所示[32]。
圖7 BOOTES-4 程序控制系統(tǒng)結構圖Fig.7 BOOTES-4 program control system structure diagram
BOOTES-4 的整個系統(tǒng)分為用戶層、 觀測控制層、 設備控制層、 設備層。 設備層由構成望遠鏡的各個設備組成; 設備控制層負責向設備發(fā)送命令、 監(jiān)測設備狀態(tài)、 收集數據; 觀測控制層控制整個觀測流程; 用戶層采用本地操作接口和衛(wèi)星通道兩種方式向設備發(fā)出指令。
中國的天文工作人員在開源的BOOTES 系列的RTS2 系統(tǒng)基礎上再次開發(fā)完成了我國第一個程控自主望遠鏡的系統(tǒng)實現[38]。 2016年, 我國自主建設的世界上最大最靈敏的單口徑射電望遠鏡FAST 全面建成投入使用, 研究人員設計了一種基于最大匹配邊緣檢測的方法來減小問題規(guī)模, 并提出了一種回溯算法用最小轉換成本找到完美匹配[8]。 FAST 的調度系統(tǒng)概覽如圖8 所示。
圖8 FAST 調度系統(tǒng)概覽Fig.8 The overview of FAST scheduling system
用戶向中國虛擬天文臺系統(tǒng)(Chinese Virtual Observatory System, China-VO) 所提供的接口提交申請, 提交的申請由天文學家審核, 申請被接受后獲得科學優(yōu)先級。 調度系統(tǒng)將每個申請分成幾個最小可調度塊(Minimum Schedulable Blocks,MSBs), 每個MSB 包含一個天體。 調度程序讀取China-VO 系統(tǒng)的MSB, 然后運行調度算法分配MSB 的觀測時間。 在這個過程中, 一些MSB 可能由于限制條件無法獲得觀測時間被拒絕。 最后,調度程序把生成的觀測計劃發(fā)送到測量和控制系統(tǒng)執(zhí)行。
2016年, 基于EPICS 和RTS2 的南極望遠鏡自主測控系統(tǒng)在云南省麗江天文臺進行了實際觀測測試, 完成了自主觀測和控制, 包括望遠鏡控制、 相機控制、 球機控制、 氣象信息獲取以及本地和遠程操作[39]。 2018年, 南極巡天望遠鏡AST3 開發(fā)了一個定制的調度程序, 這是一個基于優(yōu)先級隊列的調度程序, 同時考慮了與通用機器人望遠鏡相關的問題和一些特殊條件[40]。 此后,在AST3-1、 AST3-2 兩臺望遠鏡的基礎上改進的第三臺望遠鏡AST3-3 已于2021年3月在南極洲Dome A 投入使用。 AST3-3 設備部署如圖9 所示。2023年, Zhang 等針對時域巡天望遠鏡陣列調度問題, 提出了一種多級調度模型, 并將功能封裝在分層體系結構的軟件中開發(fā)了一個靈活的框架, 提出了一種優(yōu)化度量方式從全局的角度保持均勻覆蓋和有效的時間利用[41]。
圖9 AST3-3 設備部署Fig.9 AST3-3 deployment in dome
雖然國內的望遠鏡調度系統(tǒng)發(fā)展起步稍晚,但國內的相關研究人員學習國外先進技術不斷創(chuàng)新, 隨著國內的望遠鏡觀測設備越來越好, 國內的望遠鏡調度系統(tǒng)研究也有了長足的發(fā)展。
空間碎片問題已成為全球各國航天界關注的焦點。 望遠鏡調度是空間碎片觀測、 跟蹤和編目的必然過程, 吸引了越來越多研究人員的廣泛關注, 相關的調度模型和算法也如雨后春筍般相繼涌現。 然而不同的模型與算法之間存在較大差異, 造成這些差異的原因主要是以下兩點。 第一, 研究工作都是以研究人員使用的天文望遠鏡設備為基礎, 不同研究人員使用的天文望遠鏡設備存在著極大的差異。 其次, 望遠鏡調度算法的求解目標不同, 根據實際觀測需求存在各種各樣的差異。
望遠鏡觀測設備的更新、 空間碎片的增加以及觀測范圍的不斷擴大, 給望遠鏡調度帶來了新的挑戰(zhàn)。 當前啟發(fā)式搜索算法是望遠鏡觀測調度采用的主流方法, 也是各國望遠鏡觀測調度系統(tǒng)中使用的核心算法。 隨著深度強化學習在組合優(yōu)化問題的研究逐步深入, 使用深度強化學習方法以及采用強化學習指導啟發(fā)式算法求解望遠鏡調度問題有望成為熱點研究方向[42]。 隨著計算機算力的不斷提升, 觀測數據的不斷積累, 以及各類算法的迭代升級, 望遠鏡觀測調度將變得更加高效, 人類將會有更多更好的方法、 更加從容地來應對太空碎片的威脅。