Forward Search

Forward-search is sound

Any plan that is returned is guaranteed to be a solution

Forward-search also is complete

If a solution exists then Forward-search will return a solution.

Search proceeds as follows:

1. The algorithm starts the search at the initial state.
2. If the initial state satisfies the goal, then search ends and we get a plan of length zero.
3. If not, the algorithm applies all applicable actions to the initial state to produce new states.
4. It checks if any of the new states satisfies the goal.
5. If yes, search ends.
6. If not, then search continues by applying actions to each of the new states.
7. Search continues until either all reachable states have been examined or a goal state has been reached.
8. If a goal state is reached, the algorithm returns the sequence of actions that led from the initial state to the found goal state.

Some deterministic implementations of forward search:

• breadth-first search
• best-first search (e.g., A*)

Breadth-first and best-first search are sound and complete.

• But they usually aren’t practical because they require too much memory.
• Memory requirement is exponential in the length of the solution.

Forward search can have a very large branching factor.

• E.g., many applicable actions that don’t progress toward goal.
• Why this is bad:
  • Deterministic implementations can waste time trying lots of irrelevant actions.
• Need a good heuristic function and/or pruning procedure.