test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space 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 depth-first strategies for and-or trees
Authors: Molloy, M.
Greiner, R.
Hayward, R.
Keywords: Computational complexity
Satisficing search
Artificial intelligence
Boolean expressions
Correlation methods
Mathematical models
Theorem proving
Boolean expressions
Issue Date: 2002
Publisher: AAAI Press
Citation: Greiner, R., Hayward, R., & Molloy, M. (2002). Optimal depth-first strategies for and-or trees. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton, Alberta, Canada (pp. 725-730). 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 NP-hard - 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 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.
Description: www.aaai.org
URI: http://hdl.handle.net/1807/9521
Appears in Collections:Mathematics

Files in This Item:

File Description SizeFormat
Optimal depth-first strategies for and-or trees.pdf364.15 kBAdobe PDF

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.