Exact Dominance without Search in Decision Trees

Nilesh L. Jain, Washington University in St Louis
Ronald P. Loui, Washington University in St Louis


In order to improve understanding of how planning and decision analysis relate, we propose a hybrid model containing concepts from both. This model is comparable to [Hartman90], with slightly more detail. Dominance is simple concept in decision theory. In a restricted version of our model, we give conditions under which dominance can be detected without search: that is, it can be used as a pruning strategy to avoid growing large trees. This investigation follows the lead of [Wellman87]. The conditions seem hard to meet, but may nevertheless be useful in forward-chaining situations without focus, such as [Breese87]. It may be possible to extend this work to produce better heuristic pruning based on inexact dominance and heuristic ablity. Mainly, we contribute a detailed study of particular concept in a hybrid model that is the most detailed to date, further clarifying the relation between the two main paradigms for reasoning about preference among actions.