Hierarchical Task Network (HTN)

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 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:

• 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 Park.

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.

Example of HTN:

Case-Based Planning – A Framework for planning from experience (Part I)

• Abstract:
  • Presenting planning as a task supported by dynamic memory
  • Case-Based Planning: integrating models of memory, learning and planning into one system
  • Successful plans are stored in memory, indexed by the goals they satisfy and the problems the avoid
  • Also, failure is stored. Planner is able to anticipate an avoid future plans failures
  • CBP aims to improve planning in three areas:
    • Failure avoidance
    • Plan repair
    • Plan reuse
• Case Based Planning (CBP) is idea of planning as remembering
• CBP differs from rule-based planning in that it rests on the notion that new plans should be based on the planner’s knowledge of what has succeeded and failed in the past
• Plan for a set of goals in not build up piece by piece from the individual plans for each goal. Instead constructed by modifying a plan from memory that already satisfies or particularly satisfies many if not all goals
• CBP is concerned with previous planning errors in order to avoid them
• CBP storing mechanism must have the ability to avoid past failure and reuse succeeded plans
• CBP Differs from other planning techniques in:
  • Initial plan building
  • Reaction to plan failure
  • Vocabulary for describing and storing plans

Building a Plan

• CBP must start building a plan for a set of goals by considering how they will interact
• The CB approach to finding an initial plan is to anticipate problems so the planner can find plans that avoid them
• Previous planning mechanism was create and debug paradigm
• The main difference between them is that create and debug paradigm creates a plan and debugs a failure after it arises

Debugging Failed Plans

• CBPer should be able to recognize failed plans to mark them as failed
• A planning fails when a plan doesn’t satisfy some goal that it was designed to deal with
• An exception failure is different from planning failure. It occurs when an unexpected event occurs. The response for exception failure differs from plan failure where in PF the planner alter the plan and in EF the planner should alters its understanding of the world
• A planner must respond to plan failure by building casual explanations of why the failure has occurred and then use these explanations to access replanning strategies designed for the situation in general
• A planner must respond to exception failure by using the explanations to add new inference rules that will allow it to anticipate the problem that it previously was unable to foresee. The planner should ask first “What went wrong with the plan?” and then ask “What went wrong with planning?”
• The planner has to repair its expectations bout the world when those expectations lead to plans that fail
• A CBPer responds to planning failures by repairing both the faulty plan and its knowledge base that allowed it to build the plan incorrectly

Storing Plans for Later Reuse

• The basic vocabluray of plan indexing is nessicary the vocalary of planner’s domain and of the goals domain
• Plans must be stored by descriptions of the negative gaol interactions they avoid (umbrella example)

Learning from Planning

• Learning by remembering differs from theories of concept of learning and explanation-driven programming
• CBP Learning is divided into 3 types:
  
  • Plan Learning
    
    • It’s the creation and storage of new plans as the result of planning for situations that the planner has never encountered before
    • The planner should build a new plan and decide what features are best for indexing it in memory
  • Exception Learning:
    • Its more complex than plan learning and closely linked to the indexing of plans in memory
    • It involves learning the features in a domain that are predictive of negative interactions between plans steps
    • This is used to anticipate particular problems and then to search plans in memory designed to avoid them
  • Critic Learning:
    • Learning the repairs that have to be made if those problems arise again in different circumstances

The Structure of Cased-Based Planning

• Old theories concentrate on simulating behavior but don’t explain why it arises. They called “non-explanation explanations“
• Another look at human behavior is to ask what function this behavior serves

Building it from the Bottom

Why Case-Based?

Plan Retrieval

• A planner must know:
  
  • Its initial planning situation
  • The states that are currently true
  • The goals it needs to satisfy
• Several plans could satisfy the same goal for different situations
• When the planner wants to retrieve a plan it probably will not find an exact plan that satisfied the goals requires. So it seeks for plans with similar goals as a starting point
• This similarity could be expressed by:
  • Grouping similar goals into sets
  • Building them in ISA hierarchy
    • I’ve found a paper talking about representing ISA hierarchy using sets rather than trees. This paper state that trees have some problems in identifying similarities and it solves these problems using sets
  • Dynamically evaluating goal similarity on the basis of individual features
  • Similarity Matrix
• If a planner have a set of plans that satisfy goals partially how to choose the best match plan? How to determine what plan out of the group
• The abstraction hierarchy is used to determine the similarity between plans whereas value hierarchy used to determine the relative utilities of different plans with respect to a set of goals
• Goals that are easier to incorporate into existing plans are less important than those that are more difficult to satisfy (buildings example 10)
• In order to get a plan that is able to find best match for a set of goals, a planner needs to know 3 things:
  • A memory of plans indexed by goals they satisfy
  • A similarity matrix for judging the similarities of goals that is required for determining how close a plan comes to satisfy a set of goals
  • A value hierarchy of goals used to judge the relative utilities of plans with respect to a set of goals

Plan Modification

• Plan modification is about modifying retrieved plan in order to satisfy unsatisfied goals in it
• To alter old plans to meet new goals the planner needs:
  
  • Set of modification rules
    
    • These rules are sets of steps that can be added to a particular plans to achieve particular goal
    • These rules can just be the modifications that are needed to alter existing plan to achieve particular goal
  • Critics with knowledge of goal specific requirements
    
    • This information will let the planner tailor the general modifications of a plan to the specific needs of the items required to achieve particular goals
  • General plan specifications
    
    • This is needed so planner doesn’t violate the goals of overall the plan when it modify it to satisfy a particular goal
• For now, the RETRIVER finds a good plan and the MODIFIER makes it better

Plan Storage

• To place new plans in memory, the STORER needs to index them under the same features that the RETRIVER uses to find them:
  • Goals they satisfy
  • Situations in which they are appropriate

Plan Repair

• Giving that the planner is going to make mistakes, we’ve to give it some mechanism for repairing the faulty plans it builds. This mechanism will be called the REPAIRER
• Input to a REPAIRER:
  
  • Faulty plan
  • Some description of the fault itself
    • The desired state that it has failed to achieve
    • The undesired state that it has caused to come about
• How planner can get this information?
  
  • Run the plan and examine the results
  • Run simulation for the plan and use their results to diagnose errors
  • It can ask outside source if the plan will do what it wants to do
• The REPAIRER is going to have some vocabulary for describing plan failures that can be used to index methods for repairing the plan itself
• The relationship between problems and repair is like the relationship between goals and plans
• Plans are indexed under problems they solve and repair methods are indexed under the types of problems they resolve
• A plan repairer needs access to two types of knowledge:
  • Vocabulary for describing plan failures
  • Set of rapier methods that correspond to those description

Learning from Failure

• There’s a problem about how to anticipate that a problem will arise again
• The fact that a plan solves a particular problem is useless unless the planner can anticipate that problem will arise
• To decide which features in a situation are to blame for failure, the ASSIGNER needs to be able to describe the causes of failure. The more extensive its vocabulary for this description, the more exact its credit assignment will be
• In anticipation, if one of the features that caused failure is high, then the suitable plan will be used

Problem Anticipation

• The job of an anticipator is to look at the planner’s goals and the current situation that surrounds them and decide if there is anything in the situation that is predictive of a problem before any other planning is done
• The whole point of anticipator is to provide
  • Information about problems that have to be avoided
  • Information that will be used by retriever to find plan that does so
• To anticipate a problem on the basis of surface features, the anticipator needs the base of information built by the assigner

Learning from Planning

• A CBPer learns by correctly indexing its planning experience in memory
• CBP learning theory presents in:
  • Learning new plans
  • Learning new problems
  • Learning new solutions
• A CBPer learns new plans, the features that predict failures and past repairs to faulty plans that it can reuse