A NEW METHOD FOR INFLUENCE DIAGRAM EVALUATION

As influence diagrams become a popular representational tool for decision analysis, influence diagram evaluation attracts more and more research interests. In this article, we present a new, two-phase method for influence diagram evaluation. In our method, an influence diagram is first mapped onto a decision graph and then the analysis is carried out by evaluating the decision graph. Our method is more efficient than Howard and Matheson's because, among other reasons, our method generates a much smaller decision graph for the same influence diagram. Like those most recent algorithms reported in the literature, our method also provides a clean interface between influence diagram evaluation and Bayesian net evaluation. Consequently, various well-established algorithms for Bayesian net evaluation can be used in influence diagram evaluation. Furthermore, our method has a few unique merits. First, it takes advantage of asymmetry in influence diagrams to avoid unnecessary computation. Second, by using heuristic search techniques, it provides an explicit mechanism for using heuristic information that may be available in a domain-specific form. These additional merits make our method more efficient than the current algorithms in general. Finally, by using decision graphs as an intermediate representation, the value of perfect information can be computed in a more efficient way.