# The ICICS/CS Reading Room

## UBC CS TR-93-09 Summary

- No on-line copy of this technical report is available.

- Decision Graph Search, April 1993 Runping Qi and David Poole, 43 pages
A decision graph is an AND/OR graph with a certain evaluation function.
Decision graphs have been found a very useful representation for a variety
of decision making problems. This article present a number of search
algorithms computing an optimal solution from a given decision graph.
These algorithms include one {\it depth-first heuristic-search algorithm},
one {\it best-first heuristic-search algorithm}, one {\it anytime-algorithm}
and two {\it iterative-deepening depth-first heuristic-search algorithms}.
Similar to the *-minimax search algorithms of Ballard, our depth-first
heuristic-search algorithm is developed from the alpha--beta algorithm
for minimax tree search. In addition, we show how heuristic knowledge
can be used to improve search efficiency. Furthermore, we present an
anytime algorithm which is conveniently obtained from the depth-first
heuristic-search algorithm without incurring much overhead.
The best-first heuristic-search algorithm is obtained by modifying
the well known AO* algorithm for AND/OR graphs with additive costs.
The iterative-deepening algorithms result from combining the
iterative-deepening techniques with the depth-first search techniques.
Some experimental data on some of these algorithms performance are given.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.