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成为人们感兴趣的基准有一个历史原因和两个实际原因。
历史上的一个例子是，Blocks World被用来说明所谓的Sussman's Anomaly。它不再具有任何科学相关性，但它被用来说明规划算法的局限性和挑战，这些算法将规划问题视为直接在规划空间中搜索的问题。链接指向下一本书的一章，这是对自动规划的一个很好的介绍
自动化规划和行动Malik Ghallab，Dana Nau，Paolo Traverso
剑桥大学出版社
过去的情况是这样的，尤其是在20世纪90年代中期，当SAT求解真正兴起时，这是一个例子，说明了当时自动化规划的技术水平是多么有限。
正如你在问题中所写的，求解"块世界"很容易：你绘制的算法是众所周知的，而且显然是多项式时间的。然而，找到一个最佳计划并不容易。我推荐你看这本优秀的书
理解规划任务：领域复杂性和启发式分解
Malte Helmert
Springer，2006
或者他的较短的经典纸张
规划中标准基准域的复杂性结果马尔特·赫尔默特人工智能，2003
Blocks World相关性的第二个"实际"原因是，即使是一个"简单"的问题，它也可以击败规划启发式和对其他计算框架(如SAT或SMT(的复杂算法或汇编。
例如，直到最近(2012年(，Jussi Rintanen在对标准SAT求解器进行了大量修改后，才在"简单"基准上表现出良好的性能
可满足性规划：启发式
Jussi Rintanen
人工智能，2012
通过将启发式算法编译为单元传播、子句学习和变量选择启发式算法相结合的子句，可以快速获得演绎下界。
编辑：已要求进一步详细说明上述针对不易区块的最佳规划。从提供的参考文献来看，本文
关于区块世界规划的复杂性
Naresh Gupta和Dana S.Nau
人工智能，1992
具有原始证明，将计算块世界的最优计划问题简化为HITTING-SET(卡普NP难题之一(。
是一种更容易访问的纸张，它在区块世界领域的规划中看起来相当深入
区块世界重访
John Slaney，Sylvie Thiébaux
人工智能，2001
上面论文中的图1显示了一个例子，说明了Gupta和Nau的复杂性证明背后的直觉。
我觉得很有趣的另一篇与区块链相关的论文是HowGood is Almost Perfect(AAAI 2008(。
它表明，即使使用几乎完美的启发式(对于每种可能的状态，只有一个常数是错误的启发式(，a*搜索也必然会产生指数级大的搜索空间。(这表明，即使有关于目标距离的几乎完美的信息，搜索仍然会在该领域的搜索空间中丢失。(