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. )

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

Fig. And-Or Graph

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.

For further detail on And-Or Graphs see (Last year's AI1 notes Lecture 12).