分层任务网络规划

分层任务网络（HTN）规划通过使用方法库将高级任务递归分解为子任务来解决问题，而不是直接搜索原始动作以达到目标状态。

Definition

HTN规划将问题表示为待执行任务的初始网络和一组用于将复合任务分解为子任务的方法；解决方案是分解为原始的、可执行的动作，并遵循方法的约束。

Scope

本主题涵盖HTN规划范式：任务（原始任务和复合任务）、指定如何将复合任务分解为子任务的方法，以及将初始任务网络细化直至仅剩下可执行的原始动作的规划过程。它探讨了HTN规划相对于经典规划的表达能力和复杂性，以及著名的HTN规划器。经典的、基于目标状态的规划模型在相关主题中有所论述；HTN规划则编码过程性领域知识。

Core questions

• 方法如何编码关于如何完成复合任务的领域知识？
• 任务分解与经典规划中搜索目标状态有何不同？
• 与经典规划相比，HTN规划的表达能力和计算复杂性如何？
• 在分解过程中如何处理子任务之间的排序和前置条件约束？

Key concepts

• 原始任务和复合任务
• 方法和分解
• 任务网络
• 排序约束
• 过程性领域知识
• HTN表达能力
• 有序任务分解
• SHOP2

Key theories

使用方法进行任务分解

HTN规划用递归分解取代了目标导向搜索：复合任务通过方法扩展为子任务网络，直到所有任务都变为原始任务，从而可以直接编码人类关于如何执行任务的专业知识。

HTN规划的表达能力和复杂性

HTN规划比经典的STRIPS规划具有更强的表达能力；在其一般形式中，计划存在性可能是不可判定的，受限形式则属于更高的复杂性类别，这反映了基于方法分解的强大功能。

有序任务分解规划器

诸如SHOP2之类的实用HTN规划器通过按任务执行顺序分解任务来进行规划，这使得它们能够根据完全确定的状态评估前置条件，并有效地整合丰富的领域知识。

Clinical relevance

HTN规划广泛应用于已知并必须遵循专家程序的领域，例如制造过程规划、军事和物流操作、网络服务组合以及游戏和故事生成，因为方法允许领域专家编码完成任务的标准方式。

History

分层规划可追溯到20世纪70年代Sacerdoti的NOAH和抽象层次结构。Erol、Hendler和Nau在20世纪90年代早期形式化了HTN规划并分析了其复杂性，而SHOP和SHOP2规划器（约2000-2003年）使有序HTN规划成为一种实用且广泛使用的技术。

Key figures

• Dana Nau
• Kutluhan Erol
• James Hendler
• Earl D. Sacerdoti
• Austin Tate

Seminal works

• erol1994
• nau2003

Frequently asked questions

HTN规划与经典规划有何不同？

经典规划仅使用动作的前置条件和效果来搜索达到目标状态的任何动作序列。HTN规划则从要完成的任务开始，并使用编码这些任务通常如何按程序完成的方法来分解它们，因此它依赖于更丰富的领域知识。

为什么HTN规划可能是不可判定的？

因为方法可以将复合任务分解为包含进一步复合任务的网络，分解过程可以无限递归，很像语法生成任意长的派生。因此，在其一般形式中，判断是否存在有效分解是不可判定的。