Optimal depth-first strategies for and-or trees

Many tasks require evaluating a specified boolean expression rho over a set of probabilistic tests where we know the probability that each test will succeed, and also the cost of performing each test. A strategy specifies when to perform which test, towards determining the overall outcome of rho. This paper investigates the challenge of finding the strategy with the minimum expected cost. We observe first that this task is typically NP-hard - e.g., when tests can occur many times within rho, or when there are probabilistic correlations between the test outcomes. We therefore focus on the situation where the tests are probabilistically independent and each appears only once in rho. Here, rho can be written as an and- or tree, where each internal node corresponds to either the "And" or "Or" of its children, and each leaf node is a probabilistic test. There is an obvious depth-first approach to evaluating such and-or trees: First evaluate each penultimate subtree in isolation; then reduce this subtree to a single "mega-test" with an appropriate cost and probability, and recur on the resulting reduced tree. After formally defining this approach, we prove first that it produces the optimal strategy for shallow (depth 1 or 2) and-or trees, then show it can be arbitrarily bad for deeper trees. We next consider a larger natural subclass of strategies - those that can be expressed as a linear sequence of tests - and show that the best such "linear strategy" can also be very much worse than the optimal strategy in general. Finally, we show that our results hold in a more general model, where internal nodes can also be probabilistic tests.