Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 46 ยท Planning

Planning Heuristics and Planning Graphs

See how planners scale: delete relaxation, h_max, h_add and h_FF heuristics, planning graphs with mutexes, a GraphPlan implementation, partial-order planning and HTN.

The planner from the previous lesson, Classical Planning with STRIPS and PDDL, works but is blind: it explores states in breadth-first order with no sense of direction. For search problems such as the 8-puzzle we fixed that with a hand-written heuristic. A general planner cannot ask a human for one, because it must solve problems it has never seen. The central trick of modern planning is to compute a heuristic automatically from the problem description.

In this lesson you will learn the most important such trick, the delete relaxation, and the three heuristics it produces (h_max, h_add, h_FF). You will then build a planning graph, the data structure behind GraphPlan, extract a plan from it, and finish with a short tour of partial-order and hierarchical planning.

Relaxing the problem: ignore the delete lists

Remember from Admissible and Consistent Heuristics that good heuristics often come from relaxing a problem: removing rules to make it easier, then using the cost of the easy problem as an estimate. The standard relaxation for STRIPS is the delete relaxation: pretend that actions never remove any fact.

In the relaxed problem, facts only ever accumulate. Doing something can never undo progress, so the problem becomes much easier, solvable in polynomial time. (Finding the shortest relaxed plan is still NP-hard, but finding a relaxed plan is cheap.) We can estimate, for every fact p, how many steps it takes to make it true starting from the current state:

  • A fact already in the state costs 0.
  • An action costs 1 plus the cost of getting all its preconditions.
  • A fact costs the cheapest action that adds it.

The two natural ways to combine the precondition costs give two heuristics.

Heuristic Cost of an action Cost of the goal Properties
h_max 1 + the maximum precondition cost maximum over goal facts admissible, but weak
h_add 1 + the sum of precondition costs sum over goal facts not admissible, but very informative
h_FF length of an actual relaxed plan number of distinct actions in it not admissible, usually tight

h_max assumes that all subgoals can be achieved in parallel, so it never overestimates: it is admissible and works with A*. h_add assumes the subgoals are independent and adds their costs, which double-counts shared work but guides search well in practice. h_FF, made famous by the FF planner, fixes the double-counting: it extracts one relaxed plan by following the cheapest supporter of each needed fact, and counts each action once.

Computing the heuristics in Python

The code below computes the costs by repeatedly relaxing action costs until nothing improves (a fixed point), remembering the best supporting action for each fact. It then compares search with no heuristic against A* using h_max, h_add and h_FF on a six-block tower reversal: the start is a tower with F on top and A at the bottom, the goal is the same tower upside down. The optimal plan has 12 steps.

Python Heuristics from the delete relaxation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Run it and read the table. All four searches find a 12-step plan, but with no heuristic the planner expands 807 states, h_max needs 67, and h_add and h_FF need only 14 and 13. The numbers themselves are tiny, but notice the ratios: they widen quickly as problems grow. Also notice the estimates at the start. h_add says 35, far above the true distance of 12, because it double-counts. It still guides the search well because search only needs the heuristic to rank states correctly, not to be accurate. That is why h_add-style heuristics are used even though they lose the optimality guarantee that A* has with an admissible heuristic.

Warning: A* with h_add or h_FF is no longer guaranteed to return an optimal plan, because those heuristics are not admissible. Here the plans happen to be optimal; in general they can be longer. Use h_max (or a stronger admissible heuristic) when optimality matters.

Planning graphs

The delete relaxation is one way to look at a planning problem in a simplified way. A planning graph is another: a layered structure built once, in polynomial time, that over-approximates what is reachable. It alternates two kinds of layers.

  • A proposition level P0, P1, ... holds facts. P0 is the initial state.
  • An action level A1, A2, ... holds every action whose preconditions appear in the previous proposition level, plus a no-op for each fact (which means "this fact simply persists").
graph LR
    P0["P0<br/>initial facts"] --> A1["A1<br/>applicable actions + no-ops"]
    A1 --> P1["P1<br/>facts after one step"]
    P1 --> A2["A2<br/>more actions"]
    A2 --> P2["P2<br/>more facts"]

Each action level adds what could be done next; each proposition level adds what could then be true.

A pure layered graph would be too optimistic, since it would allow two actions in the same level that cannot happen together. GraphPlan therefore records mutual exclusion (mutex) relations.

Two actions in the same level are mutex when:

  1. Inconsistent effects or interference: one deletes a precondition or an effect of the other.
  2. Competing needs: some precondition of one is mutex with some precondition of the other.

Two facts in the same level are mutex when every pair of actions that could produce them is mutex (for example, at(hall) and at(office) cannot both be true). A solution cannot exist before the goal facts appear in a level without being mutex with each other, so the level where this first happens is a lower bound on plan length.

GraphPlan: expand, then extract

The GraphPlan algorithm alternates two phases.

  1. Expand: add levels until all goal facts appear in the last proposition level and are pairwise non-mutex. If the graph stops changing before that (it "levels off"), the problem has no solution.
  2. Extract: search backward from the goals. For each level, pick a set of non-mutex actions that achieve the current goals, take their preconditions as the goals for the previous level, and repeat down to P0. If the search fails, expand the graph one more level and try again. Failed goal sets are memoized so they are never retried at the same level.

The output is not a total order but a layered plan: a list of sets of actions, where the actions in one set can run in any order (or in parallel).

We use a small "office errand" domain in which a robot starts in the hall, must take a key, open the door, fetch a report from the office and deliver it to the hall, and should also tidy the hall. Tidying has no dependencies other than being in the hall, so GraphPlan can place it alongside another action.

Python Building a planning graph and extracting a plan

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The graph needs six levels before both goals appear without mutexes. At level 1 the only mutex pair is has_key with key_in_hall, because the no-op that keeps the key in the hall conflicts with take_key, which deletes it. The goal hall_tidy appears at level 1 (it only needs at_hall), while delivered takes until level 6. Extraction then returns six steps, and the last step holds two actions, deliver and tidy_hall, which can run together. A sequential planner would output one extra step.

Beyond STRIPS: partial-order and hierarchical planning

GraphPlan is one of several families of planners. Two others are worth knowing by name.

Partial-order planning (POP) does not commit to a total order of actions. It starts from a tiny plan (start and finish) and repeatedly adds an action to satisfy an open precondition, adds an ordering constraint (A before B) and a causal link ("A achieves p for B"). When some other action threatens a link by deleting p, the planner resolves the threat by ordering the threatening action before A or after B. The result is a set of actions with only the necessary orderings, which is flexible to execute but harder to search and to guide with heuristics, so most modern planners search over states instead.

Hierarchical Task Network (HTN) planning adds human knowledge: instead of searching for any action sequence that reaches a goal, the planner decomposes abstract tasks into subtasks using methods written by an expert. This prunes the search dramatically and is widely used in game AI and logistics. A read-only sketch:

TEXT
task travel(x, y):
  method taxi-trip:
    preconditions: cash >= taxi-fare(x, y)
    subtasks: [call-taxi(x), ride(x, y), pay-driver]
  method short-walk:
    preconditions: distance(x, y) <= 1 km
    subtasks: [walk(x, y)]

If the planner picks taxi-trip and its subtasks cannot be completed, it backtracks to another method for travel. The domain knowledge sits in the methods, not in a heuristic.

Choosing an approach

Approach Idea Typical strength
Forward search + h_FF state-space A* or greedy search with an automatic heuristic the dominant modern approach
GraphPlan layered graph with mutexes, backward extraction parallel plans, short plans, simple to implement
Partial-order planning commit to orderings only when forced flexible, human-readable plans
HTN decompose tasks with expert methods large domains with known recipes

After planning you will meet problems where the world is not deterministic or not fully known. The next chapter starts from the foundation for those: Probability for AI.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does the delete relaxation do?

    In the relaxed problem actions never remove facts, which makes the problem much easier. The cost of solving it gives an automatic heuristic.
  2. 2. Which heuristic is admissible?

    h_max takes the maximum of the precondition costs, so it never overestimates the true cost. h_add sums costs and can overestimate; h_FF counts one relaxed plan and is not admissible either.
  3. 3. When are two actions in the same planning-graph level mutex?

    Interference (one deletes something the other needs or adds) and competing needs (mutex preconditions) both prevent two actions from happening together.
  4. 4. What does GraphPlan do when backward extraction fails at the current graph depth?

    Extraction is retried after expansion. Only when the graph levels off without a solution can GraphPlan conclude that the problem is unsolvable.
  5. 5. What is the key idea of HTN planning?

    HTN planners search over task decompositions, so the domain knowledge in the methods prunes the search space.

Summary

  • Planners compute heuristics automatically from the STRIPS description, most often by ignoring delete lists (the delete relaxation).
  • h_max is admissible but weak; h_add and h_FF are not admissible but guide search far better. In the six-block demo they cut the expanded states from 807 to 14 and 13.
  • A planning graph alternates proposition and action levels, with no-ops and mutex relations that rule out impossible combinations.
  • GraphPlan expands the graph until the goals appear non-mutex, then extracts a layered (parallel) plan by backward search.
  • Partial-order planning delays ordering decisions; HTN planning uses expert-written decomposition methods.
  • The classical assumptions (known, deterministic world) end here; the next chapter handles uncertainty.

Next: Probability for AI.