Hierarchical task network
Encyclopedia
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:
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 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 is a useful way to provide the planning engine with information about the hierarchical structure of the planning domain. HTN-like planning (as it is practically used) has the same expressivity (i.e. can solve the same domains) as STRIPS
. The theoretical model of HTN is strictly more expressive than STRIPS, but cannot be directly used because of its undecidability.
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, 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:
- primitive tasks, which roughly correspond to the actions of STRIPSSTRIPSIn artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
; - compound tasks, which can be seen as composed of a set of simpler tasks;
- goal tasks, which roughly corresponds to the goals of STRIPSSTRIPSIn artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
, 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 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
Task analysis environment modeling simulation
Task Analysis, Environment Modeling, and Simulation is a problem domain independent modeling language used to describe the task structures and the problem-solving activities of intelligent agents in a multi-agent environment....
.
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:
- Nonlin, one of the first HTN planning systems.
- SIPE-2
- O-Plan
- UMCP, the first provably sound and complete HTN planning systems.
- SHOP2, a HTN-planner developed at University of Maryland, College ParkUniversity of Maryland, College ParkThe University of Maryland, College Park is a top-ranked public research university located in the city of College Park in Prince George's County, Maryland, just outside Washington, D.C...
. - HTNPlan-P (preference-basedPreference-based planningIn artificial intelligence, preference-based planning is a form of automated planning and scheduling which focuses on producing plans that additionally satisfy as many user-specified preferences as possible. In many problem domains, a task can be accomplished by various sequences of actions...
HTN planning)
HTN is a useful way to provide the planning engine with information about the hierarchical structure of the planning domain. HTN-like planning (as it is practically used) has the same expressivity (i.e. can solve the same domains) as STRIPS
STRIPS
In artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
. The theoretical model of HTN is strictly more expressive than STRIPS, but cannot be directly used because of its undecidability.
See also
- STRIPSSTRIPSIn artificial intelligence, STRIPS is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this planner...
- Hierarchical control systemHierarchical control systemA Hierarchical control system is a form of Control System in which a set of devices and governing software is arranged in a hierarchical tree. When the links in the tree are implemented by a computer network, then that hierarchical control system is also a form of Networked control system.-...
- a feedback control system well suited for HTN planning