A Comparsion of Three Problem-Solving Methods

Ranan B. Banerji, George W. ErnstIJCAI 1977

Abstract

In this seminal 1977 work, Ranan B. Banerji and George W. Ernst provide a theoretical bridge between three of the most influential early approaches to Artificial Intelligence: ABSTRIPS, Planning (as defined by Newell & Simon), and the General Problem Solver (GPS). The authors demonstrate that these methods are functionally equivalent when provided with the same heuristic information, proving that "criticality levels" in ABSTRIPS are essentially the same as "difference orderings" in GPS.

Introduction

In the mid-1970s, the AI community utilized several distinct "engines" for automated problem-solving. While these systems relied on heuristics to navigate search spaces, it was unclear if one algorithm was fundamentally superior or if they were simply using different terminology for identical concepts. Banerji and Ernst set out to formalize the relationship between these methods and identify the class of problems they are uniquely suited to solve.

Formalizing Problem-Solving Methods

The authors developed formal mathematical models to compare the three systems on equal footing:

  • ABSTRIPS (Abstraction-Based STRIPS): Assigns "criticality levels" to predicates, solving problems by first addressing high-level goals and then refining the plan with low-level details.
  • Planning (Newell & Simon): Involves a simplified "planning space" where certain operators are removed; solutions found here are later "elaborated" into the original complex space.
  • GPS (General Problem Solver): Uses "Means-Ends Analysis" to identify the "difference" between current and goal states, selecting operators based on a "difference ordering."
Table mapping criticality levels to solutions and desired states, illustrating the hierarchical nature of the problem-solving process.

The authors introduce stratified solutions to show how these different "languages" describe the same underlying process of breaking a complex plan into a hierarchy of subproblems.

Experimental Validation

The paper validates its theories using classic AI "toy problems" rather than large-scale modern datasets. These include the Monkey and Bananas problem, the Tower of Hanoi, and the Fool's Disks Problem.

The Fool's Disks Problem, a puzzle involving concentric disks used to validate the theoretical models.

Key Insights and Results

A central finding is that heuristics are universal. The criticality levels of ABSTRIPS are functionally identical to the difference orderings of GPS. Furthermore, the authors highlight the "Triangular Table of Connections": if a problem's operators and differences can be arranged in a triangular matrix, the problem becomes significantly easier to solve.

Crucially, the research suggests that the choice of heuristic parameters has a more drastic effect on search efficiency than the choice of the algorithm itself. A well-tuned GPS will outperform a poorly tuned ABSTRIPS, and vice versa. All three methods are specifically optimized for "totally ordered" problems—those where subproblems can be solved sequentially without interference.

Limitations and Future Directions

The primary limitation of these models is their struggle with "unordered" problems, such as the Sussman Anomaly, where solving one sub-goal necessitates breaking another. The authors conclude that the future of the field lies not in building better search engines, but in developing systems that can automatically discover these triangular connection tables and criticality levels from raw problem descriptions.

Summary updated

BibTeX
@inproceedings{banerji1977comparsion,
  author = {Ranan B. Banerji and George W. Ernst},
  title = {{A Comparsion of Three Problem-Solving Methods}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1977},
}
Figure