- 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:
- 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.
- If goal is reached then success otherwise fail.
- The general problem is to find a solution that satisfies a set of constraints.
- heuristics used not to estimate the distance to the goal but to decide what node to expand nest.
- Examples of this technique are design problem, labelling graphs, robot path planning and cryptarithmetic puzzles (see last year).
Algorithm:
- Propagate available constraints:
- Open all objects that must be assigned values in a complete solution.
- Repeat until inconsistency or all objects assigned valid valid values:
- select an object and strengthen as much as possible the set of constraints that apply to object.
- If set of constraints different from previous set then open all objects that share any of these constraints.
- remove selected object.
- If union of constraints discovered above defines a solution return solution.
- If union of constraints discovered above defines a contradiction return failure
- Make a guess in order to proceed. Repeat until a solution is found or all possible solutions exhausted:
- select an object with a no assigned value and try to strengthen its constraints.
- recursively invoke constraint satisfaction with the current set of constraints plus the selected strengthening constraint.
