Parametrized Families of Hard Planning Problems from Phase Transitions
Parametrized Families of Hard Planning Problems from Phase Transitions
复制标题
相变硬规划问题的参数化系列
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
J. Frank
中科院分区：
文献类型：
--
作者：
E. Rieffel;D. Venturelli;M. Do;I. Hen;J. Frank
有两种互补的方法来评估规划算法：性能的基准问题来自真实的应用程序和性能分析的参数化家庭的问题与已知的属性。在此之前的工作，很少有手段生成参数化家庭的硬规划问题是已知的。我们生成硬规划问题的可解/不可解的相变区域的充分研究的NP-完全问题，自然映射到导航和调度，方面共同的许多规划领域。我们观察到国家的最先进的规划师对这些问题的家庭之间的显着差异，使我们能够深入了解这些规划师的相对优势和劣势。我们的研究结果证实了指数尺度的硬度与问题的大小，即使在非常小的问题大小。这些系列提供了互补的测试集，展示了现有基准中没有的属性。
There are two complementary ways to evaluate planning algorithms: performance on benchmark problems derived from real applications and analysis of performance on parametrized families of problems with known properties. Prior to this work, few means of generating parametrized families of hard planning problems were known. We generate hard planning problems from the solvable/unsolvable phase transition region of well-studied NP-complete problems that map naturally to navigation and scheduling, aspects common to many planning domains. We observe significant differences between state-of-the-art planners on these problem families, enabling us to gain insight into the relative strengths and weaknesses of these planners. Our results confirm exponential scaling of hardness with problem size, even at very small problem sizes. These families provide complementary test sets exhibiting properties not found in existing benchmarks.