The historical background provides a fairly extensive bibliography of general planning and the uses of deliberation scheduling in a spectrum of domains from medical decision making to scheduling database queries. They then present the basics of decision theory, using the axioms of Keeny and Raifa, and discuss the ideas of utility and define deliberation scheduling in terms of maximizing the utility of planning, given the time changing state of the world. This concept is only functional given that there is some enforceable policy which controls deliberation. If there is only one planning system, and it always runs to completion producing it's plan, then there is no deliberation to schedule; the system has nothing to decide. However, if the system can select between alternative planners, each requiring different amounts of time (discrete deliberation scheduling), or if the planners produce improving plans given increased resources (flexible computations, anytime algorithms), then the system needs to optimize the utility of planning. The authods discuss both of these models, and provide candidate utility functions for each.
The paper then introduces a formal definition of time dependent problems, and presents a simple (restricted) discrete deliberation scheduler. The restrictions map to some known planning domains, but may be inapplicable in general. This algorithm is extended to work with uncertainties in the time of event occurances, and to address dependencies between decision procedure results (the base model assumes independence to simplify the calculation of utilities).
The authors address the issue of effective anytime algorithms for planning problems. The characterize known anytime algorithms in the following areas:
Finally, the authors present some insights into paractical deliberation scheduling, including several specific domain models, and approached to using deliberation scheduling to improve the system performance.