Many seach problems, both combinatorial and AI, can be usefully and elegantly abstracted in terms of a constrained AND/OR tree.
An AND/OR tree is a tree (or, just as frequently, a DAG) whose internal nodes are labelled either "AND" or "OR". A valuation of an AND/OR tree is an assignment of "TRUE" or "FALSE" to each of the leaves. Given a tree T and a valuation over the leaves of T, the values of the internal nodes and of T are defined recursively in the obvious way:
The above is an unconstrained AND/OR tree. Also common are constrained AND/OR trees, in which the leaves labelled "TRUE" must satisfy some kind of constraint. A solution to a constrained AND/OR tree is a valuation that satisfies the constraint and gives the tree the value "TRUE".
A number of different forms of problems over constrained AND/OR trees appear:
As we shall see, constraints come in all sizes, shapes, and flavors. We will not attempt to develop here a formal language of constraints; rather, we will just describe each constraint in English. Thus, our aim here is to develop a way of thinking about problems, more than a full-blown formalism.
An AND-OR tree is similar to the idea, in computation theory, of an alternating Turing machine, in the same sense that a non-deterministic algorithm is similar to a non-deterministic Turing machine.
We begin for simplicity with a few combinatorial problems (as it happens, four NP-complete problems). These all involve three-level AND/OR trees, where the root is an AND node; its children are OR nodes; and their children are the leaves. The tree is given explicitly; it is just a rewording of the problem.
(P or Q or not R) and (not P or R or not S) and (P or not Q or S)
We now turn to AI problems. The trees here are often given implicitly rather than explicitly. It is thus important to generate as little of the tree as possible.
The problem is, given a set of axioms in Horn clause form and a goal, show that the goal can be proven from the axioms.
An OR node is a goal to be proven. A goal G has one downward arc for each rule R whose head resolves with G. This leads to an AND node. The children in the AND node are the literals in the tail of R. Thus, a rule is satified if all its subgoals are satisfied (the AND node); a goal is satisfied if it is established by one of its rules (the OR node). The leaves are unit clauses, with no tail, labelled TRUE, and subgoals with no matching rules, labelled FALSE . The constraint is that the variable bindings must be consistent. The figure below show the AND/OR tree corresponding to the following Prolog rule set with the goal "common_ancestor(Z,edward,mary)"
Axioms: /* Z is a common ancestor of X and Y */ R1: common_ancestor(Z,X,Y) :- ancestor(Z,X), ancestor(Z,Y). /* Usual recursive definition of ancestor, going upward. */ R2: ancestor(A,A). R3: ancestor(A,C) :- parent(B,C), ancestor(A,B). /* Mini family tree */ R4: parent(catherine,mary). R5: parent(henry,mary). R6: parent(jane,edward). R7: parent(henry,edward).
S -> NP VP NP -> pronoun NP -> noun VP -> VG VP -> VG NP VG -> verb VG -> modal verb pronoun -> "I" noun -> "fish" modal -> "can" verb -> "can" verb -> "fish"Let N be the number of words in P (3 in our example) An OR node is a pair of a non-terminal T with a subinterval I of [1 .. N]. In our example, one OR node would be the pair < VP, [2..3]>, where [2..3] represents the substring "can fish". The children of the OR node are AND nodes. Each such AND node consists of a pairing of the right-hand side of a production from T together with a corresponding partition of I.
For example, the pair < VP, [2..3]> has two children:
solve-ANDOR (in T : OR node; out L : set of OR nodes and leaves)
G : OR node;
C : AND node or leaf
begin L := { T };
repeat until L contains only leaves
pick an OR-node G in L and delete it from L;
choose a child C of G;
add the children of C to L;
if it can be determined that there is no valuation consistent with
the constraint in which all the nodes of L are TRUE
then fail;
end repeat;
return L;
end.
The keywords "pick", "choose" and "fail" are defined as in (Russell and Norvig, 1995, p. 855). That is, "pick" is a choice which may be made arbitrarily, but only one choice need be considered in the state space search. "Choose" is a non-deterministic choice; all sequential combinations of choices are considered through some search technique, and a path of choices that leads to success must be found. "Fail" marks an unsuccessful path of choices.
The state space being searched here may be defined as follows: A state is a set L of OR nodes and leaves. The start state is the singleton set of the root of the tree. The operators on set L are to remove an OR-node G from L, to choose a child C of G and to add its children to L. L is a goal state if it contains only leaves, and if there is a consistent valuation in which all the leaves in L have value TRUE. The search can be pruned if it can be determined that L cannot be extended to a complete valuation that satisfies the constraint. Note that the way in which "pick" is carried out determines the state space; the way in which "choose" is done determines the form of the search through the state space.
For example, consider the problem of finding a valuation satisfying the boolean formula
((P and (Q or R)) or ((not P) and (not Q or R)) or ((not Q) and (not R))) and ((not P or Q) and (P or not Q)) or not R) andThe figures below show the corresponding AND/OR tree, and part of a possible state space in which the set L is implemented as a stack.
((not P and not Q) or R)
How the condition "V cannot be extended to a complete valuation satisfying the constraint" is to be effectuated depends on the nature of the constraint, the cleverness of the programmer, and the trade-off between the cost of performing a complex check here and the gain from pruning the search. Obviously, there is in general no simple way to compute necessary and sufficient conditions for this pruning; if there were, then the problem would be easily solved. Some general categories of pruning rules can be described:
Similar non-deterministic algorithms can be written for the optimization, evaluation, and validation problems.
Prolog style search can be implemented by (a) implementing S as a FIFO stack; (b) adding the children of C at the front of S in order from left to right; (c) exploring the choices of C in a depth-first search from left to right among the children of G. Other search protocols can be implemented by modifying the way in which the "pick" and "choose" are carried out.