为分解修改规划器

12.2.2 为分解修改规划器

现在我们显示如何修改POP以合并HTN规划。我们通过修改POP后继函数（第11.3节）以允许分解方法被应用到当前的偏序规划P中来完成这项工作。新的后继规划的形成是通过首先选择P中的一些非原始行动a'，然后对于来自规划库的任何满足a和a'可以用置换θ合一的Decompose(a, d)方法，用d ' = SUBSET(θ, d)来替换a'，从而完成的。

图12.7显示了一个例子。在顶部，是得到房子的一个规划P。高层行动a'=BuildHouse被选择进行分解。分解d是从图12.5中挑选的，BuildHouse被这个分解所替换。一个附加的步骤GetLoan（借贷）被引入用来解决新的开放条件，Money，它是被分解步骤创建的。用行动的分解替换行动有点儿像移植外科手术：我们不得不从包装中（Start和Finish步骤）取出新的子规划，插入它，正确地连接每件事物。可能有好几种方法来实现这个。为了更加精确地说明，我们对每个可能的分解d ' 完成如下步骤：

图12.7 在一个已经存在的规划内分解高层行动。BuildHouse行动被来自图12.5的分解替换。外部前提Land由来自BuyLand的已有因果连接提供。外部前提 Money在分解步骤后保持开放，所以我们添加一个新的行动GetLoan

（1）首先，从P中去除行动a'。然后，对分解d ' 中的每个步骤s，我们需要选择一个行动来承担s的责任并把它添加到规划中。它可以是s的一个新的实例化或P中一个与s合一的已有步骤s'。例如，MakeWine（酿葡萄酒）行动的分解可能建议我们BuyLand（购买土地）；很可能，我们可以使用在规划中已经有的同样的BuyLand行动。我们称这为子任务共享。

在图12.7中，没有共享的机会，所以行动的新实例被创建。一旦行动被选择，来自d ' 的所有内部约束都被完全复制——例如，GetPermit 排在 Construction 之前，并且在这两个步骤之间有一个因果连接提供Constrction的Permit前提。这就完成了用dθ的实例化替代a'的任务。

（2）接下来的步骤是建立原始规划中的 a'的定序约束与 d ' 步骤之间的连接。首先，考虑 P中形如Bπa' 的定序约束。B相对于d ' 中的步骤应该如何排序？最明显的解决方法是B应该在d ' 中的每个步骤之前，这可以通过用约束Bπs替换d ' 中每个形如Startπs的约束来获得。另一方面，这个方法可能太严格了！例如，BuyLand 必须在 BuildHouse 之前出现，但是在扩展规划中没有必要让BuyLand在HireBuilder之前出现。强加一个过于严格的排序可能会妨碍找到某些解。因此，最好的解决方法是对每个定序约束记录约束的理由；然后，当一个高层行动被扩展时，新的定序约束可以尽可能地松弛，不过要与原始约束的理由保持一致。当我们替换形如a'πC的约束时，运用同样的考虑。

（3）最后的步骤是为因果连接建立联系。如果B→a'是原始规划中的一个因果连接，对它用一组从B到具有由分解d中Start步骤所提供前提p的d ' 中所有步骤的因果连接进行替换（也就是，从B连接到d '中以p为外部前提的所有步骤）。在这个例子中，因果连接BuyLand→BuildHouse被连接BuyLand→Permit所替换。（在分解中PayBuilder的前提Money变成一个开放前提，因为原始规划中没有行动为BuildHouse提供Money。）类似地，对规划中的每个因果连接a'→C，用一组到C的因果连接来替换它，这些因果连接来自d '中能够为d分解中的Finish步骤提供p的任何一个步骤（也就是，来自d ' 中以p作为外部效果的一个步骤）。在这个例子中，我们用连接PayBuilder→Finish来替换连接BuildHouse→Finish。

这就完成了在POP规划器上下文中产生分解所需的附加步骤。[11]

对POP算法的附加修改是必要的，这是由于高层行动隐藏了关于它们的最终原始实现的信息的事实。特别地，如果当前规划包含了一个不能解决的冲突时——也就是，如果一个行动与一个因果连接冲突，但是又不能排在该连接之前或之后时——原始POP算法因为失败而回溯。（图11.9显示了一个例子。）另一方面，在高层行动上，显然不可解决的冲突有时能够通过分解冲突行动和交叉它们的步骤来解决。图12.8给出了一个例子。因此，可能是这样的状况，即一个完备且一致的原始规划能够通过分解而得到，甚至当不存在完备且一致的高层规划时。这种可能性意味着一个完备的HTN规划器必须放弃标准POP规划器能够获得的许多剪枝机会。作为选择，我们可以按任意种方式剪枝，并希望不会错过解。

图12.8（未完）

图12.8 麦琪的礼物问题，选自欧·亨利的小说，显示了一个不一致但是能被分解为一致解的抽象规划。（a）部分显示了问题：一对贫穷的夫妇只有两样有价值的财产——他有一块金表，而她有一头美丽的长发。每人都计划买一件礼物让对方高兴。他决定卖了他的表为她的头发买一把银梳子，而她决定卖掉她的长发为他的表买一条金表链。（b）中的偏序规划是不一致的，因为无法对“Give Comb”（赠予梳子）和“Give Chain”（赠予表链）抽象步骤进行排序而不产生冲突。（我们假设“Give Comb”行动具有前提Hair（头发），因为如果妻子没有了她的长发，行动就不会产生预期的使她高兴的效果，对于“Give Chain”行动也是类似的。）在（c）中，我们用一个“分期付款规划（installment plan）”方法来分解“Give Comb”步骤。在分解的第一个步骤中，丈夫购得梳子并赠与她的妻子，并同意一天后用交付手表作为偿还。在第二个步骤中，手表被移交，债务被偿清。用相似的方法分解“Give Chain”步骤。只要两个赠与步骤排在交付步骤之前，这个分解就能解决问题。（注意这依赖于问题要如此定义，以使得表链与手表一起使用或梳子与头发一起使用的快乐是可以持续的，即便在财产被交出之后。）