Models of Continual Computation

Eric Horvitz

Decision Theory & Adaptive Systems Group
Microsoft Research
Redmond, Washington 98052-6399

Access postscript or pdf file.


Automated problem solving is viewed typically as the expenditure of computation to solve one or more problems passed to a reasoning system. In response to each problem received, effort is applied to generate a solution and problem solving ends when the solution is rendered. We discuss the notion of continual computation that addresses a broader conception of problem by considering the ideal use of the idle time between problem instances. The time is used to develop solutions proactively to one or more expected challenges in the future. We consider analyses for traditional all-or-nothing algorithms as well as more flexible computational procedures. After exploring the allocation of idle time for several settings, we generalize the analysis to consider the case of shifting computation from a current problem to solve future challenges. Finally, we discuss a sample application of the use of continual computation in the setting of diagnostic reasoning.

Keywords: Continual computation, bounded resources, resource-bounded reasoning, time-critical problem solving, decision-theoretic inference.

In: Proceedings of the Fourteenth National Conference on Artificial Intelligence, Providence, RI, July 1997. AAAI Press: Menlo Park.

Author Email: