On the Complexity of Blocks-World Planning

Abstract

In this paper, we show that blocks-world planning is difficult, in the sense that finding an optimal plan is NP-hard. This is true regardless of whether or not, the goal state is completely specified, and regardless of whether or not different blocks have different sizes. However, the difficulty of blocks-world planning is not due to deleted-condition interactions, but instead due to another kind of goal interaction, which we call a deadlock. For problems that do not contain deadlocks, there is a simple hill- climbing strategy that can easily find an optimal plan, regardless of whether or not the problem contains any deleted- condition interactions.<P>The fact that deleted-condition interactions are easy and deadlocks are difficult is rather surprising, for one of the primary roles of the blocks world in the planning literature has been to provide examples of deleted- condition interactions such as creative destruction and Sussman's anomaly. This suggests that a good topic for future research might be to investigate how easily such interactions can be handled in other planning domains.