Introduction
In the field of automated planning, traditional systems often relied on a "generate-and-fix" methodology. These systems would produce a linear plan and then employ "critics" to identify and resolve conflicts. However, in high-stakes physical domains like metal machining, this reactive approach is often inefficient and prone to failure. This paper introduces Machinist, a specialized planner that proactively identifies physical goal interactions to guide the planning process from the outset.
The Problem of Physical Interactions
Machining involves transforming a raw block of metal into a finished part with specific features like holes, slots, and shoulders. These features often interact in ways that constrain the order of operations. For instance, if an angled surface is milled before a hole is drilled into it, the drill bit will likely slide off the slanted surface, leading to inaccuracy or tool breakage.
Such physical constraints mean that subgoals cannot be achieved in isolation. A successful planner must recognize these interactions early to avoid exploring a massive space of invalid plans.
The Machinist Approach
Machinist, implemented in OPS5, shifts the planning paradigm from reactive to proactive. It utilizes domain-specific "macro-operators" to recognize patterns of interaction. These operators encapsulate expert knowledge, such as "drill the hole before cutting the angle," allowing the system to prune the search space before any steps are scheduled.
The Planning Process: Graph Merging
The system's core logic involves generating and merging two distinct types of constraint graphs:
- Interaction Graph: This graph defines the necessary sequence for cutting specific features based on physical dependencies.
- Squaring Graph: This graph outlines the preparatory steps required to transform raw stock into a precise rectangular block (squaring the part).
By merging these graphs, Machinist identifies the most efficient sequence of setups and tool changes, resulting in a compact and executable manufacturing plan.
Evaluation and Results
The system was evaluated against plans generated by human machinists of varying experience levels, from apprentices to a five-year journeyman. Expert master machinists performed a blind ranking of the resulting plans.
The results were significant:
- Search Space Reduction: For a complex part with 14 features, the proactive use of interaction heuristics reduced the search space by a factor of over 1.6 million.
- Expert-Level Performance: Machinist's plans were consistently rated as high as or higher than those of the five-year journeyman. One expert judge noted that the system's output was "almost the perfect plan," demonstrating that the proactive approach effectively captures the intuition of human experts.
Conclusion
The success of Machinist highlights the importance of domain-specific knowledge in complex planning tasks. By identifying goal interactions proactively rather than reactively, the system avoids the "search space paradox" where valid solutions become increasingly sparse as complexity grows. While the specific patterns are domain-dependent, the methodology of using interaction graphs to guide planning offers a robust framework for other high-stakes engineering domains.
Summary updated