next up previous
Next: AO* Algorithm Up: Knowledge Representation and Search Previous: Knowledge Representation and Search

And-Or Graphs

Useful for certain problems where

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)

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.



dave@cs.cf.ac.uk