In artificial intelligence, hierarchical task network (HTN) planning is an approach to automated planning in which the dependency among actions can be given in the form of hierarchically structured networks.
Planning problems are specified in the hierarchical task network approach by
providing a set of tasks, which can be:
primitive (initial state) tasks, which roughly correspond to the actions of STRIPS;
compound tasks (intermediate state), which can be seen as composed of a set of simpler tasks;
goal tasks (goal state), which roughly corresponds to the goals of STRIPS, but are more general.
A solution to an HTN problem is then an executable sequence of primitive tasks that can be obtained from the initial task network by decomposing compound tasks into their set of simpler tasks, and by inserting ordering constraints.
A primitive task is an action that can be executed directly given the state in which it is executed supports its precondition. A compound task is a complex task composed of a partially ordered set of further tasks, which can either be primitive or abstract. 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 (hierarchical) 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.
Some of the best-known domain-independent HTN-planning systems are:
NOAH, Nets of Action Hierarchies.[1]
Nonlin, one of the first HTN planning systems.[2]
SIPE-2[3]
O-Plan, Open Planning Architecture[4]
UMCP, the first probably sound and complete HTN planning systems.[5]
I-X/I-Plan[6]
SHOP2, a HTN-planner developed at University of Maryland, College Park.[7]
PANDA, a system designed for hybrid planning, an extension of HTN planning developed at Ulm University, Germany.[8]
HTNPlan-P, preference-based HTN planning.[9]
HTN planning is strictly more expressive than STRIPS, to the point of being undecidable in the general case.[10] However, many syntactic restrictions of HTN planning are decidable, with known complexities ranging from NP-complete to 2-EXPSPACE-complete,[11] and some HTN problems can be efficiently compiled into PDDL, a STRIPS-like language.[12]
^NOAH
^Nonlin
^David E. Wilkins. "SIPE-2: System for Interactive Planning and Execution". Artificial Intelligence Center. SRI International. Retrieved 2013-06-13.
^O-Plan
^UMCP
^I-X/I-Plan
^SHOP2
^PANDA
^HTNPlan-P
^Erol, Kutluhan; Hendler, James; Nau, Dana S. (1996). "Complexity results for htn planning" (PDF). Annals of Mathematics and Artificial Intelligence. 18. Springer: 69–93. Retrieved 8 February 2015.
^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.
^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.
and 27 Related for: Hierarchical task network information
form of hierarchically structured networks. Planning problems are specified in the hierarchicaltasknetwork approach by providing a set of tasks, which...
certain goal-oriented tasks and was sometimes referred to as the task-negative network, in contrast with the task-positive network. This nomenclature is...
Bergson, whose philosophical views have inspired hierarchical models. Hierarchical recurrent neural networks are useful in forecasting, helping to predict...
based on hierarchical generative models and deep belief networks, may be closer to biological reality. In this respect, generative neural network models...
world model and performing planning. A hierarchicaltasknetwork is a good fit for planning in a hierarchical control system. Besides artificial systems...
arcs, is not restricted to being a hierarchy or lattice. The network model was adopted by the CODASYL Data Base Task Group in 1969 and underwent a major...
HTN can refer to: Hierarchicaltasknetwork, planning formalism in artificial intelligence "Homesteading the Noosphere", essay on computer programming...
artificial intelligence Cooperative distributed problem solving STRIPS Hierarchicaltasknetwork Keith S. Decker (1995). "Environment Centered Analysis and Design...
Suite as defined by the Internet Engineering Task Force (IETF). It consists of a set of standards for network management, including an application layer...
within-group variability, which can only be done if the hierarchy of evidence is replaced by a network that takes into account the relationship between epidemiological...
characteristics of both HB and deep networks. The compound HDP-DBM architecture is a hierarchical Dirichlet process (HDP) as a hierarchical model, incorporating DBM...
time from an SNTP source. NTP uses a hierarchical, semi-layered system of time sources. Each level of this hierarchy is termed a stratum and is assigned...
performance of packet-switched networks, which underpinned the development of the ARPANET. His theoretical work on hierarchical routing in the late 1970s with...
Bayesian hierarchical modelling is a statistical model written in multiple levels (hierarchical form) that estimates the parameters of the posterior distribution...
describing planning problems is that of hierarchicaltasknetworks, in which a set of tasks is given, and each task can be either realized by a primitive...
for hierarchicalnetworks. Operating voltage of 12 V. Data is transferred across the bus in fixed-form messages of selectable lengths. The master task transmits...
Neural networktasks are often categorized as discriminative (recognition) or generative (imagination). Often but not always, discriminative tasks use supervised...
resemble later consultation rather than vertical command”. Network organizations lack the hierarchical aspects of other structures and are characterized by...
move in opposite ways. It is not used when discussing hierarchical routing or hierarchicalnetwork topologies, as packets can be transferred both ways....
Ranganath; Andrew Ng. "Convolutional Deep Belief Networks for Scalable Unsupervised Learning of Hierarchical Representations" (PDF). {{cite journal}}: Cite...
shrinkage is a typical behavior in hierarchical Bayes models. Some care is needed when choosing priors in a hierarchical model, particularly on scale variables...
information, such as in what task or activity the person is performing. Two kinds of Hierarchical Markov Models are the Hierarchical hidden Markov model and...
originally dubbed AEHOO (All Encompassing Hierarchical Object Oriented format) began in 1987 by the Graphics Foundations Task Force (GFTF) at the National Center...
Global Information