
TSpace at The University of Toronto Libraries >
University of Toronto at Scarborough >
Computer and Mathematical Science >
Mathematics >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1807/9521

Title:  Optimal depthfirst strategies for andor trees 
Authors:  Molloy, M. Greiner, R. Hayward, R. 
Keywords:  Computational complexity Diagnosis Satisficing search Algorithms Tree Artificial intelligence Boolean expressions Correlation methods Costs Mathematical models Probability Theorem proving Boolean expressions 
Issue Date:  2002 
Publisher:  AAAI Press 
Citation:  Greiner, R., Hayward, R., & Molloy, M. (2002). Optimal depthfirst strategies for andor trees. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton, Alberta, Canada (pp. 725730). AAAI Press. 
Abstract:  Many tasks require evaluating a specified boolean expression φ 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 φ. This paper investigates the challenge of finding the strategy with the minimum expected cost. We observe first that this task is typically NPhard  e.g., when tests can occur many times within φ, 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 φ. Here, φ can be written as an andor 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 depthfirst approach to evaluating such andor trees: First evaluate each penultimate subtree in isolation; then reduce this subtree to a single "megatest" 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) andor 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. 
Description:  www.aaai.org 
URI:  http://hdl.handle.net/1807/9521 
Appears in Collections:  Mathematics

Items in TSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
