planning - 自动化规划: what makes "blocksworld" a non trivial problem?

Question

Blocksworld显然是自动化规划中的基准领域。

This domain consists of a set of blocks, a table and a robot hand.
The blocks can be on top of other blocks or on the table;
a block that has nothing on it is clear;
and the robot hand can hold one block or be empty.
The goal is to find a plan to move from one configuration of blocks to another.

有人可以解释一下是什么让这个问题变得不平凡吗？我想不出解决方案并非微不足道的问题实例(例如，一次自下而上地构建所需的塔楼)。

Answer 1

Blocks World 成为人们感兴趣的基准有一个历史原因和两个实际原因。

历史上是用Blocks World来说明所谓的Sussman's Anomaly 。它不再具有任何科学相关性，但它被用来说明规划算法的局限性和挑战，这些算法通过搜索 space of plans directly 来解决规划问题。 。该链接指向以下书籍的一个章节，该章节很好地介绍了自动化规划

自动规划和执行马利克·加拉布、达纳·瑙、保罗·特拉维索
剑桥大学出版社

过去的情况就是这样，尤其是在 20 世纪 90 年代中期，当 SAT 解决方案真正起飞时，它是当时自动化规划技术水平有多么有限的一个例子。

正如您在问题中所写的那样，解决 Blocks World 很容易:您所描绘的算法是众所周知的，并且显然是在多项式时间内完成的。然而，找到最佳计划并不容易。我向您推荐这本优秀的书

了解规划任务:领域复杂性和启发式分解
马尔特·赫尔默特
施普林格，2006 年

或者他的较短的经典论文

Complexity results for standard benchmark domains in planning马尔特·赫尔默特人工智能，2003

Blocks World 相关性的第二个“实际”原因是，即使是一个“简单”问题，它也可以击败规划启发法和复杂的算法或对其他计算框架(例如 SAT 或 SMT)的编译。

例如，直到最近(2012 年)，Jussi Rintanen 在对标准 SAT 求解器进行了大量修改后，才在“简单”基准测试中表现出了良好的性能

Planning as satisfiability: Heuristics
尤西·林塔宁
人工智能，2012

通过将启发式编译为子句，单元传播、子句学习和变量选择启发式的组合可以利用来快速获得演绎下界。

编辑:已要求提供有关上述街区最佳规划并不容易的评论的更多详细信息。根据提供的引用文献，本文

On the complexity of blocks-world planning
纳雷什·古普塔和达纳·S·瑙
人工智能，1992

拥有原始证明，将 Blocks World 的最优计划计算问题简化为 HITTING-SET(卡普的 NP 难问题之一)。

一篇更容易访问的论文，它对 Blocks World 领域的规划进行了相当深入的研究

重温积木世界
约翰·斯莱尼、西尔维·蒂埃博
人工智能，2001

Figure 1 in the paper above显示了一个实例示例，说明了 Gupta 和 Nau 复杂性证明背后的直觉。