基于HLA的多任務規劃仿真系統的研究與實現

劉桂枝，張秀程

（1.大同大學 物理與電子科學學院，山西 大同037009；2.中國科學院 空間應用工程與技術中心，北京100094）

0 引 言

分布式交互仿真技術是在美軍軍事需求的基礎上發展起來的，大致經歷了4個階段，分別是SIMNET（simulation network）、DIS（distributed interactive simulation）、ALSP（aggregated level simulation protocol）和 HLA（high level architecture）［1］。美軍當前仿真研究的主要標準和規范就是HLA，其軍事領域大型仿真系統都支持HLA。HLA也是航天領域仿真的主要技術平臺，從仿真的實際需求來看，航天領域仿真已開始由單星、單性能向多衛星、多功能、多目標的協同仿真轉變，由局部仿真向分布式大型綜合性仿真轉變［2］。

衛星是航天任務系統主要組成部分，主要用于對地觀測、氣象預報、衛星通信、科學探測等任務。以衛星為代表的航天器是在國家軍事經濟中的作用越來越重要?，F在衛星技術不僅對國民經濟發展至關重要，而且對于國家安全也是不可或缺的，其應用范圍越來越廣泛［3］?，F在針對衛星的仿真研究較多，但多是針對局部技術的仿真［4－6］。

航天信息系統是一個復雜的大系統，信息獲取平臺和傳感器不僅種類繁多，特性各異，且空間分布隨時間變化；被探測的對象也千變萬化，空間上和時間上都在變化；衛星探測的過程還受到自然條件和人為干擾的限制，而且空間任務往往具有并發特性［7］。針對紛繁眾多的資源和目標，在有條件限制的狀況下，針對多個任務需求，要快速的做出決策，光靠人力是做不到的，必須依靠系統規劃的最優化技術和現代信息技術［8］。

多任務規劃與協同控制技術就是在上述背景下提出的，即利用現有或將具備的各類衛星、地面系統充分考慮各類約束條件（如衛星數量、傳感器約束、氣象、通信等），研究如何對多個應用任務進行多平臺、多傳感器的智能協同規劃，并實現對各類相關資源的科學管理［9］。多任務指借助于各種衛星進行多個探測任務，既包括周期較長的戰略性任務，也包括諸如聚焦、變軌等的具體任務。多任務規劃是一個集任務分析和分解、指令下達、信息獲取、數據下傳于一體的智能規劃系統［9］。

在當前的技術條件下，對大范圍內的目標進行快速探測和搜索，只有借助于衛星。然而，盲目的搜索不僅發現目標的效率低，甚至還可能給決策者提供了錯誤的信息，因而有必要對使用衛星等搜索運動目標進行研究，力求給出使用衛星搜索的最優或較優策略［10］。

本文提出了MIP/CP混合模型的任務規劃算法，基于啟發式算法進行了優化。以此技術為基礎，針對海洋移動目標進行空間搜索的過程為例設計了一個多任務規劃仿真系統。航天任務仿真往往都是針對某一任務環節進行仿真，本文以任務規劃算法為基礎，對衛星對地觀測任務的全流程進行仿真，驗證MIP/CP模型的有效性。

1 動目標運動軌跡預測方法

考慮兩個運動中最基本的因素，方向θ與運行速度υ。設θ服從f分布，υ服從g分布，并且認為θ與υ是獨立的，因此（θ，υ）的聯合密度為f＊g。還假設在一定時間范圍內θ和υ是不變的，Ω是艦隊可能出現的區域，則Ω上艦隊可能出現的概率直接由（θ，υ）與時間t決定，即（θ，υt）～f＊（g＊t）。

利用計算機仿真可以把動目標運動范圍以概率的形式表示，據此可以統計出可能行分布，這樣問題就變成一個有概率權值的區域分布問題。由于計算機仿真依據時間t輸出結果，使得結果具有了時間屬性，可以進行某個時間區域的運動預測分析?？紤]到人機接口輸入的概率分布函數的復雜性，以及f，g函數精確計算所需要花費的代價，統一采用多項式插值逼近分布函數。通過f和g的分布，構造函數隨機產生出來的點落在Ω區域內。對于連續的隨機變量，有很多辦法可以模擬，常用的有兩種，一種是反變換算法，一種是接受拒絕法。對于某些復雜的函數采用后一種算法，即接受拒絕法［10］。

通過把動目標搜索問題轉化為區域覆蓋問題，并基于此來針對單顆和多顆衛星設計搜索策略。除了在海洋陸地二維曲面上采用此模型計算運動范圍外，對于空、天等三維空間運動范圍，也可以推廣得到。在三維空間里，在地球慣性坐標系下描述物體運動的球極坐標采用（α，β，γ），分別表示物體方位角、俯仰角、運動速度。使用2維處理的方法，直接統計數據點，雖然也可以解決問題，但是由于維數的增加，帶來搜索范圍的擴大，需要產生足夠多的信息點，來覆蓋物體運動范圍，這增加了模擬的運算量以及統計所需要的時間，概率密度直方圖也無法在三維空間內描述。某些對于高度變化不大的物體，可以把三維信息轉化為二維信息，從而套用前面的方法解決問題［10］。

2 多任務智能規劃技術

MIP模型能同時顧及各種約束條件，且對于簡單約束在多項式時間內求解迅速，缺點在于對含有復雜約束的問題處理效率低；CP模型由于其采用約束傳播和搜索方法進行約束推理，因而非常適合具有復雜關系的一類問題，如組合問題、離散問題等，不足在于求解最大、最小等問題等優化問題時，常常效率不高，即規劃推理更適合快速找到一個可行解，而非最優解?；旌?MIP－CP模型則是在充分考慮兩種模型的優缺點后建立的，即混合模型去掉不必要的冗余約束，并在兩者間建立聯系，同時還要針對混合模型給出合適的算法，達到快速求解問題的目的?；旌螹IP/CP模型，借助于人工智能中的智能規劃技術，設計啟發式求解算法，從而極大地提高模型求解效率。表1、2、3分別是采用MIP模型、CP模型、混合MIP/CP模型求解相同問題時的計算效率，由此對比看出，采用混合MIP/CP模型的效率更高［10］。

表1 MIP模型的計算結果

表2 CP模型的計算結果

將上述結果進行對比，比較圖見圖1。從圖1中可以看出，混合MIP/CP模型的求解效率比起單獨的兩種模型有顯著提高，尤其在問題規模較大時速度的提高更為明顯。

表3 混合MIP/CP模型的計算結果

圖1 3種模型求解效率比較曲線

3 系統需求

航天多任務智能規劃是一個多維度的資源優化配置問題，為了獲得最優或者次優解，首先需要認真分析影響任務規劃的約束條件。其中規劃模式、可用的規劃資源、規劃目標構成了影響規劃的直接約束；而光照、氣象等條件可認為是間接約束。航天信息系統多任務規劃，就是通過對各類可用資源按照一定的準則進行優化配置，以滿足執行任務的要求。而資源的所謂 “優化配置”，是與指定的任務性質和規模密切相關的。因此，分析航天信息系統可能的任務和其未來的工作模式，對于航天信息系統的多任務規劃，是至關重要的［11］。

在規劃模式中，重點考慮的是觀測時間范圍的要求以及優先級（重要程度）的要求。常見的模式有常規模式、應急模式、聚焦模式、規劃資源［11］。

規劃資源是規劃系統中最為基礎的一類數據信息，對于待規劃資源的數據結構可按其更新變化頻度及在規劃不同階段的作用，分為屬性參數、狀態參數、規劃參數3類?？臻g信息多任務規劃原型系統只考慮3類目標，地面點目標、地面區域目標、海洋移動目標［11］。

4 系統設計

航天信息多任務規劃仿真系統分為兩個子系統，即多任務規劃系統和仿真系統。當空間信息仿真計劃制定完畢以后由任務規劃系統負責規劃調度，然后仿真子系統依照規劃結果進行仿真。

系統邏輯關系圖如圖2所示。

圖2 航天信息多任務規劃系統結構

4.1 多任務規劃系統

多任務規劃系統是空間信息多任務規劃系統的主體。多任務規劃系統是建立在大量的數據資源以及多種類型搜索、規劃算法的基礎之上的。它負責根據用戶制定的觀測任務，首先對任務進行分析分解，對于不確定的任務利用搜索算法確定具體目標，再對任務分解得到元任務（任務片斷）進行規劃，最終形成完整的規劃方案。

4.2 系統層次結構

多任務規劃系統是以數據模型為驅動的，系統按照任務以及時效性等要求的不同選擇合適的模型算法以及數據資源，實現對各類觀測的規劃。因此多任務規劃系統的核心是模型算法和對這些模型算法的調用管理，以及模型在系統中的存在和使用方式，可將多任務系統劃分為4個層次，從底層到高層分別為：數據層、服務層、應用層和擴展層，如圖3所示。

圖3 空間信息多任務規劃系統功能模塊

4.3 仿真系統

仿真系統是對空間信息資源的模擬，為多任務規劃系統提供一個逼真的規劃執行環境。仿真系統主要有兩個作用：一方面，它為多任務規劃系統中各種模型、算法設計的是否合理，提供了一個測試驗證手段；另一方面，它也為未來航天信息系統，各類平臺、傳感器、地面站的部署提供了一個仿真和評估平臺。多任務規劃系統與仿真系統的邏輯劃分應遵循以下原則：一個是多任務規劃系統與仿真系統的接口應與真實系統的接口保持一致；另一個是仿真系統與多任務規劃系統應相互獨立，減少之間耦合［12］。

4.3.1 仿真系統成員劃分

根據系統的功能及航天探測實際業務進行劃分，仿真系統可劃分為管理控制聯邦成員、衛星聯邦成員、地面戰聯邦成員，目標聯邦成員，環境約束聯邦成員，可視化聯邦成員以及智能規劃聯邦成員。智能規劃聯邦成員通過規劃子系統負責對仿真任務進行分解以及數據規劃預處理，當任務下達后通過任務規劃子系統進行規劃；管理控制聯邦成員是仿真系統的管理控制核心，其他成員接收該成員發布的命令。

4.3.2 聯邦FOM 設計

對于HLA仿真，FOM的設計至關重要。FOM就是對物理系統的用面向對象的思想進行的抽象建模，FOM反映了仿真系統的物理屬性，也是成員之間進行數據交換橋梁和紐帶［12］。FOM設計遵循DMSO的對象模型模板（object model template，OMT）設計規范，是仿真系統創建聯邦執行時的基本配置文件。參加仿真聯邦的對象類和交互類以及它們的屬性和參數信息都定義在FOM中。各個仿真成員間的數據交互交換是通過HLA/RTI提供的 “公布與訂購”服務實現［13］。公布數據的仿真成員負責更新仿真數據，由RTI負責通知訂購該數據的仿真成員進行反射接收［14］。仿真系統中衛星，地面站，目標等成員作為仿真聯邦的主要實體，雖然不一定對實體的所有屬性建模，但必須要對仿真關心的屬性進行建模［15］。交互類用來記錄聯邦/仿真中的交互類及其父類、子類關系，成員之間的所有的交互都是由仿真實體發出的本仿真系統共設計了8個對象類，分別是 HLAManager，StarObjClass，StarObjClass，SimuObjClass， SensorObjClass， StationObjClass， TgtObjClass，SatePlatClass，TDRSSObjClass，TDRSTObjClass；設計了8個交互類，分別是 HLAManager，TgtInterClass，SimuInterClass， TdrInterClass，StarInterClass， SatePlatInterClass，SenInterClass，StationInterClass。

4.3.3 仿真聯邦成員設計

仿真聯邦的成員是在邏輯上協同的仿真組件，成員可以在其他仿真成員不存在或者失效的情況下獨立完成本身的仿真任務，但是不能在其他成員不存在的情況下完成全面的仿真任務。換言之，也就是各個成員需要進行數據交互，協同工作才能完成預定的任務。

管控成員是仿真系統的控制核心，執行聯邦創建、聯邦銷毀、聲明注冊同步點、控制聯邦進程等。管控成員可以集成地面任務中心的功能，進行信息交換轉發；采集用戶需求和測控數據，根據任務需要，生成有效載荷的工作計劃，生成控制指令或者數據注入，上行給航天器。

衛星成員主要是公布衛星當前的位置以及速度，以及和地面戰、中繼星進行數據通信，顯示衛星的各個運行參數，執行管控成員的各種指令。衛星成員雖然功能相對簡單，但是具有擴展性，可以根據任務需要加入多個的衛星完成不同的仿真任務。

地面站成員完成與衛星成員間的通訊并實現對空測量雷達的功能。地面站分為固定站和移動站，移動站在地理位置上不是固定的，比如我國的遠洋航天測量船，所以地面站聯邦成員必須更新位置信息給其他成員。正如現實中的地面站一樣，地面站聯邦成員也有自己的測控范圍、地面站天線的方位和俯仰角的變化等星地可見關系計算。地面站是地面管理中心和衛星的通信紐帶，通過數據交互，完成對航天器的信息收集與對航天器的數據、指令上行等通訊工作。

視景顯示聯邦成員訂購其他成員需要顯示的數據，并把數據以三維的形式進行渲染、顯示，供用戶進行觀察和分析，它是對仿真過程數據數據進行可視化渲染。

目標成員模擬在海洋中移動的目標，公布自身的位置信息，并對衛星的覆蓋進行計算，公布自身的被衛星覆蓋的信息。目標成員在后期版本準備加入點目標、區域目標，完成深入的仿真任務。

4.4 仿真系統流程

系統首先由管控成員進行仿真信息配置，規劃子系統讀取資源數據庫以及任務配置信息，進行數據預處理，進行任務分解和規劃。規劃子系統的基本流程：當觀測任務到達之后首先對任務進行分析分解處理，然后對不確定的目標根據先驗信息進行搜索，根據目標出現概率，選擇概率較高的區域作為觀測目標。任務目標確定之后，就可以對當前可用資源進行規劃處理，對于臨近空間的規劃結果，還需要進行航跡規劃處理。對多任務規劃處理過程的控制由任務規劃調度部件通過消息方式進行。規劃的結果轉化為通過管控成員的發布的指令。繼而創建聯邦執行，初始化各個聯邦成員，發送命令開始仿真。

各個成員根據收到的指令執行相應動作進行數據交互，如衛星成員根據收到的指令，進行變軌或調姿，并執行設備相關動作，例如設備開機或者關機，數據傳輸等。地面戰成員也是根據指令進行天線的跟蹤、開機、關機、通信等。

如果衛星搜索到目標，則把目標信息傳給管控成員，執行下一步指令動作，否則返回給規劃子系統，進行任務規劃調整，重新生成指令，交給控制成員，控制成員重新把指令發布給各個成員執行。

5 仿真數據分析

對規劃模型和算法進行了仿真測試，得到了相應的數據結果和結論，計算采用的模型和算法為混合 MIP－CP模型與啟發式求解算法［11］。

表4 仿真測試用例問題規模

對每一個測試問題，為仿真平臺配置了相應的可用資源，規劃周期分別取1天、7天、48天，進行規劃計算，每組測試數據運行20次，統計其平均用時和平均誤差，得到如下統計數據。

由圖4、5、6可以看出：

（1）隨著問題規模的加大，規劃用時也相應增大，但比起以往的模型和算法（如MIP模型、CP模型等），無論從增加的絕對值還是相對比例上，新模型和算法都要小許多，即新模型和算法對較大規模的規劃問題更為適合。

（2）隨著規劃周期的變長，規劃用時顯著增大，其實質也是由于問題規模的增大而引起的：規劃周期越長，可選擇的觀測、通信弧段也越多，即增大了搜索空間范圍。從表5中還看出，為了在可接受時間范圍內得到問題的可行解（未必是最優解），我們犧牲了解的精度，即允許規劃計算返回可行解而非最優解。如在規劃周期為48天情況下，得到的基本都是近似最優解。

表5 規劃求解平均用時統計

6 結束語

討論了動目標搜索的一般理論，衛星對動目標的搜索技術，以及多星多任務規劃的混合MIP/CP模型，并給出了針對該模型的算法以及仿真結果，所有結果來源于研究小組開發的空間信息多任務智能規劃仿真系統。

圖6 規劃周期48天的規劃平均用時比較

通過以上研究，得到了一些初步結論：航天信息多任務規劃系統是一個復雜的大系統，涉及到的資源、目標眾多，多任務規劃技術的研究內容廣而難，涉及到人工智能、計算機仿真、運籌學、搜索論，圖形學等多個方面，尤其是動目標搜索理論和對抗形式下的任務規劃，可借鑒和學習的理論成果還很少。文中的主要算法及模型經過測試首先驗證了其正確性，同時經測試顯示具有較高的效率，滿足有關技術指標的要求，為今后的深入的研究奠定了理論依據。

［1］WU Rongchun，ZHANG Fengli.Application of simulation in military field based on HLA ［J］.Modern Enterprise Education，2010，14（9）：81－85（in Chinese）.［吳榮春，張鳳荔.基于HLA的仿真技術在軍事領域的應用 ［J］.現代企業教育，2010，14（9）：81－85.］

［2］YANG Jianhua，PAN Yunhe.Research on virtual battle oriented the attack against the simulation technology［J］.Computer Simulation，2005，22（8）：1－8（in Chinese）.［楊建華，潘云鶴.面向虛擬戰場的攻放對抗仿真技術研究 ［J］.計算機仿真，2005，22（8）：1－8.］

［3］WANG Zonghui，SHI Jiaoying.Research on unified model supporting HLA－based simulation and parallel rendering ［J］.Journal of Computer Research and Development，2008，45（2）：329－336（in Chinese）.［王總輝，石教英.支持 HLA 仿真和并行繪制的統一對象模型研究 ［J］.計算機研究與發展，2008，45（2）：329－336.］

［4］ZHENG Hongbin，SHAO Xiaopeng，XU Jun.The man－made satellite of the orbits of the real－time simulation technology［J］.Journal of Photons，2007，36（1）：109－112（in Chinese）.［鄭宏斌，邵曉鵬，徐軍.人造衛星運行軌道的實時仿真技術 ［J］.光子學報，2007，36（1）：109－112.］

［5］ZHANG Xinyu，HUANG Kedi.Design of HLA simulation database based on object－relational fratures ［J］.Computer Simulation，2008，25（6）：138－145（in Chinese）.［張新宇，黃柯棣.基于對象關系模型的仿真數據庫設計 ［J］.系統仿真學報，2008，25（6）：138－145.］

［6］XIA Fengling，ZHAO Yushan.Aerospace mission simulation system based on HLA ［J］.Journal of System Simulation，2007，19（24）：5710－5714（in Chinese）.［夏豐領，趙玉善.基于HLA的航天任務仿真系統 ［J］.系統仿真學報，2007，19（24）：5710－5714.］

［7］SUN Shixia.Large complicated system modeling and simulation credibility assessment study ［M］.Hefei：The National Defense Science and Technology University Press，2005：17－134（in Chinese）.［孫世霞.復雜大系統建模與仿真的可信性評估研究 ［M］.合肥：國防科學技術大學出版社，2005：17－134.］

［8］Przemieniecki.Mathematical methods in defense analyses ［M］.New York：Plenum Press，2007.

［9］SHEN Rusong，ZHANG Yulin.Analysis of operational effectiveness of ocean surveillance satellite ［J］.Journal of System Simulation，2006，18（3）：531－534（in Chinese）.［沈如松，張玉林.海洋監視衛星作戰效能分析 ［J］.系統仿真學報，2006，18（3）：531－534.］

［10］LIU Wei，MENG Xin.Allocation of earth observation satellite resource for multi－target ［J］.Computer Simulation，2007，24（11）：35－37（in Chinese）.［劉偉，孟新.對地觀測衛星的多目標分配方法 ［J］.計算機仿真，2007，24（11）：35－37.］

［11］LIU Wei，MENG Xin.Research on satellite searching problem［J］.Journal of System Simulation，2007，19（23）：5487－5490（in Chinese）.［劉偉，孟新.衛星對地搜索問題研究［J］.系統仿真學報，2007，19（23）：5487－5490.］

［12］TANG Jianbing，JIAO Peng.Research on credibility of HLA simulation system based on BOM ［J］.Journal of University of Defense Technology，2008，30（5）：131－135（in Chinese）.［唐見兵，焦鵬.基于BOM的HLA仿真可信性研究［J］.國防科技大學學報，2008，30（5）：131－135.］

［13］Defense modeling and simulation office（DMSO）.high level architecture federation development and execution process（FEDEP）model version 1.5 ［S］.DMSO，2007.

［14］IEEE.IEEE draft recommended practice for high level architecture（HLA）－federation development and execution process（FEDEP）.IEEE P1516.5TM ［s］.2006.

［15］Wiesel E W，Petty M D，Mielke R R.Validity of models and classes of models in semantic composabiity ［C］.Proceedings of the Fall Simulation Interoperability Workshop，2008.