Deliberation scheduling for problem solving in time-constrained environments. (English) Zbl 0809.68103
Summary: We are interested in the problem faced by an agent with limited computational capabilities, embedded in a complex environment with other agents and processes not under its control. Careful management of computational resources is important for complex problem-solving tasks in which the time spent in decision making affects the quality of the responses generated by a system. This paper describes an approach to designing systems that are capable of taking their own computational resources into consideration during planning and problem solving. In particular, we address the design of system that manage their computational resources by using expectations about the performance of decision-making procedures and preferences over the outcomes resulting from applying those procedures. Our approach is called deliberation scheduling. Deliberation scheduling involves the explicit allocation of computational resources to decision-making procedures based on the expected effect of those allocations on the system’s performance.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
References:
| [1] | Barnett, V., (Comparative Statistical Inference (1982), Wiley: Wiley New York) · Zbl 0593.62002 |
| [2] | Bellman, R. E., (Dynamic Programming (1957), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 0077.13605 |
| [3] | Boddy, M., Anytime problem solving using dynamic programming, (Proceedings AAAI-91. Proceedings AAAI-91, Anaheim, CA (1991)) |
| [4] | Boddy, M., Solving time-dependent problems: a decision-theoretic approach to planning in dynamic environments, (Tech. Report CS-91-06 (1991), Department of Computer Science, Brown University: Department of Computer Science, Brown University Providence, RI) |
| [5] | Boddy, M.; Dean, T. L., Solving time-dependent planning problems, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)) · Zbl 0713.68069 |
| [6] | Bodin, L.; Golden, B., Classification in vehicle routing and scheduling, Networks, 11, 97-108 (1981) |
| [7] | Brooks, R. A., A robust layered control system for a mobile robot, (AI Memo No. 864 (1985), MIT Artificial Intelligence Laboratory: MIT Artificial Intelligence Laboratory Cambridge, MA) |
| [8] | Chernoff, H.; Moses, L. E., (Elementary Decision Theory (1959), Wiley: Wiley New York) · Zbl 0089.14406 |
| [9] | Dean, T. L., Decision-theoretic control of inference for time-critical applications, Int. J. Intell. Syst., 6, 4, 417-441 (1991) |
| [10] | Dean, T. L.; Boddy, M., An analysis of time-dependent planning, (Proceedings AAAI-88. Proceedings AAAI-88, St. Paul, MN (1988)), 49-54 |
| [11] | Drummond, M.; Bresina, J., Anytime synthetic projection: maximizing the probability of goal satisfaction, (Proceedings AAAI-90. Proceedings AAAI-90, Boston, MA (1990)), 138-144 |
| [12] | Einav, D., Computationally-optimal real-resource strategies for independent, uninterruptible methods, (Proceedings Sixth Workshop on Uncertainty in Artificial Intelligence. Proceedings Sixth Workshop on Uncertainty in Artificial Intelligence, Cambridge, MA (1990)), 73-81 · Zbl 0742.68074 |
| [13] | Elkan, C., Incremental, approximate planning, (Proceedings AAAI-90. Proceedings AAAI-90, Boston, MA (1990)), 145-150 |
| [14] | Etzioni, O., Tractable decision-analytic control, (Proceedings First International Conference on Principles of Knowledge Representation and Reasoning (KR-89). Proceedings First International Conference on Principles of Knowledge Representation and Reasoning (KR-89), Toronto, Ont. (1989)), 114-125 · Zbl 0709.68050 |
| [15] | Garey, M. R.; Johnson, D. S., (Computing and Intractibility: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Fransisco, CA) · Zbl 0411.68039 |
| [16] | Georgeff, M. P.; Lansky, A. L., Reactive reasoning and planning, (Proceedings AAAI-87. Proceedings AAAI-87, Seattle, WA (1987)), 677-682 |
| [17] | Good, I. J., (Good Thinking (1976), University of Minnesota Press: University of Minnesota Press Minneapolis, MN) |
| [18] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G, Optimization and approximation in deterministic sequencing and scheduling: a survey, (Proceedings Discrete Optimization. Proceedings Discrete Optimization, Vancouver, BC (1977)) · Zbl 0388.90032 |
| [19] | Hansson, O.; Mayer, A., The optimality of satisficing solutions, (Proceedings Fourth Workshop on Uncertainty in Artificial Intelligence. Proceedings Fourth Workshop on Uncertainty in Artificial Intelligence, Minneapolis, MN (1988)) |
| [20] | Harel, D., (ALGORITHMICS: The Spirit of Computing (1987), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 1243.68007 |
| [21] | Hayes-Roth, B.; Washington, R.; Hewett, R.; Hewett, M.; Seiver, A., Intelligent monitoring and control, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 243-249 · Zbl 0707.68005 |
| [22] | Henrion, M., The value of knowing how little you know, (Ph.D. Thesis (1984), Carnegie Mellon University: Carnegie Mellon University Pittsburgh, PA) |
| [23] | Henrion, M., Propagating uncertainty by logic sampling in Bayes’ networks, (Proceedings Second Workshop on Uncertainty in Artificial Intelligence. Proceedings Second Workshop on Uncertainty in Artificial Intelligence, Philadelphia, PA (1986)) · Zbl 0649.68095 |
| [24] | Horvitz, E. J., Reasoning about beliefs and actions under computational resource constraints, (Proceedings Third Workshop on Uncertainty in Artificial Intelligence. Proceedings Third Workshop on Uncertainty in Artificial Intelligence, Seattle, WA (1987)) |
| [25] | Horvitz, E. J., Reasoning under varying and uncertain resource constraints, (Proceedings AAAI-88. Proceedings AAAI-88, St. Paul, MN (1988)), 111-116 |
| [26] | Horvitz, E. J.; Suermondt, H. J.; Cooper, G. F., Bounded conditioning: flexible inference for decisions under scarce resources, (Proceedings Fifth Workshop on Uncertainty in Artificial Intelligence. Proceedings Fifth Workshop on Uncertainty in Artificial Intelligence, Windsor, Ont. (1989)) |
| [27] | King, J. R.; Spachis, A. S., Scheduling: bibliography and review, Int. J. Phys. Distrib. Materials Manage., 10, 3, 105-132 (1980) |
| [28] | Korf, R. E., Real-time heuristic search, Artif. Intell., 42, 2, 189-212 (1990) · Zbl 0718.68082 |
| [29] | Lesser, V. R.; Pavlin, J.; Durfee, E., Approximate processing in real-time problem solving, AI Mag., 9, 49-62 (1988) |
| [30] | Pearl, J., (Heuristics (1985), Addison-Wesley: Addison-Wesley Reading, MA) |
| [31] | Pearl, J., (Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA) |
| [32] | Raiffa, H., (Decision Analysis: Introductory Lectures on Choices under Uncertainty (1968), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0181.21802 |
| [33] | Robert, F., (Discrete Iterations: A Metric Study (1986), Springer: Springer New York) · Zbl 0639.39005 |
| [34] | Rosenschein, S.; Kaelbling, L. P., The synthesis of digital machines with provable epistemic properties, (Halpern, J. Y., Theoretical Aspects of Reasoning about Knowledge, Proceedings of the 1986 Conference (1987), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 83-98 |
| [35] | Ross, S., (Introduction to Stochastic Dynamic Programming (1983), Academic Press: Academic Press New York) · Zbl 0567.90065 |
| [36] | Russell, S. J.; Wefald, E. H., On optimal game-tree search using rational meta-reasoning, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 334-340 · Zbl 0707.68069 |
| [37] | Russell, S. J.; Wefald, E. H., Principles of metareasoning, (Proceedings First International Conference on Principles of Knowledge Representation and Reasoning (KR-89). Proceedings First International Conference on Principles of Knowledge Representation and Reasoning (KR-89), Toronto, Ont. (1989)) · Zbl 0737.68075 |
| [38] | Russell, S. J.; Zilberstein, S., Composing real-time systems, (Proceedings IJCAI-91. Proceedings IJCAI-91, Sydney, Australia (1991)), 212-217 · Zbl 0746.68085 |
| [39] | Shekhar, S.; Dutta, S., Minimizing response times in real time planning, (Proceedings IJCAI-89. Proceedings IJCAI-89, Detroit, MI (1989)), 972-978 |
| [40] | Shih, W.-K; Liu, J. W.S; Chung, J.-Y, Fast algorithms for scheduling imprecise computations, (Proceedings Real-Time Systems Symposium. Proceedings Real-Time Systems Symposium, Santa Monica, CA (1989)) |
| [41] | Simon, H. A.; Kadane, J. B., Optimal problem-solving search: all-or-none solutions, Artif. Intell., 6, 235-247 (1975) · Zbl 0328.68079 |
| [42] | Sproull, R. F., Strategy construction using a synthesis of heuristic and decision-theoretic methods, (Tech. Report CSL-77-2 (1977), Xerox PARC: Xerox PARC Palo Alto, CA) |
| [43] | Varga, R. S., (Matrix Iterative Methods (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ) · Zbl 0133.08602 |
| [44] | Vrbsky, S. V.; Liu, J. W.S; Smith, K. P., An object-oriented query processor that returns monotonically improving approximate answers, (Tech. Report UIUCDCS-R-90-1568 (1990), Department of Computer Science, University of Illinois: Department of Computer Science, University of Illinois Urbana-Champaign, IL) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
