planning - 自动规划：是什么让“blocksworld”成为一个不平凡的问题？

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.

有人可以解释是什么让这成为一个不简单的问题吗？我想不出解决方案不是微不足道的问题实例（例如，一次自下而上地建造所需的塔）。

标签： planning

Answer 1

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

历史上的一个是Blocks World被用来说明所谓的Sussman's Anomaly。它不再具有任何科学相关性，但它被用来说明将规划问题视为直接在规划空间中搜索的规划算法的局限性和挑战。链接指向下一本书的一章，这是对自动化计划的一个很好的介绍

自动规划和执行 Malik Ghallab、Dana Nau、Paolo Traverso
剑桥大学出版社

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

正如您在问题中所写，解决 Blocks World 很容易：您绘制的算法是众所周知的，并且显然是多项式时间。然而，找到一个最佳计划并不容易。我推荐你看这本优秀的书

了解规划任务：领域复杂性和启发式分解
Malte Helmert
Springer，2006

或者他更短的经典论文

Malte Helmert 人工智能规划中标准基准域的复杂性结果，2003 年

Blocks World 相关性的第二个“实际”原因是，即使是一个“简单”的问题，它也可以击败规划启发式算法并精心设计算法或编译到其他计算框架，如 SAT 或 SMT。

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

规划为可满足性：启发式
Jussi Rintanen
人工智能，2012

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

编辑：已要求提供有关上述块不容易的最佳规划的评论的更多详细信息。根据提供的参考资料，本文

关于块世界规划的复杂性
Naresh Gupta 和 Dana S. Nau
人工智能，1992

有原始证明，将计算 Blocks World 的最优计划的问题简化为 HITTING-SET（Karp 的 NP-hard 问题之一）。

一篇更容易访问的论文，它看起来对 Blocks World 领域的规划非常深入，是

Blocks World 重访
John Slaney，Sylvie Thiébaux
人工智能，2001

上述论文中的图 1显示了一个实例，说明了 Gupta 和 Nau 的复杂性证明背后的直觉。