基于模糊Petri网的任务分解方法

2016-08-16

福建质量管理 2016年11期

(沈阳理工大学自动化与电气工程学院辽宁沈阳 110159)

基于模糊Petri网的任务分解方法

张大权董子威沈林

(沈阳理工大学自动化与电气工程学院辽宁沈阳110159)

随着人工智能的发展，自主系统对任务分解精度的要求越来越高。为了提高任务分解的准确性，解决协同作业过程中时间不确定，工作衔接时机不容易把握等难题，本文提出一种基于模糊petri网的任务分解方法，给出模糊petri网的定义以及将模糊petri网用于任务分解的可行性。该方法是在建立数据库的基础上结合模糊petri网模型的推导过程实现的，并在理论的基础上实现分解可视化。

任务分解；协同；数据库；模糊

一、引言

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

Petri网是20世纪60年代由卡尔·A·佩特里发明的，适合于描述异步的、并发的计算机系统模型。Petri网既有严格的数学表述方式，也有直观的图形表达方式，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础。所以Petri网的并发模型可以满足任务分解需求。

二、任务分解流程分析

任务分解的主要功能是将提交的任务分解成多个具有尽可能高并行度的子任务，并选取合理的分配调度策略，决定由哪些机构执行它们。任务的分解需要考虑任务是如何表示的、分解的方式、完成任务的组织、资源以及子任务之间的联系。

任务分解的具体流程如下：

(1)初始：建立一个包含模糊规则产生式(定义1.1)的规则库。

(2)由模糊任务识别得到包含一些关键词的复杂任务(高级任务)。

(3)根据复杂任务的关键词在规则库中搜索相关模糊产生式规则。

(4)根据模糊产生式规则映射为相关的Petri网。

(5)根据Petri网的动态性能以及相关算法进行分解。

(6)输出复杂任务分解得到的相关元任务(基础任务)。

三、模糊Petri网分解原理

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

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

∑F=(P,T,F,D,M0)

(1)(P；T；F)是一个网，满足条件：(a)∀x,y∈F:(x,y)∈F+→(y,x)∉F+；(b)∀t∈T:|·t|≥1∩|t·|≥1；(c)∃p∈P:·p=φ∩∃p∈P:p·=φ

(2)D:T→(0,1]

(3)M0:P→(0,1]，满足条件∀p∈P:·p≠φ→M0(p)=0

(4)∑F的运行规则为：(a)对t∈T，如果∀s∈·t都有M(p)≥D(t)，则变迁t可以发生，记为M[t>，(b)变迁t的发生产生新的标识M′，记为M[t>M′

四种类型的模糊产生式规则可分别表示为下面的四种模糊Petri网的基本类型，如图1所示。模糊Petri网用圆表示库所，以矩形表示变迁，变迁与库所间的带箭头的连线表示流关系。库所中的实心圆点表示token(可用数字直接表示)。