Vocabularies for Problem Solver State Descriptions

Drew V. McDermottIJCAI 1977

Abstract

This paper introduces K-NET and SNIFFER, a framework for knowledge representation and reasoning that bridges the gap between formal logic and intuitive, structured data. By employing partitioned semantic networks, the system handles the rigors of first-order predicate calculus while maintaining the flexibility of hierarchical taxonomies. SNIFFER, the deduction engine, utilizes natural deduction and procedural specialists to achieve efficient, human-readable automated reasoning.

Introduction

In the late 1970s, AI researchers faced a significant dilemma: formal logic was mathematically sound but computationally expensive and often stripped away the intuitive structure of data. Conversely, traditional semantic networks were excellent for showing relationships but lacked the formal machinery to handle complex logic like negations or universal quantifiers.

To address this, the K-NET and SNIFFER systems were developed. This approach keeps the "skeleton" of a taxonomy visible for fast retrieval while enabling the proof of complex theorems without forcing data into the rigid "Clause Normal Form" (CNF) required by many contemporary theorem provers.

Methods: K-NET and SNIFFER

The architecture is built upon two primary components designed to integrate logic with structured representation.

K-NET: Partitioned Semantic Networks

K-NET is a "partitioned" semantic network where the graph is divided into Spaces. These spaces can be bundled into Vistas, allowing the system to represent different logical "worlds," such as a character's beliefs, hypothetical scenarios, or the contents of a disjunction (Either A or B).

Figure 1: A simple semantic network illustrating basic entities and relationships in the K-NET framework.

SNIFFER: The Deduction Engine

SNIFFER uses natural deduction to work backward from a query, rather than forward from facts. It incorporates several innovative features:

  • Coroutine Control: A "best-first" search powered by Interlisp coroutines allows the system to explore multiple potential proof paths in pseudo-parallel.
  • Procedural Augmentation: SNIFFER can call "specialist" procedures for specific tasks. For example, mathematical operations are handled by Lisp functions rather than logical deduction.
  • Parity Tracking: The system tracks the logical sign (positive or negative) of nodes and arcs based on their nesting within negation or implication spaces, preserving the natural form of the input.

Example Knowledge Base and Evaluation

The system's capabilities were evaluated using a hand-crafted knowledge base focused on the domain of automobiles. This domain includes facts about manufacturers (e.g., Ford, GM), specific models (e.g., Mustangs), and various ownership situations.

Figure 2: An example knowledge base demonstrating the integration of taxonomic hierarchies and logical implications.

Key Insights

  • Topology as Logic: By following "subset" and "element" arcs, SNIFFER can bypass heavy logical machinery to quickly conclude hierarchical facts, such as a Mustang being a vehicle.
  • Quantification via Spaces: Partitioning the network into spaces provides a clever mechanism for handling quantification. A "Universal" space acts as a template; nodes existing in both the "If" and "Then" spaces of an implication are treated as universally quantified variables.
  • Natural Form Reasoning: Reasoning on the "natural" form of input preserves the heuristic value of the original statements, making the search for a proof more efficient and intuitive.

Results and Discussion

The paper demonstrates qualitative success in handling complex, nested queries, such as distinguishing between different "worlds" of belief. The use of taxonomic specialists allowed the system to answer hierarchical queries almost instantly by traversing the network hierarchy.

However, certain limitations were identified. "Case Analysis" (proving a goal by showing it is true in all possible sub-cases) can lead to infinite loops if not carefully managed. Furthermore, while the system supports best-first search, identifying the most effective heuristics for path selection remains an open challenge. Future work will focus on extending the system to handle uncertainty and temporal reasoning.

Summary updated

BibTeX
@inproceedings{mcdermott1977vocabularies,
  author = {Drew V. McDermott},
  title = {{Vocabularies for Problem Solver State Descriptions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure