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

## IDA Technical Reports: abstract

*Generated: Thu, 02 Apr 2015 02:10:47 *

Bäckström, C. (1994).
** Finding Least
Constrained Plans and Optimal Parallel Executions is Harder than we
thought**.
Technical Report LiTH-IDA-R-94-20, Department of Computer and Information
Science, Linköping University, Sweden.
This paper is published in C. Bäckströ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.
(bibtex),

**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.

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

*<webmaster@ida.liu.se>*