Tech Report CS-91-06

Solving Time-Dependent Problems: A Decision-Theoretic Approach to Planning in Dynamic Environments

Mark Steven Boddy

May 1991

Abstract:

Controlling a robot involves making decisions that modify its behavior. Making good decisions may require time-consuming computation. Changes in the environment over time affect when this computation can be done (e.g., after obtaining the necessary information), and when a result is useful (e.g., before some event occurs). This sensitivity to when computation is performed and when decisions are made is what makes these problems ``time-dependent.'' A controller with more than one decision to make must trade off computation time, based on the expected effect on the system's behavior. We call the resulting meta-level scheduling problem a ``deliberation-scheduling'' problem.

We have developed a framework for doing deliberation scheduling called ``expectation-driven iterative refinement''. This framework requires that the decision procedures to which time is allocated be ``anytime algorithms,'' which can be interrupted at any point to return an answer whose expected utility increases with computation time.

We have conducted a theoretical and empirical investigation of the application of expectation-driven iterative refinement to time-dependent problems. We discuss the problem of finding or generating anytime decision procedures and gathering useful expectations on their behavior. The difficulty of doing deliberation scheduling depends in large part on the decision model to be used in computing expectations on the system's behavior. We show that for many time-dependent problems, optimal deliberation scheduling for a reasonably complex decision model is likely to be computationally expensive. We suggest some ways in which the decision model can be restricted so as to simplify deliberation scheduling. In particular, we discuss generating an explicit ``deliberation schedule'' on the occurrence of a restricted set of significant events.

Empirical results obtained for three different examples demonstrate that this approach can provide computationally inexpensive deliberation scheduling with an expected utility only slightly less than for a more complete (and computationally intractable) decision model. These examples also serve to elucidate some of the issues involved in generating solutions to time-dependent problems, and support our contention that expectation-driven iterative refinement is a useful tool for providing these solutions.

(complete text in pdf or gzipped postscript)