|
Abstract : |
The planner GRAPHPLAN is based on an efficient propagation of reachability information which then effectively guides a search for a valid plan. We propose a framework in which a broader class of information, including the original reachability information, can be propagated in the plan graph in polynomial time. As an example, we exhibit an algorithm for propagating "landmark " information, where a landmark is a proposition or action that must occur in any correct plan. This algorithm computes in polynomial-time a set of planning landmarks significantly larger than previously published landmark computation algorithms. We show how to leverage this algorithm to extract an incrementally computable planning heuristic. We present results showing that enforced hill-climbing using this heuristic is significantly more robust, |
