Anytime algorithms give intelligent systems the capability to trade deliberation time for quality of results. This capability is essential for successful operation in domains such as signal interpretation, real-time diagnosis and repair, and mobile robot control. What characterizes these domains is that it is not feasible (computationally) or desirable (economically) to compute the optimal answer. This article surveys the main control problems that arise when a system is composed of several anytime algorithms. These problems relate to optimal management of uncertainty and precision. After a brief introduction to anytime computation, I outline a wide range of existing solutions to the metalevel control problem and describe current work that is aimed at increasing the applicability of anytime computation.
The solution is based on the replacement of standard modules of a program with more flexible computation elements that are called anytime algorithms (Dean and Boddy 1988; Horvitz 1989). In addition, the solution includes an offline compilation process and a run-time monitoring component that guarantee that the agent is performing the correct amount of thinking in a well-defined sense. Artificial agents must perform some real-time deliberation to solve such problems as path planning and task scheduling. An important aspect of intelligent behavior is the capability of agents to factor the cost of deliberation into the deliberation process. Two factors determine the cost of deliberation: (1) the resources consumed by the process, primarily computation time, and (2) constant change in the environment that might decrease the relevance of the outcome and, hence, reduce its value.
Information gathering systems are operating in an ever growing environment of information sources. One of the main challenges of information gathering research is to generate a high-quality response to the information needs of the user. To achieve this goal, systems will have to trade off computational resources for quality of results. This paper shows how a special type of anytime algorithms can be used efficiently to construct and monitor information gathering systems.
Each one of these problems can be approached and solved using optimizing or satisficing techniques. Each stage involves complex tradeoffs that can be addressed off-line or online. For example, using a more precise model of the environment may complicate the problem definition and may force the system to compute less precise answers to the problem. The key question is whether bounded optimality is a useful approach to all or some of these problems. In other words, the question is whether there are any advantages to making optimal decisions within an approximate model, rather than making approximate decisions within a more precise (or even perfect) model.