Petri网的任务分解原理概述

2017-08-30沈阳理工大学自动化与电气工程学院董冲冲

电子世界 2017年15期

关键词：库所变迁阈值

沈阳理工大学自动化与电气工程学院董冲冲

Petri网的任务分解原理概述

沈阳理工大学自动化与电气工程学院董冲冲

近年来随着人工智能的发展，任务分解受到越来越多的关注。对于一个不能被任何基础机构单独完成的复杂任务，为了实现任务目标，必须进行模糊Petri网的任务分解。任务的分解是实现任务的关键，运用形式化的方法对任务分解进行描述和验证是十分必要的。

人工智能；模糊Petri网；任务分解

1.模糊Petri网分解原理

根据任务分解的规则产生式的推理过程可以采用模糊Petri网建模的方法进行分析。Petri网是一种形式化系统模型，它有很强的模拟能力和严格的数学定义，同时又具有图形化的表示，由于它有着异步、并发的特性，是描述动态并发系统的有力工具，也因此在各个领域有着广泛应用。模糊Petri网是一般网的模糊化，它更能有效地处理含有模糊特性的问题。任务分解是一个复杂困难的过程，有很强的模糊性和不确定性。我们可以通过Petri网相关的分析来判断任务的分解是否正确，通过Petri网的动态性能找到完成总任务而要采取的计划，为以后的任务动态分配打下基础。

不同的文献对模糊Petri网有不同的定义，下面介绍一种用于模糊推理的模糊Petri网。

定义2.1：模糊Petri网是一个五元组

定义2.2：任务分解的模糊Petri网定义为5元组FPN=( P，T，F，D，M0)，其中:P为模糊库所的有限集合；T为模糊变迁的有限集合；D为定义在T上的实函数；M0为初始标识。

任务映射为库所集，逻辑规则映射为变迁集，元任务的可信度映射为模糊 Petri 网的初始标识。任务分解序列采用Petri网建模后，任务分解规划问题将转化为最优变迁序列激发问题，激发序列的优化是在可行激发序列内实现的。

模糊Petri网推理是一种基于目标驱动的推理，即寻找与目标任务相关的最可能的分解，对任务分解的解释可通过的动态来显示，是一种有效的分解方法。模糊Petri网反向推理主要用于故障诊断、事故分析，缺陷检测等。目前，有关模糊Petri网反向推理机制的研究已经取得了重要的进展，提出来的推理算法从问题的结果出发，在知识库系统中提取出一个子系统或者寻找出与结果命题相关的前提命题，故是一种反向推理算法。

对Petri网的分析有两种方法，一种方法是利用网的图形模型，基于Petri网可达关系的图搜索算法，这种推理算法直观，易懂，但数据结构和算法实现复杂，推理效率偏低。另一种方法是以网的关联矩阵为基础，运用Petri网良好的数学基础实现的推理方法，从而算法实现简单，易行，效率高，但推理过程不直观，而且所提出的算法对规则前提部分的不同命题对推出的结论有重要性没有加以区别，算法有一定的使用范围。

这里运用一个基于图搜索的模糊网推理常用算法，是由Shyi-Ming Chen等人提出的，为能清楚说明该推理算法，下面给出几个重要定义，设模糊Petri网中， ta为一个变迁，pi、pj、pk为三个库所。

定义2.3：变迁发生一个变迁能够发生，即对给定的阈值D，若变迁的输入库所的token值M（相对应于任务的可信度）大于阈值D，则变迁能够发生，否则不能发生。

定义2.4：直接前集库所x经过一次变迁t可到达pi，x称为pi的直接前库所，这些库所的集合称作直接前集，用DP(pi)表示。

定义2.5：前集库所x经过变迁t可到达pi，经过变迁的个数可以是一个也可以是多个，x称为pi的前库所，这些库所的集合称作前集，用P(pi)表示。

定义2.6：相邻库所就是一系列与pi经同一个变迁能立即可达的库所组成的集合。

算法是生成所有从起始库所到目标库所之间的可达路径，根据起始库所的模糊token值来计算目标库所的模糊token值。并规定规则可信度D，以及起始库所的初始标识M0。

输入：目标库所、起始库所的初始标识M0。

输出：目标库所的有效分解。

（1）进行初始化：首先根据目标库所的输入查询直接前集DP(pi)，再查询DP(pi)中每个元素的直接前集，直到直接前集为空，得到所有前集中为起始库所的集合Q。

（2）根据集合Q可以得到所有可能到达目标库所的路径。

（3）根据Petri网的变迁规则，对所有可能到达目标库所的路径进行分析。删除无效的路径。

（4）分析每条有效路径，以及产生的目标库所的可信度，得到最可信的分解。