A DECISION STRUCTURE USING GENERALIZED AND OR TREES CONTAINING CHANCENODES

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.