If we are looking for a sequence of actions to achieve some goal, then one way to do it is to use state-space search, where each node in you search space is a state of the world, and you are searching for a sequence of actions that get you from an initial state to a final state. However, another way is to consider the different ways that the goal state can be decomposed into simpler subgoals. For example, when planning a trip to London you probably don't want to search through all the possible sequences of actions that might get you to London. You're more likely to decompose the problem into simpler ones - such as getting to the station, then getting a train to London. There may of course be more than one possible way of decomposing the problem - an alternative strategy might be to get to the airport, fly to Heathrow, and get the tube from Heathrow into London. These different possible plans would have different costs (and benefits) associated with them, and you might have to choose the best plan.
The simple state-space search techniques described above could all be represented using a tree where each successor node represents an alternative action to be taken. The graph structure being searched is referred to as an OR graph. To represent problem reduction techniques we need to use an AND-OR graph/tree. Here, you can have and nodes whose successors must all be achieved, and or nodes where one of the successors must be achieved (ie, they are alternatives). This allows us to represent both cases where ALL of a set of subgoals must be satified to achieve some goal, and where there are alternative subgoals, any of which could achieve the goal. We can represent some of our options for travelling to London by the following AND-OR tree, where sets of goals all of which must be satisfied are indicated by a line connecting all the components (fig below).
In this example we have alternating levels of AND nodes and OR nodes. Successors of AND nodes represent goals to be jointly achieved. Successors of OR nodes represent different ways of achieving a goal. Some AND-OR trees have levels that involve both AND and OR nodes, but this tends to be less clear.
To find a way to get to London we need to search this tree to find a set of simple goals that we trivially know how to satisfy. Maybe ordering a taxi is a primitive goal - we could decompose it into ``pick up phone, dial number ..'' but this wouldn't be very helpful. Anyway, we need to apply our basic ideas of tree/graph search to searching AND-OR trees/graphs.
There are many possible ways of searching AND-OR graphs. One way is to effectively tranform them back into OR graphs where each node represents a whole set of goals to be satisfied. So, in terms of our search algorithsm each item on the agenda (/open node list) is a set of goals. Finding a successor to an item on the agenda involves picking a non-primitive goal (say G) from this set of goals and finding possible subgoals for that goal. If the node (corresponding to G) was an AND node then there is a single successor which is a set of goals with the goal G replaced by its subgoals. If the node was an OR node then there will be several possible successor node, each being a set of goals with G replaced by a possible successor. A final ``goal state'' in these terms will be a set of directly executable or primitive goals/actions, and our node lists will be lists of lists of goals, where each sublist will represent a partially developed possible plan. An example node list might be the following:
open = [[cycle-to-QS, get-train],[walk-to-QS, get-train], [get-to-airport, get-plane, get-tube]]
Things get slightly more complex when you want to use heuristic search. Then we have to evaluate the ``goodness'' of a whole set of goals. If each goal has an associated (approximate) cost, then the cost of a set of goals will just be the sum of these costs.
Rich &Knight give a rather different algorithm for searching AND-OR trees. The above is simpler, but will lead to non-optimal performance. In particular, it will result in some redundant work. The goal get-train may be exanded out twice, once in the context of cycling to the station and once in the context of walking there! As the different subgoals are meant to be independent this really shouldn't be necessary, and more specialized AND-OR graph search techniques will ensure both that we don't have to work out how to take a train to London (or whatever) twice, and that any estimates of costs of nodes are updated (to be more accurate) once we have worked out how to satisfy a goal.
Note that AND-OR graph (or tree) search techniques are needed if we want to use backward chaining to prove something given a set of rules of the form ``IF A AND B AND ... THEN C''. The problem of proving (say) C is being reduced to the problems of proving A and proving B etc. In fact, we can view Prolog's built in search strategy as implementing a simple AND-OR tree search.