Hierarchical task network

In artificial intelligence, the hierarchical task network, or HTN, is an approach to automated planning in which the dependency among actions can be given in the form of networks.

Planning problems are specified in the hierarchical task network approach by providing a set of tasks, which can be:

  1. primitive tasks, which roughly correspond to the actions of STRIPS;
  2. compound tasks, which can be seen as composed of a set of simpler tasks;
  3. goal tasks, which roughly corresponds to the goals of STRIPS, but are more general.

A primitive task is an action that can be executed. A compound task is a complex task composed of a sequence of actions. A goal task is a task of satisfying a condition. The difference between primitive and other tasks is that the primitive actions can be directly executed. Compound and goal tasks both require a sequence of primitive actions to be performed; however, goal tasks are specified in terms of conditions that have to be made true, while compound tasks can only be specified in terms of other tasks via the task network outlined below.

Constraints among tasks are expressed in the form of networks, called task networks. A task network is a set of tasks and constraints among them. Such a network can be used as the precondition for another compound or goal task to be feasible. This way, one can express that a given task is feasible only if a set of other actions (those mentioned in the network) are done, and they are done in such a way that the constraints among them (specified by the network) are satisfied. One particular formalism for representing hierarchical task networks that has been fairly widely used is TAEMS.

A task network can for example specify that a condition is necessary for a primitive action to be executed. When this network is used as the precondition for a compound or goal task, it means that the compound or goal task requires the primitive action to be executed and that the condition must be true for its execution to successfully achieve the compound or goal task.

The best-known domain-independent HTN-planning software is:

HTN planning is strictly more expressive than STRIPS, to the point of being undecidable in the general case.[7] However, many syntactic restrictions of HTN planning are decidable, with known complexities ranging from NP-complete to 2-EXPSPACE-complete,[8] and some HTN problems can be efficiently compiled into PDDL, a STRIPS-like language.[9]

See also

References

  1. ↑ Nonlin
  2. ↑ David E. Wilkins. "SIPE-2: System for Interactive Planning and Execution". Artificial Intelligence Center. SRI International. Retrieved 2013-06-13.
  3. ↑ O-Plan
  4. ↑ UMCP
  5. ↑ SHOP2
  6. ↑ HTNPlan-P
  7. ↑ Erol, Kutluhan; Hendler, James; Nau, Dana S. (1996). "Complexity results for htn planning" (PDF). Annals of Mathematics and Artificial Intelligence (Springer) 18: 69–93. Retrieved 8 February 2015.
  8. ↑ Alford, Ron; Bercher, Pascal; Aha, David (June 2015). Tight Bounds for HTN Planning (PDF). Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS). Retrieved 8 February 2015.
  9. ↑ Alford, Ron; Kuter, Ugur; Nau, Dana S. (July 2009). Translating HTNs to PDDL: A small amount of domain knowledge can go a long way (PDF). Twenty-First International Joint Conference on Artificial Intelligence (IJCAI). Retrieved 8 February 2015.
This article is issued from Wikipedia - version of the Saturday, December 05, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.