Constrained AND/OR trees

Many seach problems, both combinatorial and AI, can be usefully and elegantly abstracted in terms of a constrained AND/OR tree.

Definitions

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.

Combinatorial Examples

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.

CNF Boolean formulas (SAT)

A Boolean formula in CNF is a constrained AND/OR tree of three levels. The root is an AND node; the clauses are OR nodes; the leaves are the literals; and the constraint is that an atom and its negation must have opposite truth values. The figure below shows the AND/OR tree for the formula
(P or Q or not R) and (not P or R or not S) and (P or not Q or S)

Vertex cover

The problem is, given an undirected graph, find the smallest set S of vertices such that every edge has at least one endpoint in S. The leaves of the AND/OR tree are the vertices of the graph. Each edge is an OR node. There is no constraint. The objective function to be maximized is the number of leaves marked "FALSE".

Hamiltonian cycle

The problem is, given a directed graph in G, find a cycle through G that goes exactly once through each vertex. The leaves are the edges. Each vertex V is an OR node, whose children are the outarcs from V. The constraint is that the arc corresponding to the leaves marked TRUE in the valuation form a single cycle.

Minimal set cover

The problem is, given a set O and a collection C of subsets of O, find the smallest subcollection S of C such that each element of O is in exactly one set in S. The AND/OR tree has three levels. The root is an AND node. There is an OR node for each element X of S; its children are the sets in C that contains X. There is no constraint. The objective function to be maximized is the number of nodes marked "FALSE".

AI Examples

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.

Horn clause logic

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

Parsing a sentence P using a Context Free Grammar G

As an example, let P be the sentence "I can fish" and let G be the grammar
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:

The pair < S,[1..3]> has two children: A list of this kind is an AND node whose children are the elements of the list. The leaves of the tree are pairs of a terminal with a location. The problem is, given the tree in the implicit form of the grammar, establish that the value of the tree is indeed TRUE by identifying a subtree of nodes labelled TRUE connecting the root with the leaves. Note that adding constraints of various kinds to the grammar corresponds to turning this unconstrained AND/OR tree to a constrained AND/OR tree.

Planning

In general, in planning, an AND node is a step of the plan; its children are all its preconditions. That is, all the preconditions must hold in order to carry out the step. An OR node is any subgoal; its chidren are all the different actions that would achieve that goal. (Charniak and McDermott, 1985, pp. ??) For instance An SNLP planner (Weld ??) can be viewed as a satisfaction problem over the following AND/OR tree. An OR node is an unsatisfied precondition Q in some partially specified plan P. Its children are all the ways in which P can be extended to satisfy Q, either with a causal links or with a new step and a causal link. An AND node is a new step in the plan; its OR nodes are all its preconditions. The constraint on the leaves is that the causal links are all sound.

Relation to state spaces

A constrained AND/OR tree can be solved using the following non-deterministic algorithm. We will assume, without loss of generality, (a) that the root of the tree is an OR node; (b) that the leaves of the tree are all children of AND nodes; (c) that AND nodes and OR nodes strictly alternate: that is, every child of an AND node is an OR node and vice versa. Any AND/OR tree can easily be modified to conform to this rule (if necessary, by adding dummy nodes with one child.)
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) and 
((not P and not Q) or R)
The 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.

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.

Back to course home page