搜索研究论文-基于cpn模型的coa状态空间搜索算法

《搜索研究论文-基于cpn模型的coa状态空间搜索算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、搜索研究论文-基于CPN模型的COA状态空间搜索算法基于CPN模型的COA状态空间搜索算法在信息化条件下，随着军事行动越来越复杂，速度越来越快，军事行动正在从一种严格纵向的组织结构向一种更加集成、更加模块化、定制能力更强的结构转变。由于战场情况的不确定性，以及作战行动的高对抗性，指挥员对参谋人员作战计划拟制、调整和修改的时效性提出了更高的要求，而传统的人工作业方式无法满足快速拟制作战计划的要求，需要采用信息化手段提高计划拟制和调整的效率［1］。行动方案是执行使命任务的行动过程或者任务流程，是在作战目的(Op

2、erationObjective)和首长意图的指导下，使一定的战争实体在一定的时间，一定的地点，执行一定的行动，并产生一定的相互作用效果，按规则判断实体状态和行动效果是否触发条件或以时间驱动，选择下一行动，最终确定整个可能的行动序列［2］。所以COA的开发与分析是作战计划制定关键步骤。COA开发过程作战单位从上级指挥部门受领作战任务之后，军事计划人员分析作战资源和能力指标、评估当前的敌我双方的作战态势、作战限制条件以及事实与假设，其中事实与假设决定了首长的关键情报需求。然后，军事计划人员确定理想的作战最终状

3、态，并把整个作战过程分解成若干个决定点，针对每个作战决定点开发具体的作战任务。最后，因为这些大量的作战任务之间存在复杂的因果关系，必须针对这些作战任务进行排序以及对作战资源进行分配，进行COA开发。如图1所示。着色Petri网着色Petri网是一种典型的高级Petri网，当我们在对较复杂的系统进行建模时，常会出现库所节点和变迁节点过多的情况，导致Petri网的建模和分析的复杂性大大增加。着色Petri网就是用来简化Petri网模型结构的。它通过把系统中具有同类行为特性的库所节点归并到一个库所节点中，并通过令

4、牌的不同颜色来进行区分，这样就可以简化Petri网的结构。着色Petri网中，还可以引入层次的概念，通过层次来把整个系统的模型组织起来，因此，建模和使用起来更方便和清楚［3］。CPN建模语言可以对那些可被视为并行系统的系统进行建模，在这些系统里，同步化与资源分配是关键要素。系统的CPN模型既面向行动，也面向状态，因为它可以捕获该系统的当前状态以及在特定状态下可能发生的事件。CPN还包括一个时间概念，该概念使得有可能对系统里的事件所需要的时间进行描述。COA具有的大量的作战任务，给定的作战资源、同步化约束及任

5、务间的复杂关系使得COA的开发十分复杂，而CPN的上述特性决定了其适用于对COA的建模与开发［4］。在第一阶段的基础上执行宽度优先搜索。宽度优先搜索也用到了三个结构：Visited保存己访问状态的轨迹；LOP用来关联状态和从初始状态到达该状态所有的可能路径，这些路径用LOPs表示；Queue存储宽度优先搜索遍历队列。调用此算法时，初始状态插入到该队列中，算法通过选择队列中的状态s来获得状态s的lops。但是，随着作战任务数量的增加，模型执行的可选方式也在增加，导致模型的状态空间成指数级增长，例如：在时刻t有

6、n个具备开始条件的作战任务，那么就有2n个作战任务执行方式，这将带来模型的状态空间爆炸问题。该文目的是对两阶段算法进行改进，采用反向路径搜索算法替代宽度优先搜索算法缓解COA开发的模型状态空间爆炸问题。改进的两阶段算法两阶段算法中的深度优先搜索算法能快速产生部分完整的及不完整的LOPs。虽然作战任务之间存在复杂的约束关系，通常情况下，作战任务清单中包括一个确定的最终任务，这个任务的执行将到达理想的最终状态，例如：两栖登陆作战计划，其中两栖登陆这个任务可以看作是作战任务清单中的最终作战任务，在一定程度上，其他

7、的所有作战任务都是为这个最终的作战任务的执行提供开始条件的。当作战计划参谋人员开发的作战任务清单中不存在作战任务冗余时，一个COA的CPN模型状态空间最多只有一个理想的最终状态。由于作战任务之间紧密的约束关系，即使存在作战任务冗余，理想的最终状态的个数相比于可达状态集也是占很小的比例。对于COA开发问题，作战计划参谋人员需要的是完整的LOPs,因此可以考虑在两阶段算法中，用反向路径搜索算法取代宽度优先搜索算法，即从理想的最终状态节点由下往上搜索，由子节点找到父节点，最后到达模型的初始状态。反向路径搜索算法同

8、宽度优先搜索算法相似，采用三个数据结构。Visited保存已访问状态的轨迹，LOP用来关联状态和该状态到达理想的最终状态的所有可能路径，这些路径用lops来表示，Queue存储宽度优先搜索遍历队列算法通过选择队列中的状态s来获得状态s的lops。与宽度优先搜索不同的是当调用此算法时，将理想的最终状态插入到该队列中。