基于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］。

卫星是航天任务系统主要组成部分，主要用于对地观测、气象预报、卫星通信、科学探测等任务。以卫星为代表的航天器是在国家军事经济中的作用越来越重要。现在卫星技术不仅对国民经济发展至关重要，而且对于国家安全也是不可或缺的，其应用范围越来越广泛［3］。现在针对卫星的仿真研究较多，但多是针对局部技术的仿真［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模型则是在充分考虑两种模型的优缺点后建立的，即混合模型去掉不必要的冗余约束，并在两者间建立联系，同时还要针对混合模型给出合适的算法，达到快速求解问题的目的。混合MIP/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类。空间信息多任务规划原型系统只考虑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.