Exact algorithms and bounds for the dynamic assignment interdiction problem

We study a multi‐stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP‐hard, even when the attacker can interdict only one arc. We propose an exact exponential‐state dynamic‐programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373–387, 2017     

多阶段任务系统可靠性分析的ROBDD算法

针对Markov方法分析多阶段任务系统(Phased-Mission System,PMS)可靠性时的状态空间爆炸问题,基于层次化建模思想,建立了PMS任务可靠性的顶层系统二维决策图(Binary Decision Diagram,BDD)模型和底层部件Markov模型。通过分析BDD中的同构节点和冗余节点,提出顶层模型构造过程中的同构节点合并策略和冗余节点删除策略。利用上述节点压缩策略生成简化模型,提高模型构造和存储效率。基于PMS部件排序规则,给出了层次化模型的递归求解方法,该方法的计算复杂度与顶层模型中的节点总数呈线性关系。通过算例分析,对比采用节点压缩策略前后的模型节点数,以及层次化方法与Markov方法的计算结果,验证了简化层次模型的正确性和有效性。     

基于改进鸽群优化的直升机协同目标分配

针对多直升机协同目标分配问题,建立了基于敌我相对态势的对地打击多目标的分配模型。引入多Agent系统机制,加快了有益信息在系统中的流动;并借助雁群成员在飞行中借鉴雁群整体经验的操作,来修正鸽群算法中地标算子的寻优方向,进而提出了基于多Agent的改进鸽群优化的问题求解策略。最后,以典型的直升机对地作战目标分配问题为背景,仿真验证了模型及其求解算法的合理性和有效性。     

预警机指挥多机群空战的协同战术决策

分析了预警机指挥下的多机群协同空战的战术决策方法,建立起了它的战术编队、威胁评估以及目标分配模型,并进行了仿真计算,结果表明此战术决策方法对于提高多机群协同空战的作战效能有着显著的作用,对于未来无人作战飞机多编队协同作战也具有很好的参考价值.     

一种武器-目标分配模型及求解算法

武器-目标分配是拟制作战计划的一项重要内容,是合理运用现有武器系统,充分发挥其作战效能的关键.依据火力分配的基本要素,针对多种武器对多个目标的分配问题,运用一种基于模糊优选技术的多目标混合优化理论,建立了武器-目标最佳分配模型,然后用遗传算法来求解,并在计算机条件下对求解的效果进行了检验.     

权值编码遗传算法在单机任务规划中的应用

任务规划是在任务有不同威胁程度,资源消耗和战术价值条件下,寻找总战术价值最高,而又不超出约束的任务链,这对飞机完成任务中具有重要作用,针对机载资源有限、任务有不同威胁程度和战术价值,提出了基于权值编码遗传算法的任务规划方法,该算法通过对原始问题的偏离和启发式解码来得到最优的可完成任务子集.仿真结果验证了算法的有效性.     

高炮群火力优化分配的指派模型

火力优化分配是高炮群指挥控制的关键环节。依据有严格理论证明和实用价值的指派问题及其解法(匈牙利法),构建了一对一射击和多对一射击情形下的高炮群火力优化分配的指派模型,探讨了该模型的求解,分析了该模型的实际应用,并通过具体实例对该模型进行了初步验证。该模型的解法被证明是多项式时间算法,满足作战实时性要求。实际应用表明该模型用于解决高炮群的火力分配问题是有效的。     

多UCAV协同作战自主任务规划系统

在分析未来多UCAV协同作战任务的基础上,构建了一个多UCAV协同作战的自主任务规划系统结构,探讨了其运行机制。提出这个系统的核心是自主规划器,它应该具有任务分解、智能信息处理和机载任务规划与重规划能力。设计了自主规划器的初步方案。指出了这个系统下一步研究的任务和方向。     

战场物资无人机配送研究

战场物资无人机配送是未来信息化战争后勤保障发展的重点方向,是适应未来高强度、快节奏战争的重要手段。对国内外配送无人机的应用与战场物资配送保障的情况进行概述,重点讨论了无人机在配送过程中涉及的任务分配问题。提出了未来战场物资无人机配送的一些重点研究方向,包括战场物资无人化保障理论研究、军民融合式战场物资无人机配送研究、战场物资无人机配送过程一体化研究以及传统车辆与无人机联合配送的研究。     

基于模型转换的异步空间配准算法

在分布式融合系统中,融合中心在对传感器发送过来的航迹数据进行融合处理前,需要采用空间配准算法来消除航迹数据中可能存在的系统误差.已有的空间配准算法未考虑滤波处理中的状态方程对配准过程的影响.对不同传感器具有不同状态方程条件下的异步空间配准实现进行了研究,采用将模型误差和系统误差合并处理的思路,提出了基于模型转换的异步空间配准(AMCBA)算法.仿真结果表明AMCBA算法能够实现对模型误差和系统误差的准确估计.