基于动态规划的海上编队侦察预警任务分配∗

（海军大连舰艇学院作战软件与仿真研究所 大连 116018）

1 引言

侦察预警是海上编队掌握海战场态势的重要基础，由于海战场情况复杂，威胁方向多，需要多个区域同时侦察［1］。海上编队可执行侦察预警任务的兵力包括舰艇［2］和预警机［3～5］，舰艇单次可执行任务时间长，但是预警探测距离相对较短；预警机单次执行任务时间短，预警探测距离远于舰艇。当同时有多个区域需要侦察时，此时需要合理进行任务分配。线性规划一般可以用于解决任务分配问题［6］，但是由于在侦察预警任务分配时，如果侦察区域要求的执行任务时间较长，此时必须要安排两架次以上预警机才能有效完成任务，这使得在进行线性规划前确定目标函数很困难。动态规划是军事运筹学中一种重要的方法，主要解决的是多阶段决策问题［7～9］，如果把侦察预警任务分配转化为多阶段决策问题，那么可以应用动态规划方法求解侦察预警任务分配的最优方案。

2 动态规划相关理论

2.1 多阶段决策问题

图1 状态转移图

当某类问题能够分为多个相互联系的阶段，每个阶段都需要采取决策，各个阶段的决策依赖于当前面临的状态，而且又能影响后续的发展，称之为多阶段决策问题，如图1所示。当各阶段的决策确定后，可得到一个决策序列，称之为策略。多阶段决策问题的目标就是求解最优策略［10～11］。

2.2 动态规划相关概念

动态规划是一种解决多阶段决策问题的方法，基于多阶段决策问题的动态规划包含以下要素［12］：

1）阶段与阶段变量：将问题分为若干阶段，阶段变量为描述阶段的变量，用k表示。

2）状态与状态变量：状态是各阶段开始所处的客观条件，状态变量为描述状态的变量，第k阶段的状态变量用xk表示，状态变量集合用Xk表示。

3）决策与决策变量：决策表示某阶段时可作出的决定，决策变量为描述决策的变量，第k阶段的决策变量用uk表示，决策变量的全体成为允许决策集合，记为Dk。

4）策略与最优策略：策略指的是一个按顺序排列的决策组成的组合，由过程k阶段开始到终止状态的过程的决策函数序列成为k子过程策略，记为Pk（xk）。

5）状态转移方程：如果已知第k阶段状态变量xk，并给定决策变量uk，则xk+1也可以随之确定，且存在状态转移方程Tk，满足 xk+1=Tk（xk，uk）。

6）指标函数和最优值函数：指标函数用来衡量所选策略的优劣，用Vk表示，该指标函数满足：

其中指标函数的最优值称为最优值函数，用fk（xk）表示。

3 侦察预警任务分配求解

3.1 任务分配预期目标

一般来说，海上编队有可执行侦察预警任务的舰艇和预警机若干，需要同时侦察的目标区域多个。由于预警机的单次执行任务时间较短，舰艇单次执行任务时间较长，另外预警机可以多架次配合执行任务，当侦察区域的任务时长不同时，兵力执行任务的方式和预警效果都会变化。单侦察区域目标可以选择的兵力为单机，双机，三机，单舰，对于上述四种兵力：当侦察区域的侦察要求时长在8h以内，兵力对应的预警效果量化值为a1、a2、a3和a4；当侦察区域的侦察要求时长在（8h，16h）区间以内，兵力对应的预警效果量化值为b1、b2、b3和b4；当侦察区域的侦察要求时长在（16h，24h）区间以内，兵力对应的预警效果量化值为 c1、c2、c3和c4；当侦察区域的侦察要求时长大于24h，兵力对应的预警效果量化值d1、d2、d3和d4。

侦察预警任务分配的预期目标就是利用海上编队兵力实现对侦察区域最好的预警效果。

3.2 基于动态规划建模

通过将侦察预警任务分配问题转化为多阶段决策问题，可对该问题进行动态规划建模。

1）确定过程的阶段：设需要同时侦察的目标区域有n个，可以将对n个侦察区域的兵力分配看成n个阶段决策过程，确定对第k个侦察区域分配的兵力类型和数量看成第k阶段的决策，k=1，2，…n。

2）确定状态变量xk：为可分配至第k，k+1，…n个侦察区域的兵力类型和数量，状态变量集合为Xk。

3）确定决策变量uk：为第k阶段对第k个侦察区域分配的兵力类型和数量。

4）确定允许决策集合Dk：第k阶段至少分配一个兵力，且不分配两种类型兵力。

5）确定状态转移方程：在侦察预警任务分配问题中，状态变量和决策变量间满足一下关系：xk+1=xk-uk，k=1，2，…n。

6）确定过程指标函数Vk：在多阶段决策过程过程中，第k阶段投入的兵力类型和数量不同时，会产生不同的预警效果，即为该阶段的指标函数vk，vk是状态变量xk与决策变量uk的函数，对于侦察预警的任务分配问题，指标函数Vk满足求和形式：

7）确定最优指标函数fk（xk）：为了获得最佳预警效果，最优值指标函数应取过程指标函数Vk的最大值，即

3.3 获取最优任务分配方案

基于对侦察预警任务分配的动态规划建模，求取最优任务分配方案可以转化以下方程式的求解

式（4）为递推方程，递推过程从k=n开始，利用兵力在不同侦察要求时长的预警效果量化值确定阶段指标函数，逐阶段逆推，直到求出f1（x1），可得到侦察预警任务分配的最优策略。

4 举例分析

4.1 问题描述

已知单个侦察区域目标可以选择的兵力为单机，双机，三机，单舰。当侦察区域的侦察要求时长在8h以内，兵力对应的预警效果量化值为0.5，0.4，0.05，0.05；当侦察区域的侦察要求时长在（8h，16h）区间内，兵力对应的预警效果量化值为0.1，0.2，0.6，0.1；当侦察区域的侦察要求时长在（16h，24h）区间内，兵力对应的预警效果量化值为0.05，0.15，0.5，0.3；当侦察区域的侦察要求时长大于24h，兵力对应的预警效果量化值为0.01，0.09，0.3，0.6。海上编队可分配的侦察预警兵力为三个预警机和一个舰艇，需要侦察的区域目标有三个，其中要求的侦察时长分别是10h，18h和26h，如何合理分配侦察预警兵力，使得总体预警效果最好。

4.2 问题求解

根据问题描述，有三个侦察目标区域，因此该问题可转换为三阶段决策问题，初始条件：n=3，x1为3个飞机和1个舰艇。设定第一阶段对侦察时长为10h的侦察区域兵力分配进行决策，第二阶段对对侦察时长为18h的侦察区域兵力分配进行决策，第三阶段对侦察时长为26h的侦察区域兵力分配进行决策，状态转移图如图2所示。

图2 侦察预警任务分配状态转移图

下面根据式（4）采用逆序法求解。

1）k=3时，此时对侦察时长为26h的侦察区域兵力分配进行决策，若还有侦察兵力为x3，且分配到该侦察区域的兵力为u3，则该阶段最大的侦察预警效果为

又因为f4（x4）=0，所以

因为允许决策集合要保证各阶段至少分配一个兵力且不同时分配两种不同类型兵力，因此决策变量集合X3满足：

允许决策集合D3满足：

根据以上分析，结合侦察区域的侦察要求时长大于24h的兵力预警效果量化值，可得到k=3时的侦察预警效果表，如表1所示。

表1 k=3时侦察预警效果表

2）k=2时，此时对侦察时长为18h的侦察区域兵力分配进行决策，若还有侦察兵力为x2，且分配到该侦察区域的兵力为u2，则该阶段最大的侦察预警效果为

根据允许决策集合规则，决策变量集合X2满足：

允许决策集合D2满足：

表2 k=2时侦察预警效果表

根据以上分析，结合侦察区域的侦察要求时长在区间（16h，24h）的兵力预警效果量化值，可得到k=2时的侦察预警效果表，如表2所示。

3）k=1时，此时对侦察时长为10h的侦察区域兵力分配进行决策，若还有侦察兵力为x1，且分配到该侦察区域的兵力为u1，则该阶段最大的侦察预警效果为

根据允许决策集合规则，决策变量集合X1满足：

允许决策集合D1满足：

根据以上分析，结合侦察区域的侦察要求时长在区间（8h，16h）的兵力预警效果量化值，可得到k=1时的侦察预警效果表，如表3所示。

表3 k=1时侦察预警效果表

此时最大侦察预警效果为0.85，对应的最优任务分配策略为侦察时长为10h的侦察区域分配两个飞机，侦察时长为18h的侦察区域分配一个飞机，侦察时长为26h的侦察区域分配一个舰艇。

5 结语

海上编队可执行侦察预警任务的兵力包括舰艇和预警机，不同兵力的侦察预警效果随单次执行任务时长的不同会有所变化，同时当侦察区域的侦察要求时长过长时，当同时有多个区域需要侦察时，这些情况会给侦察预警任务分配带来困难。线性规划方法是一个较好地解决任务分配问题的方法，但是无法在进行线性规划前确定目标函数。

本文利用动态规划方法将侦察预警任务分配转化为多阶段决策问题，借助于动态规划相关理论，明确了侦察预警任务分配的预期目标，构建了侦察预警任务分配动态规划模型，通过递推方程可求解得到侦察预警任务分配的最优方案。最后通过一个具体分配案例验证了上述方法，通过计算得到了侦察预警任务分配的最优方案，该方法可为海上编队辅助决策软件设计提供参考。