Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-24T06:19:39.407Z Has data issue: false hasContentIssue false
  • English
  • Français

Planning and decision theory

Published online by Cambridge University Press:  07 July 2009

Peter Haddawy  and
Larry Rendell
Peter Haddawy
Affiliation:
University of Illinois, Dept of Computer Science, 1304 W. Springfield, Urbana, IL 61801, USA
Larry Rendell
Affiliation:
University of Illinois, Dept of Computer Science, 1304 W. Springfield, Urbana, IL 61801, USA
Get access Rights & Permissions [Opens in a new window]

Extract

Research on planning in AI can be separated into the two major areas: plan generation and plan representation. Most AI planners to date have been based on the STRIPS planning representation. This representation has a number of limitations. Much recent work in plan representation has addressed these limitations. It was shown that Decision Theory can be used to remove a number of the limitations. Furthermore, the decision theoretic framework provides a precise definition of rational behaviour. There remain open questions within decision theory regarding belief revision and causality. It should be noted that these problems are not artifacts of the representation. Rather they arise because the rich representation allows their formulation. Some work integrating AI and decision theoretic approaches to planning has been done but this remains a largely untouched research area.

We see two main avenues for fruitful research. First, the straightforward decision theoretic formulation of planning is computationally impractical. Techniques need to be developed to do efficient decision theoretic planning. Work in AI plan generation has exploited information contained the structure of qualitative representations to guide efficient plan construction. These techniques should be applied to decision theoretic representations as well. Second, AI has developed many representations that allow useful structuring of knowledge about the world. Decision Theory has concentrated on representing beliefs and desires. Integration of AI and decision theoretic representations would yield powerful representation languages. Some of the benefits of such work can already be seen in the research combining temporal and decision theoretic representations.

Type
Research Article
Information
The Knowledge Engineering Review , Volume 5 , Issue 1 , March 1990 , pp. 15 - 33
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allen, JF, 1984, “Towards a general theory of action and time” Artificial Intelligence 23(2) 123–154.CrossRefGoogle Scholar
Allen, JF and Koomen, JA, 1983, “Planning using a temporal world model” In: Proceedings of the eighth International Joint Conference on Artificial Intelligence pp 741–747, Karlsruhe, W. Germany,August 1983.Google Scholar
Appelt, D, 1985, “Planning English referring expressions” Artificial Intelligence 26(1) 1–33.CrossRefGoogle Scholar
Berger, JO, 1980, Statistical Decision Theory and Bayesian Analysis Springer-Verlag.CrossRefGoogle Scholar
Blackwell, D and Dubins, L, 1962, “Merging opinions with increasing information” Annals of Mathematical Statistics 33 882–887.CrossRefGoogle Scholar
Carnap, R, 1950, Logic Foundations of Probability Univ. of Chicago Press.Google Scholar
Cheeseman, P, 1983, “A method of computing generalized bayesian probability values for expert systems” In: Proceedings of the Eighth International Joint Conference on Artificial Intelligence pp 198–202, Karlsruhe, W. Germany,August 1983.Google Scholar
de Finetti, B, 1937, “La prevision: ses lois logiques, ses sources subjectives” Ann. Inst. Henri Poincare 7 1–68 (English translation in Kyburg and Smolker, 1964).Google Scholar
Dean, T and Kanazawa, K, 1988, “Probabilistic causal reasoning” In: Proceeding of the Fourth Workshop on Uncertainty in AI pp 73–80, Minneapolis, MN, August 1988.Google Scholar
Dean, T and Kanazawa, Keiji, 1988, “Probabilistic temporal reasoning” In: Proceedings of the Seventh National Conference on Artificial Intelligence pp 524–528, St. Paul, MN,1988.Google Scholar
DeGroot, M, 1970, Optimal Statistical Decisions McGraw-Hill.Google Scholar
Feldman, JA and Sproull, RF, 1977, “Decision theory and artificial intelligence ii: the hungry monkey” Artificial Intelligence 1 158–192.Google Scholar
Fikes, RE and Nilsson, NJ, 1971, “Strips: a new approach to the application of theorem proving to problem solving” Artificial Intelligence 2 189–208.CrossRefGoogle Scholar
Fishburn, PC, 1981, “Subjective expected utility: a review of normative theories” Theory and Decision 13 129–199.CrossRefGoogle Scholar
Fisher, RA, 1959, Smoking: The Cancer Controversy Oliver and Boyd.Google Scholar
Gaifman, H, 1986, “A theory of higher order probabilities” In: Proceedings of the Conference on Theoretical Aspects of Reasoning about Knowledge pp 275–292, Monterey,California,1986.Google Scholar
Gibbard, A and Harper, WL, 1978, “Counterfactuals and two kinds of expected utility” In: Hooker, , Leach, , and McClennen, , eds., Foundations and Applications of Decision Theory pp 125–162, D. Reidel, Dordrecht, Holland, 1978.Google Scholar
Goldstein, M, 1983, “The prevision of a prevision” J. American Statistical Association 78(384) 817–819.CrossRefGoogle Scholar
Green, C, 1969, “Application of theorem proving to problem solving” In: Proceedings of the First International Joint Conference on Artificial Intelligence pp 219–239, Washington, DC (Also in Weber, BL and Nilsson, NJ, eds., Readings in Artificial Intelligence Morgan Kaufmann, Los Alto, CA.)Google Scholar
Haas, AR, 1985, “Possible events, actual events, and robots” Computational Intelligence 1 59–70.CrossRefGoogle Scholar
Hass, AR, 1986, “A syntactic theory of belief and action” Artificial Intelligence 28 245–292.CrossRefGoogle Scholar
Haddawy, P and Frisch, AM, 1990, “Modal logics of higher-order probability” In: Shachter, R, Levitt, TS, Lemmer, J and Kanal, LN, eds., Uncertainty in Artificial Intelligence Elsevier.Google Scholar
Halpern, YJ, 1989, “The relationship between knowledge, belief, and certainty” In: Proceedings of the Fifth Workshop on Uncertainty in AI pp 142–151, An expanded version appears as IBM Research Report RJ 6765.Google Scholar
Hanks, S, 1988, “Representing and computing temporally scoped beliefs” In: Proceedings of the Seventh National Conference on Artificial Intelligence pp. 501–505, St. Paul, Minn.Google Scholar
Hanks, S, 1989, “Projecting plans for uncertain worlds” PhD thesis, Yale University.Google Scholar
Hayes, PJ, 1973, “The frame problem and related problems in artificial intelligence” In: Elithorn, A and Jones, D, eds., Artificial and Human Thinking pp 45–59, Jossey-Bass.Google Scholar
Hayes-Roth, B and Hayes-Roth, F, 1979, “A cognitive model of planning” Cognitive Science 3(4) 275–310.CrossRefGoogle Scholar
Hogarth, RM, 1975, “Cognitive processes and the assessment of subjective probability distributions” Journal of the American Association 70 271–294.CrossRefGoogle Scholar
Jaynes, ET, 1968, “Prior probabilities” IEEE Transactions on Systems, Science, and Cybernetics SSC–4 227–241.Google Scholar
Jaynes, ET, 1979, “Where do we stand on maximum entropy” In: Levine, and Tribus, , eds., The Maximum Entropy Formalism MIT Press.Google Scholar
Jeffrey, RC, 1965, The Logic of Decision McGraw-Hill.Google Scholar
Jeffreys, H, 1961, Theory of Probability 3rd edn., Oxford University Press.Google Scholar
Keeney, RL and Raiffa, H, 1976, Decisions with Multiple Objectives: Preferences and Value Tradeoffs Wiley.Google Scholar
Kemeny, J, 1955, “Fair bets and inductive probabilities” Journal of Symbolic Logic 20 263–273.CrossRefGoogle Scholar
Keynes, JM, 1921, A Treatise on Probability MacMillan.Google Scholar
Konolige, K, 1979, “A computer based consultant for mineral exploration, Appendix D: Bayesian methods for updating probabilities” report, SRI.Google Scholar
Kreps, DM, 1988, Notes on the Theory of Choice. Underground Classics in Economics Westview Press.Google Scholar
Kripke, S, 1963, “Semantical considerations on modal logic” Acta Philosophica Fennica 16 83–94 (Proceedings of a Colloquium on Modal and Many-Valued Logics Helsinki, 23–26 August, 1962).Google Scholar
Kyberg, HE Jr, and Smokler, HE, eds., 1969, Studies in Subjective Probability Wiley.Google Scholar
Lehman, RS, 1955, “On confirmation and rational betting” Journal of Symbolic Logic 20 251–262.CrossRefGoogle Scholar
Levi, I, 1980, The Enterprise of Knowledge MIT Press.Google Scholar
Levi, I, 1987, “The demons of decision” The Monist 70 193–211.CrossRefGoogle Scholar
Lewis, D, 1981, “Causal decision theory” Australasian Journal of Philosophy 56(1) 5–30.CrossRefGoogle Scholar
Maher, P, 1987, “Causality in the logic of decision” Theory and Decision 22 155–172.CrossRefGoogle Scholar
Maher, P, 1990, “Betting on theories (unpublished manuscript).Google Scholar
Maher, P, 1990, “Symptomatic acts and the value of evidence in causal decision theory” Philosophy of Science September.CrossRefGoogle Scholar
McCarthy, J and Hayes, P, 1969, “Some philosophical problems from the standpoint of artificial intelligence” In: Meltzer, B and Michie, D, eds., Machine Intelligence 4, pp 463–502, Edinburgh University Press.Google Scholar
McDermott, DV, 1982, “A temporal logic for reasoning about processes and plans” Cognitive Science 6 101–155.Google Scholar
Moore, RC, 1985, “A formal theory of knowledge and action” In: Hobbs, JR and Moore, RC, eds., Formal Theories of the Commonsense World Ablex.Google Scholar
Morgenstern, L, 1986, “A first order theory of planning, knowledge, and action” In: Vardi, M, ed., Proceedings of the Conference on Theoretical Aspects of Reasoning About Knowledge, pp 99–114, Monterey.CrossRefGoogle Scholar
Pelavin, RN and Allen, JF, 1986, “A formal logic of plans in temporally rich domains” Proceedings of the IEEE 74(10) 1364–1382.CrossRefGoogle Scholar
Raiffa, H, 1968, Decision Analysis Addison-Wesley.Google Scholar
Raiffa, H and Schlaifer, R, 1961, Applied Statistical Decision Theory MIT Press.Google Scholar
Ramsey, FP, 1926, “Truth and probability” In: Mellor, DH, ed., Foundations, chapter 3, pp 58–100, Humanitities Press.Google Scholar
Sacerdoti, ED, 1975, “A structure for plans and behavior” Technical Note 109, SRI.Google Scholar
Savage, LJ, 1954, The Foundations of Statistics John Wiley & Sons (Second revised edition published 1972).Google Scholar
Savage, LJ, 1971, “Elicitation of personal probabilities and expectations” Journal of the American Statistical Association 66 783–801.CrossRefGoogle Scholar
Schervish, MJ and Seidenfeld, , 1987, “An approach to consensus and certainty with increasing evidence” Technical Report 389, Carnegie-Mellon University, July 1987 (Forthcoming: J. Statistical Inference and Planning).Google Scholar
Seidenfeld, T, 1986, “Entropy and uncertainty” Philosophy of Science 53 467–491.CrossRefGoogle Scholar
Shimony, A, 1955, “Coherence and the axioms of confirmation” Journal of Symbolic Logic 20 8–20.CrossRefGoogle Scholar
Shoham, Y, 1987, Reasoning About Change MIT Press.Google Scholar
Skyrms, B, 1980, Causal Necessity Yale Univ. Press.Google Scholar
Sussman, GJ, 1975, A Computer Model of Skill Acquisition American Elsevier.Google Scholar
Tate, A, 1974, “INTERPLAN: A plan generation system which can deal with interactions between goals” memo MIP-R-109, Machine Intelligence Research Unit, Univ. of Edinburgh.Google Scholar
Tate, A, 1977, “Generating project networks” In; Proceedings of the Fifth International Joint Conference for Artificial Intelligence pp 888–893, Cambridge.Google Scholar
van Fraassen, B, 1984, “Belief and the will” Journal of Philosophy 81 235–256.CrossRefGoogle Scholar
Venn, J, 1966, The Logic of Chance MacMillan (new paperback edition, Chelsea, 1962).Google Scholar
Vere, S, 1983, “Planning in time: windows and durations for activities and goals” IEEE Transactions on Pattern Analysis and Machine Intelligence 5(3) 246–267.CrossRefGoogle ScholarPubMed
Villegas, C, 1977, “On the representation of ignorance” J. American Statistical Association 72 651–654.CrossRefGoogle Scholar
von Miesis, R, 1957, Probability, Statistics and Truth Allen and Unwin.Google Scholar
Wellman, MP, 1988, “Formulation of tradeoffs in planning under uncertainty” PhD thesis, MIT.Google Scholar
Wilensky, R, 1983, Planning and Understanding. Addison-Wesley.Google Scholar
Wilkins, DE, 1984, “Domain independent planning: representation and plan generation” Artificial Intelligence 22 269–301.CrossRefGoogle Scholar