Table of Contents
Recent Advances in AI Planning: A Unified View
Planning is hot...
Overview
Planning : The big picture
The Many Complexities of Planning
Planning & (Classical Planning)
PPT Slide
Broad Aims & Biases of the Tutorial
Why Care about “neo-classical” Planning?
Applications (Current & Potential)
The (too) many brands of classical planners
A Unifying View
Modeling Planning Problems: Actions, States, Correctness
Modeling Classical Planning
Some notes on action representation
Actions with Resources and Duration
Planning vs. Scheduling
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 for refinement planning
PPT Slide
CONJUNCTIVE REFINEMENT PLANNING
PPT Slide
Forward State-space Refinement
Backward State-space Refinement
PPT Slide
PPT Slide
Tradeoffs among Refinements
PPT Slide
Generating Conjunctive Refinement Planners
Issues in instantiating Refineplan
Tractability Refinements
Case Study: UCPOP
Many variations on the theme..
Interleaving Refinements
PPT Slide
Conjunctive planners: The State of the Art
DISJUNCTIVE REFINEMENT PLANNING
Disjunctive Planning
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
Compilation to Binary Decision Diagrams (BDDs)
Relative Tradeoffs Offered by the various compilation substrates
Direct vs. compiled solution extraction
Disjunctive planners based on BSS and PS refinements?
Lines of Proof as basis for (naïve) encodings
Encodings based on state-based proofs
Encodings based on Causal proofs
Alternative causal 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
Conjunctive vs. Disjunctive planners
Controlled Splitting
Characterizing Difficult Problem Classes
Subgoal Interactions and Planner Selection
Handling Resources, Metric and Temporal Contraints
Adapting to Metric/Temporal Planning
Issues in handling time and resources
Scheduling: Brief Overview
What planners are good for handling resources and time?
Some Implemented Approaches
Tradeoffs in the current implementations
HEURISTICS & OPTIMIZATIONS
Distance Heuristics from Relaxed Problems
PPT Slide
Bottom-up Distance computation
Improving the Heuristic
Using the Planning Graph to account for +ve/-ve Interactions
Plan Graph produces a large spectrum of effective heuristics with differing tradeoffs
PPT Slide
Using Distance Heuristics
Other notable optimizations
Simplifying (SAT) encodings
CUSTOMIZING PLANNERS WITH DOMAIN SPECIFIC KNOWLEDGE
Improving Performance through 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 Guidance
Where does guidance come from?
Ways of using the Domain 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 Declarative Guidance
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
Adapting to Incompleteness, Uncertainity and Dynamism
Incomplete Information
Incomplete Information: Some Implemented Approaches
Dynamic Environments
Stochastic Actions
Complex & Conflicting Goals
Summary
Status
Resources
CSP/SAT/TCSP Review
PPT Slide
Important ideas in solving CSPs
Important ideas in solving CSPs
Temporal Constraint Satisfaction Problem (TCSP)
What makes CSP problems hard?
Hardness & Local Consistency
PPT Slide
|