Useless actions are useful
Martin Wehrle, Sebastian Kupferschmid, Andreas Podelski · 2008
Planning as heuristic search is a powerful approach to solving domain independent planning problems. In recent years, var-ious successful heuristics and planners like FF, LPG, FAST DOWNWARD or SGPLAN have been proposed in this con-text. However, as heuristics only estimate the distance to goal states, a general problem of heuristic search is the ex-istence of plateaus in the search space topology which can cause the search process to degenerate. Additional techniques like helpful actions or preferred operators that evaluate the “usefulness ” of actions are often successful strategies to sup-port the search in such situations. In this paper, we introduce a general method to evaluate the usefulness of actions. We propose a technique to enhance heuristic search by identifying “useless ” actions that are not needed to find optimal plans. In contrast to helpful actions or preferred operators that are specific to the FF and Causal Graph heuristic, respectively, our method can be combined with arbitrary heuristics. We show that this technique often yields significant performance improvements.