DecisionTheoretic Refinement Planning: Principles and Application
AnHai Doan and Peter Haddawy Department of Electrical Engineering and Computer Science University of WisconsinMilwaukee PO Box 784 Milwaukee, WI 53201
We present a general theory of action abstraction for reducing the complexity of decisiontheoretic 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 decisiontheoretic refinement planning system. We apply the planner to the problem of selecting the optimal test/treat strategy for managing patients suspected of having deepvein thrombosis of the lower extremities. We show that drips significantly outperforms a standard branchandbound decision tree evaluation algorithm on this domain. We would like to thank Charles Kahn for pointing us to the DVT application.