Abstract
Automated theorem proving in geometry has traditionally been treated as a search problem within formal logic, often leading to an exponential explosion of the search space. This paper presents POLYA, a case-based planning system that shifts the paradigm from exhaustive search to memory-driven reasoning. By leveraging a library of past proof plans indexed by diagrammatic features, POLYA mimics the way human students solve geometry problems: through pattern recognition, the use of "idioms," and the flexible adaptation of known solutions to new contexts.
Introduction
In the realm of automated reasoning, geometry theorem-proving represents a significant challenge. From a purely formal perspective, the search for a proof is an NP-complete problem; the number of possible inferences at any given step can grow uncontrollably. However, human learners rarely struggle with this "search space" in the same way a computer does. Instead of chaining axioms from first principles, students utilize a repertoire of heuristics and recurring patterns. They recognize that a certain diagrammatic configuration—such as an isosceles triangle or a set of parallel lines—suggests a specific set of logical moves.
POLYA, developed by Thomas F. McDougal, is a system designed to bridge this gap. It operates on the principle that geometry is a "regular domain" where problems are not random but structured. By treating theorem-proving as a task of case-based planning and memory retrieval, POLYA demonstrates how everyday reasoning strategies can be applied to formal mathematical domains.
The POLYA Architecture
POLYA’s methodology is rooted in case-based planning, consisting of four primary pillars that facilitate human-like problem solving.
1. The Plan Library
At the heart of the system is a hierarchical library of plans. These range from high-level strategies for solving complex, multi-step theorems down to low-level plans for executing single inferences. This hierarchy allows the system to think in terms of "chunks" rather than individual axioms.
2. Feature-Based Indexing and Perception
Unlike traditional solvers that rely solely on logical predicates, POLYA "sees" the problem. Plans in the library are indexed by diagrammatic features. Before a proof begins, the system employs search plans to extract visual features from the diagram’s numerical coordinates. For example, if a triangle appears isosceles, a search plan is triggered to verify the equality of its legs. Once verified, this feature serves as a key to retrieve relevant proof plans from memory.
3. Flexible Adaptation
Retrieving a past case is only the beginning. Because a new problem rarely matches a stored case perfectly, POLYA must adapt. The retrieved case establishes a sequence of subgoals, but the system remains responsive to the specific features of the current problem to determine how those subgoals are achieved. This flexibility allows POLYA to handle variations in geometry and logical constraints that differ from the original case.
Methodology and Domain Regularity
The system was tested using problems from a standard high school textbook, Geometry for Enjoyment and Challenge (Rhoad, Whipple, and Milauskas, 1988). This choice was deliberate: textbooks are designed to be pedagogical, meaning they are intentionally structured with recurring patterns and incremental complexity.
This "regularity" is crucial for case-based reasoning. In a regular domain, the past is a reliable predictor of the future. By training on a structured curriculum, POLYA can develop a library of "idioms"—common patterns of inference that bypass the need for exhaustive search.
Key Insights
- Diagrams as Heuristics: Diagrams are not merely illustrations; they are rich heuristic sources. By perceiving symmetry or specific configurations, POLYA prunes the search space, focusing only on the most promising lines of inquiry.
- Avoiding First Principles: By recognizing perceptual chunks, the system avoids the "first principles trap." It jumps directly to the relevant inferences, much like an expert geometer who "just knows" which theorem to apply based on the look of the figure.
- Reasoning as Memory: The research suggests that reasoning in formal domains is fundamentally similar to everyday planning. Success in both depends on an agent’s ability to remember what worked previously and adapt it to the present situation.
Results and Discussion
While the 1994 abstract focuses on the architectural framework rather than modern quantitative benchmarks, its qualitative contributions are significant. POLYA successfully demonstrated that proofs could be reused and adapted by focusing attention on previously important objects within a diagram.
By using case-based indexing, the system achieved a level of efficiency that bypassed the heavy inference-chaining stages required by contemporary systems of the era. Furthermore, the author identified three universal planning challenges—selection, flexibility, and interrupts—positioning the geometry domain as a laboratory for broader AI research into how agents act in structured environments.
Limitations and Future Directions
Despite its successes, POLYA faced several hurdles:
- The Interrupt Problem: The system tended to follow a plan to completion even if a shortcut or a potential failure became apparent mid-way. Real-world reasoning requires the ability to "interrupt" a plan based on new observations.
- Optimal Selection: When multiple plans were applicable, the system occasionally struggled to identify which would lead to the most efficient solution.
- Generalization: The ultimate goal remains the development of a general theory of action for all regular domains, moving beyond the specific constraints of high school geometry.
In conclusion, POLYA represents a pivotal attempt to move automated theorem proving away from brute-force logic and toward a more cognitive, experience-based model of intelligence.
Summary updated