Reflection and Action Under Scarce Resources: Theoretical Principles and Empirical Study
Eric Horvitz, Gregory Cooper, David Heckerman
Access pdf or postscript.
We define and exercise the expected value of computation as a
fundamental component of reflection about alternative inference
strategies. We present a portion of Protos research focused on the
interlacing of reflection and action under scarce resources, and
discuss how the techniques have been applied in a high-stakes medical
domain. The work centers on endowing a computational agent with the
ability to harness incomplete characterizations of problem-solving
performance to control the amount of effort applied to a problem or
subproblem, before taking action in the world or turning to another
problem. We explore the use of the techniques in controlling
decision-theoretic inference itself, and pose the approach as a model
of rationality under scarce resources.
Keywords: Decision-theoretic metareasoning, bounded optimality, flexible computation, Bayesian networks, rationality under bounded resources, automated reasoning,
influence diagrams, decision-theoretic inference.
Published in: Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI, pages 1121-1127. Morgan Kaufmann, San Mateo, CA, August 1989.. Also, Stanford CS Technical Report KSL-89-1.
- E.J. Horvitz, Computation and Action Under Bounded Resources, PhD dissertation. Stanford University, 1990.
- E. Horvitz, Reasoning about Beliefs and Actions
under Computational Resource
Constraints, Third Workshop on Uncertainty in Artificial Intelligence, Seattle, Washington. July 1987. Association for
Uncertainty and Artificial Intelligence. pp. 429-444. Also in
L. Kanal, et al. ed., Uncertainty in Artificial Intelligence 3,
Elsevier, 1989, pps. 301-324. Click here to access postscript.
- E.J. Horvitz, Reasoning under varying and uncertain resource
constraints. Proceedings of the Seventh National Conference on
Artificial Intelligence, Minneapolis, MN. August 1988. Morgan
Kaufmann, San Mateo, CA. pp. 111-116. (An analysis of ideal decisions
about computation for urgent, deadline, and uncertain deadline situations, conditioned on available reasoning strategies).
Click here to access postscript.
- E. Horvitz and G. Rutledge. Time-Dependent Utility and Action Under
Uncertainty. Uncertainty in Artificial Intelligence, Los Angeles, 1991,
Morgan Kaufman, pp. 151-158. On the assessment, representation, and
inference with time-dependent utility in high-stakes, time-critical situations.
- J.S. Breese and E.J. Horvitz. Ideal Reformulation of Belief Networks ,
Proceedings of Sixth Conference on Uncertainty in Artificial
Intelligence, Cambridge, MA, Association for Uncertainty in
Artificial Intelligence, Mountain View, CA. July 1990. pp 64-72. (On
strategic bounded optimality--the ideal control of flexible
algorithms that are applied in sequence to compute actions.)
- E. Horvitz. Models of Continual Computation. Proceedings of the Fourteenth National Conference on Artificial Intelligence,
Providence, RI, July 1997. AAAI Press: Menlo Park. (Introduces concept and illustrative models for the ideal allocation of idle resources for precomputing
future problem challenges.)
- E. Horvitz. Continual Computation Policies for Utility-Directed Prefetching.
Proceedings of the Seventh ACM Conference on Information and Knowledge Management,
Bethesda MD, November 3-7 1998, pp. 175-184. ACM Press: New York. (On policies for
continual computation--the ideal use of idle computational or networking resources--
for prefetching and caching content over limited bandwidth lines.)
- E. Horvitz. Principles and Applications of Continual Computation. Artificial Intelligence Journal, 126:159-196, Elsevier Science, February 2001.
- E. Horvitz and S. Zilberstein,
Computational Tradeoffs Under Bounded Resources, Artificial Intelligence Journal, 126:1-4, Elsevier Science, February 2001.
- E. Horvitz, Y. Ruan, C. Gomes, H. Kautz, B. Selman, D. M. Chickering. A Bayesian Approach to Tackling Hard Computational Problems. Proceedings of the Seventeenth Conference on Uncertainty and Artificial Intelligence, July 2001.
- E.J. Horvitz, H.J. Suermondt, G.F. Cooper. Bounded conditioning:
Flexible inference for decisions under scarce resources. In:
Proceedings of Conference on Uncertainty in Artificial
Intelligence, Windsor, ON. August 1989. Association for
Uncertainty in Artificial Intelligence, Mountain View, CA,
pp. 182-193. (On the control of flexible computation for probabilistic inference.)
- E.J. Horvitz and J.S. Breese, Ideal Partition of Resources for
Metareasoning. Technical Report KSL-90-26, Knowledge Systems
Laboratory, Stanford University, February 1990. (On strategic
bounded optimality--the ideal control of a set of available flexible algorithms
applied in sequence.)
- E.J. Horvitz, Rational Metareasoning and Compilation for Optimizing
Decisions Under Bounded Resources. Proceedings of Computational
Intelligence '89, Milan, Italy, September 1989. Association for
Computing Machinery. (On the role of compilation in bounded-optimal
architectures, and the value of partial compilation and platform results).
- D. Heckerman, J.S. Breese, E. Horvitz, The Compilation of Decision Models, Proceedings of the Conference on Uncertainty in Artificial Intelligence, Association for Uncertainty in Artificial Intelligence, July 1989, pages 162-173.
- E.J. Horvitz, Problem-Solving Design: Reasoning about Computational Value, Tradeoffs, and Resources. Proceedings of the 1987 NASA Artificial Intelligence Forum, Palo Al
to, CA, October 1987, pp. 26-43. National Aeronautics And Space Administration: Mountain View, CA. (On different classes of control; strategic versus fine-grained control of computation.).
Back to Eric Horvitz's home page.