Bäckström, C. (1992). Planning with Partical States in O(n2) Time: The SAS+-PUS Planning Problem. Technical Report LiTH-IDA-R-92-05, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: We generalize the previously presented, tractable SAS-PUS planning problem to the SAS+-PUS planning problem. This generalization allows partial initial and goal states as well as actions changing a state variable from the undefined value to some defined value. We also present a sound and complete algorithm for finding minimal, maximally parallel plans for instances of the SAS+-PUS planning problem. Although the algorithm solves a more general problem it---somewhat surprisingly---improves over the earlier algorithms by running in O(n2) time in the worst case.
CS Dept TR Overview