01
What planning means
Planning is the synthesis of actions that transform an initial condition into a desired goal state. Unlike a simple reaction, planning requires a model of actions and their consequences and therefore supports reasoning about sequences.
Classical planning assumes a fully observable, deterministic and discrete environment. These assumptions are useful because they make the problem precise, even though physical environments usually violate them.
02
STRIPS and PDDL
STRIPS describes actions through preconditions and effects. An action is applicable when its preconditions are satisfied, after which its effects update the state.
Action Move(x, A, B) Precondition: At(x,A) ∧ Clear(B) Effect: At(x,B) ∧ ¬At(x,A)
PDDL later provided a standard language for describing planning domains and problems. It supports richer objects, predicates and extensions such as time and numeric resources.
03
Planning algorithms
- Forward state-space search explores action sequences from the initial state.
- Backward reasoning starts from the goal and asks which actions could produce it.
- Planning graphs compactly represent reachable propositions and actions across layers.
- SAT-based planners encode bounded planning as satisfiability.
- Heuristic planners estimate solution cost using relaxed planning problems.
04
Hierarchical planning
Hierarchical Task Network planning decomposes abstract tasks into smaller subtasks. The method introduces domain knowledge about how a task should be performed, reducing the search space at the cost of requiring carefully designed decomposition rules.
05
Planning under uncertainty
When outcomes are stochastic, the problem moves from deterministic planning toward decision theory and reinforcement learning. Markov decision processes model states, actions, transition probabilities and rewards. The desired result is a policy rather than a single guaranteed sequence.
When the state itself is only partially observable, the agent must maintain beliefs over possible world states. This leads to partially observable Markov decision processes, which are substantially more difficult computationally.