Next: Goal Stack Planning Up: Planning System Components Previous: Rule application

### Detecting Progress

The final solution can be detected if

• we can devise a predicate that is true when the solution is found and is false otherwise.
• requires a great deal of thought and requires a proof.

Detecting false trails is also necessary:

• E.g. A* search -- if insufficient progress is made then this trail is aborted in favour of a more hopeful one.
• Sometimes it is clear that solving a problem one way has reduced the problem to parts that are harder than the original state.
• By moving back from the goal state to the initial state it is possible to detect conflicts and any trail or path that involves a conflict can be pruned out.
• Reducing the number of possible paths means that there are more resources available for those left.

Supposing that the computer teacher is ill at a school there are two possible alternatives

• transfer a teacher from mathematics who knows computing or
• bring another one in.

Possible Problems:

• If the maths teacher is the only teacher of maths the problem is not solved.
• If there is no money left the second solution could be impossible.

If the problems are nearly decomposable we can treat them as decomposable and then patch them, how?

Consider the final state reached by treating the problem as decomposable at the current state and noting the differences between the goal state and the current state and the goal state and the initial state and use appropriate Means End analysis techniques to move in the best direction.

Better is to work back in the path leading to the current state and see if there are options. It may be that one optional path could lead to a solution whereas the existing route led to a conflict.

Generally this means that some conditions are changed prior to taking an optional path through the problem.

Another approach involves putting off decisions until one has to, leaving decision making until more information is available and other routes have been explored. Often some decisions need not be taken as these nodes are never reached.

Next: Goal Stack Planning Up: Planning System Components Previous: Rule application

dave@cs.cf.ac.uk