A New Approach to Heuristic Estimations for Cost-Based Planning

All Papers

Solving relaxed problems is a commonly used technique in heuristic search to derive heuristic estimates. In heuristic planning, this is usually done by expanding a planning (reachability) graph on the current search state where the delete lists of operators are removed from their definition. Usually, this technique is used to obtain plan length estimates. However, in cost-based planning the goal is to find plans minimizing some criteria. This requires the redefinition of the heuristic estimation to account for operators costs. This paper introduces a new approach to compute cost-based heuristics using planning graphs in order to overcome some problems of the existing heuristics, together with a common way of characterizing heuristics based on planning graphs. We explore the heuristics behaviour in combination to two search algorithms. Results show that in some domains the new heuristics are adequate to obtain good quality plans without imposing significant overheads in running time.