Tunneling and decomposition-based state reduction for optimal planning Conference Paper uri icon

abstract

  • Action pruning is one of the most basic techniques for improving a planner's performance. The challenge of preserving optimality while reducing the state space has been addressed by several methods in recent years. In this paper we describe two optimality preserving pruning methods: The first is a generalization of tunnel macros. The second, the main contribution of this paper, is a novel partition-based pruning method. The latter requires the introduction of new automated domain decomposition techniques which are of independent interest. Both methods prune the actions applicable at state s based on the last action leading to s, and both attempt to capture the intuition that, when possible, we should focus on one subgoal at a time. As we demonstrate, neither method dominates the other, and a combination of both allows us to obtain an even stronger pruning rule. We also introduce …

publication date

  • January 1, 2012