一种有限资源约束的博弈概率图规划模型

刘兆鹏 罗 睿 张金璐 黄润宇

1.军事科学院战争研究院 北京 100091 2.军事科学院军队政治工作研究院 北京 100091 3.军事科学院研究生院 北京 100091

联合作战任务规划就是由本级指挥员带领指挥机构在有限资源约束条件下, 将上级赋予的任务目标分解为本级可执行的带偏序约束的行动方案的过程, 属于联合作战筹划的行动方案开发环节[1-2]. 运用智能方法替代或者辅助指挥员进行任务规划是该领域的重要发展趋势, 相关研究可以归纳为两类：一是基于符号逻辑的规划方法, 1969年Newell 和Simon设计了行动方案的通用问题求解器[3]（general problem solver, GPS）, 1971年Fikes 和Nilsson 设计了基于命题逻辑描述方法的斯坦福研究所问题求解（stanford research institute problem solver,STRIPS）规划系统[4]. 二是启发式规划方法, 1998年Bonet 和Feffner提出了采用启发式函数来指导状态空间搜索的启发式规划方法[5]. 2019年欧峤等在传统武器指派问题中运用排队论模型对空中目标与防空反导系统之间的服务关系建模, 并通过离散差分进化（discrete differential evolution, DDE）模型对武器指派问题求解[6]；李瑞阳等运用列生成算法对无人机运输问题进行求解[7]；刘兆鹏等针对联合作战规划中兵力调度的资源不确定性、时间不确定性构建了遗传模糊网络模型[8]；潘永强等运用遗传算法对多武器混合区域防空部署问题进行求解[9].

分析基于符号逻辑的规划方法求解效率较低,启发式规划方法较少考虑联合作战的体系对抗特征.Blum 和Furst 提出的图规划方法[10]虽然属于基于符号逻辑的规划方法, 但是具有较高求解效率, 且便于对联合作战体系中的支撑关系、对抗关系等要素建模. 本文在图规划研究进展基础上[11,15], 运用博弈论模型对联合作战中的体系对抗特征建模, 并综合考虑联合作战中的执行效果不确定性和指挥员满意度因素,设计了博弈概率图规划模型, 并针对联合作战方案验证难问题, 设计了虚实结合的规划框架.

1 规划框架设计

1.1 联合作战任务规划问题定义及假设

联合作战任务规划的核心问题是指挥员和指挥机构将领受的上级任务分解为符合指挥员决策风格的下级作战单元可执行的行动方案, 与传统智能规划问题的主要区别在于人机结合、敌我激烈对抗和对抗过程中的高度不确定性, 需要综合考虑指挥员决策偏好、不确定性和对手策略干扰3 个因素. 本文以实验室环境为研究背景, 忽略指挥员与指挥机关、指挥机关各部门之间在方案拟制流程中的协调、配合等因素, 将联合作战任务规划问题抽象为如何将低分辨率上级任务解聚为由高分辨率本级任务组成的带因果、协同等偏序关系的行动方案, 并对联合作战任务规划问题空间作出如下假设：

1）行动集合假设：敌方行动集合A 和我方行动集合AO是有限已知的；

2）不确定性假设：任务规划中面临的不确定性因素主要包括态势认知不确定性和任务执行效果不确定性, 在规划过程中, 主要对任务执行效果不确定性建模, 不考虑红蓝初始态势不存在不确定性；

3）资源有限假设：只考虑装备实体资源限制, 暂不考虑弹药等消耗性资源的限制；

4）稳定策略假设：不考虑时间因素给指挥员决策带来的决策偏好和权重的变化；

5）非线性毁伤假设：敌方任务资源的实力值遵循二项分布rSO={0, 1}, 当敌方资源实体状态为1 时,具备对我方执行行动实体威胁能力, 当敌方资源实体状态为0 时, 不具备对我方执行行动实体威胁能力.

基于上述假设, 将联合作战任务规划问题空间形式化为：

其中, ∑为有限状态转移系统；S 表示∑系统的有限状态空间；BS表示系统状态S 的概率分布；Pγ表示行动效果的概率分布, 上级任务分解中的规划问题P的形式化定义为：

其中, S0表示上级任务分解的初始状态空间；G'表示包含指挥员决策偏好的目标状态空间；gi表示目标状态空间的一个状态；ri表示实现该目标状态需要面临的风险；li表示指挥员对承担风险ri实现目标gi的满意度.

1.2 博弈概率图规划框架

本文针对联合作战领域规划成果无法在真实对抗环境中进行验证的情况, 依托作战仿真系统, 构建具有虚实结合特征的博弈概率图规划框架, 虚实结合是指在真实世界运用博弈概率图规划算法将上级任务分解为行动方案, 在作战仿真系统虚拟世界构建近真实对抗环境, 验证生成的行动方案, 具体如图1 所示.

图1 博弈概率图规划框架Fig.1 Planning framework of game probability graph

其中, 知识库用于存储博弈概率图规划模型所依赖的规划知识模型, 采用“节点-属性-值”结构概念内涵, 采用“边-属性-值”结构刻画概念语义的外延和概念之间的关联关系；利用资源、能力、任务之间的路径来对规划中的程序性知识建模. 规划知识的形式化定义为：

其中, KGB 表示知识库, Node 表示知识库中的节点；Verge 表示知识库中的边；Nrc表示知识库中的资源概念节点；Ncap表示知识库中的能力概念节点；Nact表示知识库中的行动概念节点；Vkpo表示资源概念节点之间的上下位隶属关系, 并由下位概念节点指向上位概念节点, 比如装备概念节点Equip 是武器平台概念节点WPlatform 的上位概念；Vhc表示资源概念节点与能力概念节点之间的拥有能力关系, 由资源概念节点指向能力概念节点, 比如轰炸机HZPlane 具有空地打击能力KDAtkCap；Vsp表示资源概念节点之间的支撑关系, 由支撑资源概念节点指向被支撑资源概念节点, 比如机场设施Airport 对轰炸机武器平台HZPlane 具有支撑能力；Vprec表示行动概念节点与能力概念节点之间的依赖关系, 由行动概念节点指向能力概念节点, 比如空地打击行动KDAct 依赖空地攻击能力KDAtkCap；Veff表示行动概念节点与资源概念节点之间的行动效果关系, 空地打击行动KDAct可以对指挥所设施CP 的实力值dHState 属性产生打击效果；Vcoo表示行动概念节点之间的协同关系, 协同包括主行动和辅助行动, 由主行动概念节点指向辅助行动概念节点, 空地打击行动KDAct 需要空中护航行动KZHHAct 协同.

目标选择和遗传优化两部分相互关联, 流程包括两个主要步骤：一是根据遗传算法随机生成的目标选择顺序进行逐步规划扩张, 实现从上级任务初始状态到上级任务目标状态的转变；二是根据上级任务面临的总体威胁值采用遗传算法进行目标选择顺序优化. 具体如图2 所示.

图2 目标选择和遗传优化流程Fig.2 Target selection and genetic optimization process

目标选择模块根据规划知识将上级任务目标分解为多个存在偏序关系的子目标, 在目标选择研究中强调基于效果和系统视角[16], 基于效果是指目标选择要基于指挥员的作战意图和预期作战效果, 其中包含了指挥员的决策偏好；系统视角是指当前作战形态是体系对抗, 作战体系是一个复杂性系统, 具有鲁棒性和脆弱性特征, 鲁棒性是指作战体系具有抗随机打击能力特征, 脆弱性是指作战体系存在关键节点, 当关键节点受到攻击时, 会产生级联失效和体系坍塌, 产生“1+1>2”的作战效果. 遗传优化模块是利用遗传算法, 从系统视角搜索打击敌方脆弱节点的行动方案, 在遗传算法中对指挥员决策偏好因素建模，将上级任务面临的风险最小作为指挥员决策偏好和优化目标, 其形式化定义为：

其中, ri表示行动方案中一个特定行动面临的风险；n表示行动方案中行动的数量.

序贯博弈规划步设计是博弈概率图规划模型的核心,包括博弈策略、图规划步和行动效果3 部分. 其中,有限策略集合为实验所选择仿真系统的红、蓝双方模型的控制指令集,红方策略依据式（1）～式（10）选择,蓝方策略通过指挥员枚举方式选择.具体如图3 所示.

图3 序贯博弈规划步Fig.3 Sequential game planning step

其中, 左侧为图规划步中的博弈树示意图, 红色圆圈表示红方策略, 蓝色圆圈表示蓝方策略, 右侧为图规划步的数学模型, 由两类节点四类边构成, 节点包括资源节点和策略节点, 资源节点由我方资源和敌方资源构成, 其中, 我方资源形式化定义为：

敌方资源形式化定义为：

策略节点由我方策略和敌方策略构成, 其中, 我方策略形式化定义为：

敌方策略形式化定义为：

边由我方条件边、敌方条件边、威胁边和执行效果边组成, 其中, 我方条件边形式化定义为：

敌方条件边用于表示敌方资源对敌方行动的支撑关系, 其形式化定义为：

威胁边用于表示敌我双方行动之间的威胁关系,其形式化定义为：

执行效果边用于表示行动对∑系统产生的状态变化, 其形式化定义为：

由于当前作战样式是体系对抗, 在敌我作战体系中, 资源之间存在大量支撑关系, 比如机场设施与飞机资源之间存在的支撑关系, 打击作战体系的关键节点资源, 会通过这种支撑关系产生体系坍塌. 故本文在传统条件边中增加资源之间的支撑关系描述, 比如图3 中的e2、eo2. 通过敌方行动与我方资源的效果边、以及我方资源之间的支撑边、我方资源与我方行动之间的条件边, 实现敌方指挥员策略对我方指挥员策略的影响.

在图规划步规划过程中, 针对传统图规划模型存在的搜索空间大问题, 采用目标引导的剪枝策略,不考虑与上级任务目标无关的可执行行动, 增加可执行资源总量约束和状态偏序约束：

其中, stepi表示当前规划步, stop 表示规划步终止,resact表示规划步内单个行动的资源需求量, restotal表示我方资源总量, 式（1）～式（19）表示当前规划步我方全部行动的资源需求量超过我方资源总量时, 终止当前规划步；acti、actj表示我方两个行动, rm、rn表示资源的两个状态, effi表示我方行动acti的效果, effj表示我方行动actj的效果, stepk表示行动actj所在规划步, 式（1）～式（20）表示如果行动acti效果rm和行动actj的效果rn存在偏序关系, 则行动acti和行动actj不能出现在同一个规划步.

行动效果部分借鉴概率图规划方法, 采用概率分布P 来描述行动的成功与否, 并将行动的终止判断形式化为：

其中, n 为行动次数；x 为判断该行动执行成功的阈值概率.

2 博弈概率图规划模型设计

2.1 模型参数

博弈概率图规划模型中的参数包括：

10）steph：规划器当前规划步h, 规划步一般由初始实体状态列、行动列、效果实体状态列和连接各列的边组成, 如图3 所示, 初始实体状态列和效果实体状态列由敌我双方资源实体组成, 行动列由敌我双方在当前规划步的全部策略组成, 边由我方条件边、敌方条件边, 效果边组成.

2.2 博弈概率图规划模型

博弈概率图规划模型的形式化定义为：

其中, 式（16）为目标函数, 表示以上级任务面临的威胁最小为优化目标；式（17）为资源约束, 表示当前规划步steph中全部行动实体所用资源数量不能超过资源总量, 在传统图规划方法中, 多采用行动互斥方法终止当前规划步, 博弈概率图规划模型采用资源总量约束的方法终止当前规划步, 这是与传统图规划模型不同的一个特征；式（18）为威胁能力约束, 当敌方资源状态下降到毁伤要求时, 则不具备威胁能力；式（19）为威胁条件约束, 其中, rdj表示敌方资源实体rj的威胁覆盖范围,表示敌方资源实体rj与我方执行行动k 的资源实体ri的行动航迹之间的最短距离, 当敌方资源与我方行动航迹的距离超出其作用范围时, 则该资源不具备威胁条件.

3 实验验证

3.1 实验数据环境设计

本次实验依托Neo4j 开源图数据库开展数据准备, 设计了“知识-信息”两层结构, 在知识层, 人工构建的知识模型如图4 所示.

在信息层构建红蓝对抗想定数据, 其中, 红方上级任务包括联合火力打击等4 个, 任务间存在条件、因果逻辑关系, 涉及陆上、海上、空中、常导、信息等作战力量和港口、机场等基础设施；蓝方上级任务空中防御等3 个, 涉及空中、海上、信息等作战力量和港口、机场、电站等基础设施, 将上述数据导入Neo4j 后, 如图5 所示.

图5 规划实验信息模型Fig.5 Experimental information models for planning

其中, 上半部分紫色网络表示蓝方作战力量和基础设施, 下半部分左侧紫色网络表示红方作战力量和基础设施, 下半部分红色网络表示4 个上级实验任务.

3.2 实验结果及分析

本次选择联合火力打击任务开展规划实验, 将博弈概率图规划模型的遗传算法种群规模参数设置为30, 遗传代数设置为30, 实验结果如图6 所示.

图6 目标选择遗传优化结果Fig.6 Genetic optimization results of target selection

其中, 纵坐标表示战役任务面临总威胁值, 横坐标表示遗传算法代数, 根据图6 显示, 遗传算法在第17 代开始收敛. 根据遗传算法收敛后最优染色体生成的行动方案如图7 所示.

图7 基于最优染色体的行动方案Fig.7 Action scheme based on optimal chromosome

实验依托作战仿真系统开展, 博弈概率图规划模型中对作战力量、基础设施的实力值、毁伤、支撑关系部分, 参考了作战仿真系统中模型建模方法, 与实际战场情况还有一定差异. 博弈概率图规划模型采用资源约束替代传统图规划步互斥方法终止单步规划, 并采用遗传算法对行动方案进行优化, 实验证明, 该模型能够将上级任务分解为考虑本级指挥员决策风格的行动方案.

4 结论

联合作战任务规划不同于传统智能任务规划, 行动方案作为规划结果, 可以直接应用于机器人, 以验证其有效性, 联合作战任务规划的结果难以直接在真实空间进行有效性验证, 本文设计了具有真实规划、虚拟验证特征的虚实结合规划框架, 提出了将上级作战任务细化为本级行动方案的博弈概率图规划模型,并通过联合火力打击作战任务验证了该模型的有效性. 随着研究的深入, 还存在以下3 方面改进空间：

1）运用作战仿真系统对博弈概率图规划模型规划的行动方案进行有效性验证, 形成真实规划、虚拟验证, 再根据虚拟验证结果修正真实世界博弈概率图规划模型的闭环；

2）扩展红方、蓝方的策略空间, 增加蓝方指挥员的决策风格建模；

3）在仿真推演数据中挖掘规划知识, 将人在回路的知识建模转变为人不在回路的知识建模.