论文部分内容阅读
自动推理和智能规划自从二十世纪五十年代被提出,已经成为计算机科学中最重要的研究领域。基于演绎推理的规划求解方法、基于SAT的经典规划求解方法和基于QBF以及知识编译的非确定规划求解方法在智能规划研究领域也取得了有目共睹的成绩。同时,智能规划领域的发展也对自动推理技术和知识表示方法提出了更高的要求。本文的贡献如下:(1)提出了四种基于扩展规则求解模型计数和加权模型计数的算法:基于扩展规则的模型计数算法CER,基于知识编译的模型计数算法KCCER,基于扩展规则的加权模型计数算法CWER,基于知识编译的加权模型计数算法KCCWER。证明了上述方法的有效性和完备性。实验结果表明,在有些问题中基于扩展规则的#SAT问题求解比目前最为高效的#SAT问题求解系统更为高效。(2)将扩展规则推广到可能性逻辑中,提出可能性扩展规则,建立了基于可能性扩展规则的推理方法。和经典逻辑中的结果类似,当互补因子较高时,基于可能性扩展规则的推理方法效率更高。引入了“最优化形式蕴含可控制类”和“不一致性程度计算可控制类”的概念,定义了EPPCCCL(Each Pair of Possibilistic Clauses Contains Complementary Literal)理论,证明了EPPCCCL理论是在“最优化形式蕴含可控制”的类和“不一致性程度计算可控制”的类中,可以在多项式时间内回答任意最优化形式蕴含问题和决策形式蕴含问题,因此可以作为可能性知识编译的目标语言。最后,基于扩展规则,我们提出了将任意子句集合编译为EPPCCCL理论的一般方法。(3)提出一种基于启发式搜索的一致性规划求解方法。设计了一种将基于二值逻辑表示的一致性规划问题转换为基于多值逻辑表示的一致性规划问题,从而可以大幅度的压缩状态表示空间;设计了一种启发式函数,该函数的求解类似于求解旅行商问题。在此基础上,我们实现了上述思想,搭建了基于多值规划表示的一致性规划系统:JLU-CD,实验结果表明该系统在很多一致性规划域上的表现优于现有的一致性规划系统。