Scaling up Heuristic Planning with Relational Decision Trees
  Current evaluation functions for heuristic planning are expensive to compute.
In numerous planning problems these functions provide good guidance to the
solution, so they are worth the expense. However, when evaluation functions are
misguiding or when planning problems are large enough, lots of node evaluations
must be computed, which severely limits the scalability of heuristic planners.
In this paper, we present a novel solution for reducing node evaluations in
heuristic planning based on machine learning. Particularly, we define the task
of learning search control for heuristic planning as a relational
classification task, and we use an off-the-shelf relational classification tool
to address this learning task. Our relational classification task captures the
preferred action to select in the different planning contexts of a specific
planning domain. These planning contexts are defined by the set of helpful
actions of the current state, the goals remaining to be achieved, and the
static predicates of the planning task. This paper shows two methods for
guiding the search of a heuristic planner with the learned classifiers. The
first one consists of using the resulting classifier as an action policy. The
second one consists of applying the classifier to generate lookahead states
within a Best First Search algorithm. Experiments over a variety of domains
reveal that our heuristic planner using the learned classifiers solves larger
problems than state-of-the-art planners.
