Efficient Decision­Theoretic Planning: Techniques and Empirical Analysis

Peter Haddawy AnHai Doan Department of EE&CS University of Wisconsin­Milwaukee Milwaukee, WI 53201

Richard Goodwin School of Computer Science Carnegie Mellon University 5000 Forbes Ave. Pittsburgh, PA 15213


This paper discusses techniques for perform­ ing efficient decision­theoretic planning. We give an overview of the drips decision­ theoretic refinement planning system, which uses abstraction to efficiently identify opti­ mal plans. We present techniques for au­ tomatically generating search control infor­ mation, which can significantly improve the planner's performance. We evaluate the effi­ ciency of drips both with and without the search control rules on a complex medical planning problem and compare its perfor­ mance to that of a branch­and­bound deci­ sion tree algorithm.