
CMUCS99114
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS99114
Iterative MacroOperators Revisited:
Applying Program Synthesis to Learning in Planning
Ute Schmid
March 1999
CMUCS99114.ps
CMUCS99114.pdf
Keywords: Macro generation, planning, inductive program
synthesis
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)
macrooperations from planning. Input in the program synthesis system
is a socalled initial program which represents an ordered set of
straightforward 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
nonlinear backward planner which generates such a complete
partial order as a byproduct 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 macroconstruction. 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
