IJCAI-03 Tutorial
Resource-Bounded and Time-Critical Reasoning

 

Lloyd Greenwald
Department of Computer Science
Drexel University
3141 Chestnut Street
Philadelphia, PA 19104
Phone: (215) 895-2678
Fax: (215) 895-1582
Email: lgreenwald@cs.drexel.edu
URL: http://www.cs.drexel.edu/~lgreenwa/

Shlomo Zilberstein
Department of Computer Science
University of Massachusetts at Amherst
140 Governors Drive
Amherst, MA 01003-4610
Phone: (413) 545-4189
Fax: (413) 545-1249
Email: shlomo@cs.umass.edu
URL: http://www.cs.umass.edu/~shlomo/

 

Summary

A central problem in artificial intelligence is how to develop computational models that allow decision-support systems or autonomous agents to react to a situation after performing the right amount of deliberation. Frequently, the complexity of problem solving makes it beneficial to use approximate solutions rather than try to compute the optimal answer. This issue arises in a variety of application domains including medical trauma management, Bayesian inference, sequence alignment, graphics rendering, web page prefetching, autonomous space exploration, real-time avionics, and robot navigation. This tutorial explores the theory and practice of building intelligent systems that reason explicitly about employing limited computational resources to generate timely solutions to difficult combinatorial optimization, planning and scheduling problems. Solution techniques go beyond simple greedy or reactive algorithms to achieve high-quality solutions while meeting both hard and soft real-time deadlines. We will explore over fifteen years of progress in this area, covering historical perspectives, state-of-the-art solution techniques, and current and future challenges.

Intended Audience and Goals

The intended audience for this tutorial is artificial intelligence researchers and practitioners who are concerned about the impact of limited resources on time-critical problem solving. Participants will learn how to model the resource-bounded and time-critical aspects of their problems and explore how to match solution techniques to problem properties. Building intelligent systems requires understanding the interplay of bounded and uncertain computational resources, time-varying environmental uncertainty and exogenous influences, the computational complexity of optimal and approximate algorithms, and problem-solving objectives that include timing and solution quality guarantees. Tutorial participants will learn methods for problem and environment profiling, how to re-formulate artificial intelligence solution algorithms as flexible/anytime computations, and how to deploy meta-level reasoning algorithms both off-line and on-line. Open discussion periods will allow participants to explore solution techniques as they relate to their own areas of expertise.

Topics to be covered include: Computational tradeoffs in inference, planning, and search; representation and measurement of computational tradeoffs; dependency of performance on problem instances; anytime algorithms and flexible computation; strategies for allocating resources among reasoning subproblems; myopic and non-myopic control; partitioning resources between meta-level and object-level reasoning; applications of resource-bounded systems; and current research challenges.

Required background: Tutorial participants should be familiar with introductory artificial intelligence, algorithm design and analysis, and introductory probability and statistics.

Tentative Outline

Format: Half-day tutorial (4 hours including a 30-minute break.)

  1. Introduction to meta-level control of computation (30 minutes)
    • Motivation and historical background
    • Models of satisficing and bounded-rationality
    • Brief review of decision and utility theory
    • Meta-level modeling and control

  2. Algorithm design, performance modeling and prediction (45 minutes)
    • Flexible computation and anytime algorithms
    • Performance profiles
    • Comprehensive value
    • Anytime algorithm development

  3. Algorithm composition and transformations (45 minutes)
    • Composition of anytime algorithms
    • Contract to interruptible transformations

    Break (30 minutes)

  4. Meta-reasoning and deliberation scheduling (45 minutes)
    • Optimal stopping of anytime algorithms
    • Policies for monitoring computation
    • Models of continual computation
    • Sequential deliberation scheduling

  5. Sample applications (30 minutes)
    • Survey of application areas
    • Sample application: anytime heuristic search

  6. Current research directions and wrap-up (15 minutes)
    • Summary
    • Open problems and research directions

Instructors

Lloyd Greenwald is an Assistant Professor of Computer Science and Director of the Intelligent Time-Critical Systems Lab at Drexel University. He received a B.S.E. in Computer Science and Engineering with honors from the University of Pennsylvania, and a Sc.M. and Ph.D. in Computer Science from Brown University. Professor Greenwald is a recipient of a Drexel University Research Synergies award, a Veteran's Health Administration Medical Informatics fellowship, and a Brown University fellowship. His research interests include real-time planning and scheduling under uncertainty, mobile robotics, resource-bounded reasoning, anytime algorithms, sequential decision making, reinforcement learning, ad hoc networks, sensor networks, and medical informatics.

Professor Greenwald has designed and taught a graduate-level course on Resource-Bounded and Time-Critical Reasoning, and has prepared and conducted one- to five-day workshops to high school students and civilian and military federal employees on topics ranging from mobile robotics to introductory computer science, computer engineering, database management, and computer networks.

Shlomo Zilberstein is an Associate Professor of Computer Science and Director of the Resource-Bounded Reasoning Lab at the University of Massachusetts at Amherst. He received a B.A. in Computer Science summa cum laude from the Technion - Israel Institute of Technology, and a Ph.D. in Computer Science from the University of California at Berkeley. Professor Zilberstein is a recipient of a National Science Foundation Research Initiation Award (1994), a National Science Foundation CAREER Award (1996), the European Conference on AI Best Paper Award (1998), and the Lady Davis Visiting Associate Professorship at the Technion (2000). His research interests include approximate reasoning, decision theory, design of autonomous agents, heuristic search, information gathering, monitoring and control of computation, planning and scheduling, reinforcement learning, resource-bounded reasoning, and reasoning under uncertainty.

Professor Zilberstein has designed and taught a graduate-level course on Resource-bounded Reasoning Techniques, has designed and conducted a tutorial on Resource-Bounded Reasoning at the Fifteenth International Joint Conference on Artificial Intelligence, and has presented numerous invited talks on resource bounded reasoning, including: building resource-bounded reasoning systems, decision-theoretic control of resource-bounded reasoning systems, resource-bounded reasoning: new directions and opportunities, meta-level control of resource-bounded reasoning systems, and resource-bounded reasoning with anytime algorithms.

Bibliography

  1. D.S. Bernstein, T.J. Perkins, S. Zilberstein, and L. Finkelstein. Scheduling contract algorithms on multiple processors. Proceedings of the 18th National Conference on Artificial Intelligence, 702-706, Edmonton, Alberta, 2002.

  2. J. Bresina, K. Golden, D.E. Smith, and R. Washington. Increased flexibility and robustness for Mars rovers. Fifth International Symposium on Artificial Intelligence, Robotics, and Automation in Space, ESTEC, Noordwijk, Netherlands, 1999.

  3. M. Boddy and T. Dean. Decision-theoretic deliberation scheduling for problem solving in time-constrained environments. Artificial Intelligence, 67(2):245-286, 1994.

  4. V. Bultiko, I. levner, and R. Greiner. Real-time lookahead control policies. AAAI/KDD/UAI-2002 Joint Workshop on Real-Time Decision Support and Diagnosis Systems, 28-36, Edmonton, Alberta, 2002.

  5. P. Chakrabarti, S. Ghosh, and A. Acharya. Heuristic search in restricted memory. Artificial Intelligence, 47:197-221, 1989.

  6. A. Darwiche. Any-space probabilistic inference. Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, 133-142, Stanford, California, 2000.

  7. T. Dean and M. Boddy. An analysis of time-dependent planning. Proceedings of the 7th National Conference on Artificial Intelligence, 49-54, Minneapolis, Minnesota, 1988.

  8. T. Dean. Context-dependent computational components, In M. Pittarelli (Ed.), SIGART Bulletin Special Issue on Anytime Algorithms and Deliberation Scheduling, 7(2):3-6, 1996.

  9. T. Dean, L. Kaelbling, J. Kirman, and A. Nicholson. Planning with deadlines in stochastic domains. Proceedings of the 11th National Conference on Artificial Intelligence, 574-579, Washington, D.C., 1993.

  10. S. de Givry and G. Verfaillie. Optimum anytime bounding for constraint optimization problems. AAAI Workshop on Building Resource-Bounded Reasoning Systems, 37-42, Providence, Rhode Island, 1997.

  11. A. Delhay, M. Dauchet, P. Taillibert, and P. Vanheeghe. Maximization of the average quality of anytime contract algorithms over a time interval. Proceedings of the 16th International Joint Conference on Artificial Intelligence, 212-217, Stockholm, Sweden, 1999.

  12. J. Doyle. Rationality and its roles in reasoning. Proceedings of the 8th National Conference on Artificial Intelligence, 1093-1100, Boston, Massachusetts, 1990.

  13. J. Doyle. Bounded rationality. In MIT Encyclopedia of the Cognitive Sciences, Cambridge: MIT Press, 1999.

  14. D.H. Dash and M.J. Druzdzel. A hybrid anytime algorithm for the construction of causal models from sparse data. Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence, 142-149, San Francisco, CA, 1999.

  15. M. Drummond and J. Bresina. Anytime synthetic projection: Maximizing the probability of goal satisfaction. Proceedings of the National Conference on Artificial Intelligence, 138-144, Boston, MA, 1990.

  16. M. Drummond, J. Bresina, and K. Swanson. Just-in-case scheduling. Proceedings of the Twelth National Conference on Artificial Intelligence, 1098-1104, Seattle, WA, 1994.

  17. L. Finkelstein and S. Markovitch. Optimal schedules for monitoring anytime algorithms. Artificial Intelligence, 126(1-2):63-108, 2001.

  18. L. Finkelstein, S. Markovitch, and E. Rivlin. Optimal schedules for parallelizing anytime algorithms: The case of independent processes. Proceedings of the 18th National Confernce on Artificial Intelligence, 719-724, Edmonton, Alberta, 2002.

  19. A. Garvey and V. Lesser. Design-to-time real-time scheduling. IEEE Transactions on Systems, Man and Cybernetics, 23(6):1491-1502, 1993.

  20. A. Garvey and V. Lesser. A survey of research in deliberative real-time artificial intelligence. Journal of Real-Time Systems, 6(3):317-347, 1994.

  21. S. Ghosh, A. Mahanti, and D. Nau. BDFS: A resource bounded search procedure for combinatorial optimization problems. AAAI Fall Symposium on Flexible Computation in Intelligent Systems, 44-48, Boston, Massachusetts, 1996.

  22. C.P. Gomes and B. Selman. Algorithm portfolio design: Theory vs. practice. Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence, San Francisco, California, 1997.

  23. I. Good. Twenty-seven principles of rationality. In Godambe, V. P., and Sprott, D. A. (Eds.) Foundations of Statistical Inference, Toronto: Holt, Rinehart, Winston, 1971.

  24. J. Grass and S. Zilberstein. A value-driven system for autonomous information gathering. Journal of Intelligent Information Systems, 14:5-27, 2000.

  25. J. Grass and S. Zilberstein. Anytime algorithm development tools. In M. Pittarelli (Ed.), SIGART Bulletin Special Issue on Anytime Algorithms and Deliberation Scheduling, 7(2):20-27, 1996.

  26. L. Greenwald and T. Dean. Solving time-critical decision-making problems with predictable computational demands. Proceedings of the Second International Conference on AI Planning Systems, 1994.

  27. L. Greenwald and T. Dean. A conditional scheduling approach to designing real-time systems. Proceedings of the Fourth International Conference on AI Planning Systems, 1998.

  28. H. Guo and W.H. Hsu. A survey of algorithms for real-time bayesian network inference. AAAI/KDD/UAI-2002 Joint Workshop on Real-Time Decision Support and Diagnosis Systems, 1-12, Edmonton, Alberta, 2002.

  29. P. Haddawy. Focusing attention in anytime decision-theoretic planning. In M. Pittarelli (Ed.), SIGART Bulletin Special Issue on Anytime Algorithms and Deliberation Scheduling, 7(2):34-40, 1996.

  30. E. Hansen, A. Barto, and S. Zilberstein. Reinforcement learning for mixed open-loop and closed-loop control. Proceedings of Neural Information Processing Systems Conference, 1026-1032, Denver, Colorado, 1996.

  31. E. Hansen and S. Zilberstein. Monitoring the progress of anytime problem solving. Proceedings of the 13th National Conference on Artificial Intelligence, 1229-1234, Portland, Oregon, 1996.

  32. E. Hansen, S. Zilberstein, and V. Danilchenko. Anytime heuristic search: First results. University of Massachusetts, Computer Science Department, Technical Report #97-50, 1997.

  33. E. Hansen and S. Zilberstein. Monitoring and control of anytime algorithms: A dynamic programming approach. Artificial Intelligence, 126(1-2):139-158, 2001.

  34. O. Hansson and A. Mayer. Heuristic search as evidential reasoning. Proceedings of the 5th Workshop on Uncertainty in Artificial Intelligence, Windsor, Ontario, 1989.

  35. O. Hansson and A. Mayer. DTS: A decision-theoretic scheduler for space telescope applications. In M. Fox and M. Zweben (eds.), Intelligent Scheduling, Chapter 13, 371-388, Morgan Kaufmann, 1994.

  36. R. Holte, M. Perez, R. Zimmer, and A. MacDonald. The tradeoff between speed and optimality in hierarchical search. AAAI Fall Symposium on Flexible Computation in Intelligent Systems, 60-67, Boston, Massachusetts, 1996.

  37. M.C. Horsch and D. Poole. An anytime algorithm for decision making under uncertainty. Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, 246-255, Madison, Wisconsin, 1998.

  38. M.C. Horsch and D. Poole. Estimating the value of computation in flexible information refinement. Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence, San Francisco, California, 1999.

  39. E.J. Horvitz. Reasoning under varying and uncertain resource constraints. Proceedings of the 7th National Conference on Artificial Intelligence, 111-116, 1988.

  40. E.J. Horvitz, G.F. Cooper, and D.E. Heckerman. Reflection and action under scarce resources: Theoretical principles and empirical study. Proceedings of the 11th International Joint Conference on Artificial Intelligence, 1121-1127, Detroit, Michigan, 1989.

  41. E.J. Horvitz, H.J. Suermondt, and G.F. Cooper. Bounded conditioning: Flexible inference for decision under scarce resources. Proceedings of the 5th Workshop on Uncertainty in Artificial Intelligence, 182-193, Windsor, Ontario. 1989

  42. E. Horvitz and J. Breese. Ideal partition of resources for metareasoning. Technical Report KSL-90-26, Stanford Knowledge Systems Laboratory, 1990.

  43. E.J. Horvitz and G. Rutledge. Time-dependent utility and action under uncertainty. Proceedings of 7th Conference on Uncertainty in Artificial Intelligence, 151-158, 1991.

  44. E. Horvitz and J. Lengyel. Perception, attention, and resources: A decision-theoretic approach to graphics rendering. Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence, 238-249, 1997.

  45. E. Horvitz. Principles and applications of continual computation. Artificial Intelligence, 126(1-2):159-196, 2001.

  46. E. Horvitz, Y. Ruan, C. Gomes, H. Kautz, B. Selman, D. M. Chickering. A Bayesian approach to tackling hard computational problems. Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, August 2001.

  47. R. Howard. Information Value Theory. IEEE Transactions on System Science and Cybernetics, SSC-2(1):22-26, 1966.

  48. D. Hull and W. Feng and J. W. S. Liu. Operating System Support for Imprecise Computation. AAAI Fall Symposium on Flexible Computation, 1996.

  49. R. Jensen and J. Schlimmer. An anytime solution to inductively learn decision trees. AAAI Fall Symposium on Flexible Computation in Intelligent Systems, 106-110, Boston, Massachusetts, 1996.

  50. N. Jitnah and A.E. Nicholson. treeNets: A framework for anytime evaluation of belief networks, ECSQARU-FAPR, 350-364, 1997.

  51. N. Jitnah and A.E. Nicholson. A best-first search method for anytime evaluation of belief networks. AAAI Workshop on Building Resource-Bounded Reasoning Systems, 69-73, Providence, Rhode Island, 1997.

  52. H. Kautz, E. Horvitz, Y. Ruan, C. Gomes, B. Selman. Dynamic restart policies. Proceedings of the 18th National Conference on Artificial Intelligence, 674-681, Edmonton, Alberta, 2002.

  53. S. Koenig and M. Likhachev. Improved fast replanning for robot navigation in unknown terrain. Proceedings of the International Conference on Robotics and Automation, 2002.

  54. R. Korf. Real-time heuristic search. Artificial Intelligence, 42(3):189-212, 1990.

  55. C.T. Kwok, D. Fox, and M. Meila. Real-time particle filters using mixtures of samples sets. AAAI/KDD/UAI-2002 Joint Workshop on Real-Time Decision Support and Diagnosis Systems, 2002.

  56. M. Lagoudakis, M. Littman, and R. Parr. Selecting the right algorithm. AAAI Fall Symposium Series: Using Uncertainty within Computation, Cape Cod, MA, 2001.

  57. K. Larson and T. Sandholm. Bargaining with limited computation: deliberation equilibrium. Artificial Intelligence, 132(2):183-217, 2000.

  58. K. Larson and T. Sandholm. An alternating offers bargaining model for computationally limited agents. Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, Bologna, Italy, 2002.

  59. V. Lesser, J. Pavlin and E. Durfee. Approximate processing in real-time problem-solving. Artificial Intelligence Magazine, 9(1):49-61, 1988.

  60. C.-L. Liu and M. Wellman. On state-space abstraction for anytime evaluation of Bayesian networks. In M. Pittarelli (Ed.), SIGART Bulletin Special Issue on Anytime Algorithms and Deliberation Scheduling, 7(2):50-57, 1996.

  61. J.W.S. Liu, K.J. Lin, W.K. Shih, A.C. Yu, J.Y. Chung, and W. Zhao. Algorithms for scheduling imprecise computations, IEEE Computer, 24:58-68, 1991.

  62. M. Marengoni, A. Hanson, S. Zilberstein, and E. Riseman. Control in a 3D reconstruction system using selective perception. Proceedings of the 7th IEEE International Conference on Computer Vision, 1229-1236, Kerkyra, Greece, 1999.

  63. V. Millan-Lopez, W. Feng, and J.W.S. Liu. Using the imprecise computation technique for congestion control on a real-time traffic switching element. International Conference on Parallel and Distributed Systems, 1994.

  64. A.-I. Mouaddib and S. Zilberstein. Optimal scheduling of dynamic progressive processing. Proceedings of the 13th Biennial European Conference on Artificial Intelligence, 449-503, Brighton, UK, 1998.

  65. S.H. Nawab, A.V. Oppenheim, A.P. Chandrakasan, J.M. Winograd, and J.T. Ludwig. Approximate signal processing. Journal of VLSI Signal Processing, 15:177-200, 1997.

  66. D. Parkes and L. Greenwald. Approximate and compensate: A method for risk-sensitive meta-deliberation and continual computation. AAAI Fall Symposium on Using Uncertainty in Computation, Cape Cod, Massachusetts, 2001.

  67. J. Pemberton and L. Greenwald. On the need for dynamic scheduling of imaging satellites. Future Intelligent Earth Observing Satellites Symposium, 2002.
  68. J. Pemberton. k-best: A new method for real-time decision making. Proceedings of the 14th International Joint Conference on Artificial Intelligence, 227-233, Montreal, Canada, 1995.

  69. A. Pos. Time-constrained model-based diagnosis. Master Thesis, Department of Computer Science, University of Twente, The Netherlands, 1993.

  70. F.T. Ramos, F.G. Cozman, and J.S. Ide. Embedded Bayesian networks: Anyspace, anytime probabilistic inference. AAAI/KDD/UAI-2002 Joint Workshop on Real-Time Decision Support and Diagnosis Systems, 13-19, Edmonton, Alberta, 2002.

  71. S. Russell. Efficient memory-bounded search methods. Proceedings of the 10th European Conference on Artificial Intelligence, 1-5, Vienna, Austria, 1992.

  72. S. Russell. Rationality and intelligence. Artificial Intelligence, 94(1):57-77, 1997.

  73. S. Russell and D. Subramanian. Provably bounded-optimal agents. Journal of Artificial Intelligence Research, 2, 1995.

  74. S. Russell and E. Wefald. Do the Right Thing: Studies in limited rationality. Cambridge, Massachusetts: MIT Press, 1991.

  75. S. Russell and E. Wefald. Principles of metareasoning. Artificial Intelligence, 49:361-395, 1991.

  76. T.W. Sandholm and V.R. Lesser. Coalitions among computationally bounded agents. Artificial Intelligence, 94(1):99-137, 1997.

  77. H. Simon. >From substantive to procedural rationality. In H. Simon, Models of Bounded Rationality, Volume 2, Cambridge, Massachusetts: MIT Press, 1982.

  78. P. Smyth and D. Wolpert. Anytime exploratory data analysis for massive data sets. Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining, 54-60, 1997.

  79. L. Steinberg. Searching stochastically generated multi-abstraction-level design spaces. Artificial Intelligence, 129(1-2):63-90, 2001.

  80. K. Toyama. Handling tradeoffs between precision and robustness with incremental focus of attention for visual tracking. AAAI Fall Symposium on Flexible Computation in Intelligent Systems, 142-147, Boston, Massachusetts, 1996.

  81. R. Wallace and E. Freuder. Anytime algorithms for constraint satisfaction and SAT problems. In M. Pittarelli (Ed.), SIGART Bulletin Special Issue on Anytime Algorithms and Deliberation Scheduling, 7(2):7-10, 1996.

  82. W. Ruml. Real-time heuristic search for combinatorial optimization and constraint satisfaction. AAAI/KDD/UAI-2002 Joint Workshop on Real-Time Decision Support and Diagnosis Systems, 85-90, Edmonton, Alberta, 2002.

  83. W. Zhang. Complete anytime beam search. Proceedings of the 15th National Conference on Artificial Intelligence, 425-430, Madison, Wisconsin, 1998.

  84. W. Zhang. Iterative state-space reduction for flexible computation. Artificial Intelligence, 126(1-2):109-138, 2001.

  85. R. Zhou and E.A. Hansen. Memory-bounded A* graph search. Fifteenth International FLAIRS Conference, Pensacola, Florida, 2002.

  86. S. Zilberstein. Resource-bounded sensing and planning in autonomous systems. Autonomous Robots, 3:31-48, 1996.

  87. S. Zilberstein. Using anytime algorithms in intelligent systems. Artificial Intelligence Magazine, 17(3):73-83, 1996.

  88. S. Zilberstein and S. Russell. Optimal composition of real-time systems. Artificial Intelligence, 82(1-2):181-213, 1996.

  89. S. Zilberstein and A.-I. Mouaddib. Optimizing resource utilization in planetary rovers. Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space, 163-168, San Francisco, California, 2000.

  90. S. Zilberstein, R. Washington, D.S. Bernstein, and A.I. Mouaddib. Decision-theoretic control of planetary rovers. To appear in Springer LNAI, 2002.

  91. M. Zweben, E. Davis and R. Guargan. Anytime rescheduling. Proceedings of DARPA Workshop on Innovative Approach for Planning and Scheduling, 251-259, San Francisco, 1990.