Finding All of the Solutions to a Problem

David E. SmithAAAI 1983

Introduction

In the early development of artificial intelligence, automated problem solvers often suffered from a lack of "common sense" regarding search termination. A system tasked with identifying a person's parents might find two names and then continue to search its entire database for hours, hoping to find a third. This "blindly" exhaustive approach is computationally expensive and redundant. Humans, by contrast, utilize meta-knowledge—such as the fact that biological parents come in pairs—to stop searching once a known quota is met. This paper, originally published in 1983, introduces a formal method for teaching computer systems to recognize when they have found all possible solutions to a query, thereby optimizing search efficiency through meta-level reasoning.

The Meta-Level Approach

The proposed architecture operates on two distinct levels to manage search resources effectively. The Base Level performs the standard search for solutions, while the Meta Level reasons about the search process itself, specifically asking: "How many solutions should this problem have?"

By determining the expected number of solutions before or during the search, the system can prune unnecessary branches once the target count is reached. This logic is encapsulated in the flowchart below, which illustrates how the system checks for completion after each new solution is found.

Flowchart of the meta-level reasoning process for determining when to stop searching for solutions.

The NUMBEROF Predicate and Cardinality

Central to this method is the NUMBEROF predicate, a formal representation stating that a specific query has $n$ solutions. The system can derive these counts from known set sizes (cardinality). For instance, if the system knows the set of HEART_CHAMBERS has a cardinality of 4, it will terminate its search for chambers immediately upon finding the fourth one.

Implementation: Caching and Truth Maintenance

For problems where the solution count is not known a priori, the system performs an exhaustive search once, counts the results, and "caches" this number for future queries. However, caching in a dynamic database presents a challenge: if data is added or deleted, the cached count may become obsolete.

To address this, the system employs a Truth Maintenance System (TMS). The TMS tracks the justifications for each cached count, allowing the system to invalidate and update counts when the underlying data changes. To further optimize, certain counts can be marked as "invariant"—such as the number of bones in a human hand—indicating they do not change over time and do not require active maintenance.

Evaluation and Results

The meta-level reasoning system (MRS) was evaluated using two complex expert systems of the era: Kunz’s Renal Physiology Model and Barnes’ Income Tax Consultant.

In the Renal Physiology model, incorporating knowledge about set sizes and invariance led to speedups ranging from 2x to 10x. In the Tax Consultant system, which frequently navigates complex familial relationships, the impact was equally significant. A query regarding siblings that previously generated hundreds of subgoals and took 15 minutes was reduced by a factor of 3 simply by defining "Mother" and "Father" as functional symbols (yielding only one result).

Decomposition of a goal into subgoals, illustrating the search space for familial relationships.

As shown in the figure above, queries like SON(x, MARTHA) are decomposed into multiple subgoals. Without meta-knowledge, the system might exhaustively explore every branch of the CHILD relationship even after the relevant sons have been identified.

Key Insights and the Pruning Paradox

A significant finding of the research is the "Pruning Paradox." This occurs when a meta-level rule prunes a search branch because it won't lead to new solutions for the primary goal. While efficient for the current task, this results in an artificially low count for that specific sub-problem. If this low count is cached without context, it could lead to errors in future, unrelated queries. The author suggests including a "context" argument in cached counts to mitigate this risk.

Ultimately, the paper demonstrates that knowing the number of solutions is often computationally cheaper than storing every individual solution and its associated justifications. While managing the overhead of a TMS is complex, the performance gains in large-scale expert systems justify the investment in meta-level reasoning.

Conclusion

This work highlights a critical component of intelligent problem solving: knowing when to quit. By integrating meta-knowledge about solution counts and employing robust maintenance strategies, automated systems can move beyond blind exhaustion toward more human-like, efficient search behaviors. Future work remains to integrate these techniques with other pruning methods and more expressive ways to handle database invariance.

Summary updated

BibTeX
@inproceedings{smith1983finding,
  author = {David E. Smith},
  title = {{Finding All of the Solutions to a Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}

Loading related content...

Figure