Complexity Results for Blocks-World Planning

Abstract

Although blocks-world planning is well-known, its complexity has not previously been analyzed, and different planning researchers have expressed conflicting opinions about its difficulty. In this paper, we present the following results: 1. Finding optimal plans in a well-known formulation of the blocks-world planning domain is NP-hard, even if the goal state is completely specified. 2. Classical examples of deleted-condition interactions such as Sussman's anomaly and creative destruction are not difficult to handle in this domain, provided that the right planning algorithm is used. Instead, the NP-hardness of the problem results from difficulties in determining which of several different actions will best help to achieve multiple goals. Introduction Various versions of blocks-world planning have been widely investigated, primarily because they appear to capture several of the relevant difficulties posed to planning systems. The following version, which we call the Elementary Blocks W...