模型检测规划中的状态之间的可达关系研究

当前,对基于模型检测规划研究的算法中存在大量的冗余计算,一些不可能参与构成解的状态动作序偶被反复筛选.文中给出了一种在不确定规划领域求规划解的新思路:在求规划解之前,找到不确定状态转移系统的状态之间的可达关系,从而根据状态之间的可达关系进行约简.提出了不确定状态转移系统的超图、超图的邻接矩阵和可达矩阵等概念,设计了用超图的邻接矩阵求不确定状态转移系统中状态之间可达关系的方法.利用不确定状态转移系统的超图、超图的邻接矩阵和状态之间的可达关系获得了关于弱规划解、强规划解和强循环规划解的一些重要性质.这些性质是关于一些状态动作序偶是否不可能参与构成弱规划解、强规划解和强循环规划解的结论.通过这些性质可以将大量的状态动作序偶直接去掉,从而大幅度简化求规划解的过程,提高求规划解效率.

基于可达关系的安全协议保密性分析

借助形式化的方法或工具分析安全协议是非常必要而且行之有效的.进程演算具有强大的描述能力和严格的语义,能够精确刻画安全协议中各个参与者之间的交互行为.作者以进程演算为基础,嵌入消息推理系统以弥补进程演算固有的缺乏数据结构支持的特点,尝试地提出了一个基于可达关系的安全协议保密性分析模型.基于此模型,形式化地描述了安全协议的保密性,证明了一定限制条件下的可判定性.并且以TMN协议为例,给出了该模型的实例研究.

基于可达关系的Rough集

根据Rough集的思想提出了一种新的基于可达关系的Rough集模型,这种Rough集模型的思想是基于信息粒和可达关系的,比经典的Rough集更一般.除了Rough集原来的应用外,这种Rough集模型还可望有更广泛的应用.基于可达关系的Rough集思想将Rough集思想推广到一般的方法论.

不确定规划中状态循环可达关系的求解方法

在不确定规划领域中,不确定状态转移系统求规划解常常会搜索大量无用的状态和动作,造成冗余计算。获得不确定状态转移系统的状态可达关系可以避免无用搜索、减少冗余计算,为系统提供引导信息。以非循环可达关系为基础,定义矩阵的计算规则,使用系统的邻接矩阵来计算可达矩阵。同时首次提出了循环可达关系的分类、二可达关系等,并设计了求循环可达关系的算法,且以实例证明了算法的有效性和正确性。在不确定规划中获得状态之间的可达性关系,在求规划解的过程中可以删除大量无用的状态动作序偶,降低问题规模,提高求解规划问题的效率。

信息传递法求不确定系统中的状态可达关系

在不确定规划领域中,在求规划问题的解时,由于缺少引导信息,会导致许多无用状态和动作被搜索,造成冗余计算。所以在求规划解之前,找到不确定状态转移系统中状态之间的可达关系是很有意义的。以往的算法是通过矩阵相乘来模拟状态转移,但该类算法对于规模较大的系统开销较大。因此,提出了用信息传递法来求解可达关系,用矩阵来模拟不确定状态转移系统。其中每个状态记录了其他状态到达该状态的可达信息,通过状态之间的可达信息的传递,求得不确定系统的状态可达关系,以避免大量的矩阵运算。通过实验对比表明,当不确定系统规模较大时,所设计的算法优于矩阵相乘的算法。

利用有向环的性质求解可达关系

不确定规划研究的最终目标是求出规划解,但是由于缺少引导信息,直接求规划解会导致大量的无用状态和动作被搜索。获得状态间的可达关系可以避免冗余计算。目前求可达关系的方法效率较低,因此设计了一种求可达关系的新方法。将不确定状态转移系统抽象成一个图,在这个图中,查找状态之间的可达信息是否形成一个有向环。若存在一个有向环,说明环内每两个状态之间都有可达关系。将其中一个状态作为父节点,并且将这个环内所有状态的可达关系记录在父节点中,通过访问父节点的可达信息更新环内状态的可达信息,减少了许多无用的状态和动作被搜索。实验结果表明,所设计的算法不仅能得到更全面的可达关系,而且效率也高于已有的算法。

不确定规划中可达关系的快速求解算法

在不确定规划领域中,通常需要在同一个不确定状态转移系统中解决多个规划问题,如果能得到不确定规划中状态之间的可达关系即可方便求解该规划问题,然而现有矩阵乘法求解可达关系时存在算法复杂度高的问题。为此,设计一种快速求解不确定规划中状态之间可达关系的算法,将确定动作和不确定动作区分处理,先求解所有确定动作的可达关系,再采用链表和队列求解不确定动作的可达关系。实验结果表明,与矩阵乘法相比,该算法能得到更全面的可达关系,且求解效率更高。

交通网络可达关系的矩阵分析和应用

给出了具有实用意义的交通网络局部可达概念及其矩阵和图的刻画。在布尔阵的1种标准型及与可达关系研究的基础上,实现了交通网络可达关系的整体结构分析。为科学地设计网络连通性和模糊网络可达程度分析提供理论工具和实用方法。

不确定系统中状态可达关系的维护

对于一个理想的不确定系统,动作的执行是可靠的,即动作是可以执行的且动作的执行效果是可以确定的,但现实世界中,动作的执行很有可能是不可靠的,例如某个动作无法执行,并有可能对不确定系统中状态之间的可达关系产生影响,因此需要重新对该系统状态之间的可达关系进行求解。针对这一情况,分析了信息传递法求不确定系统中状态可达关系的算法,提出了不确定系统的最小信息传递集(简称MIDS),证明了当不可执行的动作不属于MIDS时,该系统状态之间的可达关系不发生变化。并给出了当该动作不属于MIDS时的局部更新可达关系的算法,从而避免了对该系统状态之间可达关系的重新计算。

析取范式公式的化简

本文阐述了离散数学中析取范式公式化简的计算机实现过程,给计算要实现模拟化简提供了理论方法。

工作流合并规则中的冲突检测方法

在关系型规则和活动型规则形式描述工作流合并需求的基础上,提出一种基于可达关系的合并规则冲突检测算法。通过记录每条规则应用后的可达关系矩阵,以及新增可达关系对应的规则集方式,为合并规则集中存在冲突的若干规则组合进行较为准确的定位。实例分析表明,该算法为规则集的合理调整提供直接依据,可有效实施工作流的合并。