A Cost-Directed Planner: Preliminary Report

Eithan Ephrati, Martha E. Pollack, Marina Milshtein

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.