Representing and Using Procedural Knowledge to Build Geometry Proofs

Thomas F. McDougal, Kristian J. HammondAAAI 1993

Introduction

In high school geometry, students often struggle not with learning theorems, but with knowing when to apply them. While a student might understand the Side-Angle-Side (SAS) theorem, they can easily become overwhelmed by a "search space" of hundreds of valid but irrelevant logical inferences. POLYA is a computational model designed to bridge this gap by mimicking human expertise. Instead of exhaustive search, it utilizes "procedural knowledge"—specialized plans triggered by specific visual cues in a diagram—to focus reasoning on the most promising paths.

The POLYA Architecture

The system treats geometry solving as a process of integrating diagram parsing with formal proof construction. POLYA consists of three primary interacting modules that facilitate this reactive planning approach.

The architecture of the POLYA system, showing the interaction between plan memory, the interpreter, and simulated vision.
  1. Simulated Vision: This module contains over 120 operators that allow the program to "inspect" a diagram. It identifies shapes, estimates sizes, and detects critical annotations such as congruency marks (ticks on segments or arcs on angles).
  2. Plan Memory & Retriever: Based on the DMAP architecture, this module uses a marker-passing scheme to trigger specific plans when relevant visual features are detected.
  3. Plan Interpreter: This component executes the steps of a triggered plan, which may involve further visual inspection or the addition of formal statements to the proof.

Procedural Plans and Active Sensing

POLYA's expertise is encoded in two types of plans. Search Plans direct the system's attention to relevant parts of the diagram (e.g., "If a triangle looks isosceles, check its base angles"). Proof Plans represent formal geometric rules; if visual conditions are met, these plans commit a formal step to the proof.

A complex geometry diagram illustrating the visual cues (like angle arcs and segment ticks) that POLYA uses to trigger specific proof plans.

This approach highlights several key insights into geometric reasoning:

  • The Diagram as External Memory: Rather than maintaining a perfect internal model of every fact, POLYA treats the diagram as a primary source of truth, re-inspecting it as needed.
  • Active Sensing: The system does not process the entire image at once. Instead, it uses "active vision" to compute only the features relevant to the current plan, mirroring human focus.
  • "May" vs. "Should": Expertise is defined as the ability to distinguish between a rule that can be applied and one that should be applied based on the current goal and visual context.

Performance and Results

The system was evaluated using problems from standard high school textbooks, such as Geometry for Enjoyment and Challenge. POLYA demonstrated efficient "forward reasoning," often making significant logical leaps based on diagram symmetry before even fully processing the goal statement. For a typical moderate problem, the system utilizes between 12 and 28 plans, involving 50 to 120 discrete visual actions.

Limitations and Future Directions

While successful in the domain of triangle congruence, the system's scope remains a limitation. Expanding to more complex shapes like quadrilaterals would require a significant expansion of the plan library. Additionally, as the library grows, the challenge shifts toward more sophisticated plan prioritization and maintaining efficient retrieval speeds. Future work aims to refine how the system chooses between multiple competing plans triggered by the same visual stimulus.

Summary updated

BibTeX
@inproceedings{mcdougal1993representing,
  author = {Thomas F. McDougal and Kristian J. Hammond},
  title = {{Representing and Using Procedural Knowledge to Build Geometry Proofs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure