@techreport{R-92-05,
TITLE = {Planning with Partical States in O(n2) Time: The SAS+-PUS Planning Problem},
AUTHOR = {Christer B{\"a}ckstr{\"o}m},
YEAR = {1992},
NUMBER = {R-92-05},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-92-05+abstr},
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.},
IDANR = {LiTH-IDA-R-92-05}