Tech Report CS-94-41

Time-Critical Planning and Scheduling Research at Brown University

Thomas L. Dean, Lloyd Greenwald, Leslie Pack Kaelbling

October 1994

Abstract:

This report is a summary of recent work on time-critical planning and scheduling at Brown University. Much of our research over the last six years has been concerned with systems that are capable of managing computational resources for complex problem-solving tasks, in which the time spent in decision making affects the quality of the responses generated by a system. We developed an approach to designing algorithms and allocating computational resources to algorithms that is widely cited in the areas of real-time problem solving. We have provided a number of basic results regarding the design of systems that manage their computational resources by using expectations about the performance of decision-making procedures and preferences over the outcomes resulting from applying those procedures. We have also provided a basic framework for planning systems that employ decision theoretic techniques to evaluate plans and to perform probabilistic prediction.

The main thread of our recent research in time-critical planning and scheduling is concerned with decision making under uncertainty. Of particular interest are problems in which the notion of risk is complicated by limitations on time to plan and act. Our research has resulted in a family of algorithms that extend techniques in operations research to efficiently handle stochastic processes with very large state and/or action spaces. Preliminary experimental results have helped to formulate a characterization of the class of problems for which our methods are well suited.

(complete text in pdf or gzipped postscript)