Top-Quality Planning: Finding Practically Useful Sets of Best Plans
Top-Quality Planning: Finding Practically Useful Sets of Best Plans
复制标题
高质量规划：寻找实用的最佳计划集
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
O. Udrea
中科院分区：
文献类型：
--
作者：
Michael Katz;Shirin Sohrabi;O. Udrea
各种规划应用促使人们需要找到一套而不是一套计划。这个问题是在多样性规划和top-k规划的背景下研究的：虽然多样性规划关注的是计划对之间的差异，但top-k规划的重点是每个单独计划的质量。最近在多样化规划方面的工作还引入了对解决方案质量的限制。当然，有些应用领域的多样性发挥了主要作用，有些领域的质量是主要特征。然而，在这两种情况下，计划的制作数量往往是人为的约束，因此实际数字意义不大。受最近多样化规划工作的启发，我们提出了一类新的计算问题，称为最高质量规划，其中解的有效性是通过计划质量界限来定义的，而不是通过计划的任意数量来定义。切换到边界平面质量允许我们隐式表示多组平面。特别是，它使用单个计划表示对应于有效计划重新排序的计划集成为可能。我们形式化地定义了无序最高质量计划计算问题，并给出了该问题的第一个计划器。我们的经验证明，与基于top-k计划员的基准相比，我们的方法具有卓越的性能，从查找所有最优计划的覆盖率提高41%到寻找所有质量计划的覆盖率提高69%，最高可达最优计划成本的120%。最后，通过生成给定计划的所有有效重新排序的完整过程来补充新方法，我们得到了一个最高质量的计划器。我们展示了计划者与基于TOP-K计划者的基线相比具有竞争力。
The need for finding a set of plans rather than one has been motivated by a variety of planning applications. The problem is studied in the context of both diverse and top-k planning: while diverse planning focuses on the difference between pairs of plans, the focus of top-k planning is on the quality of each individual plan. Recent work in diverse planning introduced additionally restrictions on solution quality. Naturally, there are application domains where diversity plays the major role and domains where quality is the predominant feature. In both cases, however, the amount of produced plans is often an artificial constraint, and therefore the actual number has little meaning. Inspired by the recent work in diverse planning, we propose a new family of computational problems called top-quality planning, where solution validity is defined through plan quality bound rather than an arbitrary number of plans. Switching to bounding plan quality allows us to implicitly represent sets of plans. In particular, it makes it possible to represent sets of plans that correspond to valid plan reorderings with a single plan. We formally define the unordered top-quality planning computational problem and present the first planner for that problem. We empirically demonstrate the superior performance of our approach compared to a top-k planner-based baseline, ranging from 41% increase in coverage for finding all optimal plans to 69% increase in coverage for finding all plans of quality up to 120% of optimal plan cost. Finally, complementing the new approach by a complete procedure for generating all valid reorderings of a given plan, we derive a top-quality planner. We show the planner to be competitive with a top-k planner based baseline.