Computer Science Department
School of Computer Science, Carnegie Mellon University
Applying Inductive Program Synthesis to Learning
Domain-Dependent Control Knowledge - Transforming Plans into Programs
Ute Schmid*, Fritz Wysotzki*
This report was written while the first author was a visiting researcher at Carnegie Mellon University.
Keywords: Control knowledge learning, universal planning,
inductive program synthesis, data type inference
The report gives an extended and updated presentation of the work reported at AIPS-00.
To obtain the programs described, contact
The goal of this paper is to demonstrate that inductive
program synthesis can be applied to learning domain-dependent control
knowledge from planning experience. We represent
control rules as recursive program schemes
(RPSs). An RPS represents the complete subgoal structure of a given problem
domain with arbitrary complexity (e.g., rocket transportation problem
with n objects). That is, if an RPS is provided for a planning domain, search
can be omitted by exploiting knowledge of the domain.
We propose the following steps for automatical inference of
control knowledge: (1) Exploring a problem with small complexity
(e.g., rocket with 3 objects) using an universal planning technique,
(2) transforming the universal plan into a finite program, and (3)
generalizing this program into an RPS. While generalization can be performed
purely syntactical, plan transformation is knowledge dependent. Our approach
to folding finite programs into RPSs is reported in detail elsewhere. In this
report we focus on plan transformation. We propose that inferring the data
type underlying a given plan provides a suitable guideline for
*Department of Computer Science, Technical University Berlin, Franklinstrasse 28, D-10587 Berlin, Germany.