Boosting Reasoning Technology Through Randomization,

Research Objectives:   General Problem Description

In order for computers to perform increasingly complex tasks --- including ones that require a certain level of intelligence --- programs need to incorporate vast amounts of general knowledge, and data about the system’s environment and how to operate in it. This information is stored in a knowledge base. A key advantage of such a knowledge-based approach is that one does not need to represent all knowledge in an explicit form but rather one can employ general reasoning engines to make implied information explicit and to deal with changing information due to a dynamically changing environment. A major challenge in making large-scale knowledge-based systems a practical reality concerns the computational complexity of the reasoning task. In this project we will focus on inference problems derived from the domain of chess

Main goals: The scale-up of current reasoning technology by two orders of magnitude combined with a principled management of computational resources. Progress to be measured in terms of several factors: (1) response time, (2) query coverage, and (3) coverage of knowledge base. 

Tangible benefit to end users: Efficient, predictable, and general inference technology for query answering.

Critical technical barriers: (1) Tractable hidden problem structure can dramatically speed-up inference. However, uncovering such structure can be computationally expensive. Randomization, portfolio strategies, and tailored heuristics should alleviate this problem. (2) More powerful interactive reasoning systems can, in principle, push reasoning capabilities far beyond propositional. The challenge is to design hybrid systems that integrate many different forms of reasoning in a single reasoning engine. (p. 8-22,23)

Main elements of proposed research: Our research will directly address the critical barriers listed above. We propose to so by (1) exploiting randomization and parallel portfolio techniques (Selman et al. 1997; Gomes et al. 2000), (2) uncovering hidden structure and variable dependencies in the underlying reasoning tasks (“backdoor variables”, Williams, Gomes and Selman, 2003), (3) compilation strategies (Selman and Kautz 1996), and (4) hybrid, higher-order reasoning methods (Constable et al. 1986; Kreitz and Otten 1999). Propositional inference techniques have improved dramatically over the past decade. Progress is driven by a close interaction between theory, empirical research, and application demands. Our current proposal aims to integrate several of the most promising recent developments in a general inference engine for large-scale knowledge-based systems.

Evaluation of progress:  Repeated benchmarking of progress throughout program. We will use both existing benchmarks and newly developed ones based on challenge inference problems derived from the domain of chess. 

Current Approach: Problem Solving Strategies Using Quantified Boolean Formulas