Abstract
This paper presents a theoretical framework for automating the discovery of heuristics in General Problem Solver (GPS) systems. By redefining differences as nested sets of states and identifying conditions for triangular strategy tables, the authors enable the mechanical generation of connection tables from problem specifications, moving toward truly autonomous problem-solving.
Introduction
In the early era of artificial intelligence, Newell and Simon’s General Problem Solver (GPS) represented a major milestone. However, its "generality" was limited by the requirement for human-defined heuristics. Specifically, a human programmer had to construct a Connection Table to map operators to differences between current and goal states. Banerji and Ernst address this bottleneck by proposing a method for mechanization: allowing a computer to derive these tables directly from the rules of a puzzle or problem.
Methodology: The Two-Phase Process
The proposed framework operates in two distinct phases: Parameter Generation and Problem Solving.
- Parameter Generation: The system analyzes the formal problem specification to identify "good parameters"—specifically, differences and their corresponding operator mappings.
- Problem Solving: These generated parameters are then used by the GPS strategy to navigate the state space toward a solution.
A critical innovation is the simplification of "differences." Rather than complex binary relations, the authors treat a difference as a simple set of states. This monadic approach makes the mathematical derivation of heuristics tractable for automated systems.
Key Insights: Nested Differences and Triangularity
The core of the theory lies in the organization of state space. The authors introduce "Good Differences," which are defined by their nested structure.
As shown in Figure 3, the most difficult differences contain easier ones as subsets. This nesting ensures that progress made on a "hard" difference is not accidentally undone by moves intended to solve "easier" ones. This leads to Triangular Connection Tables. In such a table, the operators are ordered such that an operator used to reduce difference $d_i$ does not reintroduce any difference $d_j$ where $j < i$. This property prevents "backsliding" and drastically reduces the search space.
Evaluation and Results
The theory was tested against classic symbolic AI benchmarks, including the Tower of Hanoi, the Monkey and Bananas problem, and the Fool’s Disk Problem.
The authors successfully demonstrated that:
- GPS-solvable problems can be formally characterized as those possessing "totally-ordered solutions."
- Non-nested problems (like Tower of Hanoi) can often be mathematically transformed into nested structures through set operations.
- A proof-of-concept program could successfully construct these triangular tables automatically using invariant attributes of problem states.
Limitations and Conclusion
While a significant advancement, the framework assumes the existence of a totally-ordered solution path. It may struggle with problems requiring non-linear planning—where one must move temporarily away from a goal. Future work points toward integrating non-linear planning techniques and detecting "factorable subproblems" to handle more complex, multi-faceted tasks. This research remains a foundational step in shifting the burden of heuristic design from humans to machines.
Summary updated