分层任务网络（HTN）规划是一种人工智能（AI）规划技术，它突破了以往规划技术的传统。该技术背后的基本思想包括初始状态描述（initial state description），作为要实现的目标的初始任务网络（initial task network），以及由原始和复合任务网络组成的领域知识（domain knowledge）。任务网络表示任务的层次结构。
规划问题在HTN中通过提供一组任务来指定，这些任务可以是：
- 原始任务，大致对应于STRIPS(Stanford Research Institute Problem Solver)的行动;
- 复合任务，可以看作是由一组更简单的任务组成;
- 目标任务，与STRIPS的目标基本一致，但更具一般性。
其中，原始任务是指一个可以直接执行的动作；复合任务是一个复杂的任务，由部分有序的进一步任务组成，它们可以是原始的或抽象的；目标任务是需要满足条件/约束的任务。原始操作和其他任务之间的区别在于原始操作可以直接执行。复合和目标任务则都需要执行一系列原始操作。然而，目标任务是根据必须成立的条件来规定的，而复合任务只能通过下面概述的任务网络来指定其他任务。
任务之间的约束以网络形式表示，称为（分层）任务网络。一个任务网络是其中的一组任务和约束。这样的网络可以作为另一个复合或目标任务可行的前提条件。通过这种方式，人们可以表达只有当一组其他的行为（网络中提到的那些行为）完成时，并且满足它们之间的约束（由网络指定），一个给定的任务才是可行的。
规划过程首先分解初始任务网络，直到所有复合任务都被分解完为止，即通过不断的递归分解找到解决方案。
HTN 规划基本过程:
- 输入规划问题P
- 如果P仅含原始任务（primitive tasks，又称原子任务），那么直接求解该问题返回结果；若求解失败，返回失败
- 选择P中的一个非原始任务t
- 为t求得一个替代t‘
- 用t’代替t
- 消除问题P中该非原子任务和约束条件的冲突
- 返回步骤（2）
【描述来源：维基百科 URL：https://en.wikipedia.org/wiki/Hierarchical_task_network 】
【描述来源：Georgievski, I.; Aiello, M. (2014). An Overview of Hierarchical Task Network Planning. arXiv:1403.7426.】
【描述来源：规划 (AI Planning) 幻灯片: http://staff.ustc.edu.cn/~jianmin/lecture/AI2014/planning_slides.pdf】
以 SHOP（Simple Hierarchical Ordered Planner）系列产品为例，该研究组使用的第一个用于有序任务分解的计划系统是特定于域的，即它们是针对特定应用程序域而量身定制的。其中包括用于集成产品设计和制造计划的EDAPS系统和Bridge Baron，这是一个赢得1997年电脑桥牌世界冠军的桥牌计算机程序，并且是一个非常成功的商业产品。而SHOP则是第一个与有序任务分解的领域无关的实现，SHOP及其后续产品（最新的产品为SHOP2和JSHOP2）可以在许多不同的规划领域工作。在2002年国际规划竞赛中，SHOP2解决了比赛中每个规划领域的问题，而总共有近1000个规划问题，并且SHOP2获得了比赛前四名的奖项之一。目前该研究组在研发的系统是JSHOP2，一个SHOP2的Java实现（用Lisp编写）。
【描述来源：Description of the SHOP Project URL：http://www.cs.umd.edu/projects/shop/description.html】
发展历史
Earl D Sacerdoti于1975年提出的NOAH(Nets Of Action Hierarchies)系统是HTN规划的第一个实现，一年后Austin Tate基于他的工作提出了Nonlin，并在1977年发表的论文中进行了详细描述。
随后1984年交互式规划和执行系统（SIPE）出现，DAVID E. WILKINS于1990年描述了其继任者SIPE-2的新应用。
1991年Ken Currie和Austin Tate基于以前在Nonlin规划师及其衍生品方面的经验提出了O-Plan。Nonlin和其他类似的计划系统的控制架构有限，仅限于部分搜索空间；O-Plan则是一个更灵活的系统的设计和实施，旨在支持规划研究和开发，开辟新的规划方法并支持强大的搜索控制启发式。这项工作之后的成果有O-Plan2，1994年Austin Tate等学者在论文中对其进行了概述：O-Plan2（开放式规划架构）提供了一个适用于命令，规划和执行应用程序的通用领域独立计算架构。他们认为O-Plan2研究的主要贡献是对模块化的、灵活的计划和控制系统的完整设想，并且该系统结合了人工智能方法。
1996年，Erol Kutluhan提出了通用方法组合规划器（UMCP），包括设计HTN规划的数学框架，分析该框架，开发基于该分析的可证明正确的算法，以及为进一步评估和探索而实施这些算法。1999年Dana Nau和Hector Munoz-Avila等学者提出了SHOP（Simple Hierarchical Ordered Planner），这是一个独立于域的HTN规划系统。由于SHOP在计划过程的每一步都知道完整的世界状态，因此它可以使用高度表达性的域表示。 其之后的版本SHOP2规划系统获得了2002年国际规划竞赛中杰出表现的奖项之一。Dana Nau等学者在2003年的论文中对其进行了描述。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1975 | Earl D Sacerdoti提出了NOAH(Nets Of Action Hierarchies)系统 | Sacerdoti, E. D.(1975). A Structure for Plans and Behavior. Ph.D. dissertation, Standfor University, AI Center. aAI7605794. |
| 1977 | Austin Tate基于Earl D Sacerdoti的工作提出了Nonlin | Tate, A. (1977). Generating Project Networks. in Proceedings of the 5th International Joint Conference on Artificial Intelligence. 2: 888–893. |
| 1990 | DAVID E. WILKINS描述了SIPE-2的新应用 | Wilkins, D. E. (1990). Can AI Planners Solve Practical Problems?. Comput. Intell., 6(4): 232–246. |
| 1991 | Ken Currie和Austin Tate基于以前在Nonlin规划师及其衍生品方面的经验提出了O-Plan | Currie, K. and Tate, A. (1991). O-Plan: The Open Planning Architecture. Artificial Intelligence. 52(1): 49–86. |
| 1994 | Austin Tate等学者在论文中对O-Plan2进行了概述 | Tate, A.; Drabble, B. and Kirby, R. (1994). O-Plan2: An Open Architecture for Command, Planning and Control. in Intelligent Scheduling. Morgan Kaufmann Publishers Inc.,pp. 213–239. |
| 1996 | Erol Kutluhan提出了通用方法组合规划器（UMCP） | Erol, K. (1996). Hierarchical Task Network Planning: Formalization, Analysis, and Implementation. Ph.D. dissertation, Computer Science Department, University of Maryland. |
| 1999 | Dana Nau和Hector Munoz-Avila等学者提出了SHOP（Simple Hierarchical Ordered Planner） | Nau, D. S.; Cao, Y.; Lotem, A. and Avila, H. M. (1999). SHOP: Simple Hierarchical Ordered Planner. In Proceedings of the 16th International Joint Conference on Artificial Intelligence, ser. IJCAI’99. pp. 968–975. |
| 2003 | Dana Nau等学者对SHOP2进行了描述 | Nau, D. S.; Ilghami, O.; Kuter, U.; Murdock, J. W.; Wu, D. and Yaman, F. (2003). SHOP2: An HTN Planning System. Journal of Artificial Intelligence Research. 20(1): 379–404. |
发展分析
瓶颈
由于子任务有共享的可能性，HTN规划不能保证产生的结果是最优的，在最差的情况下甚至可能是错误的。
未来发展方向
HTN规划主要应用于游戏中，比如在实时战略（RTS）游戏中的应用，目前有些研究试图适应有限的决策时间以及动态的对抗环境中所带来的挑战，提出了对抗HTN（adversarial HTN， AHTN）以及基于其之上的改进算法AHTN-R，这些是目前有关HTN规划比较新的进展。
Contributor：Yuanyuan Li