Recent Advances in AI Planning: A Unified View


Click here to start

Table of Contents

Recent Advances in AI Planning: A Unified View

Planning is hot...


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 for refinement planning

PPT Slide


PPT Slide

Forward State-space Refinement

Backward State-space Refinement

PPT Slide

PPT Slide

Position, Relevance and 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 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 and Planner Selection


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


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-Classical Planning

Metric and Temporal constraints

Scheduling as CSP

Incomplete Information

Incomplete Information: Some Implemented Approaches

Dynamic Environments

Stochastic Actions

Complex & Conflicting Goals




Author: MBE


Home Page: