CSM-184 - Planning and Execution using Partial Decision Trees

We present a planning system which combines decision theory and AI planning techniques. Since actions have costs and uncertain outcomes, decision theory is used as a criterion for choosing among different courses of action in the plan tree. The plan representation can be seen as either a tree-structured conditional plan or a decision tree. In order to be reasonably responsive to the external environment, the system has a meta level control structure which lets it trade off further planning against execution by reasoning about the utility of planning. After executing an object level action, the system monitors the outcome and recurses on the appropriate remaining parts of the tree.