Sd. Wu et Vj. Leon, A DECISION STRUCTURE USING GENERALIZED AND OR TREES CONTAINING CHANCENODES, Computers & industrial engineering, 26(1), 1994, pp. 151-171
A decision structure was developed which generalizes the well known AN
D/OR trees to include ''CHANCE'' nodes. A CHANCE node is a generalizat
ion of an AND node and its associated value is defined as the expected
value of the successors. A search algorithm was developed for this de
cision structure. The algorithm utilizes an informed model, which enco
des heuristic information as upper and lower bounds for non-terminal n
odes. These ''CHANCE/OR'' trees pertain to a large variety of decision
processes involving limited look-ahead, and reasoning under uncertain
ty, e.g. strategic decision making, short-term planning, etc. The sear
ch algorithm was implemented and tested against a direct extension of
the alpha-beta pruning procedure. The results of 1440 runs of the algo
rithms based on various matrices and tree configurations were analyzed
and discussed. The computational results show that the proposed algor
ithm can sufficiently solve trees of various configurations within rea
sonable computer time.