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*

June 2000

This report was written while the first author was a visiting researcher at Carnegie Mellon University.
The report gives an extended and updated presentation of the work reported at AIPS-00.

To obtain the programs described, contact
or see

Keywords: Control knowledge learning, universal planning, inductive program synthesis, data type inference

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 plan-to-program transformation.

126 pages

*Department of Computer Science, Technical University Berlin, Franklinstrasse 28, D-10587 Berlin, Germany.

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by