On the Complexity of Blocks-World Planning
On the Complexity of Blocks-World Planning
复制标题
DOI：
10.1016/0004-3702(92)90028-v
复制
发表时间：
1992-08
期刊：
影响因子：
--
通讯作者：
N. Gupta;Dana S. Nau
中科院分区：
文献类型：
--
作者：
N. Gupta;Dana S. Nau
在本文中，我们证明了在最著名的块世界版本（以及几个相关版本）中，规划是困难的，从某种意义上说，找到最优计划是np困难的。然而，np硬度不是由于删除条件的相互作用，而是由于我们称之为死锁的情况。对于不包含死锁的问题，有一个简单的爬坡策略，可以很容易地找到最优计划，而不管问题是否包含任何已删除条件交互。上述结果相当令人惊讶，因为在规划文献中，街区世界的主要作用之一是提供删除条件相互作用的例子，如创造性破坏和萨斯曼异常。然而，我们可以用独立于域的目标交互来解释死锁难以处理的原因，我们称之为启用条件交互，在这种交互中，为实现一个目标而调用的操作具有使实现其他目标更容易的副作用。如果不同的行动有不同的有用的副作用，那么很难确定哪一组行动将产生最佳计划。
In this paper, we show that in the best-known version of the blocks world (and several related versions), planning is difficult, in the sense that finding an optimal plan is NP-hard. However, the NP-hardness is not due to deleted-condition interactions, but instead due to a situation which we call a deadlock. For problems that do not contain deadlocks, there is a simple hill-climbing strategy that can easily find an optimal plan, regardless of whether or not the problem contains any deleted-condition interactions.The above result is rather surprising, since one of the primary roles of the blocks world in the planning literature has been to provide examples of deleted-condition interactions such as creative destruction and Sussman's anomaly. However, we can explain why deadlocks are hard to handle in terms of a domain-independent goal interaction which we call an enabling-condition interaction, in which an action invoked to achieve one goal has a side-effect of making it easier to achieve other goals. If different actions have different useful side-effects, then it can be difficult to determine which set of actions will produce the best plan.