Decision­Theoretic Refinement Planning: Principles and Application

AnHai Doan and Peter Haddawy Department of Electrical Engineering and Computer Science University of Wisconsin­Milwaukee PO Box 784 Milwaukee, WI 53201

Abstract

We present a general theory of action abstraction for reducing the complexity of decision­theoretic planning. We develop projection rules for abstract actions and prove our abstraction techniques to be correct. We present a planning algorithm that uses the abstraction theory to efficiently explore the space of possible plans by eliminating suboptimal classes of plans without explicitly examining all plans in those classes. An instance of the algorithm has been implemented as the drips decision­theoretic refinement planning system. We apply the planner to the problem of selecting the optimal test/treat strategy for managing patients suspected of having deep­vein thrombosis of the lower extremities. We show that drips significantly outperforms a standard branch­and­bound decision tree evaluation algorithm on this domain. We would like to thank Charles Kahn for pointing us to the DVT application.