Next: Blocks World Planning Examples Up: Planning I Previous: What does planning involve?

## Search in Planning

Search basically involved moving from an Initial state to a Goal State. Classic search techniques could be applied to planning state in this manner:

A* Algorithm
-- best first search,
Problem decomposition
-- Synthesis, Frame Problem.
AO* Algorithm
-- Split problem into distinct parts.
Heuristic reasoning
-- ordinary search backtracking can be hard so introduce reasoning to devise heuristics and to control the backtracking.

The first major method considered the solution as a search from the initial state to a goal state through a state space. There are many ways of moving through this space by using operators and the A* algorithm described the best first search through a graph. This method is fine for simpler problems but for more realistic problems it is advisable to use problem decomposition. Here the problem is split into smaller sub problems and the partial solutions are then synthesised. The danger in this method occurs when certain paths become abortive and have to be discarded. How much of the partial solution can be saved and how much needs to be recomputed.

The frame problem -- deciding which things change and which do not -- gave some guidance on enabling us to decide on what stays the same and on what changes as we go from state to state. If the problem concerned designing a robot to build a car then mounting the engine on the chassis would not affect the rear of the car nowadays.

The AO* algorithm enabled us to handle the solution of problems where the problem could be split into distinct parts and then the partial solutions reassembled. However difficulties arise if parts interacted with one another. Most problems have some interaction and this implies some thought into the ordering of the steps; for example if the robot has to move a desk with objects on it from one room to another; or to move a sofa from one room to another and the piano is near the doorway. The thought process involved in recombining partial solutions of such problems is known as planning. At this point we run into a discussion about the role of the computer in the design of a plan as to how we can solve a problem. It is extremely unlikely at this stage that a computer will actually solve the problem unless it is a game and here some interaction with a person is needed.

Generally the computer is used to decide upon or to offer words of wisdom on the best method of approaching the solution of a problem. In one sense this can be interpreted as a simulation; if we are considering the handling of queues at an airport or a post office there are no actual people and so we can try a range of possibilities; likewise in a traffic control problem there are no cars or aircraft piling up at a junction or two miles over an airport. Once the computer based investigation has come up with the best solution we can then implement it at the real site.

This approach assumes that there is continuity in the way of life. It cannot budget for rapid change or revolution. How can this approach cater for unexpected events such as a faulty component or a spurious happening such as two items stuck together or a breakdown in the path somewhere vital such as in a camera reel. When a fault or some unrecognisable state is encountered it is not necessary to restart for much of what has been successfully solved is still useful. Consider a child removing the needles from a partially completed knitted sweater. The problem lies in restarting from a dead end and this will need some backtracking. This method of solution is pursued to reduce the level of complexity and so to ensure successful handling we must introduce reasoning to help in the backtracking required to cater for faults. To assist in controlling backtracking many methods go backward from the goal to an initial state.

Next: Blocks World Planning Examples Up: Planning I Previous: What does planning involve?

dave@cs.cf.ac.uk