Finding optimal satisficing strategies for and-or trees

摘要: Many tasks require evaluating a specified Boolean expression @f over set of probabilistic tests whose costs and success probabilities are each known. A strategy specifies when to perform which test, towards determining the overall outcome @f. We interested in finding with minimum expected cost. As this task is typically NP-hard-for example, can occur many times within @f, or there correlations between test outcomes-we consider those cases probabilistically independent appears only once In such cases, be written as an and-or tree, where internal node corresponds either ''and'' ''or'' its children, leaf test. paper we investigate ''probabilistic tree resolution'' (PAOTR), namely problem optimal strategies for trees. first depth-first approach: evaluate penultimate rooted subtree isolation, replace single ''mega-test'', recurse on resulting reduced tree. show that produced by approach trees depth at most two but arbitrarily sub-optimal deeper Each described giving linear relative order executed, understanding any becomes irrelevant skipped. The class strictly larger than strategies. even best also sub-optimal. next prove honors natural partial among common parent (''leaf-sibling tests''), use produce dynamic programming algorithm finds time O(d^2(r+1)^d), r maximum number leaf-siblings d leaf-parents; hence, bounded nodes, run-time polynomial size. present another special takes time. close presenting other plausible approaches PAOTR, together counterexamples their limitations.