基于Graphplan的ARBAC策略安全分析方法

策略安全分析是访问控制系统保持安全状态的重要机制.针对具有角色继承层次和角色静态互斥特征的分布式访问控制系统,文中采用智能规划技术进行策略安全分析.首先,提出了策略安全分析问题向规划问题转换的整体思路,定义"虚动作"模型以描述角色继承关系,使用领域互斥表述静态互斥角色,引入领域公理处理ARBAC策略的开放世界假设问题和前提条件中的负谓词问题.其后,运用图规划(Graphplan)算法求解转换而来的规划问题,重点分析了领域公理对规划图中部分NooP动作的剪枝作用,提出了领域公理在规划图扩展阶段的应用方式以及据此改进的图规划算法,介绍了已开发的面向ARBAC策略安全分析实验型规划系统.最后,进行了应用示例说明.

基于压缩编码的经典最优规划方法

在基于Graphplan的编码方式的基础上,设计了基于PMA的编码方式,并从理论上证明了该编码方式的有效性;提出了编码求解过程中的一种目标状态预处理策略;设计并实现了相应的规划系统PMA-SP,并利用国际规划竞赛选用的Benchmark问题予以测试。结果表明:与SATPLAN2006相比,对于顺序规划域Blocks World,编码规模压缩了40%,求解效率提高了2倍;对于并发规划域Logistics,编码规模压缩了80%以上,求解效率各有好坏,PMA-SP对于所测两类规划域编码规模有所压缩,求解效率也有一定程度的提高。

基于命题可满足性的经典最优规划方法

基于Graphplan的编码方式是2006年国际规划竞赛中著名的最优规划系统SATPLAN2006采用的编码方式。首先给出与编码相关的概念与性质,在基于Graphplan的编码方式的基础上,设计一种新的编码方式:基于FA的编码方式,并从理论上证明该编码方式的有效性。设计并实现对应的规划系统FA-SP,利用国际规划竞赛选用的Benchmark问题予以测试。实验结果表明,与SATPLAN2006相比,FA-SP对于所测两类规划域编码规模均有所压缩,除个别问题外求解效率都有一定程度的提高;对于顺序规划域Blocks World,编码规模平均压缩了40%,求解效率平均提高了2倍;对于并发规划域Logistics,带有小于5%的框架公理的FA编码规模平均压缩了75%,求解效率也有不同程度的提高。

基于FAHP与规划图融合的Web服务组合方法

近年来,随着云计算的发展,越来越多的服务被发布在网上。如何将不同的Web服务组合在一起并使其满足功能性需求和非功能性需求成为了一个研究难点。Web服务质量(Quality of Service,QoS)感知的Web服务组合问题属于NP难问题。为了解决这个问题,文中提出一种融合FAHP与改进Graphp lan算法的方法(FAHP and Improved Graphplan,FIGP)。首先,根据用户偏好使用模糊分析层生成服务的综合QoS;其次,在Graphplan向前扩展中,使用动态阈值对竞争力较差的服务进行剪枝,在保留关键服务的同时降低了时间复杂度;最后,在Graphplan向后搜索阶段,在满足功能性需求的前提下选择综合QoS最好的服务加入到组合中。实例分析和实验结果表明,与普通的Graphplan,Skyline及其他方法相比,FIGP不仅较好地提高了服务组合的质量,而且显著缩短了程序的执行时间。

图规划框架下的启发式搜索的研究与发展

随着智能规划研究的深入,以往的规划器已不能满足实际应用的需要。为了提高规划器求解实际问题的能力,启发式搜索产生了。对近10年来各种启发式搜索方法进行了分析,指出了它们的优缺点,并进行了比较。同时对智能规划及其启发式搜索的未来发展方向进行了分析与预测,旨在让研究和关心该领域的学者较为全面地了解这一领域。

命题编码中公理的组合与设计

近年来,基于可满足性的规划方法研究逐渐成为智能规划研究领域中的热点。提出3种基于Graphplan的编码方式中公理的改进:动作互斥的部分放松、动作互斥的完全放松方法、添加框架公理。基于SATPLAN2006规划系统分别实现上述3种改进的编码方式,并对国际规划竞赛中选用的标准后勤域与积木世界域的问题样例予以测试,分析不同编码方式的编码规模与求解效率,验证了基于Graphplan编码方式的改进在绝大多数情况下是有效的。最后,实现基于状态的编码方式,并对上述两个域进行测试,比较约简动作与约简状态这两种极端方式的求解效率和编码规模。实验结果表明,在后勤域的某些问题上基于状态的编码方式比基于动作的编码方式有效得多。上述的改进策略表明,可根据问题域的特性等来考虑该问题最适宜哪些公理组合的编码方式,而不固定使用某种特定的编码方式。

图规划框架下智能规划的研究与发展

分门别类地介绍了近10年间国内外相关研究的主要结果,着重介绍了在图规划框架下智能规划的研究工作,特别关注当前研究的热点、难点问题,重点展示智能规划技术的研究现状及面临的问题,试图勾画出目前智能规划研究的重要方面、关键技术及其发展趋势,旨在让研究与关心该领域的学者通过本文对这一领域有一个较为全面的了解。

一种带权值的图规划算法

图规划算法在智能规划的研究和发展中具有重要的意义和价值,它采用图的方式来求解规划问题,并且提出了用于规划的“规划图”的概念[1,2]。这一方法可以获得经典规划问题的最少动作数意义的最优解,但是却不能求解与动作代价相关的数值规划问题。本文提出一种带权值的图规划算法,在规划图的“动作增加效果”边上增加权值,用来表示动作产生这些效果的代价,从而使得通过规划图来获得最小动作代价意义的最优解。因此,这种方法不但提高了规划解的质量,而且所得到的规划更加贴近实用。

考虑IOPE匹配的语义web服务组合

针对传统语义web服务组合方法中仅考虑I/O接口间匹配,从而导致服务间功能匹配度不高的情况,提出一个新的语义web服务组合框架.该框架改进传统规划图以便体现服务的IOPE特性,为抽取组合方案提供功能匹配相关的启发信息.为了获得更多组合方案,框架一方面支持抽象用户请求的表达,另一方面在规划图的基础上,采用基于广度优先的后向搜索策略.最后,基于该框架实现一个web服务组合系统,一系列实验表明该框架是有效的和可伸缩的.

一种可检测类型缺陷攻击的SAT改进模型

针对现有SAT模型检测器不能检测类型缺陷攻击的问题,提出了一种新的SAT#改进模型.该模型通过在匹配模式下引入无类型变量,并利用无类型消息的概念,解除了SAT模型检测器对未知消息的类型限制,并且在诚实主体重写规则中用无类型消息替换了原来的强类型限制消息.通过增加消息匹配算法,使诚实主体能够接受带有类型缺陷的消息,从而实现类型缺陷攻击的检测.通过对Otway-Rees协议进行检测,不仅发现了已有的针对发起者A的类型缺陷攻击,而且发现了新的针对响应者B的类型缺陷攻击,其实验结果证明了SAT#模型具有一定的可靠性.

嵌入模糊部件的数值图规划

使用偏好和优先权隶属函数定义了数值规划中模糊部件的数学模型,并通过在问题描述域扩展偏好和优先权字段的方法,将模糊部件嵌入到数值图规划中,使规划器能在问题求解过程中有效地捕捉与问题相关的细节信息;在规划提取阶段,利用规划图与约束满足问题的对应关系,使用增量式局部修改技术进行问题求解;局部修改最大限度地利用以前问题的求解结果,避免了规划器问题求解过程中的重复性,为开发高效数值规划器提供了理论依据.

图规划框架下的规划合成与分解

提出了原子规划、独立规划、子规划以及父规划等概念,给出了图规划框架下的规划分解算法,有效地解决了在现实世界中求出有效规划后,初始条件发生改变的情况。定义了相关动作、相关规划以及相关规划的判定方法,提出了规划合成算法。几个有效规划的单独执行会浪费资源,针对这种情况该文提出了解决方案。

可能性规划表示与求解

利用可能性理论提出了一种基于PDDL(planning domain definition language)的可能性规划表示方法——Poss-PDDL,给出了基于可能性理论框架下的定性决策理论和图规划算法的可能性规划求解方法——可能性图规划,设计并开发了可能性规划问题求解器Poss-Graphplan.PDDL是国际规划器大赛的标准域定义语言,这使得Poss-PDDL更具通用性和标准性.由于用可能性理论表示动作效果和状态的不确定性更具优势,因此Poss-Graphplan更适用于解决那些概率模型无法解决或者很难获得概率信息的不确定规划问题.可以证明,应用可能性图规划方法求解可能性规划问题得到的规划解是最优的.实验结果表明,可能性图规划方法在问题求解能力和速度上的表现都较为突出.

图规划基于距离的目标排序启发式

讨论图规划回溯搜索过程中变量和值排序的缺点,并且提出一个基于实现某一子目标的难度的简单策略即获得子目标的困难度,该标准可以通过规划图本身的结构加以量化,特殊的使用子目标在规划图中最早出现用层的下标来表示.结果表明该方法在许多标准的规划问题求解过程中的惊人效果.

基于条件效果的对象动态可变图规划

主要研究了基于条件效果的对象动态可变的规划问题.提出了相关元件、无关元件、创建/删除对象元件和普通元件等概念,把带有条件效果的动作和不带有条件效果的动作都元件化,并采用了对象命题化的思想.给出了新的基于目标驱动的规划图扩展算法和前向搜索有效规划算法,并给出了相应的后向传播互斥的定义,使得规划图的规模比较小,减少了搜索空间,大大提高了求解有效规划的效率.由于算法中的动作创建的效果是依赖于上下文的描述,这更加符合现实需要,使处理的问题更接近于真实的世界状态,因而此算法比以往的算法应用性更强,更具有现实意义.

图规划框架下的并行概率规划

针对具有并发性概率效果的规划问题,考虑了动作的概率效果和并发执行,通过定义并行动作集以及节点间互斥的概念,实现了在概率规划算法中处理并行动作和概率效果,打破了原有概率规划算法中"每个时间步只允许执行一个非空动作"的限制,弥补了原有算法的不足.该方法能生成非循环规划和循环规划,选择性地开发利用问题潜在的并行性,提高了概率规划器的求解质量,使得概率规划更适合于处理现实世界问题.

带权值的规划图在物流车辆规划调度系统中的运用

图规划算法在智能规划的研究和发展中具有重要的意义和价值,它采用图的方式来求解规划问题,提出了用于规划的"规划图"概念[1]。利用在规划图的动作-添加效果边上增加权值,用来表示动作产生这些效果的代价,从而将物流车辆规划调度问题中的车辆路线分配问题转化为简单的单一车辆路线安排问题进行求解。并由此开发出了适合于中小型物流公司用于调度车辆来实现智能化配送的规划调度系统。通过模拟测试,效果良好。显示了图规划在实际运用中具有重要的研究价值。

以目标为导向的时序图规划算法的研究

本文提出了一种从目标集扩张时序规划图的新算法。此算法与现有算法不同,采用逆向扩张、正向搜索的策略;由于扩张保留了关于目标的信息,实现了动作方案的完全量化。在搜索阶段,只搜索相关可用动作的交叉点,减少了搜索代价,极大地提高了搜索效率。

图规划在路径规划中的应用

随着科学技术的不断发展,机器人研究成为当今的热门话题,人们趋向于用机器人替代人类去完成一些危险的工作。而路径规划是机器人研究的难点之一。本文以机器人的运输问题为例,介绍了图规划的算法,以及如何利用图规划技术对路径规划问题进行求解。

图规划及其扩展的分析和研究

AI Plannig and Scheduling are a classical problem of Artificial Intelligene. It is a highlight of AI for it' s significance in many application domains. Recenctly,dramatic advances have been made in this field. In this paper,we introduce our study on Graphplan which is one of the best methods and it's descendent technologys. First,we will analyse Graphplan's algorithm and it's key for success, then briefly introduce it's descendants,at the end of the paper,we suggest areas for future research.