Reference: Horvitz, E. Computation and Action Under Bounded Resource. Knowledge Systems Laboratory, December, 1990.
Abstract: I define and implement a model of rational action for automated reasoning systems that makes use of flexible approximation methods and decision-theoretic procedures to determine how best to solve a problem under bounded computational resources. The model provides a perspective on the use of metareasoning techniques to balance the costs of increased delays with the benefits of better results in a decision context. I focus on the use of inexpensive real-time analyses to control the allocation of computational resources in complex decision-theoretic reasoning. The approach extends traditional decision analyses to autoepistemic models that represent knowledge about problem solving, in addition to knowledge about distinctions and relationships in the world. To investigate the use of decision analysis for controlling computation, I constructed a computer program named Protos. Protos uses information about the progress of problem solving to identify the ideal time to halt computation and take action in the world. Protos' metareasoner controls the precision of probabilities inferred from complex network models that represent domain-specific expertise about uncertain relationships among observations and hypotheses. I found that it can be valuable to allocate a portion of costly reasoning resources to deliberate about the best way to solve a decision problem. In addition to serving as a testbed for exploring the value of metareasoning, I made use of Protos to examine the integration of reflex and deliberative analyses and the construction of time-dependent utility models from observations. After discussing principles for applying multiattribute utility theory to the control of basic computational procedures, I describe how these principles can be used to control probabilistic reasoning. In particular, I present techniques for controlling, at run time, the tradeoff between the complexity of detailed, accurate analyses and the tractability of less complex, yet less accurate probabilistic inference. Then, I describe the architecture and functionality of Protos and review the system's behavior on high-stakes decision problems in medicine. Finally, I move beyond the consideration of time constraints to investigate the constraints on decision-theoretic reasoning posed by the cognitive limitations of people seeking insight from automated decision systems.
Notes: Report not available.