Complexity Results for Blocks-World Planning

Naresh Gupta, Dana S. Nau

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.