Linear Time Near-Optimal Planning in the Blocks World

Abstract

This paper reports an analysis of near-optimal Blocks World planning. Various methods are clarified, and their time complexity is shown to be linear in the number of blocks, which improves their known complexity bounds. The speed of the implemented programs (ten thousand blocks are handled in a second) enables us to make empirical observations on large problems. These suggest that the above methods have very close average performance ratios, and yield a rough upper bound on those ratios well below the worst case of 2. Further, they lead to the conjecture that in the limit the simplest linear time algorithm could be just as good on average as the optimal one. Motivation The Blocks World (bw) is an artificial planning domain, of little practical interest. Nonetheless, we see at least two reasons for examining it in more detail. In the first place, for good or ill, bw is by far the most extensively used example in the planning literature. It often serves for demonstrating t...