Planning with Abstraction Hierarchies Can Be Exponentially Less Efficient

Abstract

It is well-known that state abstraction can speed up planning exponentially, under ideal conditions. We extend this finding---showing that state abstraction may likewise slow down planning exponentially, and even result in generating an exponentially longer solution than necessary. This phenomenon can occur for abstraction hierarchies which are generated automatically by the Alpine and Highpoint algorithms. We further show that there is little hope of any drastic improvement upon these algorithms---it is computationally difficult to generate abstraction hierarchies which allow finding good approximations of optimal plans. 113 1 Introduction One common approach to improving the efficiency of planning is to use a hierarchical planner based on state abstraction---ignoring certain literals, either in the operator preconditions [ Sacerdoti, 1974 ] or in the whole language [ Knoblock, 1991, 1994 ] . First an abstracted version of the problem instance is solved, thus not taking all details ...