车载光学测量设备任务调度问题建模与求解*

柴 华，宋旭民，赵 乾，胡 涛

(1. 航天工程大学 航天指挥学院， 北京 101416； 2. 北京市遥感信息研究所， 北京 100089；3. 中国卫星发射测控系统部， 北京 100094)

空间目标编目是管理空间资产、维护空间环境的重要手段[1-2]。随着航天产业的快速发展与空间目标的不断增多，提升空间目标探测能力已成为空间目标编目的迫切需求。与传统大型地基测量设备相比，车载光学测量设备[3-4]具有成本低、小型化、可移动、可批量部署等优点，为提升空间目标探测能力提供了一种新的思路，具有诱人的应用前景。本文以此为背景，开展车载光学测量设备观测任务调度问题研究，所构建的数学模型与分析方法对车载光学测量设备的运用实践具有一定的参考价值。

1 问题提出

本文涉及的车载光学测量设备(以下简称设备)的使用具有如下特点：设备部署于特定的地面测站，在空间目标过顶的一个较短的时间区间内，设备可对其进行观测，该时间区间称为设备对空间目标的观测窗口(观测窗口的计算涉及设备工作机理与空间目标需满足的运动特性、光学特性约束，这一问题并非本文关注的重点，此处不再赘述)。设备可随载车沿公路机动，往返于车库与测站、测站与测站之间。设备机动到达特定测站后、具备观测状态前需要进行的准备工作的耗时称为展开时间topen，设备完成一次观测后、具备机动状态前需要进行的准备工作的耗时称为收拢时间tclose，设备在同一测站的两次观测之间需要进行的准备工作(伺服转动、搜索、捕获等)的耗时称为冷却时间tcool。

对上述车载光学测量设备的使用涉及一个观测任务调度问题，该问题可描述为：

现有M台测量设备Ei(i=1,2,…,M)，设备Ei的初始位置为Pi；所有设备最早可由t0时刻出发，需在t1至t2时间内对N个空间目标Tj(j=1,2,…,N)进行观测；有L个可供使用的测站Sk(k=1,2,…,L)，求最优的观测方案。

上述问题的本质是一个武器目标分配(Weapon Target Assignment, WTA)问题。WTA问题关注的核心是如何把具有不同杀伤力和经济价值的武器分配到不同的目标，构成整体效益最优的火力打击方案[5]。

国内外对WTA问题的探索可划分为模型研究与算法研究两类[6-7]。模型研究讨论如何将背景各异的工程实际问题抽象为可供求解的WTA数学模型[8]；算法研究则针对特定模型，考察如何给出效率更高的求解算法[5]。

WTA属于寻优决策问题，其模型研究主要聚焦三方面要素：第一，模型假设与自变量描述，即如何准确刻画问题的自变量；第二，约束条件确定，即如何排除无效解；第三，目标函数或评价指标选择，即如何衡量较优解。针对分析过程中是否考虑时间窗口约束，可将WTA模型进一步区分为静态模型与动态模型。美国早在20世纪50年代就开始了WTA建模研究。20世纪80年代，Hosein等[9]对WTA问题展开了系统研究，给出了静态WTA与动态WTA的定义，针对静态WTA问题提供了一般性的解决方案。Rosenberger等[10]探索了武器平台对多目标打击的WTA问题，增加了武器可用数量与效能两个约束条件，将武器目标分配抽象为一个线性整数规划模型。进入21世纪以来，国内学者对WTA建模问题开展了大量研究。韩松臣[11]提出了基于马尔科夫决策过程最优化的动态WTA方法。王正元等[12]建立了坦克战斗中的动态WTA模型并提出了求解方法。胡建[13]探索了大气层外导弹防御中多拦截器的目标分配问题。张先剑[14]构建了基于双方动态博弈的攻防对抗综合数学模型，并利用纳什均衡和帕累托最优算法进行了分阶段求解。针对传感器-武器-目标分配问题，王艺鹏等[15]等提出了一种分阶段建模与求解策略。上述对WTA模型的研究主要呈现两个特点：一是涉及大量相似而不相同的工程实际问题，使得建立的数学模型存在差异；二是对静态分配问题的研究较为充分，而动态分配问题尚未得到较好的解决。

自WTA问题诞生之日起，国内外学者一直致力于寻找更加有效的求解算法。20世纪80年代以前，对WTA问题的求解局限于传统算法，主要包括隐枚举法、分支定界法、割平面法、动态规划法等[5-6]。这些算法在数学上为精确算法，思想较为简单，但编程实现较为烦琐，且其收敛速度随着武器、目标数目的增多而变慢，难以处理维数较大的WTA问题。20世纪80年代以来，随着计算机技术的发展，一些新颖的启发式优化算法，如遗传算法、蚁群算法、粒子群算法、模拟退火算法、电磁算法及其混合优化策略等，为解决复杂问题提供了新的思路和手段。闫玉铎[16]在传统遗传算法基础上引入了1V1种群竞争机制、差分变异机制以及粒子群算法更新规则，提出了基于改进遗传算法的陆军分队级计算机生成兵力WTA问题求解方法。针对动态战场环境下多通道武器转火和来袭目标分阶段打击问题，邵诗佳[17]提出了一种改进的蚁群算法。夏维等[18]针对毁伤效能最大和用弹量最少两个目标函数，建立了基于改进型多目标粒子群优化算法的WTA模型，验证了算法的有效性。上述研究为WTA算法的不断完善提供了参考价值，然而，已有研究大多引入了一定的简化假设与理想条件，仍属理论研究范畴，在工程实际中的应用效果有待进一步检验。随着高新技术的发展与战场对抗强度的增加，适用于大规模动态WTA问题的求解方法仍然是后续研究的重点。

本文提出的属于广义、动态WTA问题。与经典的WTA问题相比，观测任务调度问题不仅将时间窗口纳入考虑，而且增加了测站这一维度。也就是说，观测方案涉及设备、测站、目标、窗口四者的映射关系，从而增加了问题的复杂性。针对这一复杂问题，已有的WTA模型无法使用：常用的表征武器-目标对应关系的自变量xij难以涵盖测站及窗口信息，而观测方案约束条件与评价指标也需要结合实际背景分析确定。为解决这一矛盾，提出了一套结构巧妙的数学模型，将观测方案简化为一个一维数组，并结合观测设备的工作流程给出了约束条件和评价指标的定义及计算方法。在此基础上，将观测方案寻优问题视为一个多属性决策问题[19-20]，通过蒙特卡洛抽样与线性加权综合寻找较优解，为观测方案的制定提供了一条有效途径。

2 问题建模

车载光学测量设备观测任务调度问题的建模分三部分，即观测方案的描述、方案约束的确定以及方案指标的提炼。在执行观测任务的过程中，一个观测要素指明了某台设备部署于某个测站在某个窗口观测某个目标，而观测方案实质上为若干观测要素的集合。为了确保一个观测方案切实可行，需要结合设备特点梳理确定方案约束，不满足方案约束的观测方案为无效方案；当存在多套可行观测方案时，为了进行排序评优，需要提炼观测方案的评价指标，从成本、收益等角度反映观测方案的优劣。

2.1 观测方案

观测方案描述策略如下：

1)利用已有的观测窗口算法，计算t1至t2时间内，设备部署在Sk测站对Tj目标的观测窗口集合Wj,k,q(q=1,2,…,qjk)，由表达式可知，该集合中窗口数目为qjk；

3)引入一个长度为qtotal的一维数组，数组中的第x个元素对应于第x个观测窗口，其取值y为0到M之间的整数，表示将第x个观测窗口分配给第y台设备以执行观测任务。

如图1所示，将M台设备的一个观测方案抽象为一个一维数组来表示。举例来讲，形如[1,0,2,1,0,3]的数组表示设备的观测窗口共有6个，观测方案指定第1台设备在第1和第4个窗口实施观测、第2台设备在第3个窗口实施观测、第3台设备在第6个窗口实施观测，其余窗口不实施观测。

图1 观测方案的描述Fig.1 Description of observation plan

2.2 方案约束

满不满足约束决定了一个观测方案是否可行。在方案寻优过程中，不满足约束的观测方案应该首先被排除。结合问题背景，提出观测方案应该满足如下约束。

2.2.1 设备转场约束

在一个观测方案中，一台设备可能需要往返于多个测站以执行多个观测任务。设备转场约束是指观测任务的编排应该将设备的机动时间、展开时间、收拢时间、冷却时间等因素纳入考虑，确保每一设备能够在给定的时间内完成所有必需的动作，如图2所示。

图2 单台设备典型观测任务流程Fig.2 Typical observation process of single equipment

设备转场约束的计算步骤如下。

步骤1：针对给定的观测方案，梳理所有涉及的设备及每一台设备需要实施观测的窗口集合。

步骤2：针对第i台设备，对其需要实施观测的窗口集合中的元素按照时间先后进行排序。

1)：设备由初始位置转场至第1个窗口对应测站实施观测需满足的时间约束为

(1)

式中，tmove(·)为已知地面上设备的初始位置与终点位置计算机动耗费时间的算子，该过程需考虑设备机动速度以及地理信息等因素，此处不再赘述。

步骤2)设备由第α个窗口对应测站转场至第α+1个窗口对应测站实施观测需满足的时间约束为

(2)

步骤4：重复步骤2、步骤3，检验观测方案涉及的所有设备转场时间是否足够，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足设备转场约束。

2.2.2 测站进出约束

在一个观测方案中，一个测站可能需要被多台设备使用以执行多个观测任务。测站进出约束是指观测任务的编排应该将设备进出测站所耗费的展开时间、收拢时间等因素纳入考虑，确保每一测站能够有效保障其被赋予的所有观测任务，如图3所示。

测站进出约束的计算步骤如下。

步骤1：针对给定的观测方案，梳理出所有涉及的测站及每一个测站需要实施观测的窗口集合。

步骤2：针对方案中的第k个测站，对其需要实施观测的窗口集合中的元素按照时间先后进行排序。

步骤3：设排序后第k个测站需要实施观测的窗口集合可表示为Wiβ,jβ,k,qβ(β=1,2,…,βk)，则测站进出约束的计算方法如下。

图3 单个测站典型观测任务流程Fig.3 Typical observation process of single station

1)如果第k个测站需要实施观测的窗口不超过1个，则该测站不存在测站进出约束。

2)如果第k个测站需要实施观测的窗口不少于2个，则第β个窗口与第β+1个窗口需要满足的测站进出约束为：

(3)

步骤4：重复步骤2、步骤3，检验观测方案涉及的所有测站进出时间是否冲突，一旦出现不等式不成立的情形，则终止计算，判定该观测方案不满足测站进出约束。

至此，给出任一观测方案必须满足的两个约束。需要指出的是，式(2)与式(3)中的第一式本质上是等价的。在实际操作中，为了减小计算量，两者取其一即可。

2.3 方案指标

方案指标是判定观测方案质量的依据。在选取方案指标的过程中，应该注意以下原则：①完备性，即选择的指标应该尽可能充分地涵盖反映观测任务过程的关键参数。②独立性，即选择的指标之间应该尽可能地保持独立，避免指标之间含义重叠。③定量性，即选择的指标应该便于量化计算，避免挑选界限模糊、主观性强的指标。

2.3.1 总机动距离

总机动距离刻画了一个观测方案中所有设备需要机动的距离的总和，为了降低观测方案的成本，总机动距离应该尽可能小。

总机动距离的计算步骤如下。

步骤1：针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合Wi,jα,kα,qα,(α=1,2,…,αi)，则第i台设备的机动距离可表示为：

(4)

式中，dmove(·)为已知地面上设备的初始位置与终点位置计算机动距离的算子，该过程需考虑地理信息等因素，此处不再赘述。

步骤2：总机动距离可表示为：

(5)

需要指出，对于观测方案中没有分配观测任务的设备，其机动距离取0。

2.3.2 总观测时长

总观测时长刻画了一个观测方案对所有空间目标观测的时间窗口长度的总和，为了提高观测方案的效益，总观测时长应该尽可能大。

总观测时长的计算步骤如下。

步骤1：针对给定的观测方案，在计算设备转场约束的过程中已经梳理得到了第i台设备需要实施观测的窗口集合并将其表示为Wi,jα,kα,qα(α=1,2,…,αi)，则第i台设备的观测时长可表示为：

(6)

步骤2：总观测时长可表示为：

(7)

需要指出，对于观测方案中没有分配观测任务的设备，其观测时长取0。

2.3.3 观测目标数目

观测目标数目刻画了一个观测方案能够覆盖的所有空间目标的数目，为了提高观测方案的效益，观测目标数目应该尽可能多。

观测目标数目的计算较为简单，针对给定的观测方案，梳理出所有涉及的空间目标的数目Ninvol即可。

至此，给出考察任一观测方案质量的三个指标。

3 问题求解

前文对车载光学测量设备观测任务调度问题进行了建模，接下来给出问题的求解策略。

1)给定已知条件，首先利用特定的观测窗口算法计算设备部署在所有测站对所有目标存在的观测窗口全集；

2)结合已知条件与观测窗口全集，利用Monte Carlo抽样方法抽取初始观测方案集合；

3)判定所有初始观测方案是否满足方案约束，剔除无效方案，获得可行观测方案集合；

4)计算所有可行观测方案的方案指标，利用多属性决策方法进行指标聚合，从而实现对观测方案的排序；

5)依据排序结果选定最优观测方案。

在上述求解策略中，多属性决策方法是解决问题的关键。

多属性决策方法是决策与评估领域的经典方法，用于支持分析人员在面对多个选项或方案时做出最优决定。多属性决策方法处理的一类常见问题是有限方案排序问题，即综合考虑多方面属性对不同方案质量进行评估的问题。

有限方案排序问题由以下两类要素构成：

1)方案集X={X1,X2,…,Xm}，即参与排序的可行方案的集合；

2)属性集O={O1,O2,…,On}，即反映方案质量的属性指标的集合。

方案集对应于所有可行的观测方案，属性集对应于方案指标。多属性决策方法的操作流程如图4所示。图4中，方案集与属性集为方法输入，评估结果为方法输出，由输入到输出需经决策矩阵构建、决策矩阵规范化、权重矢量确定与指标聚合排序四步，下文将依次给出其过程。

图4 多属性决策方法的操作流程Fig.4 Workflow of the multi-attributes-decision-making method

决策矩阵包含了参与决策的所有信息，若将方案Xi的属性指标Oj记为xij，那么决策矩阵可表示为：

(8)

考虑到不同属性指标的量纲与物理含义等存在差异，需要对其进行规范化处理，使不同指标之间具备可比性与可加性。常用的指标规范化方法包括矢量规范化方法、极性变差法、线性变换法、Z-Score法等。采用离散信息损失相对较少的线性变换法进行矩阵规范化处理，其思路可由式(9)描述。

(9)

(10)

权重体现了评价指标的重要性程度以及对评价对象分辨信息量的多少，如何确定权重是多属性决策方法研究的重点。常见的权重确定方法包括主观赋权法与客观赋权法。主观权重主要源于决策者和相关专家对于指标相对决策目标所起作用重要性的认知，体现了决策者的一种偏好，因此主观权重可以由决策者或者专家采取打分的方式确定，或者采用能使专家思维更加规范化的层次分析法获得。客观权重主要通过提取决策矩阵所蕴含的离散信息获得，一般包括方案集之间的分类信息和聚类信息。采用一种客观赋权法来实现对权重wA的确定，即文献[21]中的相关系数与标准差(Correlation Coefficient and Standard Deviation，CCSD)方法，该方法的基本思想是：①考虑任一指标与剔除其之后其他指标加权综合结果的相关性，如果相关系数大，表明该指标对评估结果影响较小，因而赋予其较小的权重，否则赋予其较大的权重；②考虑任一指标取值的标准差，如果标准差小，表明指标分布范围小，因而其对评估结果的影响较小，赋予其较小的权重，否则赋予其较大的权重。综合考虑相关系数与标准差，确定每一指标的最优权重。

CCSD方法具有简洁、有效、便于扩展等优点，其操作方法如下。

由式(10)出发，若将属性集中的指标Oj移去，则观测方案Xi的剩余总体效能将变为：

(11)

指标Oj与剩余总体效能EXij的相关系数可由式(12)给出。

(12)

Rj刻画了指标Oj与剔除Oj后的剩余总体效能EXij的相关程度。若Rj很大接近于1，表示Oj与EXij相关性很大，引入Oj对评估结果影响很小，因而赋予Oj较小的权重；反之，若Rj很小接近于-1，则表示Oj与EXij相关性很小，需要赋予Oj较大的权重。

另外，若对于不同方案，指标Oj取值的标准差很小，说明Oj对方案排序所起的作用小，因而赋予Oj较小的权重；反之，若指标Oj取值的标准差很大，则赋予Oj较大的权重。

综合相关性与标准差两方面特性，采取如式(13)所示的权重确定策略。

(13)

式(13)为3方程3未知数的非线性方程组，其求解可通过构造如式(14)所示的优化模型来实现。

(14)

4 仿真校验

首先给定初始条件，取t0、t1、t2时刻分别为:

t0=(2018-05-24 T 00:00:00 UTCG)

t1=(2018-06-01 T 00:00:00 UTCG)

t2=(2018-06-08 T 00:00:00 UTCG)

取设备载车的最大机动速度为60 km/h，设备的展开时间topen=3 h、收拢时间tclose=1 h、冷却时间tcool=0.5 h。

假设有6台观测设备，其基本信息见表1。假设需对4个空间目标实施观测，其在t1时刻的经典轨道根数见表2。假设可供使用的测站有4个，其基本信息见表3。

表1 观测设备初始条件

表2 空间目标在t1时刻的经典轨道根数

表3 测站初始条件

本算例利用了卫星工具包(Satellite Tool Kit, STK)软件[22]的卫星过境计算工具Access来计算设备观测窗口，针对每一测站，分别添加一个传感器对象Sensor，将Sensor类型设为简单圆锥形，锥角取60°，使用Access工具可以获得测站对目标的观测窗口。本例利用了地球圆球模型来计算设备的机动距离与机动时间，即假设对于球面上任意两点，设备以匀速沿球面劣弧由起点机动至终点。需要强调的是，对于更加精密的观测窗口算法与设备机动算法，本文提出的方法同样适用。

图5给出了利用Access工具计算得到的所有测站对所有目标的观测窗口的集合，图5中每一条彩色竖线均表示一个观测窗口。表4给出了测站1对目标1的11个观测窗口的具体细节，限于篇幅，不再给出其他窗口细节。

图5 所有测站对所有目标的观测窗口全集Fig.5 Universal set of observation windows of all stations for all targets

表4 测站1对目标1的观测窗口集合

由图5可知，在给定的初始条件下，共有140个观测窗口。因此，本文算例涉及的观测方案是长度为140的一维数组。

利用蒙特卡洛抽样方法抽取容量为10 000的初始观测方案集合，剔除无效方案后，得到3 080个可行方案。这些观测方案对应的指标分别如图6～8所示。

图6 可行观测方案的总机动距离Fig.6 Total move distance of feasible observation plans

图7 可行观测方案的总观测时长Fig.7 Total time interval of feasible observation plans

图8 可行观测方案的观测目标数目Fig.8 Target amount of feasible observation plans

图9 可行观测方案的总体效能Fig.9 Overall efficiency of feasible observation plans

由总体效能可知：3 080个可行观测方案中，第1 638个方案为最优方案，其对应的观测方案见表5。表5方案对应的3个指标分别为总机动距离19 897.26 km，总观测时长1 436 s，观测目标4个。

表5 最优观测方案

5 结论

本文为解决车载光学测量设备的观测任务调度问题提出了一套结构巧妙且扩展性强的数学模型与方法框架。将涉及设备、测站、目标、窗口四者映射关系的观测方案简化为一个一维数组来处理，从而使观测方案的寻优转化为一个多属性决策问题；随着对问题认识的不断加深与建模粒度的不断细化，方法中涉及的观测方案约束、观测方案指标、观测窗口算法、机动算法等环节均可改进并灵活替换，从而实现方法性能的快速提升。

需要指出的是，对于WTA这一NP完全问题，采用先进、高效的算法是快速获得满意解的保证。为验证所提数学模型与方法框架的有效性，采用了蒙特卡洛抽样与线性加权综合算法来求解问题，算法的计算效率与所得方案的质量仍然有一定的改进空间。在下一步研究中，将尝试引入遗传算法、蚁群算法等智能优化思想，探索提出更加适用的求解算法，给出更高质量的解决方案。