Transcript Practical HTN Planning

Practical HTN Planning
Putting HTN Planning
into Use
Literature

Human Planning

Klein, G. (1998) Sources of Power: How People Make Decisions, MIT Press.

Refinement Search

Kambhampati, S., Knoblock, C.A. and Yang, Q. (1995) Planning as Refinement Search: A Unified
Framework for Evaluating Design Tradeoffs in Partial-Order Planning, Artificial Intelligence, Vol. 76, No. 12, pp. 167-238, Elsevier.

Nonlin


http://www.aiai.ed.ac.uk/project/nonlin/
Tate, A. (1977) Generating Project Networks, Proceedings of the Fifth International Joint Conference on
Artificial Intelligence (IJCAI-77) pp. 888-893, Boston, Mass. USA, August 1977.

O-Plan


http://www.aiai.ed.ac.uk/project/oplan/
Currie, K and Tate, A. (1991) O-Plan: the Open Planning Architecture, Artificial Intelligence Vol. 52, No. 1,
pp 49-86, Elsevier.

Other Practical Planners

Ghallab, M., Nau, D. and Traverso, P., Automated Planning – Theory and Practice, chapters 19, 22 and
23. Elsevier/Morgan Kaufmann, 2004.
Practical HTN Planning
2
Overview







Human Approaches to Planning
Practical HTN Planning
Refinement Planning as a Unifying View
Nonlin and O-Plan Features
QA (Modal Truth Criterion)
Time, Resource and Other Constraint Handling
I-X/I-Plan Overview
Practical HTN Planning
3
Some Planning Features






Expansion of a high level abstract plan into greater detail
where necessary.
High level ‘chunks’ of procedural knowledge (Standard
Operating Procedures, Best Practice Processes, Tactics
Techniques and Procedures, etc.) at a human scale typically 5-8 actions - can be manipulated within the system.
Ability to establish that a feasible plan exists, perhaps for a
range of assumptions about the situation, while retaining a
high level overview.
Analysis of potential interactions as plans are expanded or
developed.
Identification of problems, flaws and issues with the plan.
Deliberative establishment of a space of alternative options,
perhaps based on different assumptions about the situation
involved, of especial use ahead of time, in training and
rehearsal, and to those unfamiliar with the situation or
utilising novel equipment.
Practical HTN Planning
4
More Planning Features







Monitoring of the execution of events as they are expected to
happen within the plan, watching for deviations that indicate
a necessity to re-plan (often ahead of this becoming a
serious problem).
Represent the dynamic state of the world at points in the plan
and use this for ‘mental simulation’ of the execution of the
plan.
Pruning of choices according to given requirements or
constraints.
Situation dependent option filtering (sometime reducing the
choices normally open to one ‘obvious’ one.
Satisficing search to find the first suitable plan that meets the
essential criteria.
Heuristic evaluation and prioritisation of multiple possible
choices within the constrained search space.
Uniform use of a common plan representation with
embedded rationale to improve plan quality, shared
understanding, etc.
Practical HTN Planning
5
Human Approach



Previous slides describe aspects of problem
solving behaviour observed in expert humans
working in unusual or crisis situations.
Gary Klein, “Sources of Power”, MIT Press, 1998.
But they also describe the hierarchical and mixed
initiative approach to planning in AI developed
over the last 30 years.
Practical HTN Planning
6
HTN - Planning Approach

HTN Planning is a useful paradigm…

Compose workflows/processes from
requirements and component/template libraries
Covers simple through to very complex (preplanned) components
Allows for execution support, reactive repair,
recovery, etc.
Suited to mixed initiative (people and systems)
planning and execution
Gives an understandable framework within
which specialised constraint solvers, domainspecific planners (e.g. route finders), optimisers,
plan analysers and simulators can work




Practical HTN Planning
7
HTN - Activity Composition
Plan Library
A2 Refinement
S1
S2
“Initial” Plan
“Final” Plan
A2.1
A2
A2.2
Refine
A4
A1
A5
A4
A1
A5
A3
A3
Introduce activities to achieve preconditions
Resolve interactions between conditions and effects
Handle constraints (e.g. world state, resource, spatial, etc.)
Practical HTN Planning
8
HTN – Initial Plan as “Goals”
Plan Library
Ax Refinement
S1
S2
P
“Initial” Plan
“Refined” Plan
P
P
Refine
Q
A1.1
A1.2
Q
Initial Plan can be any combination of Activities and Constraints
Practical HTN Planning
9
Nonlin (1974-1977)

Hierarchical Task Network Planning
Partial Order Planner
Plan Space Planner
Goal structure-based plan development - considers
alternative “approaches” only based on plan rationale
QA/Modal Truth Criterion Condition Achievement
Condition “Types” to limit search
“Compute Conditions” for links to external data and
systems (attached procedures)
Time and Resource Constraint checks

Nonlin core is basis for text book descriptions of HTN Planning







Practical HTN Planning
10
Nonlin Domain Language – TF
opschema makeon
actschema puton
pattern {on $*x $*y}
pattern {put $*x on top of $*y}
expansion 1 goal {cleartop $*x}
conditions usewhen {cleartop $*x} at self
2 goal {cleartop $*y}
usewhen {cleartop $*y} at self
3 action {put $*x on top of $*y}
usewhen {on $*x $*z} at self
orderings 1 ---> 3 2 ---> 3
effects + {on $*x $*y}
vars x undef y undef;
- {cleartop $*y}
“typed”
condition
search space
end;
- restricts
{on $*x $*z}
example of search
control knowledge
+ {cleartop
$*z}
opschema makeclear
vars x undef y undef z undef;
pattern {cleartop $*x}
end;
expansion 1 goal {cleartop $*y}
2 action {put $*y on top of $*z}
always {cleartop table};
orderings 1 ---> 2
conditions usewhen {on $*y $*x} at 2
initially {on c a}
usewhen {cleartop $*z} at 2
{on a table}
vars x <:non table:> y undef
{on b table}
z <:et <:non $*x:> <:non $*y:> :>;
{cleartop c}
end;
{cleartop b} ;
$*x is a variable
plan goal {on a b} goal {on b c};
Practical HTN Planning
11
QA/Modal Truth Criterion








QA in a partially ordered network of nodes
Way to establish value of a condition P=V at some point in the plan
Yes/no/maybe responses
Alternative Terminology:
•
•
•
Contributors, deletors (Austin Tate, Nonlin, QA, Edinburgh, 1975-7)
White nights and clobberers (David Chapman, MIT, MTC, 1987, 1st Formalisation)
Producers, consumers (Some textbooks)
Initially just allowed imposition of orderings on nodes for a
condition,
a  b (ordering)
Later also allowed variables within condition to be constrained –
= (codesignation), ≠ (non-codesignation)
Intuitively, a white knight is an activity which re-establishes a
clobbered precondition p
A clobberer in a plan can be "defeated" by imposing ordering or
codesignation/non-codesignation constraints on the plan, or by
inserting a white knight between the clobberer and the point where
a condition is needed
Practical HTN Planning
12
QA/Modal Truth Criterion
Before
After
Need to ensure no deletor
appears between a chosen
contributor and point of need
Contributor
No Effect
Deletor
P=V
Practical HTN Planning
13
O-Plan (1983-1999) Features










Hierarchical Task Network Planning
Nonlin-like goal-structure, QA and Typed/Compute conditions
Partial-Plan “Refinement “ Approach
Plan State has “flaws”/issues attached
Agenda Architecture with Plan Modification Operations
“Opportunistic Search” (agenda type, branch1/branch N)
Multiple constraint managers with yes/no [and maybe] results
Least Commitment Approach (on activity ordering,
object/variable bindings and other constraints)
Constraint “Posting” rather than explicit commitments
(and/or trees with sets of “before” temporal constraints and
variable binding (= and ≠) constraints) [as in MOLGEN]
Goal structure recording and monitoring to preserve plan
rationale
Practical HTN Planning
14
O-Plan (1983-1999) Features
Practical HTN Planning
15
O-Plan Domain Language – TF
types objects = (a b c table),
movable_objects = (a b c);
always {cleartop table};
schema puton;
vars ?x = ?{type movable_objects},
?y = ?{type objects},
?z = ?{type objects};
vars_relations ?x /= ?y, ?y /= ?z, ?x /= ?z;
expands {puton ?x ?y};
only_use_for_effects
{on ?x ?y}
= true,
“typed” condition restricts search space
{cleartop ?y} = false,
example of search control knowledge
{on ?x ?z}
= false,
{cleartop ?z} = true;
conditions only_use_for_query {on ?x ?z}
achieve {cleartop ?x}
achieve {cleartop ?y};
end_schema;
?x is a variable
Practical HTN Planning
16
O-Plan Agent Architecture
Practical HTN Planning
17
O-Plan Agent Architecture
Later became
• Issues
• Nodes
• Constraints
• Annotations
Practical HTN Planning
Later became
Plan
Modification
Operators
18
O-Plan Planning Workflow
Practical HTN Planning
19
A More Collaborative
Planning Framework





Human relatable and presentable objectives, issues,
sense-making, advice, multiple options, argumentation,
discussions and outline plans for higher levels
Detailed planners, search engines, constraint solvers,
analyzers and simulators act in this framework in an
understandable way to provide feasibility checks,
detailed constraints and guidance
Sharing of processes and information about process
products between humans and systems
Current status, context and environment sensitivity
Links between informal/unstructured planning, more
structured planning and methods for optimisation
Practical HTN Planning
20
I-X/I-Plan (2000- )

Shared, intelligible, easily communicated and
extendible conceptual model for objectives,
processes, standard operating procedures and plans:
•
•
•
•



I
N
C
A
Issues
Nodes/Activities
Constraints
Annotations
Communication of dynamic status and presence for
agents, and reports about their collaborative
processes and process products
Context sensitive presentation of options for action
Intelligent activity planning, execution, monitoring, replanning and plan repair via I-Plan and I-P2 (I-X
Process Panels)
Practical HTN Planning
21
<I-N-C-A> Framework
Plan State
I
Issues or Implied
Constraints
Issues
N
Node
Constraints
Nodes
C
Detailed
Constraints
Constraints
Space of Legitimate Behaviours
A
Annotations
Practical HTN Planning
22
<I-N-C-A> & I-X
Plan State
I
Issues or Implied
Constraints
Issues
N
Node
Constraints
Nodes
C
Detailed
Constraints
Constraints
Space of Legitimate Behaviours
A
Choose (IH)
Do (IH)
Propagate
Constraints
IH=Issue Handler
(Agent Functional Capability)
Annotations
Practical HTN Planning
23
Anatomy of an I-X Process
Panel
Practical HTN Planning
24
I-P2 aim is a Planning, Workflow
and Task Messaging “Catch All”




Can take ANY requirement to:
•
•
•
•
Handle an issue
Perform an activity
Respect a constraint
Note an annotation
Deals with these via:
•
•
•
•
•
Manual activity
Internal capabilities
External capabilities
Reroute or delegate to other panels or agents
Plan and execute a composite of these capabilities (I-Plan)
Receives reports and interprets them to:
•
•
•
Understand current status of issues, activities and constraints
Understand current world state, especially status of process products
Help user control the situation
Copes with partial knowledge of processes and organisations
Practical HTN Planning
25
I-X Process Panel and Tools
Domain Editor
Process Panel
Messenger
Map Tool
I-Plan
I-X for Emergency Response
Central
Authorities
Collaboration
and
Communication
Command
Centre
Emergency
Responders
Isolated
Personnel
Planning Research Areas & Techniques
•
•
•
Domain Modelling
Domain Description
Domain Analysis
HTN, SIPE
PDDL, NIST PSL
TIMS
•
•
•
•
•
•
•
•
•
Search Methods
Graph Planning Algthms
Partial-Order Planning
Hierarchical Planning
Refinement Planning
Opportunistic Search
Constraint Satisfaction
Optimisation Methods
Issue/Flaw Handling
Heuristics, A*
GraphPlan
Nonlin, UCPOP
NOAH, Nonlin, O-Plan
Kambhampati
OPM
CSP, OR, TMMS
NN, GA, Ant Colony Opt.
O-Plan
•
•
•
Plan Analysis
Plan Simulation
Plan Qualitative Mdling
NOAH, Critics
QinetiQ
Excalibur
•
•
•
Plan Repair
Re-planning
Plan Monitoring
O-Plan
O-Plan
O-Plan, IPEM
•
•
•
Plan Generalisation
Case-Based Planning
Plan Learning
Macrops, EBL
CHEF, PRODIGY
SOAR, PRODIGY
•
•
•
User Interfaces
Plan Advice
Mixed-Initiative PlanS
SIPE, O-Plan
SRI/Myers
TRIPS/TRAINS
•
•
•
Plan Generalisation
Case-Based Planning
Plan Learning
Macrops, EBL
CHEF, PRODIGY
SOAR, PRODIGY
•
Planning Web Services O-Plan, SHOP2
•
•
•
Plan Sharing & Comms I-X, <I-N-C-A>
NL Generation
…
Dialogue Management …
Deals with whole
life cycle of plans
Summary







Human Approaches to Planning
Practical HTN Planning
Refinement Planning as a Unifying View
Nonlin and O-Plan Features
QA (Modal Truth Criterion)
Time, Resource and Other Constraint Handling
I-X/I-Plan Overview
Practical HTN Planning
29