A Cost-Directed Planner: Preliminary Report

Abstract

We present a cost-directed heuristic planning algorithm, which uses an A strategy for node selection. The heuristic evaluation function is computed by a deep lookahead that calculates the cost of complete plans for a set of pre-defined top-level subgoals, under the (generally false) assumption that they do not interact. This approach leads to finding low-cost plans, and in many circumstances it also leads to a significant decrease in total planning time. This is due in part to the fact that generating plans for subgoals individually is often much less costly than generating a complete plan taking interactions into account, and in part to the fact that the heuristic can effectively focus the search. We provide both analytic and experimental results. Introduction Most of the work on search control for planning has been based on the assumption that all plans for a given goal are equal, and so has focused on improving planning efficiency. Of course, as has been recognized in the liter...