通用型回答集程序关键问题研究

Answer set programming (ASP) is one of the most active research areas in knowledge representation and declarative programming in artificial intelligence; it is particularly suitable for representing and reasoning with combinatorial search problems. To meet broader application requirements, in recent years the ASP community has started to exploit more expressive ASP programs, called general ASP programs, which admit first-order formulas, abstract constraints, external knowledge sources, etc. The introduction of such complex expressions makes the previous ASP semantics and inference algorithms no longer applicable, and even incurs several challenging issues. Summarizing, for general ASP programs the existing approaches cannot correctly handle the default negation operator (may produce incorrect answer sets), cannot correctly handle the if-then rule operator (may produce answer sets with circular justifications), cannot effectively handle abstract constraints (difficult to determine whether or not their solutions should be minimized), and can only handle normal ASP programs with multiple external knowledge sources. The objective of this research is to solve these existing key issues with general ASP programs. We will develop new semantics and inference algorithms, analyze in depth their computational complexity, exploit system implementation techniques, and apply them to the state-of-the-art ASP systems.

回答集程序设计（ASP）是目前人工智能知识表达和说明性程序设计中最为活跃的一个研究领域，它特别适用于组合搜索问题的表达和推理。为使ASP满足更广泛的应用需求，近年来，国际学术界开始研究表达能力更强的ASP程序，称为通用型ASP程序，它允许规则中含有一阶逻辑公式、抽象约束、外部知识源查询等。这些复杂表达式的引入使得原有的ASP语义模型和推理算法不再可用，并且引出了多个挑战性问题。对通用型ASP程序，现有方法不能正确处理缺省否定算子（会产生不正确回答集），不能正确处理if-then规则算子（会产生循环论证回答集），不能有效处理抽象约束（难于区分什么解答需要极小化，什么解不能被极小化），并且只能处理简单ASP程序与外部多知识源的集成。本项研究的目标是解决通用型ASP程序目前存在的这些关键问题，我们将提出新的语义模型和推理算法，分析它们的计算复杂性，研究系统实现技术，并应用到国际主流ASP系统中。

回答集程序设计（ASP）是目前人工智能知识表达和说明性程序设计中最为活跃的一个研究领域，它特别适用于组合搜索问题的表达和推理。为使 ASP 满足更广泛的应用需求，近年来，国际学术界开始研究表达能力更强的 ASP 程序，称为通用型 ASP 程序，它允许规则中含有一阶逻辑公式、抽象约束、外部知识源查询等。本项研究的目标是解决通用型ASP存在的几个关键问题，包括否定算子、规则算子、复杂类抽象约束、以及外部多知识源等，最终实现通用型 ASP 程序系统，并将它集成到国际主流的 ASP 程序推理系统中。该目标已圆满完成，取得了一系列重要的理论成果，得到了国际同行的高度评价。特别是，我们提出了通用回答集程序的语义模型以及语义Web本体与规则的集成模型，而且解决了ASP语言的非单调认知否定问题，这是美国M. Gelfond教授在1990年AAAI会议上提出，二十多年来多位知名学者一直未能解决的重要公开问题。受此基金资助完成学术论文15篇，其中12篇发表在国际一流期刊和会议，包括Artificial Intelligence (AIJ)、ACM Transactions on Computational Logic (TOCL)、ACM Transactions on Information Systems (TOIS)、The AAAI Conference on Artificial Intelligence (AAAI)、The International Joint Conference on Artificial Intelligence (IJCAI)、The ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)等。