Bäckström, C. (1994). Executing Parallel Plans Faster by Adding Actions. Technical Report LiTH-IDA-R-94-22, Department of Computer and Information Science, Linköping University, Sweden. This paper will appear in the proceedings of the 11th European Conference on Artificial Intelligence, Amsterdam, Netherlands, August 1994. Wiley. (bibtex),
Abstract: 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.
CS Dept TR Overview