Simple Algorithm
Artificial Intelligence · Deep Layer · 28 min

Hierarchical & Probabilistic Planning

HTN planning and planning under uncertainty.

Experts don't plan a trip by searching over every possible step; they refine "travel to Rome" into "book a flight, get to the airport, fly". Hierarchical task networks turn that habit into a formalism that is fast in practice and, in its general form, provably undecidable. And when actions can fail or the world is only partly visible, a plan stops being a sequence and becomes a policy.

What you’ll learn

  • Define HTN planning (tasks, methods, task networks, solutions) and trace a SHOP2-style ordered task decomposition.
  • Prove that HTN plan existence with partially ordered task networks is undecidable, and contrast the total-order case and the plan languages that HTNs can express.
  • Formalize nondeterministic and probabilistic planning (FOND, MDPs, POMDPs), and state their complexity.
  • Explain how determinization with replanning, heuristic search and Monte Carlo methods solve probabilistic planning, and when determinization fails.

Hierarchical task networks

In a travel domain, the compound task travel(x,y)\mathit{travel}(x,y) might have a method "walk", applicable when yy is near xx, and a method "by taxi", which decomposes into callTaxi\mathit{callTaxi}, ride(x,y)\mathit{ride}(x,y) and pay\mathit{pay}, in that order, applicable when you can afford the fare. Methods encode how a task is done: domain knowledge that a classical planner would have to rediscover by search.

text
SEEK-PLAN(s, tasks, plan):          # tasks: a totally ordered list
  if tasks is empty: return plan
  t ← first(tasks);  rest ← the remaining tasks
  if t is primitive:
    for each ground action a for t with pre(a) ⊆ s:       # choice point
      result ← SEEK-PLAN(s⟦a⟧, rest, plan + [a])
      if result ≠ failure: return result
  else:
    for each method m for t whose precondition holds in s:  # choice point
      result ← SEEK-PLAN(s, subtasks(m) + rest, plan)
      if result ≠ failure: return result
  return failure

Ordered task decomposition in the style of SHOP (Nau et al., 1999). SHOP2 extends it to partially ordered subtasks by choosing, at each point, which unordered task comes first. Because tasks are decomposed in the order in which they will be executed, the current state is always known, so method preconditions can call external code, do arithmetic or query databases. The price is that the domain author must write methods that encode good strategies.

SHOP2 (Nau et al., 2003) was among the award winners of the 2002 International Planning Competition, in the track for planners given hand-tailored domain knowledge. HTN planning is also widely used in practice, for example to control non-player characters in video games.

Expressivity and undecidability

Classical planning cannot express everything that HTNs can. The solutions of a STRIPS task form a regular language over actions, since its state space is a finite automaton. A total-order HTN can impose context-free structure: a method that rewrites TT as a T ba\,T\,b, together with one that rewrites TT as nothing, makes the solutions exactly the sequences anbna^nb^n, which no STRIPS task over the same actions can impose (Höller et al., 2014). Partial order adds interleaving, which is more powerful still.

DerivationProof sketch: two grammars in lockstep
  1. L(G1)∩L(G2)=?∅L(G_1)\cap L(G_2)\overset{?}{=}\varnothing

    Reduce from the intersection problem for context-free grammars: given grammars G1G_1 and G2G_2 over an alphabet Σ\Sigma, is L(G1)∩L(G2)L(G_1)\cap L(G_2) nonempty? This is undecidable (Bar-Hillel, Perles & Shamir, 1961).

  2. tn0={S1, S2, finish},S1≺finish,S2≺finish\mathit{tn}_0=\{S_1,\ S_2,\ \mathit{finish}\},\qquad S_1\prec\mathit{finish},\quad S_2\prec\mathit{finish}

    With both grammars in Chomsky normal form, make each nonterminal of GiG_i a compound task, with one method per production: A→BCA\to BC becomes the ordered subnetwork B≺CB\prec C, and A→σA\to\sigma becomes the primitive task emiti(σ)\mathit{emit}_i(\sigma). The initial network holds the two start symbols, unordered, both followed by a primitive task finish\mathit{finish}:

  3. emit1(σ): pre={turn1}, add={lastσ,turn2}, del={turn1}emit2(σ): pre={turn2,lastσ}, add={turn1}, del={turn2,lastσ}\begin{aligned}\mathit{emit}_1(\sigma)&:\ \mathrm{pre}=\{\mathit{turn}_1\},\ \mathrm{add}=\{\mathit{last}_\sigma,\mathit{turn}_2\},\ \mathrm{del}=\{\mathit{turn}_1\}\\ \mathit{emit}_2(\sigma)&:\ \mathrm{pre}=\{\mathit{turn}_2,\mathit{last}_\sigma\},\ \mathrm{add}=\{\mathit{turn}_1\},\ \mathrm{del}=\{\mathit{turn}_2,\mathit{last}_\sigma\}\end{aligned}

    The state synchronizes the two derivations. Initially turn1\mathit{turn}_1 holds; finish\mathit{finish} requires turn1\mathit{turn}_1; the emitting actions pass the turn back and forth and check the letter:

  4. a solution exists  ⟺  L(G1)∩L(G2)≠∅\text{a solution exists}\iff L(G_1)\cap L(G_2)\neq\varnothing

    Any executable interleaving alternates between the two derivations, one letter at a time; each emit2\mathit{emit}_2 must repeat the letter just emitted by emit1\mathit{emit}_1, and finish\mathit{finish} forces the words to have equal length. So a solution exists exactly when some word is derivable in both grammars. Plan existence is semi-decidable, because decompositions can be enumerated, but not decidable.

Check your understanding

The undecidability proof needs an ingredient that total-order HTN planning lacks. Which one?

  1. Variables ranging over infinite domains
  2. Two unordered recursive tasks whose primitive steps can interleave, so that the plan can synchronize two context-free derivations
  3. Numeric fluents
  4. Methods with preconditions
Show the answer

B. Two unordered recursive tasks whose primitive steps can interleave, so that the plan can synchronize two context-free derivations

The construction is propositional and finite; its power comes from interleaving. With total order, the decompositions behave like a single context-free derivation intersected with the finite state space, which is decidable.

When actions have uncertain outcomes

In fully observable nondeterministic (FOND) planning, an action may have several possible effects, and the agent observes which one occurred. A plan becomes a policy mapping states to actions (Cimatti, Pistore, Roveri & Traverso, 2003). A weak solution reaches the goal on some execution; a strong solution reaches it on every execution, within a bounded number of steps; a strong cyclic solution reaches it on every fair execution, possibly after loops (retry the grasp until it succeeds).

In probabilistic planning the outcomes have probabilities, the model is a factored Markov decision process, and the objective is to maximize the probability of reaching the goal or to minimize the expected cost of getting there. When the agent cannot see the state, it plans over belief states, probability distributions over states, as in a POMDP:

b′(s′)=η  O(o∣s′,a)∑sT(s′∣s,a) b(s)b'(s')=\eta\;O(o\mid s',a)\sum_{s}T(s'\mid s,a)\,b(s)
The belief update after action aa and observation oo: predict with the transition model TT, weight by the observation model OO, and renormalize (η\eta). A POMDP is an MDP over this continuous space of beliefs.
SettingQuestionComplexity
Deterministic, fully observable (classical), compact inputplan existencePSPACE-complete (Bylander, 1994)
Nondeterministic, fully observable (FOND), compact inputstrong plan existenceEXPTIME-complete (Rintanen, 2004)
Nondeterministic, unobservable (conformant), compact inputplan existenceEXPSPACE-complete (Haslum & Jonsson, 1999)
Nondeterministic, partially observable, compact inputplan existence2-EXPTIME-complete (Rintanen, 2004)
Explicit MDP, finite horizonoptimal policy valueP-complete (Papadimitriou & Tsitsiklis, 1987)
Explicit POMDP, finite horizona policy with value at least a thresholdPSPACE-complete (Papadimitriou & Tsitsiklis, 1987)
Partially observable probabilistic planning, infinite horizona policy that reaches the goal with probability above a thresholdundecidable (Madani, Hanks & Condon, 2003)
Each loss of determinism or observability costs roughly one exponential. A compact input describes states by variables, as in STRIPS; an explicit one lists the states one by one.

Solving probabilistic planning in practice

Dynamic programming, by value or policy iteration, is exact but enumerates states, exponentially many in the number of state variables. Heuristic search for MDPs explores only the states reachable under promising policies from the initial state: LAO* (Hansen & Zilberstein, 2001) and labeled RTDP (Bonet & Geffner, 2003), guided by admissible heuristics that are often computed on a deterministic relaxation.

Determinization turns each probabilistic action into deterministic ones, one per outcome (or keeps only the most likely outcome), plans with a classical planner, executes, and replans whenever something unexpected happens. FF-Replan (Yoon, Fern & Givan, 2007) did exactly this with FF and won the first International Probabilistic Planning Competition, in 2004, a result that surprised the field. It fails on probabilistically interesting problems (Little & Thiébaux, 2007), where a short but risky route can lead into a dead end, because the all-outcomes determinization lets the planner choose the lucky outcome.

Check your understanding

Why can all-outcomes determinization, as in FF-Replan, choose a disastrous plan?

  1. Because FF cannot handle actions with several effects
  2. Because replanning after every step is too slow
  3. It lets the planner choose which outcome of an action occurs, so a route that works only if an unlikely outcome happens looks as good as a safe one
  4. Because it minimizes expected cost with too short a horizon
Show the answer

C. It lets the planner choose which outcome of an action occurs, so a route that works only if an unlikely outcome happens looks as good as a safe one

Each outcome becomes a separate deterministic action, and the classical planner picks whichever sequence is cheapest, including one that relies on luck. Replanning repairs ordinary surprises, but not a fall into a dead end from which the goal is unreachable.

Monte Carlo tree search handles such risks by sampling outcomes: PROST (Keller & Eyerich, 2012), based on UCT, won the probabilistic tracks of the 2011 and 2014 competitions. For POMDPs, point-based value iteration (Pineau, Gordon & Thrun, 2003) and online Monte Carlo planning such as POMCP (Silver & Veness, 2010) scale far beyond exact methods.

Key takeaways

  • HTN planning refines tasks with methods. Ordered task decomposition, as in SHOP and SHOP2, always knows the current state, so rich domain knowledge can make search fast.
  • With partially ordered networks, HTN plan existence is undecidable, by reduction from context-free grammar intersection; propositional total-order HTN is EXPTIME-complete, and HTNs express plan languages that STRIPS cannot.
  • Under nondeterminism, plans become policies (weak, strong, strong cyclic). With compact inputs, FOND planning is EXPTIME-complete, conformant planning EXPSPACE-complete and partially observable planning 2-EXPTIME-complete; finite-horizon POMDPs are PSPACE-complete, and infinite-horizon goal-probability questions undecidable.
  • In practice: heuristic search for MDPs (LAO*, LRTDP), determinization with replanning (FF-Replan), which fails on probabilistically interesting problems, and Monte Carlo tree search (PROST).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why is HTN plan existence undecidable with partially ordered task networks, while classical plan existence is decidable?

  1. HTN methods have preconditions, which classical actions lack
  2. HTN problems have no goal formula
  3. HTN planning allows infinitely many objects
  4. Unordered recursive tasks can interleave and synchronize two context-free derivations, which encodes grammar intersection, whereas a classical state space is a finite automaton
Show the answer

D. Unordered recursive tasks can interleave and synchronize two context-free derivations, which encodes grammar intersection, whereas a classical state space is a finite automaton

The reduction from context-free grammar intersection needs only propositional facts and interleaving. A classical state space is finite, so plan existence is decidable there, though PSPACE-complete.

Question 2

Plan existence for nondeterministic actions with no observations (conformant planning), given a compact propositional description, is…

  1. PSPACE-complete
  2. EXPSPACE-complete
  3. EXPTIME-complete
  4. 2-EXPTIME-complete
Show the answer

B. EXPSPACE-complete

A conformant plan must work from every possible state at once, so the search runs over belief states, which are sets of states and therefore exponentially large objects. Haslum & Jonsson (1999) proved the problem EXPSPACE-complete.

Question 3

A pickup action either succeeds or fails, leaving the state unchanged. The policy "pick up until holding" is…

  1. a strong solution
  2. only a weak solution
  3. a strong cyclic solution: every fair execution reaches the goal, though no fixed bound on its length exists
  4. not a solution, because it may loop forever
Show the answer

C. a strong cyclic solution: every fair execution reaches the goal, though no fixed bound on its length exists

If every outcome eventually occurs (fairness), the loop is exited for certain; with success probability pp per attempt it takes 1/p1/p attempts on average. No bound holds for all executions, so the solution is not strong.

Question 4

For an explicitly listed POMDP with a finite horizon, deciding whether some policy achieves at least a given value is…

  1. PSPACE-complete
  2. P-complete
  3. NP-complete
  4. undecidable
Show the answer

A. PSPACE-complete

Papadimitriou & Tsitsiklis (1987) proved it PSPACE-complete, whereas the fully observable version is P-complete. With an infinite horizon, related POMDP questions become undecidable (Madani, Hanks & Condon, 2003).

Further reading

  • K. Erol, J. Hendler & D. S. Nau, "HTN planning: complexity and expressivity," Proceedings of AAAI (1994).
  • D. Nau, T.-C. Au, O. Ilghami, U. Kuter, J. W. Murdock, D. Wu & F. Yaman, "SHOP2: an HTN planning system," Journal of Artificial Intelligence Research 20 (2003), 379–404.
  • P. Bercher, R. Alford & D. Höller, "A survey on hierarchical planning: one abstract idea, many concrete realizations," Proceedings of IJCAI (2019).
  • S. Yoon, A. Fern & R. Givan, "FF-Replan: a baseline for probabilistic planning," Proceedings of ICAPS (2007).
  • O. Madani, S. Hanks & A. Condon, "On the undecidability of probabilistic planning and related stochastic optimization problems," Artificial Intelligence 147(1–2) (2003), 5–34.