And-Or Graphs

Useful for certain problems where

• The solution involves decomposing the problem into smaller problems.
• We then solve these smaller problems.

Here the alternatives often involve branches where some or all must be satisfied before we can progress.

For example if I want to learn to play a Frank Zappa guitar solo I could (Fig. 2.2.1)

• Transcribe it from the CD. OR
• Buy the ``Frank Zappa Guitar Book'' AND Read it from there.

Note the use of arcs to indicate that one or more nodes must all be satisfied before the parent node is achieved. To find solutions using an And-Or GRAPH the best first algorithm is used as a basis with a modification to handle the set of nodes linked by the AND factor.

Inadequate: CANNOT deal with AND bit well.