Pruning methods for optimal delete-free planning using domination-free reachability Academic Article uri icon


  • Delete-free planning (DFPlan) underlies many popular relaxation (h+) based heuristics used in state-of-the-art planners, and a number of recent planning domains are naturally deletefree. This has led to increased interest in efficient methods for cost-optimal DFPlan. To aid in the solution of DF-Plan problems, we introduce a new analysis technique, called domination-free reachability (DFR). DFR is an improved version of the well known notion of reachability in graphs that filters out nodes that are not useful for optimal planning. We explain how to compute DFR, and present three new pruning techniques that use it. Combined with a recent decomposition technique these pruning methods lead to effective pruning in delete-free planning.

publication date

  • January 1, 2013