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 might have a method "walk", applicable when is near , and a method "by taxi", which decomposes into , and , 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.
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 failureOrdered 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 as , together with one that rewrites as nothing, makes the solutions exactly the sequences , which no STRIPS task over the same actions can impose (Höller et al., 2014). Partial order adds interleaving, which is more powerful still.
Reduce from the intersection problem for context-free grammars: given grammars and over an alphabet , is nonempty? This is undecidable (Bar-Hillel, Perles & Shamir, 1961).
With both grammars in Chomsky normal form, make each nonterminal of a compound task, with one method per production: becomes the ordered subnetwork , and becomes the primitive task . The initial network holds the two start symbols, unordered, both followed by a primitive task :
The state synchronizes the two derivations. Initially holds; requires ; the emitting actions pass the turn back and forth and check the letter:
Any executable interleaving alternates between the two derivations, one letter at a time; each must repeat the letter just emitted by , and 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.
The undecidability proof needs an ingredient that total-order HTN planning lacks. Which one?
- Variables ranging over infinite domains
- Two unordered recursive tasks whose primitive steps can interleave, so that the plan can synchronize two context-free derivations
- Numeric fluents
- 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:
| Setting | Question | Complexity |
|---|---|---|
| Deterministic, fully observable (classical), compact input | plan existence | PSPACE-complete (Bylander, 1994) |
| Nondeterministic, fully observable (FOND), compact input | strong plan existence | EXPTIME-complete (Rintanen, 2004) |
| Nondeterministic, unobservable (conformant), compact input | plan existence | EXPSPACE-complete (Haslum & Jonsson, 1999) |
| Nondeterministic, partially observable, compact input | plan existence | 2-EXPTIME-complete (Rintanen, 2004) |
| Explicit MDP, finite horizon | optimal policy value | P-complete (Papadimitriou & Tsitsiklis, 1987) |
| Explicit POMDP, finite horizon | a policy with value at least a threshold | PSPACE-complete (Papadimitriou & Tsitsiklis, 1987) |
| Partially observable probabilistic planning, infinite horizon | a policy that reaches the goal with probability above a threshold | undecidable (Madani, Hanks & Condon, 2003) |
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.
Why can all-outcomes determinization, as in FF-Replan, choose a disastrous plan?
- Because FF cannot handle actions with several effects
- Because replanning after every step is too slow
- 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
- 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.
Why is HTN plan existence undecidable with partially ordered task networks, while classical plan existence is decidable?
- HTN methods have preconditions, which classical actions lack
- HTN problems have no goal formula
- HTN planning allows infinitely many objects
- 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.
Plan existence for nondeterministic actions with no observations (conformant planning), given a compact propositional description, is…
- PSPACE-complete
- EXPSPACE-complete
- EXPTIME-complete
- 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.
A pickup action either succeeds or fails, leaving the state unchanged. The policy "pick up until holding" is…
- a strong solution
- only a weak solution
- a strong cyclic solution: every fair execution reaches the goal, though no fixed bound on its length exists
- 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 per attempt it takes attempts on average. No bound holds for all executions, so the solution is not strong.
For an explicitly listed POMDP with a finite horizon, deciding whether some policy achieves at least a given value is…
- PSPACE-complete
- P-complete
- NP-complete
- 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.