Optimal Satisficing Tree Searches

Dan Geiger, Jeffrey A. Barnett

We provide an algorithm that finds optimal search strategies for AND trees and OR trees. Our model includes three outcomes when a node is explored: (1) finding a solution, (2) not finding a solution and realizing that there are no solutions beneath the current node (pruning), and (3) not finding a solution but not pruning the nodes below. The expected cost of examining a node and the probabilities of the three outcomes are given. Based on this input, the algorithm generates an order that minimizes the expected search cost.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.