Hierarchical task network

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 byproviding a set of tasks, which can be:

# primitive tasks, which roughly correspond to the actions of STRIPS;
# compound tasks, which can be seen as composed of a set of simpler tasks;
# 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 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 [K. Decker (1995). [http://www.cis.udel.edu/~decker/pubs/decker-thesis-tr.pdf] . Environment Centered Analysis and Design of Coordination Mechanisms. Ph.D. Thesis at University of Massachusetts, Department of Computer Science.] [B. Horling, V. Lesser, R. Vincent, T. Wagner, A. Raja, S. Zhang, K. Decker, and A. Garvey (2004). [http://dis.cs.umass.edu/research/taems/white/] . The Taems White Paper. ] 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:
* [http://www.aiai.ed.ac.uk/project/nonlin/ Nonlin] , one of the first HTN planning systems.
* [http://www.ai.sri.com/~sipe/ SIPE-2]
* [http://www.aiai.ed.ac.uk/~oplan/ O-Plan]
* [http://www.cs.umd.edu/projects/plus/umcp/ UMCP] , the first provably sound and complete HTN planning systems.
* [http://www.cs.umd.edu/projects/shop/ SHOP2] , a HTN-planner developed at University of Maryland, College Park.

HTN is a useful way to provide the planning engine with information about the hierarchical structure of the planning domain.

HTN-like planning has the same expressivity (i.e. can solve the same domains) as STRIPS [M. Lekavy and P. Navrat (2007). [http://www2.fiit.stuba.sk/~lekavy/publikacie/2007%20Expressivity%20of%20STRIPS-Like%20and%20HTN-Like%20Planning/strips_vs_htn_lekavy.pdf Expressivity of STRIPS-Like and HTN-Like Planning] . Lecture Notes in Artificial Intelligence, Vol. 4496 Agent and multi-agent Systems. Technologies and applications. 1st KES International Symposium, KES-AMSTA 2007, Wroclaw, Poland, May/June 2007. - Germany, Springer-Verlag Berlin Heidelberg, 2007. pp. 121-130] . Previously, it was believed, that HTN-like planning is strictly more expressive than STRIPS [K. Erol, J. Hendler and D. Nau. HTN Planning: Complexity and Expressivity. In Proc. AAAI-94] .

ee also

* STRIPS
* Hierarchical control system a feedback control system well suited for HTN planning

References

* K. Erol, J. Hendler, and D. Nau (1994). [http://drum.umd.edu/dspace/bitstream/1903/624/1/CS-TR-3239.ps Semantics for hierarchical task-network planning] . Technical Report TR-94-31, UMIACS.

* K. Erol, J. Hendler, and D. Nau (1996). [http://drum.umd.edu/dspace/retrieve/720/CS-TR-3240.ps Complexity results for HTN planning] . "Annals of Mathematics and Artificial Intelligence", 18(1):69-93.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Hierarchical control system — A 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 …   Wikipedia

  • Task allocation and partitioning of social insects — Task allocation and partitioning refers to the way that tasks are chosen, assigned, subdivided, and coordinated (here, within a single colony of social insects). Closely associated are issues of communication that enable these actions to… …   Wikipedia

  • Network architecture — is the design of a communications network. It is a framework for the specification of a network s physical components and their functional organization and configuration, its operational principles and procedures, as well as data formats used in… …   Wikipedia

  • Network-centric warfare — Warfare Military history Eras Prehistoric Ancient Medieval Gunpowder Industrial …   Wikipedia

  • Network diagram — A network diagram is a general type of diagram, which represents some kind of network. A network in general is an interconnected group or system, or a fabric or structure of fibrous elements attached to each other at regular intervals.A network… …   Wikipedia

  • Network layer — layer 3 redirects here. For the MPEG 1 Audio format, see MP3. For the layer in the cerebral cortex, see Cerebral cortex#Laminar pattern. The OSI model 7 Application layer 6 Presentation layer 5 Session layer 4 Transport layer …   Wikipedia

  • Collins & Quillian Semantic Network Model — The most prevalent example of the semantic network processing approach is the Collins Quillian Semantic Network Model. cite journal title=Retrieval time from semantic memory journal=Journal of verbal learning and verbal behavior date=1969… …   Wikipedia

  • Computer network — Computer networks redirects here. For the periodical, see Computer Networks (journal). Datacom redirects here. For other uses, see Datacom (disambiguation). Internet map. The Internet is a global system of interconnected computer networks that… …   Wikipedia

  • Simple Network Management Protocol — (SNMP) forms part of the internet protocol suite as defined by the Internet Engineering Task Force (IETF). SNMP is used in network management systems to monitor network attached devices for conditions that warrant administrative attention. It… …   Wikipedia

  • Bayesian network — A Bayesian network, Bayes network, belief network or directed acyclic graphical model is a probabilistic graphical model that represents a set of random variables and their conditional dependencies via a directed acyclic graph (DAG). For example …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”