Table of Contents
Recent Advances in AI Planning:A Unified View
Planning is hot...
Overview
Planning : The big picture
Planning & (Classical Planning)
Why care about classical Planning?
The (too) many brands of classical planners
Advantages of the Unified View
Modeling Classical Planning:Actions, States, Correctness
Modeling Classical Planning
Some notes on action representation
Checking correctness of a plan:The State-based approaches
Checking correctness of a plan:The Causal Approach
The Refinement Planning Framework:
Refinement Planning:Overview
Partial Plans: Syntax
Partial Plans: Semantics
PPT Slide
Refinement (pruning) Strategies
PPT Slide
The Refinement Planning Template
A flexible Split&Prune search forrefinement planning
PPT Slide
CONJUNCTIVE REFINEMENT PLANNING
PPT Slide
Forward State-space Refinement
Backward State-space Refinement
PPT Slide
PPT Slide
Position, Relevanceand Commitment
PPT Slide
Generating Conjunctive Refinement Planners
Issues in instantiating Refineplan
Tractability Refinements
Case Study: UCPOP
Many variations on the theme..
Interleaving Refinements
Effective Heuristics for conjunctive planners
Greedy Regression Graphs & Subgoal distance measures
Bottom-up Greedy Distance computation
PPT Slide
Greedy Distance Heuristic: Uses
PPT Slide
Conjunctive planners:The State of the Art
DISJUNCTIVE REFINEMENT PLANNING
Disjunctive Planning
CSP and SAT Review
(very) Quick overview of CSP/SAT concepts
PPT Slide
What makes CSP problems hard?
Hardness & Local Consistency
Important ideas in solving CSPs
PPT Slide
PPT Slide
Disjunctive Representations
Refining Disjunctive Plans (1)
PPT Slide
Refining Disjunctive plans (3)
Refining Disjunctive plans (4)
Graphplan Plangraph(Blum & Furst, 1995)
Constructing Planning Graph
Open issues in disjunctive refinement
Ideas for enforcing consistency for BSR
Solution Extraction in Disjunctive Plans
Graphplan Backward Search(Direct Search I)
Backward Search
Other Direct Extraction Strategies
Compilation to CSP
Compilation to SAT
Compilation to Integer Linear Programming
Direct vs. compiled solution extraction
Direct generation of SAT encodings
Encodings based on state-based proofs
Encodings based on Causal proofs
Alternative causal encodings
Simplifying SAT encodings
Tradeoffs between encodings based on different proof strategies
Tradeoffs between encodings based on different proof strategies
Direct compilation vs. compilation of refined disjunctive plans
On the difficulty of enforcing directional consistency at the SAT level
Impact of Refinements on Encoding Size
Some implemented disjunctive planners
Accelerating Disjunctive Planners
Conjunctive vs. Disjunctive planners
Controlled Splitting
Characterizing Difficult Problem Classes
Subgoal Interactions andPlanner Selection
CUSTOMIZING PLANNERS WITH DOMAIN SPECIFIC KNOWLEDGE
Improving Performancethrough Customization
User-Assisted Customization(using domain-specific Knowledge)
Many User-Customizable Planners
With right domain knowledge any level of performance can be achieved...
Types of domain-specific knowledge
Where does guidance come from?
Uses of Domain-specific knowledge
Task Decomposition (HTN) Planning
Modeling Reduction Schemas
PPT Slide
Dual views of HTN planning
SAT encodings of HTN planning
Solving HTN Encodings
Non-HTN domain knowledge for SAT encodings
Case Study: SATPLAN with domain specific knowledge
Rules on desirable State Sequences: TLPlan approach
PPT Slide
Full procedural control: The SHOP way
Folding the Control Knowledge into the planner: CLAY approach
Conundrums of user-assisted cutomization
Automated Customization of Planners
Symmetry & Invariant Detection
Abstraction
Example: Abstracting Resources
Learning Search Control Rules with EBL
Example Rules (Learned)
Case-based Planning Macrops, Reuse, Replay
Case-study: DerSNLP
PPT Slide
Reuse in Disjunctive Planning
Connections to Non-ClassicalPlanning
Metric and Temporal constraints
Scheduling as CSP
Incomplete Information
Incomplete Information:Some Implemented Approaches
Dynamic Environments
Stochastic Actions
Complex & Conflicting Goals
Summary
Status
Resources
|