12.2 分层任务网络规划
处理复杂度的一个最普遍的想法是分层分解。复杂软件从子程序或对象类的层次体系创建出来，军队作为单位的等级体系而运转，政府和企业有部门、子部门和分支办公室的分层体系。层次结构的关键好处是，在层次的每一层上，一个计算任务、军事任务或管理功能都被还原为下一个较低层次的少量行动，所以对当前问题寻找正确的方法来安排这些行动的计算消耗是小的。在另一方面，非层次方法将一个任务还原为大量单个行动；对大规模问题，这是完全不切实际的。在最好情况下——当高层的解总有令人满意的低层实现时——分层方法能够产生线性时间而不是指数时间的规划算法。
本节描述基于分层任务网络或缩写为HTN的规划方法。这个方法将来自偏序规划的思想（第11.3节）和众所周知的“HTN规划”领域的思想结合在一起。在HTN规划中，用来描述问题的初始规划被视为对需要做什么的非常高层的描述——例如，建造一幢房屋。通过应用行动分解来改进规划。每个行动分解将一个高层行动还原为一个低层行动的偏序集。因此，行动分解包含了关于如何实现行动的知识。例如，建造一幢房屋可以还原为获得一张许可证、雇佣一名承包人、进行建筑、付钱给承包人。（图12.5显示了这样的一个分解。）过程继续进行直到规划中只剩下原始行动。典型地，原始行动是那些智能体能够自动执行的行动。对一名一般的承包人而言，“安置景观美化”可能是原始的，因为它只涉及叫来景观美化承包人。对于景观美化承包人，诸如“在这里种植杜鹃花”这样的行动可能被认为是原始的。
在“纯”HTN 规划中，规划只由相继的行动分解产生。因此，HTN 将规划视为使行动描述更具体化的过程，而不是（如同状态空间和偏序规划中的情况那样）一个从空行动开始构建行动描述的过程。这表明每个STRIPS行动描述都能够被转变成一个行动分解（参见习题12.6），且偏序规划可以被看成纯HTN规划的一种特殊情况。然而对于特定任务——尤其是“新颖”的合取式目标——纯HTN规划的视点相当不自然，这样我们更喜欢用混合方法，除了建立开放条件和通过添加定序约束解决冲突的标准操作外，行动分解被用作偏序规划中的规划改进。（将HTN规划看作偏序规划的扩展具有额外的优点，我们可以使用相同的符号约定而不是引入一个全新的集合。）我们从更详细地描述行动分解开始。然后我们解释必须如何修改偏序规划算法以处理分解，最后我们讨论完备性、复杂度和实用性的问题。
图12.5 对BuildHouse行动的一个可能的分解
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
