The goal of this paper is to demonstrate that a method for inductive program synthesis (as described in Schmid & Wysotzki 1998) can be applied to the problem of learning cyclic (iterative/recursive) macro-operations from planning. Input in the program synthesis system is a so-called initial program which represents an ordered set of straight-forward transformations from input states to the desired output. In the context of planning, the input states correspond to initial states, the output state to the planning goal, and transformations are shortest operation sequences. Ordering of transformations can be achieved by calculating a minimal spanning tree for the problem graph with the state(s) fulfilling the goal as root. We have implemented a non-linear backward planner which generates such a complete partial order as a by-product of planning. Output of the program synthesis system is a recursive program scheme representing the generalization of a program limited to solving a finite problem of given size to a general solution strategy. Our synthesis method is embedded in the theory of the semantic of functional programs and in the theory of inductive inference (see Muehlpfordt & Schmid 1998) and thereby provides a sound formal basis for macro-construction. The current implementation can generalize tail, linear and tree recursive structures and combinations of such structures with multiple (and possibly interdependent) recursive parameters. 89 pages

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

This page maintained by reports@cs.cmu.edu