Planning and decision theory

Peter Haddawy; Larry Rendell; Peter Haddawy; Larry Rendell

doi:10.1017/S026988890000521X

1990 Volume 5

Article Contents

Next Previous

RESEARCH ARTICLE Open Access

Planning and decision theory

More Information

Published online: 07 July 2009
The Knowledge Engineering Review 5, Article number: 10.1017/S026988890000521X (1990) | Cite this article

Abstract

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.
Rights and permissions
Copyright © Cambridge University Press 19901990Cambridge University Press

References

Allen JF, 1984, “Towards a general theory of action and time” Artificial Intelligence23(2) 123–154.

Google 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 Intelligence26(1) 1–33.

Google Scholar

Berger JO, 1980, Statistical Decision Theory and Bayesian AnalysisSpringer-Verlag.

Google Scholar

Blackwell D and Dubins L, 1962, “Merging opinions with increasing information” Annals of Mathematical Statistics33882–887.

Google Scholar

Carnap R, 1950, Logic Foundations of ProbabilityUniv. 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 Poincare71–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 DecisionsMcGraw-Hill.

Google Scholar

Feldman JA and Sproull RF, 1977, “Decision theory and artificial intelligence ii: the hungry monkey” Artificial Intelligence1158–192.

Google Scholar

Fikes RE and Nilsson NJ, 1971, “Strips: a new approach to the application of theorem proving to problem solving” Artificial Intelligence2189–208.

Google Scholar

Fishburn PC, 1981, “Subjective expected utility: a review of normative theories” Theory and Decision13129–199.

Google Scholar

Fisher RA, 1959, Smoking: The Cancer ControversyOliver 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 Association78(384) 817–819.

Google 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 Intelligence159–70.

Google Scholar

Hass AR, 1986, “A syntactic theory of belief and action” Artificial Intelligence28245–292.

Google 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 IntelligenceElsevier.

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 Science3(4) 275–310.

Google Scholar

Hogarth RM, 1975, “Cognitive processes and the assessment of subjective probability distributions” Journal of the American Association70271–294.

Google Scholar

Jaynes ET, 1968, “Prior probabilities” IEEE Transactions on Systems, Science, and Cybernetics SSC–4227–241.

Google Scholar

Jaynes ET, 1979, “Where do we stand on maximum entropy” In: Levine and Tribus , eds., The Maximum Entropy FormalismMIT Press.

Google Scholar

Jeffrey RC, 1965, The Logic of DecisionMcGraw-Hill.

Google Scholar

Jeffreys H, 1961, Theory of Probability3rd edn., Oxford University Press.

Google Scholar

Keeney RL and Raiffa H, 1976, Decisions with Multiple Objectives: Preferences and Value TradeoffsWiley.

Google Scholar

Kemeny J, 1955, “Fair bets and inductive probabilities” Journal of Symbolic Logic20263–273.

Google Scholar

Keynes JM, 1921, A Treatise on ProbabilityMacMillan.

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 EconomicsWestview Press.

Google Scholar

Kripke S, 1963, “Semantical considerations on modal logic” Acta Philosophica Fennica1683–94 (Proceedings of a Colloquium on Modal and Many-Valued Logics Helsinki, 23–26 August, 1962).

Google Scholar

Kyberg HEJr, and Smokler HE, eds., 1969, Studies in Subjective ProbabilityWiley.

Google Scholar

Lehman RS, 1955, “On confirmation and rational betting” Journal of Symbolic Logic20251–262.

Google Scholar

Levi I, 1980, The Enterprise of KnowledgeMIT Press.

Google Scholar

Levi I, 1987, “The demons of decision” The Monist70193–211.

Google Scholar

Lewis D, 1981, “Causal decision theory” Australasian Journal of Philosophy56(1) 5–30.

Google Scholar

Maher P, 1987, “Causality in the logic of decision” Theory and Decision22155–172.

Google 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.

Google Scholar

McCarthy J and Hayes P, 1969, “Some philosophical problems from the standpoint of artificial intelligence” In: Meltzer B and Michie D, eds., Machine Intelligence4, pp 463–502, Edinburgh University Press.

Google Scholar

McDermott DV, 1982, “A temporal logic for reasoning about processes and plans” Cognitive Science6101–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 WorldAblex.

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.

Google Scholar

Pelavin RN and Allen JF, 1986, “A formal logic of plans in temporally rich domains” Proceedings of the IEEE74(10) 1364–1382.

Google Scholar

Raiffa H, 1968, Decision AnalysisAddison-Wesley.

Google Scholar

Raiffa H and Schlaifer R, 1961, Applied Statistical Decision TheoryMIT 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 StatisticsJohn Wiley & Sons (Second revised edition published 1972).

Google Scholar

Savage LJ, 1971, “Elicitation of personal probabilities and expectations” Journal of the American Statistical Association66783–801.

Google 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 Science53467–491.

Google Scholar

Shimony A, 1955, “Coherence and the axioms of confirmation” Journal of Symbolic Logic208–20.

Google Scholar

Shoham Y, 1987, Reasoning About ChangeMIT Press.

Google Scholar

Skyrms B, 1980, Causal NecessityYale Univ. Press.

Google Scholar

Sussman GJ, 1975, A Computer Model of Skill AcquisitionAmerican 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 Philosophy81235–256.

Google Scholar

Venn J, 1966, The Logic of ChanceMacMillan (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 Intelligence5(3) 246–267.

Google Scholar

Villegas C, 1977, “On the representation of ignorance” J. American Statistical Association72651–654.

Google Scholar

von Miesis R, 1957, Probability, Statistics and TruthAllen 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 Intelligence22269–301.

Google Scholar