A Cost-Directed Planner: Preliminary Report

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.