Algorithms for Classical Planning
The description of a planning problem provides an obvious way to search from the initial state through the space of states, looking for a goal. A nice advantage of the declarative representation of action schemas is that we can also search backward from the goal, looking for the initial state. A third possibility is to translate the problem description into a set of logic sentences, to which we can apply a logical inference algorithm to find a solution.
Forward planning
Search in the state space from the initial state to a state satisfying the goal and the formulation is the one of a classical search problem.
| Search problem | Forward planning |
|---|---|
| initial state | initial state |
| ACTIONS(s) | instances of action schemas applicable in π |
| RESULT(s,a) | application of π΄ in π |
| goal test | is the goal satisfied in the current state? |
| step cost | cost of applying actions (unitary, in some cases) |
We can solve planning problems by applying any of the heuristic search algorithms.
The states in this search state space are ground states, where every fluent is either true or not. The goal is a state that has all the positive fluents in the problemβs goal and none of the negative fluents. The applicable actions in a state, Actions(s), are grounded instantiations of the action schemasβthat is, actions where the variables have all been replaced by constant values.
To determine the applicable actions we unify the current state against the preconditions of each action schema. For each unification that successfully results in a substitution, we apply the substitution to the action schema to yield a ground action with no variables.
Forward planning problems
- Forward planning can be inefficient, for example when the number of possible actions is large and the branching factor is large.
- Usually, there are much more actions that are applicable in a state than actions that are relevant to reach a goal
- Need for accurate heuristics
Backward planning
In backward search (also called regression search) we start at the goal and apply the actions backward until we find a sequence of steps that reaches the initial state. At each step we consider relevant actions (in contrast to forward search, which considers actions that are applicable). This reduces the branching factor significantly, particularly in domains with many possible actions.
A relevant action is one with an effect that unifies with one of the goal literals, but with no effect that negates any part of the goal.
The regression of a goal πΊ through a relevant action π΄ is the less constraining goal π [πΊ, π΄] such that, given a state π that satisfies π [πΊ, π΄]:
- The preconditions of π΄ are satisfied in π
- The application of π΄ in π reaches a state πβ that satisfies πΊ
That is, the preconditions must have held before, or else the action could not have been executed, but the positive/negative literals that were added/deleted by the action need not have been true before.
| Search problem | Backward planning |
|---|---|
| initial state | goal |
| ACTIONS(s) | actions that allow the regression of a sub-goal πΊ |
| RESULT(s,a) | regression of a sub-goal πΊ through an action π΄ |
| goal test | is the goal satisfied in the initial state? |
| step cost | cost of applying actions (unitary, in some cases) |