Means-Ends Analysis

• Allows both backward and forward searching.
• This means we could solve major parts of a problem first and then return to smaller problems when assembling the final solution.
• GPS was the first AI program to exploit means-ends analysis.
• STRIPS (A robot Planner) is an advanced problem solver that incorporates means-ends analysis and other techniques.

Very loosely the means-ends analysis algorithm is:

1. Until the goal is reached or no more procedures are available:
   • Describe the current state, the goal state and the differences between the two.
   • Use the difference the describe a procedure that will hopefully get nearer to goal.
   • Use the procedure and update current state.
2. If goal is reached then success otherwise fail.

See last year's course for numerous examples of this.