任务规划中基于案例推理的高维解空间适应性问题研究

 时间:2017-12-07 06:21:47 贡献者:汉斯出版社

导读:ComputerScienceandApplication计算机科学与应用,2015,5(12),454-463PublishedOnlineDecember2015inHans.http://www.hanspub.org/journal/csahttp://dx.doi.org/10.12677/csa.2015.512057TheResearchofHighDimensionalSolutionSpaceAdaptationBasedonCase-Based

任务规划中基于案例推理的高维解空间适应性问题研究(图3)
任务规划中基于案例推理的高维解空间适应性问题研究(图3)

Computer Science and Application 计算机科学与应用, 2015, 5(12), 454-463 Published Online December 2015 in Hans. http://www.hanspub.org/journal/csa http://dx.doi.org/10.12677/csa.2015.512057The Research of High Dimensional Solution Space Adaptation Based on Case-Based Reasoning during Mission PlanningYuan Zhang, Yudong Qi, Yongjun Qiao, Qinghua ChenDepartment of Ordnance Science and Technology, Naval Aeronautical and Astronautical University, Yantai Shandong Received: Dec. 11 , 2015; accepted: Dec. 27 , 2015; published: Dec. 30 , 2015 Copyright © 2015 by authors and Hans Publishers Inc. This work is licensed under the Creative Commons Attribution International License (CC BY). http://creativecommons.org/licenses/by/4.0/th th thAbstractAdaptation is the most difficult stage in the CBR cycle, especially, when the solution space is multidimensional in the Command Entity’s Mission Planning. This paper discusses the adaptation of a high dimensional solution space in the Command Entity’s Mission Planning and proposes a possible approach to it. A Visualization induced Self Organizing Map (ViSOM) is used to map the problem space and solution space first, then a Back Propagation (BP) network is applied to analyze the relations between these two maps. A simple military scenario is used as a case study for evaluation purposes.KeywordsCBR, Multi-Dimensional Solution Space, Adaptation, ViSOM, Mission Planning任务规划中基于案例推理的高维解空间适应性 问题研究张 媛,齐玉东,乔勇军,陈青华海军航空工程学院兵器科学与技术系,山东 烟台文章引用: 张媛, 齐玉东, 乔勇军, 陈青华. 任务规划中基于案例推理的高维解空间适应性问题研究[J]. 计算机科学 与应用, 2015, 5(12): 454-463. http://dx.doi.org/10.12677/csa.2015.512057

任务规划中基于案例推理的高维解空间适应性问题研究

张媛 等收稿日期:2015年12月11日;录用日期:2015年12月27日;发布日期:2015年12月30日摘要利用案例推理对指挥实体任务规划过程中决策问题求解方法的修正过程是该方法推理过程中最困难的阶 段,尤其当决策问题解空间是多维的情况下。

文章讨论了指挥实体任务规划过程中高维决策空间的修正 问题,并提出了可行的解决方法。

首先利用自组织匹配法(ViSOM)清晰展现问题空间与决策空间的映射 过程,然后,利用BP神经网络分析匹配结果间的相关性问题,最后选取一个简化的军事剧情对该方法的 合理性进行验证。

关键词CBR,多维解空间,适应,ViSOM,任务规划1. 引言案例推理法(Case-Based Reasoning, CBR)是一种利用曾经求解过的类似问题来类比映射得到决策问 题解的适配方法。

其中对决策问题求解方法的修正过程是CBR推理过程中最困难的阶段。

最简单的修正策略是由一系列用于解决新问题与已有案例间差异性与冲突性问题的修正规则构成。

为了克服基于规则推理的修正计算所带来的困难和局限性,里克等人[1]提出了一种转换型修正方法与规 则相结合的混合案例修正计算方法,这些规则用于引导实现系统空间中必要的转换。

此系统空间中不仅 保留着修正过程中的转换操作过程,而且还保持着空间中的每一步搜索痕迹。

尽管里克提出的方法功能 比较强大,但由于每次仅能实现对一个修正目标的计算,所以仍然存在一定的局限性。

另外,这种方法 也不太适用于具有有限知识需求能力的CBR系统。

这是因为,里克的方法依赖于大量进行明确表示的可 用知识,并且无论系统进行修正所需的知识储备是否充足,都依赖于用户的紧密参与。

因此,通过分析 识别案例及其决策结果之间的差异性,Hanney和Keane[2]提出了一种在案例库中直接建立修正规则的方 法,如果可能的话,这将是一种可行的模式。

Jarmulak等人[3]基于CBR知识内容的可用性特点也开发了 一套修正方案。

此方法指出系统空间中的每一个案例都作为测试案例,并将其与案例库中其它与其最相 近的案例进行比较。

每一种比较过程中,都会构建一种修正方案。

这个方案包含了测试案例库与检索案 例中问题与决策结果之间的差异性及其描述信息。

当新问题产生时,修正案例就会对所提出解决方案的 正确性进行估计并提出必要的建议性意见。

上述提到的解决方法都是“知识启发式方法”[4],即对CBR系统的自身案例进行修正性学习,并把 它们作为知识库建立的来源。

这些方法首先对所萃取出的信息进行预处理, 再用学习算法对其进行处理。

学习过程中必须考虑所调查的问题域及其修正目标的问题。

它将预处理信息转换成满足要求的修正决策 方案。

知识启发式修正方法必须由CBR系统提供足够数量的多种知识来支撑。

不充足的知识储备可能会 对系统造成负面影响。

此外,由学习算法产生的修正知识必须正确,并适当结合已有的修正单元、解析 过程,必要的时候也要考虑一下矛盾情况和不相匹配的情况。

许多CBR系统的决策空间只是一维的,例如对财产的估值,或对案例的评估分析等[5]-[8]。

但是,在 利用CBR技术来解决军事行动方案的制定问题(suitable course of action, COA)时,每一行动路线由相应时 间所对应的实体位置来表示,因此我们所建立的案例决策空间是一个多维空间。

这个多维空间可以简单 认为是由若干个单维空间组成,每个单维空间应用相同的方法,然后再将每个单维决策结果进行组合。

455

任务规划中基于案例推理的高维解空间适应性问题研究

张媛 等然而,这种思路可能会认为COA是一个由多个独立决策单元组成的结合体,这明显是错误的。

所以,我 们提出了自组织匹配(SOM)和ViSOM相结合的案例修正方法以解决类似情况下的案例修正问题。

2. SOM 和 VISOMSOM是一种被模式识别、图像分析和误差诊断等广泛领域成功应用的无人监督神经网络算法。

基本 的SOM算法受到人脑直觉思维模式的启发,通过神经元将感知印象映射到大脑立体空间或形成神经元色 质间的立体空间关系。

这就是所谓的竞争学习。

SOM算法是由两层神经元组成:具有n个输入节点的输入 层(表示n维输入向量)和N个输出节点的输出层(表示N个决策范围)。

每一个输入节点都与一个输出节点相 连接,所有的连接关系都会赋予相关的权重,因此SOM就形成了一个将高维数据整合成低维网格的非线 性投影图,基本过程如下: 1) 初始化:随机赋予全部神经元的权重向量值。

2) 相似性匹配:运用角距离公式或欧几里德距离公式。

计算模式i与模式j之间的欧几里德距离为:dij = xi − x j =∑ ( xin − x jn )n =1N2(1)其中 dij 越小,表示向量就越接近。

角距离是基于向量的内积:cos θ =x = x T x 是向量的欧几里德范数。

xT y x y(2)在这里 cos θ 值越大,向量的相似度就越接近。

所以我们就可以发现时间t时最佳匹配值 i ( x ) 为:= i ( x ) arg min j x ( t ) − w j = j 1, 2, , N(3)3) 更新:利用更新公式调整所有神经元的突触权重向量:( d r − d j ) ∗ w j ( t )  , 其中 j ∈ N i ( x ) , 否则, 不变. w j (= t + 1) η ( t )  (4)其中 η (t ) 表示当前t时刻神经元的学习率; η ( t ) 是一个以最佳匹配值 i ( x ) 为中心的邻域方程,这个最佳匹 配单元和它的邻域都可以通过修正当前输入的参考向量值来对输入进行表示。

学习单元的大小由其邻近 的影响函数来决定,这个影响函数在映射网格中是一个从最佳匹配单元进行单元距离递减的函数。

最大 权重的修正过程就是最佳匹配值正向产生的过程,并且根据正向产生过程中节点j和节点 d j 之间的距离, 以最佳匹配点为始,直到某一径向距离 d r 处,权重修正值经过微调降为0(N中的最大允许距离)。

这种效 应可以通过高斯函数方便地实现: −d ( j )2   exp  Λ ( j, t ) =  2σ ( t )2   (5)其中 σ 2 为高斯函数方差,它确定了节点j偏离理想节点的距离d范围。

其效果会随着训练时间t的增长而降 低。

为了加快计算的速度,可以使用Λ函数,这个函数规定在半径r范围内的神经元只能进行恒等的正向 权重改变。

4) 延拓:在过程2)执行基础上,通过训练过程中对参数η和Λ进行动态计算,直到其没有显著变化为 止。

学习进程开始时,邻域的半径是相当大的,但它会随着学习过程的开展而有所收敛。

这保证了学习456

任务规划中基于案例推理的高维解空间适应性问题研究

张媛 等开始时就对全局次序进行确定,随着过程的结束,半径变得越来越小,匹配表中模型向量的局部修正过 程将更具体。

SOM算法最重要的典型特征就是保持映射过程的拓扑性。

Bauer和Pawelzik [9]和Kohonen等人[10]采 取各种测量方法,将高维数据映射到低维特征图(一维或二维特征地图),同时文献[11]和文献[12]也相继 提出了提高SOM算法的拓扑可维护性方法。

然而,SOM算法不会一直可靠地描述数据及其结构分布,因 此需要采取一些措施来计算特征图的质量以便得出最好结果。

平均量化误差表示矢量数据与其原型之间 的平均距离。

一般来说,当特征图的尺寸增加时,就需要有更多的单元来对其数据进行表示,因此每个 数据向量越会更接近其最佳匹配单元,从而两者之间的平均量化误差就会越小。

ViSOM使用与标准SOM类似的网格结构,两者的不同之处在于前者更新理想点邻域中神经元权重值 的方式如方程(6)所示。

= wk ( t + 1  x ( t ) − wv ( t )   ) wk ( t ) + α ( t )η ( v, k , t ) (6)其中 η ( K , T , V ) 是邻域函数,而ViSOM利用公式(7)对理想点邻域中神经元权重值进行更新: d vk − ∆ vk λ  wk ( t + 1) =wk ( t ) + α ( t )η ( v, k , t )    x ( t ) − wv ( t )  +  wv ( t ) − wk ( t )   ∆ λ  vk  (7)其中 wv ( t ) 为时间t时理想神经元的权重值; d vk 为输入空间中神经元 v 和神经元 k 间的距离; ∆ vk 为特征 图中神经元 v 和神经元 k 间的距离; λ 为预先指定结论参数的相对值。

这个值越小,表明得到的特征图 决策质量越高。

ViSOM的关键特征在于特征图中神经元之间的距离可以反映出原始数据空间对应点间的距离。

我们 在案例问题空间及其决策空间中都采用了ViSOM理论。

一旦这两类空间中都采用ViSOM算法,那么案例 问题空间中的案例位置就是ViSOM算法的输入,决策空间中相应案例的位置就是ViSOM算法的输出。

由 于位置变量是一个二维向量,因此BP网络结构比直接输入原数据库所采用的BP网络结构简单的多。

这种 方法试图分别模仿问题空间作为输入模型和决策空间作为输出模型的过程,并且通过调整连接权重值的 大小将问题与其决策结果关系相映射。

ViSOM算法的输入为案例问题空间中每对案例位置间的位置差异,而非实际位置点。

同样,案件决 策方案中同一案例对间的位置差异作为ViSOM算法的输出。

目标案例与其最相似案例间的区别经过训练 后作为神经网络的输入。

同样得到决策空间特征表中目标方案的位置信息。

由于ViSOM算法保留着特征图中输入数据各点间的距离信息,因此离目标案例最近的案例就是所采 用的目标案例决策结果。

在实验中,我们采用了一个三层BP神经网络,此神经网络由2个元素构成输入 向量,5个神经元构成隐藏层以及2个神经元构成输出层组成, tan δ 函数作为各层间的传递函数,训练过 程采用适用于小型神经网络的快速训练方法——trainlm算法(莱文博格–马夸特算法)。

3. 目标案例解的求解在获得ViSOM案例决策空间中目标案例的位置后,如果同一位置没有预期存在的案例信息,那么这 个案例的决策方案就作为目标决策结果。

如果同一位置不只存在一个预期案例,那么这些预期案例决策 结果的平均值就是目标案例的决策结果。

但是,当在这个位置上没有预期案例存在时,我们采取下几种 可能的解决方式从相应高维决策方案中寻找准确决策结果的位置: 首先,建立ViSOM案例解空间中对应节点的向量原型。

一旦对ViSOM解空间进行训练,解空间中每 一个节点都会有其对应的原型向量。

当ViSOM解空间中目标案例的位置已知时,对应节点就可能成为目 标案例解的理想节点,并且此节点的权重大小可能对输出结果具有一定的影响。

457

任务规划中基于案例推理的高维解空间适应性问题研究

张媛 等其次,使用反向距离加权的KNN算法。

需要注意的是,此算法使用的是目标案例位置间的距离和决 策空间特征图中的相邻距离,而非问题空间中的距离。

4. 实验设计我们将一个COA表示作战兵团中一个作战指挥官,选取MAK VR-Forces软件作为我们的仿真环境。

通过利用VR-Forces软件中实体的位置及其到达此航路点所对应的时间来表示一个COA的决策制定过程。

换句话说,一个COA是由一个相当于人类指挥官指挥过程公式化表示的同步矩阵进行表示的。

其中,矩 阵是由仿真过程中不同时间段上所对应的实体航路点组成:其中行表示实体,列表示时间段。

文中,利用VR-Forces软件产生一个剧情作为测试实例。

剧情设计为四个敌方坦克(BMP 1, 3, T80, BMP2, BMP2和2)部署在一个雷区后面。

我方用三个排(每排拥有4辆坦克,分别用蓝排,红排和白排进行 标识)对敌方坦克进行压制,同时安排两个工程车辆进行扫雷。

作战想定如图 1 所示。

攻防剧情描述场景为: 蓝排原地待命,随时准备向敌军开火;红排向红色路线点挺进,为工程兵排雷提供掩护;白排向白 色路线点挺进,为工程兵排雷提供掩护;工程兵紧随红排其后,当红排到达红色路线点,并且敌军被摧 毁后,工程兵挺进雷区进行排雷。

4.1. 情景描述在有关CBR系统军事案例中,案例来自于实战训练科目安排,先验知识,战术及其作战条例[13]。

根 据领域知识和经验,任务,敌人,地形,部队,和时间(METT-T)通常是人类指挥官真实作战过程中考虑 的因素。

本剧情中,在保持突破雷区任务不变的情况下。

为了简化剧情的表示形式,本项目中不需要对 任务进行描述,只是由一个符号对象来每个实体进行表示。

即使这样,也仍然无法比较敌对双方的能力 大小。

因此我们对每组兵力采取综合表示而非分别表示的方式,利用可以采用简化的方式,根据其兵力 比例等级来表示其能力大小。

例如,T80坦克的能力为5,M1A2的能力为6,BMP2的能力为3。

同时,把 战斗效能认为是一组有序数据而非符号。

因此,“全能”用1表示,而“无法使用”用0表示和“退化” 用0.5表示。

然后兵力比例等级由公式(8)给出:兵力比例等级 =n∑ TiCti ∑ E j Cejj =1 i =1 m(8)Figure 1. Breaching scenario 图 1. 攻防剧情458

任务规划中基于案例推理的高维解空间适应性问题研究

张媛 等其中 Ti 为友方兵力第 i 队的能力, Cti 表示友方兵力第 i 队的战斗效能。

E j 为第 j 个敌方兵力的能力, Cei 表示第 j 个敌方兵力的战斗效能。

VR-Forces仿真过程中,整个仿真战场中实体的位置都使用网格坐标系中(x,y)网格信息来表示一个 实体的位置,不在网格单元中心的实体将被分配到最近的网格单元上。

我们用矩阵存储所有实体的网格信息。

如果某一网格单元中没有实体,我们就将这个网格单元位置 赋予0;否则表示此网格单元存有实体。

表1中,我们在仿真战场中产生实体a和实体b,定义相应的矩阵 为:0  0 0  0 0   0  0 0 0 0  0  0 a 0 0  0 0 0 0 0  0  0 0 0 b  0 0 0 0 0  0       0 0 0 0  0 对于每一实体的数据表示方式主要有两种, 一种为分类数据的表示方式, 另一种为数据的表示方式。

例如有两种敌方实体:BMP2 和 T80。

每类实体的数量可能有所不同。

若采用分类数据的表示方式,假 设用 1 代表 BMP2,用 2 代表 T80。

那么敌方兵力就可以用一个含有 0,1,2 三种元素构成的矩阵来表 示。

若采用数据的表示方式,那么实体的位置就可以根据其在坐标系中的位置来进行存储。

例如,实体 A = (3,2)和 B = (5,4)的表示如表 1 所示。

第二种方法更适合表示实验方案中的友军信息。

假设友军部队主要有四个角色组成:蓝排,红排, 白排和工兵。

为了简化决策的过程,文中忽略了案例表示中的时间,采用(X,Y)两维坐标进行表示友军 部队兵力的位置(假设地形是确定的, 并且每一兵力同时到达每一航路点)。

表 2 显示了此剧情中对所有实 体兵力的表示。

Table 1. Grid representation 表1. 网格表示0 1 2 3 4 5 … N b a 1 2 3 4 5 … NTable 2. Scenario representation 表 2. 剧情表示敌方兵力矩阵 兵力效能比例 蓝排矩阵 红排矩阵 白排矩阵 工程兵矩阵(3 × 9)(Xb, Yb )(Xr, Yr )(Xw, Yw )(Xe, Ye )459

任务规划中基于案例推理的高维解空间适应性问题研究

 
 

微信扫一扫 送福利