一阶逻辑中的重写证明算法

本文在布尔代数标准重写系统的基础上,提出了一种把一阶逻辑公式转换成布尔环中等式的方法,并由此建立了一阶逻辑的重写证明算法.这种算法可以充分利用环上的因子分解,证明过程中所产生的中间等式的数量也显著减少,对包含蕴涵符号的一阶逻辑公式尤为便利.     

对不确定规划中观测约简的进一步研究

从3个方面改进了不确定规划(non-deterministic planning,简称NDP)中的观测约简:一是如何找最小观测集合(minimal observation set,简称MOS),二是如何在观测代价不均等时找最优观测集合(optimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cover,简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2^mm²)且不低于Ω(2^m?1)的算法,其中m是观测的个数.通过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.     

规划的形式表示技术研究

智能规划是人工智能研究领域中的一个富有挑战性的课题.同时,智能规划问题具有广泛的实际应用背景.而自动规划问题面临的首要问题是规划问题的形式表示问题.本文系统地分析了情景演算,STRIPS,PDDL,HTN等各种规划形式表示技术,比较了各种形式表示技术的优缺点,并指出了进一步研究设计高效智能规划系统的方向.     

从WSBPEL程序中学习Web服务的不确定动作模型

智能规划是一种比较有前途的Web服务组合(WSC)方法.用规划进行WSC需要Web服务(WS)的动作模型,而让工程师来写它却很困难.考虑到现存WSC解决方案多用Web服务业务流程语言(WSBPEL)手工编写,可从现存方案中提取动作模型.由于WS本身有不确定性,且现存方案中蕴含对WS的语义要求,所以学习的应是体现流程语义且包含条件效果的不确定动作模型.为此,先将WSBPEL程序转成保留流程语义的标签转换系统(LTS);然后将动作模型学习技术扩展到包括条件效果的不确定规划(NDP),并从LTS中学习动作模型.实现了ARMS-WS系统,它可从WSBPEL程序中学习WS的不确定动作模型.     

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

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

基于AI Planning的Parlay X电信业务设计

Parlay X是一组电信网络服务(WS)应用程序接口(APIs),智能规划可作为一种WS组合(WSC)方法,所以理论上可基于智能规划设计使用Parlay X APIs的电信业务.但WSC有容错和对动作变化推理的要求,电信业务有多种触发方式和异步响应等特性,智能规划要有确定状态等Parlay X不满足的条件.结合典型P...     

智能规划中的可纳子目标排序

提出了一种称为可纳子目标排序(admissible subgoal ordering,简称ASO)的排序关系,给出了可纳排序的形式化定义并讨论其对增量式规划的重要性.随后介绍了原子依赖关系理论和原子依赖图技术,能够在多项式时间内近似求解可纳子目标排序关系.最后给出了一种计算可纳子目标序列的算法.其所有思想已经在规划系统ASOP中实现.通过在国际规划大赛标准测试领域问题上的实验,其结果表明,该方法能够有效地求解大规模的规划问题,并能极大地改善规划性能.     

含约束的基于模型的诊断系统

在诊断空间中如何选取理想诊断是诊断系统面临的一个重要问题。在实际的诊断过程中,人们会利用限制条件排除不太可能的诊断,或者利用强制条件选取较优的诊断。按照这个思想,作者提出含约束的基于模型的诊断系统,通过增加依赖于应用领域的约束控制诊断空间,这是一种能够融入计算过程的选择诊断的机制,同时作者在系统拓扑结构的基础上给出了选取理想约束的理论依据。     

基于有序爬山法的前向启发式搜索规划

根据快速前向启发式搜索规划器FF中放宽规划图和有利动作之间的关系,定义了状态适用度函数的概念,可对后继扩展状态的启发式估值进行快速近似的比较。在此基础上,结合增强型爬山法搜索后继状态的贪婪选择机制,提出了一种改进的局部搜索算法——有序爬山法,即根据状态适应度函数对所有待扩展的后继状态进行排序,并加入到扩展优先队列。在启发式估值阶段,适应度高的状态将被优先计算评估,有利于更快地发现较优状态,从而减少调用启发式估值程序的次数。通过在国际规划大赛基准测试领域的实验结果表明,该方法减少了搜索节点的数目和搜索时间,有效地提高了启发式搜索效率,而计算状态适应度及对状态进行排序的时间消耗几乎可以忽略,因此整体规划性能比FF有显著的提升。