RI: Small: Universal Automated Reasoning by Knowledge Compilation

RI：小：通过知识编译进行通用自动推理

• 批准号: 0916161
• 负责人: Adnan Darwiche
• 金额: $ 47.5万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-10-01 至 2013-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916161&HistoricalAwards=false
• 关键词: RI; Small; Universal; Automated; Reasoning

A long term goal motivating this project is the development of a universal computational engine to support reasoning across different applications of intelligent systems (e.g., planning and diagnosis). The project is founded on an approach that compiles knowledge bases into a taxonomy of tractable forms, which result from imposing various conditions, such as decomposability and determinism, on Negation Normal Form (NNF). Certain queries, which are generally intractable, become tractable on the compiled NNF forms. To implement a task like planning or diagnosis, all one needs to do is compile their knowledge base to the most succinct subset of NNF that provides polytime support for the queries required by the task. The project will focus in particular on algorithms for imposing various conditions on NNF compilations, using both top-down and bottom-up compilation techniques, to support a larger set of tractable forms. This will lead to developing and evaluating a more powerful inference engine than traditional SAT solvers, supported by a more comprehensive set of queries and transformations on knowledge bases. It will also lead to extending the compilation approach to a larger class of AI applications.

这个项目的长期目标是开发一个通用的计算引擎，以支持智能系统的不同应用（例如，规划和诊断）的推理。该项目建立在一种方法的基础上，该方法将知识库编译成可处理形式的分类法，这是通过对否定范式（NNF）施加各种条件（如可分解性和决定论）而产生的。某些通常难以处理的查询在编译后的NNF表单上变得容易处理。要实现计划或诊断之类的任务，需要做的就是将知识库编译为最简洁的NNF子集，该子集为任务所需的查询提供多时支持。该项目将特别关注对NNF编译施加各种条件的算法，使用自顶向下和自底向上的编译技术，以支持更大的可处理表单集。这将导致开发和评估一个比传统SAT求解器更强大的推理引擎，由知识库上更全面的查询和转换集支持。它还将导致将编译方法扩展到更大类别的AI应用程序。