逻辑程序的回答集存在性理论与应用问题研究

摘要

回答集编程(Answer Set Programming, ASP)的出现是非单调推理领域的突破性成果,其理论基础是Gelfond和Lifschitz提出的回答集语义。目前,ASP在规划、诊断、行动推理、智能机器人的规划与决策以及航空火箭的决策等领域均已得到广泛应用。为了更有效的利用ASP,国内外众多学者对ASP的性质及应用进行了广泛的研究。本文对逻辑程序回答集的存在性和ASP在知识表示和推理方面的应用进行了探索和研究。课题得到了国家自然科学基金( No.60803033)和广西研究生科研创新项目资助(No.2010105950812M28)。论文研究内容分为三部分:
　　1)逻辑程序回答集存在性判断。判断逻辑程序回答集的存在性是回答集求解器设计的一个关键技术,其判断的准确性直接关系到回答集求解的效率,因而成为ASP研究中的一个热点问题。目前利用否定圈边数的奇偶性来判断回答集存在性的方法还具有一定的局限性,无法全面准确地判断回答集的存在性。针对该问题,提出了一种基于否定圈的新的回答集存在性判断方法,该方法可以判断非分层逻辑程序回答集是否存在,给出了该判断方法的实现框架,证明了该方法的正确性,并以实例分析说明了该方法的有效性。
　　2)ASP在全局数据流分析(Global Data Flow Analysis, GDFA)中的应用。数据流分析(Data Flow Analysis, DFA)是软件工程中非常重要的任务之一,在程序验证、编译优化、程序理解等方面起着重要的作用。当前方法在对不同程序设计语言编写的程序进行数据流分析时,需根据各种语言的特征开发相应的分析软件,软件代码和相关信息的重用度较低,造成极大资源浪费。研究发现以知识表示为基础的方法在解决具体问题时不仅具有较高的效率,且只需要改变问题的描述部分,即可适应具有不同语法结构程序的数据流分析,从而降低程序分析工具开发的周期,使分析工作变得简单。本文提出了一种基于ASP的GDFA方法,并设计实现了一套基于ASP的数据流分析系统。在该系统中,只需要输入合法的SimC程序,所有DFA所需的知识均能自动生成。实验表明该方法具有较高的执行效率。
　　3)ASP在装配序列规划中的应用。本文提出一种基于ASP的机械装配序列规划(Mechanical Assembly Sequence Planning,MASP)方法。该方法表明,将ASP程序划分为EDB(Extensional Datanase, EDB)和IDB(Intensional Database, IDB)可提高知识的重用度,即:拥有相同的零件数目的装配体可以共享IDB。实验分析表明,该方法具有较高的时间效率和空间效率。另外,当一个机械装配体零件数目增多时,装配问题的复杂度程急剧增加,因此单纯的利用装配序列规划方法在有限的时间内无法生成大型装配体的装配规划序列。子装配体识别(Subassembly Identification, SI)技术可将大型的装配体中的部分零件转化为少数子装配体,从而降低装配过程的计算复杂性。为此,本文提出了一种基于ASP的子装配体识别技术,以必要的装配体信息为输入,求解器将自动识别其中的子装配体。根据该思想开发了一套基于ASP的子装配识别系统。实验表明了该方法的有效性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1引论

§1.2背景介绍

§1.3本文的主要工作

§1.4本文的结构

第二章 ASP基础

§2.1 逻辑程序

§2.2 逻辑程序的声明式语义

§2.3 ASP语法扩展及相应回答集

§2.4 回答集的计算方法

§2.5 ASP的相关性质

第三章 回答集存在性判断

§3.1否定圈等基础概念

§3.2方法概述

§3.3 逻辑程序的约简

§3.4 正规逻辑程序的分类

§3.5 否定圈回答集存在性判断

§3.6实例分析

§3.7 小结

第四章 ASP在数据流中的应用

§4.1 知识介绍

§4.2 构造DFA模型

§4.3 基于ASP的DFA方法

§4.4相关软件设计

§4.5 实验

§4.6小结

第五章 ASP在装配序列规划中的应用

§5.1装配基础知识

§5.2装配序列规划

§5.3基于ASP的子装配体的识别技术

§5.4小结

第六章 结束语

§6.1本文主要贡献

§6.2 研究展望

参考文献

致谢

作者在攻读硕士期间主要研究成果