Online Speedup Learning for Optimal Planning
  Domain-independent planning is one of the foundational areas in the field of
Artificial Intelligence. A description of a planning task consists of an
initial world state, a goal, and a set of actions for modifying the world
state. The objective is to find a sequence of actions, that is, a plan, that
transforms the initial world state into a goal state. In optimal planning, we
are interested in finding not just a plan, but one of the cheapest plans. A
prominent approach to optimal planning these days is heuristic state-space
search, guided by admissible heuristic functions. Numerous admissible
heuristics have been developed, each with its own strengths and weaknesses, and
it is well known that there is no single "best heuristic for optimal planning
in general. Thus, which heuristic to choose for a given planning task is a
difficult question. This difficulty can be avoided by combining several
heuristics, but that requires computing numerous heuristic estimates at each
state, and the tradeoff between the time spent doing so and the time saved by
the combined advantages of the different heuristics might be high. We present a
novel method that reduces the cost of combining admissible heuristics for
optimal planning, while maintaining its benefits. Using an idealized search
space model, we formulate a decision rule for choosing the best heuristic to
compute at each state. We then present an active online learning approach for
learning a classifier with that decision rule as the target concept, and employ
the learned classifier to decide which heuristic to compute at each state. We
evaluate this technique empirically, and show that it substantially outperforms
the standard method for combining several heuristics via their pointwise
maximum.
