Width-based Algorithms for Classical Planning: New Results

Abstract. We have recently shown that classical planning problems can be characterized in terms of a width measure that is bounded and small for most planning benchmark domains when goals are re-stricted to single atoms. Two simple algorithms have been devised for exploiting this structure: Iterated Width (IW) for achieving atomic goals, that runs in time exponential in the problem width by per-forming a sequence of pruned breadth first searches, and Serialized IW (SIW) that uses IW in a greedy search for achieving conjunctive goals one goal at a time. While SIW does not use heuristic estimators of any sort, it manages to solve more problems than a Greedy BFS using a heuristic like hadd. Yet, it does not approach the performance of more recent planners like LAMA. In this short paper, we intro-duce two simple extension to IW and SIW that narrow the perfor-mance gap with state-of-the-art planners. The first involves changing the greedy search for achieving the goals one at a time, by a depth-first search that is able to backtrack. The second involves computing a relaxed plan once before going to the next subgoal for making the pruning in the breadth-first procedure less agressive, while keeping IW exponential in the width parameter. The empirical results are in-teresting as they follow from ideas that are very different from those used in current planners.