Useless Actions are Useful

Martin Wehrle, Sebastian Kupferschmid, Andreas Podelski

Planning as heuristic search is a powerful approach to solving domain independent planning problems. In recent years, various successful heuristics and planners like FF, LPG, Fast Downward or SGPlan have been proposed in this context. However, as heuristics only estimate the distance to goal states, a general problem of heuristic search is the existence 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 support 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.

Subjects: 1.11 Planning; 15.7 Search

Submitted: Jun 27, 2008


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.