Applying Inductive Program Synthesis to Learning Domain-Dependent Control Knowledge - Transforming Plans into Programs

摘要

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.