AND/OR graph

From Semantic Portal Wiki

definition

An AND/OR graph G is a directed graph with a special node s, called the start (or root) node, and a nonempty set of terminal leaf nodes t, t1, t2,....

The start node s represents the given problem to be solved
The terminal leaf nodes correspond to subproblems with known solutions.
The nonterminal nodes m, n, p,q,r,... of G are of three types: OR, AND, and nonterminal leaf.
- An OR node can be solved in any one of a number of alternative ways,
- An AND node is solved only when every one of its immediate subproblems is solved.
- A nonterminal leaf node has no successors and is unsolvable.

Note: it seems that "AND/OR graph" and "AND/OR tree" are used interchangeably

A solution graph D(m) with root m is a finite subgraph of G with the following properties

m is in D(m)
for any OR node in D(m), D(m) should contain exactly one its immediate successor in G
for any AND node in D(m), D(m) should have all its immediate successors in G.
every maximal (direct) path in D(m) ends in a terminal leaf node.