自动规划：是什么让 "blocksworld" 成为一个不平凡的问题？
Automated planning: what makes "blocksworld" a non trivial problem?
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.
有人可以解释一下是什么让这个问题变得如此重要吗？我想不出一个解决方案不是微不足道的问题实例（例如，一次一个方块地自下而上建造所需的塔）。
Blocks World 成为受关注的基准有一个历史原因和两个实际原因。
历史上的一个是用积木世界来说明所谓的Sussman's Anomaly. It has no longer any scientific relevance, but it was used to illustrate the limitations and challenges of planning algorithms that approach the problem of planning as that of searching through the space of plans directly。 link 指向以下书籍的一章，这是对自动化计划的一个很好的介绍
自动规划和执行
Malik Ghallab、Dana Nau、Paolo Traverso
剑桥大学出版社
曾经是这种情况，尤其是在 1990 年代中期，当 SAT 解决真正起飞时，这是一个例子，说明当时自动化规划的技术水平是多么有限。
正如您在问题中所写，解决 Blocks World 很容易：您绘制的算法是众所周知的，并且显然是多项式时间。然而，找到一个最佳 计划并不容易。我推荐你看这本好书
了解规划任务：领域复杂性和启发式分解
马尔特赫尔默特
施普林格，2006
或他较短的经典论文
Complexity results for standard benchmark domains in planning
马尔特赫尔默特
人工智能, 2003
Blocks World 相关性的第二个 "practical" 原因是，即使是 "simple" 问题，它也可以击败规划启发式算法和精心设计的算法或编译其他计算框架，例如 SAT 或贴片机。
例如，直到最近（2012 年）Jussi Rintanen 在大量修改标准 SAT 求解器后才在 "simple" 基准测试中表现出良好的性能
Planning as satisfiability: Heuristics
尤西·林塔宁
人工智能，2012
通过将启发式作为子句编译到其中，单元传播、子句学习和变量选择启发式的组合可以利用来快速获得演绎下界。
编辑：已请求有关上述块优化规划不容易的评论的更多详细信息。从提供的参考资料来看，本文
On the complexity of blocks-world planning
Naresh Gupta 和 Dana S. Nau
人工智能，1992
有原始证明，将计算 Blocks World 的最优计划的问题减少到 HITTING-SET（卡普的 NP-hard 问题之一）。
一篇更容易获取的论文，它看起来对 Blocks World 领域的规划很深入
重访积木世界
约翰·斯莱尼、西尔维·蒂博
人工智能，2001
Figure 1 in the paper above 显示了一个实例示例，说明了 Gupta 和 Nau 的复杂性证明背后的直觉。
另一篇我发现非常有趣的 Blocksworld 相关论文是 Helmert 和 Röger 的 Good is Almost Perfect? (AAAI 2008)。
它表明，即使使用近乎完美的启发式（一种启发式，对于每个可能的状态，只有一个常数是错误的）A* 搜索也必然会产生指数级的大搜索 space。 （这表明即使有关于目标距离的近乎完美的信息，搜索仍然会在搜索space这个域中丢失。）
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.
有人可以解释一下是什么让这个问题变得如此重要吗？我想不出一个解决方案不是微不足道的问题实例（例如，一次一个方块地自下而上建造所需的塔）。
Blocks World 成为受关注的基准有一个历史原因和两个实际原因。
历史上的一个是用积木世界来说明所谓的Sussman's Anomaly. It has no longer any scientific relevance, but it was used to illustrate the limitations and challenges of planning algorithms that approach the problem of planning as that of searching through the space of plans directly。 link 指向以下书籍的一章，这是对自动化计划的一个很好的介绍
自动规划和执行
Malik Ghallab、Dana Nau、Paolo Traverso
剑桥大学出版社
曾经是这种情况，尤其是在 1990 年代中期，当 SAT 解决真正起飞时，这是一个例子，说明当时自动化规划的技术水平是多么有限。
正如您在问题中所写，解决 Blocks World 很容易：您绘制的算法是众所周知的，并且显然是多项式时间。然而，找到一个最佳 计划并不容易。我推荐你看这本好书
了解规划任务：领域复杂性和启发式分解
马尔特赫尔默特
施普林格，2006
或他较短的经典论文
Complexity results for standard benchmark domains in planning 马尔特赫尔默特 人工智能, 2003
Blocks World 相关性的第二个 "practical" 原因是，即使是 "simple" 问题，它也可以击败规划启发式算法和精心设计的算法或编译其他计算框架，例如 SAT 或贴片机。
例如，直到最近（2012 年）Jussi Rintanen 在大量修改标准 SAT 求解器后才在 "simple" 基准测试中表现出良好的性能
Planning as satisfiability: Heuristics
尤西·林塔宁
人工智能，2012
通过将启发式作为子句编译到其中，单元传播、子句学习和变量选择启发式的组合可以利用来快速获得演绎下界。
编辑：已请求有关上述块优化规划不容易的评论的更多详细信息。从提供的参考资料来看，本文
On the complexity of blocks-world planning
Naresh Gupta 和 Dana S. Nau
人工智能，1992
有原始证明，将计算 Blocks World 的最优计划的问题减少到 HITTING-SET（卡普的 NP-hard 问题之一）。
一篇更容易获取的论文，它看起来对 Blocks World 领域的规划很深入
重访积木世界
约翰·斯莱尼、西尔维·蒂博
人工智能，2001
Figure 1 in the paper above 显示了一个实例示例，说明了 Gupta 和 Nau 的复杂性证明背后的直觉。
另一篇我发现非常有趣的 Blocksworld 相关论文是 Helmert 和 Röger 的 Good is Almost Perfect? (AAAI 2008)。
它表明，即使使用近乎完美的启发式（一种启发式，对于每个可能的状态，只有一个常数是错误的）A* 搜索也必然会产生指数级的大搜索 space。 （这表明即使有关于目标距离的近乎完美的信息，搜索仍然会在搜索space这个域中丢失。）