IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Tue, 21 Apr 2015 05:00:36

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.

Goto (at Linköping University): CS Dept TR Overview