控制与决策  2020, Vol. 35 Issue (5): 1052-1062  
0

引用本文 [复制中英文]

孙鹏, 陈冠宇, 张杰勇, 武君胜. 基于突发事件的任务计划动态调整模型及算法[J]. 控制与决策, 2020, 35(5): 1052-1062.
[复制中文]
SUN Peng, CHEN Guan-yu, ZHANG Jie-yong, WU Jun-sheng. Dynamic task plan adjustment model and algorithm based on battlefield emergencies[J]. Control and Decision, 2020, 35(5): 1052-1062. DOI: 10.13195/j.kzyjc.2018.1096.
[复制英文]

基金项目

国家自然科学基金项目(61573017, 61773396);陕西省自然科学基金项目(2017JM6062);装备预研重点实验室基金项目(61421010201)

作者简介

孙鹏(1972-), 男, 教授, 博士, 从事指挥信息系统、指挥控制组织建模、体系建模等研究: E-mail: Sunypt@163.com;
陈冠宇(1994-), 男, 硕士生, 从事任务规划、敏捷指挥控制组织的研究, E-mail: 821932689@qq.com;
张杰勇(1983-), 男, 讲师, 博士, 从事指挥控制组织建模、体系建模等研究, E-mail: dumu3110728@126.com;
武君胜(1962-), 男, 教授, 博士, 从事指挥信息系统、软件工程等研究, E-mail: wujunsheng@nwpu.edu.cn

通讯作者

孙鹏, E-mail: Sunypt@163.com

文章历史

收稿日期:2018-08-09
修回日期:2018-12-26
基于突发事件的任务计划动态调整模型及算法
孙鹏 1,2, 陈冠宇 1, 张杰勇 1, 武君胜 3     
1. 空军工程大学 信息与导航学院,西安 710077;
2. 西北工业大学~计算机学院,西安 710072;
3. 西北工业大学 软件学院,西安 710072
摘要:由于战场环境的复杂多变, 在作战过程中会产生一些突发事件, 这些事件主要包括新任务出现和平台实体失效.为应对作战中的突发事件, 战前制定的任务计划在作战过程中需作出适应性调整, 战时任务计划的调整是作战指挥控制领域的难点问题.首先, 描述指挥控制组织的组成要素, 分析在突发事件下任务计划调整的约束条件, 建立以得到最小使命完成时间为目标函数, 以任务完成质量、任务插入顺序和调整稳定性为约束的数学模型; 其次, 提出一种基于可行任务执行序列和贪婪算法(greedy strategy, GS)的任务计划调整方法, 给出任务计划调整方法的设计思路和详细步骤; 最后, 结合联合登陆作战的案例进行仿真, 仿真实验验证了所提出方法应对突发事件的可行性和有效性.
关键词指挥控制组织    突发事件    任务计划    适应性优化    调整模型    贪婪算法    
Dynamic task plan adjustment model and algorithm based on battlefield emergencies
SUN Peng 1,2, CHEN Guan-yu 1, ZHANG Jie-yong 1, WU Jun-sheng 3     
1. College of Information and Navigation, Air Force Engineering University, Xi'an 710077, China;
2. School of Computer Science, Northwestern Polytechnical University, Xi'an 710072, China;
3. School of Software, Northwestern Polytechnical University, Xi'an 710072, China
Abstract: The high uncertainty of battlefield environment leads to some emergencies in the course of a battle. These events mainly include the emergence of new tasks and the failure of platform entities. In order to cope with emergencies in a battle, in the face of changes in the battlefield environment, the task plan formulated before the operation needs to be adjusted in the course of operations, and the adjustment of wartime task plan is a difficult issue in the field of command and control. Firstly, the components of the command and control organization are described, the constraints in the task plan adjustment are analyzed, a mathematical model is established, which takes the minimum mission completion time as the objective function, and task completion quality, task insertion order and adjustment stability as the constraints. Then, a mission planning adjustment algorithm based on the feasible task execution sequence and the greedy algorithm is proposed. The design ideas of adjustment method and detailed steps of the task plan adjustment method are given. Finally, combined with the joint landing operations case simulation, the simulation experiment verifies the feasibility and effectiveness of the method in dealing with emergencies.
Keywords: command and control organization    battlefield emergencies    mission planning    adaptive adjustment optimization    adjustment model    greedy algorithm    
0 引言

作战任务由作战使命分解得到, 任务完成的好坏直接影响作战使命能否达成[1], 因此, 如何合理高效地为任务分配平台资源, 保证每个任务的完成质量, 已经成为现阶段指挥控制领域内的热点问题[2-4].

目前, 国内外诸多学者对任务计划的制定问题进行研究, 并取得了一定的成果.文献[5]提出了多维动态列表规划(multidimensional dynamic list scheduling, MDLS)与成对交换(pair wise exchange, PWE)算法相结合的方法, 以解决任务与资源之间的分配问题; 文献[6]在MDLS算法的基础上进行改进, 提出了多优先级列表动态规划(multiPRI list dynamic scheduling, MPLDS)算法; 文献[7]提出了基于动态列表调度和遗传算法的任务-平台资源匹配方法.在任务计划的调整方面, 文献[8]提出了以方案改造代价为约束条件的任务计划调整方法.

随着战场环境复杂多变, 战场上可能出现各种不确定性因素[9-12].作战任务会根据变化的战场态势进行改变, 例如, 出现任务增加、任务位置改变、任务处理时间增加、平台损毁等情况[12].突发事件发生后, 战前拟定的任务计划无法适用于变化后的作战环境, 因此任务和平台发生改变后, 及时地调整任务-平台分配方案, 修改战前作战计划, 以使作战使命顺利达成.

目前, 关于战前平台资源调度方案的制定已经取得了许多成果[13-16], 但在任务计划的适应性调整上研究较少.鉴于此, 本文建立了任务计划调整的数学模型, 基于可行任务执行序列与贪婪算法进行模型求解, 最后结合具体的作战案例进行仿真实验, 通过数值仿真验证所提出算法的可行性和有效性.

1 任务计划调整问题建模

为了保持指控组织的稳定性, 任务计划的调整不能依赖于重新制定新的任务计划, 而是对某些任务执行精度低于阈值的任务进行平台资源的重新分配, 未受突发事件影响的任务则保持原有的任务-平台关系, 进而保证组织不会因复杂的关系调整造成不稳定.

1.1 基本概念

文中涉及到的基本概念定义如下.

定义1(任务T)  使命是战役要达到的目标, 任务是将使命分解后得到的军事行动.任务的完成需要调用一个或多个平台.在作战使命MP中, 每个任务Ti(i=1, 2, …, NT)都有以下属性, 其中NT为任务的总数:

1) 任务Ti的开始时间ts, i;

2) 任务Ti的处理时间tp, i;

3) 任务Ti的平面坐标Loc Ti =(xi, yi);

4) 任务Ti的优先权系数Pri;

5) 任务Ti的资源需求矢量Ri, Ri=[Ri1, …, Ril, …, RiL], 其中RiL是任务Ti需要L类型资源的能力数值.

定义2(资源R)  资源是兵力组织在作战活动中不可再分割的基本单元, 不同类型的资源具有不同的能力.任务的执行需要一定数量的平台, 每个平台具有一种或多种类型资源.例如火力打击资源、情报侦察资源, 这些资源不能单独存在, 而是寄托在物理平台上.描述C2组织基本的资源能力矢量为F=[f1, f2, …, fL], L为资源的类型数.

定义3(平台P)  平台在指控组织中承载着资源, 是直接执行和完成作战任务的实体.在作战使命MP中平台实体Pj(j=1, 2, …, NP)具有以下属性, 其中NP为平台实体的数目:

1) 平台Pj的移动速度vj;

2) 平台Pj的平面坐标Loc Pj =(xj, yj), 平台实体位置是可变的;

3) 平台Pj的资源能力矢量rj, rj=[rj1, …, rjl, …, rjL], 其中rjl是平台Pj拥有的l类型资源的能力数值.

任务、资源与平台的关系如图 1所示.

图 1 任务、资源与平台关系

在复杂多变的战场环境中, 影响作战的突发事件随时会出现.这些突发事件主要包括任务新增和平台失效, 当出现新的作战任务时, 需要为新的任务分配平台资源; 当出现平台损毁时, 需要为受到影响的任务重新分配平台资源.

1.2 相关变量定义

按照战前制定的任务计划执行各个作战任务, t时刻, 部分任务的状态如图 2所示.

图 2 任务分类

任务执行完成时间在t时刻前的为已完成任务Tend; 任务开始执行时间在t时刻后的为未执行的任务Te; 时刻t介于任务开始时间与结束时间之间的, 为正在进行的任务Tnow:

1) t时刻, 未执行任务Te组成的集合为STwait(t) ={Te1, Te2, …, TeN(t)}, 其中N(t)为t时刻使命中待执行的任务总数.战场上所有平台集合为SP(t) = {Pf1, Pf2, …, PfPN(t)}, 其中PN(t)为t时刻平台的总数, 若在使命的执行过程中未发生平台损毁的事件, 则PN(t)一直等于NP.

2) 分配变量mij, 若平台Pj分配给了任务Ti, 则mij为1, 否则mij为0.

3) 使命的完成时间MIT, 即使命中最后一个任务的结束时间, 有

(1)

4) 使命执行中遇到突发事件后, 未执行任务组成的集合为STwait(t') = {Tg1, Tg2, …, TgN(t')}, 平台的集合为SP(t')={Ph1, Ph2, …, PhM(t')}.

5) 分配变量m(t)ijT-P, 若m(t)ijT-P=1, 则平台Pfj被分配处理任务Tei, 否则m(t)ijT-P=0.任务-平台实体调度方案为M(t)T-P=(m(t)ijT-P)N(t)× PN(t), 调整后的分配方案为M(t')T-P = (m(t')ijT-P)N(t)× PN(t).

6) 初始任务计划调整前的任务执行序列为TS, TS=[TS1, TS2, …, T_SNT]. TS内任务的顺序即为任务的执行顺序, TS在战前准备阶段由任务规划算法得到, 常用的算法有MDLS算法、MPLDS算法、DLS算法等[5].

7) BEFORE(i)为任务Ti的直接前导任务集.

8) BACK(i)为任务Ti的直接后续任务集.

9) 任务Ti分配到的平台情况可以用矢量yi表示

yil是0-1变量, 表示执行任务Ti的平台Pj是否具有任务Ti所需的l类型资源, 若具有, 则yil=1, 否则yil=0.

1.3 目标函数

调整后的方案有多种, 选择在新的使命环境MP'下, 使命完成时间最短的平台-任务分配方案作为调整后的方案, 将最小化使命完成时间作为调整的目标函数, 有

(2)
1.4 约束条件 1.4.1 任务精度约束

一个任务的完成需要多种类型的资源, 某类资源需求的匹配情况由资源满足度Zil衡量, 资源满足度是任务中某类资源的实际数量与需求数目的比值.结果大于等于1, 表明该资源的需求完全满足; 结果小于1, 则该结果即为满足程度.因此, 任务Ti所需的l类型资源的满足度Zil

(3)

任务Ti的精度Acc(i)反映了任务内各类资源满足度的总体情况, 采用求几何平均的方法可得

(4)

其中: γ(i)为当前处理任务所需资源类型的集合, |γ(i)|为集合中类型的数目.

若任务Ti中出现某类型资源满足度为0的情况, 则表示该任务不能被完成符合实际情况.每个任务的完成精度要高于阈值γ, 由下式可得整个使命的完成精度Accuracy:

(5)

调整后的任务-平台方案应满足使命完成精度高于阈值δ的要求, 阈值结合具体使命确定.

式(5)中wi代表任务的权重, 反应了任务Ti在整个作战使命内的重要程度, 本文wi取任务总数的倒数, 即每个任务重要程度相同.单个任务和使命都有完成的精度要求, 即

(6)
1.4.2 新增任务分配顺序约束

T时刻战场环境发生变化, 记录下任务计划调整前序列TS中还未执行任务序列, 记为TSwait= [TS1, TS2, …, TSk, …, TSK ], TSkSTwait(t), K为序列中任务的总数, TSwait内任务的排列顺序参照TS中任务的顺序.

根据战场情况添加作战任务, t时刻新增的任务为Tadd.将新增的任务Tadd插入TSwait后, 得到新的任务分配序列

Tadd插入的位置为b, 则该位置应当满足Tadd的直接前续任务都在该位置之前, Tadd的后续任务都在该位置之后, 即

(7)
1.4.3 调整的稳定性约束

在方案的调整中, 要符合最小变更原则, 以保持组织结构的稳定.因此, 方案调整只为任务精度Acc(i) < γ的任务重新分配平台, 即新增加的任务集合和受平台损毁而导致任务精度低于阈值的任务.

平台损毁影响到的任务为STimpact = {Tgi||PhjSPbroken, m(t)ijT-P = 1}∩ST(t'), 损毁平台为SPbroken = SP (t)-SP(t)∩ SP(t').任务精度Acc(i)≥γ的任务集合为STkeep(t') = STwait(t')-STadd -STimpact.为符合最小变更原则, 调整的约束为

(8)

此约束表示任务精度Acc(i)≥γ的任务调整前后调用的平台一致.

1.5 问题模型

结合目标函数和各类约束条件, 构建的任务计划调整模型如下所示:

(9)

其中m(t')ijT-P为模型的决策变量.

模型(9)的突出特点是, 只为新增加的任务或平台损毁后任务执行精度低于阈值的任务重新分配平台, 其他任务精度高于阈值的任务, 继续按照战前制定的任务计划执行作战任务.传统的方法是对任务计划进行重新制定, 本文模型既避免了对任务计划的大幅度调整, 也降低了求解问题的复杂度.

2 基于可行任务执行序列和贪婪算法的求解方法 2.1 算法整体流程

按照战前制定的任务计划执行任务, t时刻突发事件产生, 战场态势发生改变, 可能会出现任务增加或平台损毁等突发事件.当出现任务新增的事件时, 任务执行序列中要插入新增的任务, 任务执行序列需要发生改变, 平台损毁后因为不涉及任务数目的变化, 可采用原来的任务分配序列.因此对任务计划的调整可根据是否有任务增加而划分为两种情况, 同时出现任务增加和平台损毁的情况可以归为任务增加进行处理.算法整体流程如图 3所示.

图 3 算法整体流程

step 1: t时刻突发事件产生, 判断变化是否有增加的任务, 若只发生平台损毁则转至step 4.

step 2:若有新增任务, 则需将新增任务添加至任务执行序列, 若新增任务有多种可行的插入位置, 则每个插入位置都能够对应一个任务执行序列.

step 3:在每种任务执行序列下使用贪婪策略进行求解, 求解后转至step 5.

step 4:若只发生平台损毁, 则结合调整之前的任务执行序列, 使用贪婪算法为相关任务重新分配平台.

step 5:选择执行时间最短的任务分配方案作为调整后的最佳方案.

新增的任务如何插入到任务执行序列, 以及贪婪策略的运用是否得当, 都会影响最终输出的调整方案是否切实可行, 因此下文介绍这两个核心环节的详细流程.

2.2 将新增任务插入任务执行序列

t时刻增加了新的作战任务Tadd, 则将新的任务Tadd按照约束公式(7)插入到TSwait中, 得到TS'.每个新增任务符合约束的插入位置可能是1个或多个, 每个满足约束条件的插入位置都会对应一个TS', 因此对应的TS'也可能不止1个.找出所有TS'并存入分配序列集合Sequence中, Sequence={TS'1, TS'2, …, TS'SQ}, SQ为集合中任务执行序列的总数.具体插入流程如下.

为了找出所有可行的任务执行序列(如图 4所示), 采用遍历方法, 将Tadd依次插入TSwait中.

图 4 新增任务插入示意图

step 1:第1个插入位置在TS1之前, 判断Tadd插入此位置能否满足约束公式(7), 即前导任务集合是否为空, 若为空, 则能够插入在此位置, 在Sequence中记录Tadd插入在TS1之前所形成的任务执行序列.

step 2:令k依次取2~K, 判断Tadd插入在TSk-1TSk之间时能否满足约束公式(7), 若能满足则在Sequence中记录Tadd插入在TSk-1TSk之间位置时得到的TS'.

step 3:最后的插入位置在TSk之后, 判断Tadd能否满足约束条件, 只需判断Tadd的后续任务集合是否为空集, 若为空集, 则能够插入在TSk之后.

step 4:在集合Sequence中记录step 1 ~ step 3所得到的任务执行序列, 由此可得到所有满足新增任务插入约束的任务执行序列.

2.3 基于贪婪策略的平台资源分配

任务-平台的分配问题, 本质上是组合优化寻找最优解的问题, 因此可以采用贪婪算法的思想对模型进行求解.

需要重新分配平台的任务集合STassign=TaddSTimpact= {Tassign1, Tassign2, …, Tassignas, …, TassignAS.其中: AS为需要重新分配的任务总数, T_{assignAS}分配到的平台集用SPas表示.

若没有出现任务新增, 则任务的执行序列为TSwait, 序列集合{Sequence}内只有TSwait; 若出现新增任务, 则任务执行序列集合Sequence内有一个或多个TS'.

定义分配方案组成的集合为O, O = { MBest1, MBest2, …, MBestV}, 其中V由Sequence中元素的数目确定.

step 1:令v=1.

step 2:从Sequence内选择任务序列TSv'.

step 3:给STassign中的每一任务都分配战场上全部平台资源, 即∀ TassignasSTassign, SPTassignas= SP(t'), STkeep中的任务遵照约束公式(8)按原任务计划分配平台, 以此作为初始分配方案M0, 计算M0下的使命完成时间MIT0, 令as = 0.

step 4:若as≤AS, 则从STassign中选择任务Tassignas, 为此任务进行平台删减, 令as=as+1, 否则转至step 7.

step 5:当as=1时, 将M0、MIT0作为Mbest、MITbest; 令Mtemp=Mbest, MITtemp=MITbest, 从SPas中选择一个平台进行删减, 删除平台后, 任务Tassignas的精度应满足Acc≥γ, 删除的平台是本轮删减中可使任务执行时间MIT减少最多的平台, 此分配方案记为Mbest, 使命完成时间记为MITbest, MITbest即为本轮删减中的最优解.

step 6:若删除SPas中的任意平台都会造成Acc < γ, 或者使命执行时间不满足小于等于上一轮执行时间, 则停止删减, 返回step 4, 若未满足任务删减的停止条件, 则返回step 5.

step 7:在分配方案集合O中记录TSv'下的最优方案Mbest.令v=v+1, 若v≥SQ, 则从集合O中输出使命执行时间最短的Mbest作为调整过后的分配方案, 否则返回step 2.

结合上文所述的具体步骤, 采用贪婪策略进行求解的流程如图 5所示.

图 5 采用贪婪策略求解的具体流程
3 案例分析

算例1[17]  我方部队计划进行一次抢滩登陆的作战行动, 行动包括占领敌方的港口和机场, 仿真算例的作战态势如图 6所示.

图 6 仿真算例的作战态势图

该作战态势图需要执行的作战任务如下:北区防御T1、南区防御T2、北区补给T3、南区补给T4、清除海区障碍T5、压制高地T6、抢占北滩T7等18个作战任务.任务之间的序列关系如图 7所示.该仿真算例可使用的平台资源包括:驱逐舰、护卫舰、两栖工兵分队、步兵分队、近距离空中支援作战飞机、舰载战机、侦察卫星等, 共NP=20个平台资源.

图 7 任务关系

作战任务的属性信息和平台资源的属性信息如表 1表 2所示, 其中任务处理时间的单位为小时.在表 1表 2中, 任务资源能力需求和平台资源能力共有8种, 分别对应如下: R1r1表示对空防御能力; R2r2表示对海防御能力(反舰); R3r3表示反潜能力; R4r4表示炮火压制能力; R5r5表示地面部队进攻能力; R6r6表示装甲兵进攻能力; R7r7表示排雷能力; R8r8表示侦查能力.

表 1 任务属性
表 2 平台属性

考虑到实际情况, 所有平台的初始位置设为(82, 41), 分配任务后, 平台由初始位置移动到第1个需要执行的任务所在位置.

根据图 7所示的任务关系以及表 1表 2任务和平台的属性信息, 采用MDLS算法进行战前任务规划, 采用长度加权算法(weighted length algorithm, WL)计算任务优先级, 函数选择WL算法[5], 得到的任务分配方案如图 8所示, 每个任务的执行精度均为1, 满足每个任务的资源需求.

图 8 调整前的任务计划甘特图

多维动态列表规划算法MDLS是进行任务-平台资源分配的常用方法, 该算法是一种快速启发式算法, 实现简单[5].复杂的军事资源调度问题大多采用MDLS算法[15-16], 因此采用MDLS算法求解初始使命下的任务平台分配方案.在最初的作战条件下, 任务执行的序列为TS=[T5, T6, T1, T3, T4, T17, T18, T2, T7, T8, T9, T11, T13, T10, T12, T15, T14, T16], 使命的完成时间为192.952 9 h.

3.1 任务增加事件的仿真分析 3.1.1 任务增加发生在前期

使命执行到t=50时, 根据战场态势的变化对作战使命进行调整, 需要新增加任务T19.任务T19插入图 8T5T7之间.任务T19的位置为(28, 78), 资源需求矢量为[0, 0, 8, 0, 0, 6, 0, 10], 任务执行时间为10 h.

图 8可知, 当t=50时, 任务T1, T3, T4, T5, T17已经执行完毕, 任务T6, T18正在执行还未结束, 执行完毕和正在执行的任务不需要进行任务分配.当t= 50时, 待执行任务集合STwait={T7, T2, T8, T9, T10, T11, T12, T13, T14, T15, T16}, 任务执行顺序TSwait=[T7, T8, T9, T11, T13, T10, T12, T15, T14, T16], 新增的任务T19根据约束条件添加至TSwait后得到TS', TS'=[T19, T7, T8, T9, T11, T13, T10, T12, T15, T14, T16].

采用第2节所述的调整方法, 求解出增加任务后的最优任务-平台方案, 以及任务增加后所有任务的执行情况, 阈值γδ均设置为1.

任务增加后的甘特图如图 9所示, 新增的任务在图中以绿色框显示.新增任务T19, 为其分配的平台为P2P17P19P20.任务增加后, 使命的完成时间由192.952 9 h变为199.524 0 h.

图 9 调整后的任务计划甘特图(任务增加发生在前期)
3.1.2 任务增加发生在后期

t=110时, 新增加任务T19.任务T19插入图 8T14T16之间.任务T19的位置为(5, 95), 资源需求矢量为[0, 0, 0, 0, 0, 8, 0, 6], 任务处理时间为20 h.

图 8可见, 当t=110时, 任务T12T13正在执行待执行任务集合STwait={T10, T14, T15, T16}, 任务执行顺序TSwait=[T10, T15, T14, T16], 新增的任务T19根据约束条件添加至TSwait中, 得到TS', TS'=[T10, T15, T14, T19, T16].任务增加后的甘特图如图 10所示, 新增的任务在图中以绿色框显示.

图 10 调整后的任务计划甘特图(任务增加发生在后期)

图 10可见, T19分配到的平台为P12P13P17P18P19P20, 分配的平台资源满足任务T19的需求, 其余任务分配到的平台与原分配方案相同.

任务增加后, 使命的完成时间由192.952 9 h增加至206.124 0 h, 执行时间多出约14 h, 新增任务的执行时间为20 h, 该调整算法较好地解决了任务增加的问题.

3.2 平台损毁事件的仿真分析

使命执行到t=60时发生平台损毁, 受损的平台为P7.由图 8可见, 原分配方案中平台P7负责的任务T11T12精度低于阈值, 需对原任务分配方案进行调整, 任务T11T12重新分配平台, 阈值γ和δ均设置为1.

平台P7损毁前任务T11T12的平台分配情况如表 3所示.平台P7损毁后, 进行任务计划调整, 为任务T11T12重新分配平台, 分配平台如表 4所示.

表 3 平台损毁前
表 4 平台损毁后

调整中, 只为任务T11T12重新分配平台资源, 其他任务分配的平台不变, 在满足平台相关约束的条件下, 调整后的甘特图如图 11所示.

图 11 调整后的任务计划甘特图(平台损毁)

调整后使命的结束时间变为206.209 4 h, 相比初始的使命完成时间, 平台P7损毁后使命完成时间向后推移了14, 满足要求, 解决了平台损耗后的任务计划调整问题.

3.3 算法对比分析

为验证本文所采用的贪婪算法(greedy strategy, GS)在解决任务计划调整问题上的优越性, 将贪婪算法与双重贪婪算法(dual greedy strategy, DGS)和一致贪婪算法(consistent greedy strategy, CGS)进行对比. 3种方法的差异体现在对冗余平台的删减方法中.删减前, 为每个需要重新分配平台的任务分配组织内的所有平台, 如图 12所示.

图 12 要调整的任务分配所有平台资源

GS算法在每一步选择要删除的平台时, 判断Timpact1~ Timpact3所分配的平台中, 删除哪个平台可使作战使命的完成时间缩短最多. DGS算法由Timpact1~Timpact3依次进行平台删减操作, 当从Timpact1平台集内任意删减一个平台后, Timpact1的任务需求便不能得到满足, 开始对Timpact2的平台集进行任务删减. CGS算法考虑受影响任务Timpact1Timpact2Timpact3的优先级, 先执行优先级高的任务, 进行冗余平台删减时, 依次从任务优先级高的任务开始进行删减.

遗传算法(genetic algorithm, GA)和模拟退火算法(simulated annealing, SA)也被用于求解任务计划的规划问题[7, 14, 18-19], 因此也将本文算法与遗传算法和模拟退火算法进行对比, 设置任务的完成质量不低于1, 进行10组仿真实验, 突发事件随机产生, 实验结果如图 13图 14所示.图中:菱形为GS算法, 六角星为DGS算法, 圆形为CGS算法, 五角星为GA算法, 方形为SA算法.

图 13 使命完成时间比较
图 14 算法耗时比较

图 13可见, GS算法、DGS算法、CGS算法、GA算法和SA算法中, 采用GS算法进行任务计划调整得到的使命完成时间最低, 进行调整的效果最好, CGS算法因为严格按照任务的优先级执行任务, 降低了平台资源的使用效率, 导致整体的使命完成时间较长, 该算法适用于紧急任务需要优先保障情况下的计划调整.

图 14可见, 在算法耗时方面, GA算法耗时较高, SA算法的用时也高于3种贪婪算法, 3种贪婪算法的耗时相差不多, 算法运行时间较低.采用GS算法在解决本文问题的耗时上明显优于智能算法, 在解决实时性要求较高的任务计划调整问题上更具有优越性.

4 结论

本文研究了任务新增和平台损毁这两类突发事件下的任务计划调整问题, 建立了以最小化使命完成时间为目标的任务计划调整模型, 结合可行任务执行序列和贪婪算法提出了模型求解的方法.最后以登陆作战案例进行实验仿真, 初始任务计划由MDLS算法对使命求解产生, 分别在两类突发事件下对任务计划进行适应性调整, 并将本文算法与双重贪婪算法、一致贪婪算法、遗传算法和模拟退火算法进行对比, 实验结果表明了所提出方法用于任务计划调整的有效性和优越性.

参考文献
[1]
Han X, Bui H, Mandal S. Optimization-based decision support software for a team-in-the-loop experiment:Asset package selection and planning[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2013, 43(2): 237-251. DOI:10.1109/TSMCA.2012.2201467
[2]
Bui H, Han X, Mandal S, et al.Optimization-based decision support algorithms for a team-in-the-loop planning experiment[C].Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics.San Antonio: IEEE, 2009: 4684-4689.
[3]
Yu F, Tu F, Pattipati K R. Integration of a holonic organizational control architecture and multi-objective evolutionary algorithm for flexible distributed scheduling[J]. IEEE Transaction on System, Man, and Cybernetics, 2008, 38(5): 1001-1017. DOI:10.1109/TSMCA.2008.923082
[4]
Han X, Mandai S, Pattipati K R, et al. An optimization-based distributed planning algorithm:A blackboard-based collaborative framework[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2014, 44(6): 673-686. DOI:10.1109/TSMC.2013.2276392
[5]
Levchuk G M, Levchuk Y N, Luo J, et al. Normative design of organizations, part Ⅰ:Mission planning[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2002, 32(3): 346-359. DOI:10.1109/TSMCA.2002.802819
[6]
阳东升, 张维明, 刘忠, 等. 战役计划的数学描述与求解算法研究[J]. 系统工程理论与实践, 2006, 26(1): 26-34.
(Yang D S, Zhang W M, Liu Z, et al. Research on mathematical description and solving algorithms of tasks scheduling for campaign[J]. Systems Engineering-Theory & Practice, 2006, 26(1): 26-34. DOI:10.3321/j.issn:1000-6788.2006.01.004)
[7]
张杰勇, 姚佩阳, 周翔翔, 等. 基于DLS和GA的作战任务-平台资源匹配方法[J]. 系统工程与电子技术, 2012, 34(5): 947-954.
(Zhang J Y, Yao P Y, Zhou X X, et al. Approach to operation task and platform resource matching based on DLS and GA[J]. Systems Engineering and Electronics, 2012, 34(5): 947-954. DOI:10.3969/j.issn.1001-506X.2012.05.17)
[8]
孙鹏, 李锴, 姚佩阳, 等. 任务计划适应性改造优化建模及方法[J]. 空军工程大学学报:自然科学版, 2016, 17(1): 90-95.
(Sun P, Li K, Yao P Y, et al. Modeling and method of adaptive reform and optimization for mission planning[J]. Journal of Air Force Engineering University:Natural Science Edition, 2016, 17(1): 90-95.)
[9]
张迎新, 陈超, 刘忠, 等. 资源不确定军事任务计划预测调度模型与算法[J]. 国防科技大学学报, 2015, 35(3): 30-35.
(Zhang Y X, Chen C, Liu Z, et al. Method for modeling and solving military mission planning with uncertain resource availability[J]. Journal of National University of Defense Technology, 2015, 35(3): 30-35.)
[10]
刘海啸.敏捷C2组织结构设计与调整方法研究[D].长沙: 国防科学技术大学研究生院, 2010.
(Liu H X.Design and adjust methodology of command and control organization[D].Changsha: Graduate School, National University of Defense Technology, 2010.)
[11]
修保新.C2组织结构设计方法及其鲁棒性、适应性分析[D].长沙: 国防科学技术大学研究生院, 2006.
(Xiu B X.Design methodology of C2 organizational structure and its analysis of robustness and adaptivity[D].Changsha: Graduate School, National University of Defense Technology, 2006.)
[12]
吴瑞杰, 孙鹏, 孙昱. 分布式任务计划动态调整模型及算法[J]. 系统工程与电子技术, 2017, 39(2): 322-328.
(Wu R J, Sun P, Sun Y. Distributed dynamic task plan adjustment model and algorithm[J]. Systems Engineering and Electronics, 2017, 39(2): 322-328.)
[13]
万路军, 姚佩阳, 周翔翔, 等. 多编组协同任务分配模型及DLS-QGA算法求解[J]. 控制与决策, 2014, 29(9): 1562-1568.
(Wang L J, Yao P Y, Zhou X X, et al. Cooperative task allocation methods in multiple groups using DLS-QGA[J]. Control and Decision, 2014, 29(9): 1562-1568.)
[14]
陈志旺, 陈林, 白锌, 等. 求解约束多目标区间优化的交互多属性决策NSGA-Ⅱ算法[J]. 控制与决策, 2015, 30(5): 865-870.
(Chen Z W, Chen L, Bai X, et al. Interactive multi-attribute decision-making NSGA-Ⅱ for constrained multiobjective optimization with interval numbers[J]. Control and Decision, 2015, 30(5): 865-870.)
[15]
张杰勇, 姚佩阳, 李凡. 完成时间限制下的任务-平台关系设计模型及算法[J]. 系统工程与电子技术, 2012, 34(8): 1621-1629.
(Zhang J Y, Yao P Y, Li F. Task-platform relation design model and its algorithm under completion time constraint[J]. Systems Engineering and Electronics, 2012, 34(8): 1621-1629. DOI:10.3969/j.issn.1001-506X.2012.08.17)
[16]
陈行军, 齐欢, 阳东升. 含时间窗联合作战计划问题的建模与求解[J]. 系统工程理论与实践, 2012, 32(9): 1980-1984.
(Chen X J, Qi H, Yang D S. Modeling and solution of joint operational plans with time window[J]. Systems Engineering-Theory & Practice, 2012, 32(9): 1980-1984.)
[17]
Yu F, Tu F, Pappipati K R. Integration of a holonic organizational control architecture and multiobjective evolutionary algorithm for flexible distributed scheduling[J]. IEEE Transactions on Systems, Man, and Cybernetics, 2008, 38(5): 1001-1017. DOI:10.1109/TSMCA.2008.923082
[18]
包卫东, 王江峰, 张茂军. 一种改进的基于MDLS与GA的作战资源分配算法[J]. 火力与指挥控制, 2008, 33(9): 18-21.
(Bao W D, Wang J F, Zhang M J. A novel algorithm of task resource distribution based on MDLS and GA[J]. Fire Control and Command Control, 2008, 33(9): 18-21. DOI:10.3969/j.issn.1002-0640.2008.09.006)
[19]
Mu L, Feng Y H, Zhang W M, et al.The adaptive optimization of C2 organization decision layer structure based on nested improved simulated annealing algorithm[C].Proceeding of the IEEE International Conference on Intelligent Computing and Intelligent Systems.Xiamen: IEEE, 2010: 682-687.