@techreport{R-94-20,
PSURL = {/publications/cgi-bin/tr-fetch.pl?r-94-20+ps},
TITLE = {Finding Least Constrained Plans and Optimal Parallel Executions is Harder than we thought},
AUTHOR = {Chruster B{\"a}ckstr{\"o}m},
YEAR = {1994},
NUMBER = {R-94-20},
INSTITUTION = ida,
ADDRESS = idaaddr,
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-94-20+abstr},
ABSTRACT = {It seems to have been generally assumed in the planning community that it is easy to compute a least-constrained partially ordered version of a total-order plan. However, it is not clear what this concept means. Five candidates for this criterion are defined in this paper, and it turns out that the only ones giving some reasonable optimality guarantee are NP-hard to compute. A related problem is to find a shortest parallel execution of a plan, also proven NP-hard. Algorithms can be found in the literature which are claimed to solve these problems optimally in polynomial time. However, according to the NP-hardness of the problems, this is impossible unless P=NP, and it is explained in this paper why the algorithms fail. The algorithms are, instead, reconsidered as approximation algorithms, but it is shown that neither algorithm gives any constant performance guarantee. This is not surprising, however, since both problems turn out not to be approximable within a constant ratio.},
IDANR = {LiTH-IDA-R-94-20},
NOTE = {This paper is published in C. B{\"a}ckstr{\"o}m and E. Sandewall (eds.), Current Trends in AI Planning: EWSP'93---2nd European Workshop on Planning, Vadstena, Sweden, Dec. 1993. IOS Press. It will also be presented at the workshop on Algorithms, Complexit and Commonsense Reasoning at the 11th European Conference on Artificial Intelligence, Amsterdam, Netherlands, Aug. 1994}