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

Advanced Search
Home   
 
Browse   
Communities
& Collections
  
Issue Date   
Author   
Title   
Subject   
 
Sign on to:   
Receive email
updates
  
My Account
authorized users
  
Edit Profile   
 
Help   
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
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 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
View/Open

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

uoft