Block-Structured Plan Deordering
Block-Structured Plan Deordering
复制标题
块结构计划解序
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
P. Haslum
中科院分区：
文献类型：
--
作者：
Fazlul Hasan Siddiqui;P. Haslum
部分排序的计划有几个有用的属性，例如更清楚地展示计划的结构，这有助于计划生成后的任务，如计划调度，向用户解释，或将其分解为子计划以进行分布式执行。偏序的标准解释意味着，只要两个子计划是无序的，两个子计划中的每个步骤的交错都会形成一个有效的执行。这将去序限制到单个步骤（即，行动）是独立的。我们提出了一个较弱的偏序概念，将计划划分为块，这样块中的步骤可能不会与块外的步骤交织，但无序块可以以任何顺序执行。我们提出了一个算法来找到这样的可无序块，并表明，它使无序计划在许多情况下，没有无序是可能的标准解释。
Partially ordered plans have several useful properties, such as exhibiting the structure of the plan more clearly which facilitates post-plan generation tasks like scheduling the plan, explaining it to a user, or breaking it into subplans for distributed execution. The standard interpretation of partial ordering implies that whenever two subplans are unordered, every interleaving of steps from the two forms a valid execution. This restricts deordering to cases where individual steps (i.e., actions) are independent. We propose a weaker notion of partial ordering that divides the plan into blocks, such that the steps in a block may not be interleaved with steps outside the block, but unordered blocks can be executed in any sequence. We present an algorithm to find such deorderable blocks, and show that it enables deordering plans in many cases where no deordering is possible under the standard interpretation.