Abstract
The acquisition of complex procedures from execution traces presents a significant challenge in machine learning due to the infinite search space of possible generalizations. This paper introduces the Procedure Matcher and Acquirer (PMA), a system that leverages domain constraints and context-limited generalization to infer hidden control structures like loops and branches. By applying principles of desirability ordering and action hierarchies, PMA successfully synthesizes generalized algorithms from a small number of specific examples.
Introduction
Generalization is the process of deriving universal rules from specific instances. In the context of procedure acquisition, this task is particularly difficult because the learner must infer unobserved control logic—such as conditional branches and iterative loops—from linear execution traces. Without constraints, a learner might identify spurious patterns that do not reflect the intended logic. This paper addresses this "search space" problem by introducing a framework of three guiding principles: Domain Constraints, Undesirability Ordering, and Context Limited Generalization.
The PMA System: Methodology
PMA represents procedures as directed graphs, where nodes signify events composed of conditions and actions. The system builds these graphs through an incremental matching process across multiple execution traces.
Incremental Matching
The process begins with Skeleton Matching, identifying "key events" like START and STOP or unique bottleneck actions that are easily paired across traces. Following this, PMA performs Propagation, "walking" through the traces from these anchor points to pair adjacent events.
Generalization and Induction
PMA utilizes pre-defined action and condition hierarchies to find commonalities between superficially different actions. For instance, a specific move to a coordinate might be generalized into a "MOVE-UNTIL-CONTACT" action if the domain knowledge suggests such a relationship.
When PMA identifies "parallel segments"—sequences that start and end at the same logical points but involve different values—it employs Function Induction. This allows the system to discover mathematical relationships, such as calculating a robot's avoidance angle based on the angle of impact.
Principles for Limiting Generalization
The core contribution of this work is the set of heuristics used to prune the hypothesis space:
- Domain Constrained Generalization: Uses physical laws (e.g., a robot cannot be in two places simultaneously) to invalidate impossible rules.
- Undesirability Ordering: Prefers simpler, conjunctive descriptions over complex disjunctive ones. Branches are only introduced when the data makes them unavoidable.
- Context Limited Generalization: Restricts powerful induction tools to specific contexts, such as parallel segments, to prevent finding patterns in noise.
Evaluation: The Turtle Procedure
The system was evaluated in a simulated 2D robot environment. The primary task was the "Turtle Procedure," where a robot must navigate toward a goal while circumnavigating obstacles.
PMA successfully synthesized this procedure from just three traces: a straight path, a path hitting one obstacle, and a path hitting a different obstacle at a different angle. The resulting graph correctly captures the loop structure and the functional relationship between impact angle and avoidance maneuver, moving from specific coordinate-based traces to a generalized algorithm.
Conclusion
PMA demonstrates that complex procedural knowledge can be acquired from a few examples if the learning process is sufficiently constrained by domain knowledge and heuristic ordering. While dependent on pre-defined hierarchies, the system provides a robust framework for moving from specific coordinate-based traces to generalized, algorithmic representations.
Summary updated