some what more expressive languages (Gazen & Knoblock, 1997; Kohler, Nebel, Hoffman,
& Dimopoulos, 1997).

Knoblock (1994) has modified the UCPOP planner with a resource concept whi makes it avoid unordered interacting actions. This means that the resulting planner produces definite parallel plans. Knoblock further modified the evaluation heuristic of the search to take parallel execution time into account. It thus seems as if this planner might be able to produce minimum reordered parallel plans, but the paper does not provide sufficient details to determine whether this is the case. It is also unclear whether the heuristic can handle actions with different duration times.

Yet another example is the polynomial-time planner for the SAS+-IAO planning language (Jonsson & Backstrom, 1998) which produces plans which are minimum-constrained reordered. That is, for this restricted formalism it is clearly possible to optimise the ordering in polynomial time.

## 9. Discussion

The previous section listed a few planning algorithms from the literature that produce or attempt to produce plans which are least constrained or minimum parallel reordered.  They do so only under certain restrictions, though. Furthermore, plans are not always generated 'from scratch', but can also be generated by modifying some already existing plan, referred to as case-based planning, or by repairing a plan that has failed during the execution phase.

In such cases, the old plan may contain many ordering relations that will be obsolete in the modified/repaired plan. In fact, the KK algorithm (Kambhampati & Kedar, 1994) is motivated in the context of case-based planning. It is also important to remember that today, and probably for a long time into the future, very few plans are generated entirely by computer programs. The vast majority of plans in various applications are designed by humans, possibly with computer support. Already for quite small plans, it is very difficult for a human to see whether the ordering constraints are optimal or not, so computer support for such analyses is vital for designing optimal plans. For the same reason, also hierarchicaltask-network planners, eg O- Plan (Currie & Tate, 1991) and SIPE (Wilkins, 1988), produce plans where reordering actions could lead to better schedules.  Such a planner often commits to one of the two possible orderings for a pair of actions based on expert-knowledge rules.

However, it is hardly possible for a human expert to design rules that in all situations will guarantee that the optimal ordering choice is made.

On the coarseness level of complexity analysis it does not matter whether the tasks of planning, plan optimization and scheduling are integrated or separated since the total resulting complexity will be the same in both cases the latter two computations are at most NP-complete and will, thus, be dominated by the planning, which is PSPACE-complete or worse.  However, for good reasons this has not prevented the research community from studying planning and scheduling as separate problems, since understanding each problem in isolation also helps understanding the overall process.  For the same reason, it is important to also study separately the problems discussed and analysed in this article. Furthermore, on a more fine-grained, practical level there might be considerable differences in efficiency between integrating the three computations and doing them separately. For instance, even if all three computations take exponential time, each of the problems considered in isolation