Executing parallel plans faster by adding actions
Christer Bäckström · 1994
. If considering only sequential execution of plans, the execution time of a plan will increase if adding actions to it. However, if also considering parallel execution of plans, then the addition of actions to a plan may sometimes decrease the execution time. It is further shown that plans which are sub-optimal in this way are likely to be frequently generated by standard partial-order planners. Unfortunately, optimizing the execution time of a plan by adding actions is NP-hard and cannot even be approximated within a constant ratio. 1 INTRODUCTION In many applications where plans, made by man or by computer, are executed, it is important to find plans that are optimal with respect to some cost measure, typically execution time. Examples of such applications are manufacturing and error-recovery for industrial processes. Many different kinds of computations can be made to improve the cost of a plan--- only a few of which have been extensively studied in the literature. The most well-k...