Computer Science – Artificial Intelligence
Scientific paper
2011-05-27
Journal Of Artificial Intelligence Research, Volume 9, pages 99-137, 1998
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.477
This article studies the problem of modifying the action ordering of a plan in order to optimise the plan according to various criteria. One of these criteria is to make a plan less constrained and the other is to minimize its parallel execution time. Three candidate definitions are proposed for the first of these criteria, constituting a sequence of increasing optimality guarantees. Two of these are based on deordering plans, which means that ordering relations may only be removed, not added, while the third one uses reordering, where arbitrary modifications to the ordering are allowed. It is shown that only the weakest one of the three criteria is tractable to achieve, the other two being NP-hard and even difficult to approximate. Similarly, optimising the parallel execution time of a plan is studied both for deordering and reordering of plans. In the general case, both of these computations are NP-hard. However, it is shown that optimal deorderings can be computed in polynomial time for a class of planning languages based on the notions of producers, consumers and threats, which includes most of the commonly used planning languages. Computing optimal reorderings can potentially lead to even faster parallel executions, but this problem remains NP-hard and difficult to approximate even under quite severe restrictions.
No associations
LandOfFree
Computational Aspects of Reordering Plans does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computational Aspects of Reordering Plans, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Aspects of Reordering Plans will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664313