zbMATH — the first resource for mathematics

Complexity results and algorithms for possibilistic influence diagrams. (English) Zbl 1183.62133
Summary: We present the framework of Possibilistic Influence Diagrams (PID), which allows to model in a compact form problems of sequential decision making under uncertainty, when only ordinal data on transitions likelihood or preferences are available. The graphical part of a PID is exactly the same as that of usual influence diagrams, the semantics however differ. Transition likelihoods are expressed as possibility distributions and rewards are considered as satisfaction degrees. The expected utility is then replaced by anyone of two possibilistic qualitative utility criteria (optimistic and pessimistic) for evaluating strategies in a PID. We then describe decision tree-based methods for evaluating PID and computing optimal strategies, and we study the computational complexity of PID optimisation problems for both cases. Finally, we propose a dedicated variable elimination algorithm that can be applied to both optimistic and pessimistic cases for solving PID.

62L10 Sequential statistical analysis
62C99 Statistical decision theory
62-09 Graphical methods in statistics (MSC2010)
91B06 Decision theory
65C60 Computational problems in statistics (MSC2010)
Full Text: DOI
[1] Benferhat, S.; Dubois, D.; Garcia, L.; Prade, H., On the transformation between possibilistic logic bases and possibilistic causal networks, Int. J. approx. reason., 29, 135-173, (2002) · Zbl 1015.68204
[2] Boutilier, C.; Dean, T.; Hanks, S., Decision theoretic planning: structural assumptions and computational leverage, J. artificial intelligence res., 11, 1-94, (2000) · Zbl 0918.68110
[3] Boutilier, C.; Dearden, R.; Goldszmidt, M., Stochastic dynamic programming with factored representations, Artificial intelligence, 121, 1, 49-107, (2000) · Zbl 0948.68167
[4] Dubois, D.; Fargier, H.; Perny, P., Qualitative decision theory with preference relations and comparative uncertainty: an axiomatic approach, Artificial intelligence, 148, 219-260, (2003) · Zbl 1082.91512
[5] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: handling priority, preference and uncertainty, Appl. intelligence, 6, 287-309, (1996) · Zbl 1028.91526
[6] Dubois, D.; Le Berre, D.; Prade, H.; Sabbadin, R., Possibilistic logic for modeling qualitative decision: atms-based algorithms, Fund. inform., 34, 1-30, (1999) · Zbl 0930.68146
[7] D. Dubois, H. Prade, Possibility theory as a basis for qualitative decision theory, in: Proc. of IJCAI’95, 1995, pp. 1925-1930
[8] Dubois, D.; Prade, H.; Sabbadin, R., Decision-theoretic foundations of qualitative possibility theory, European J. oper. res., 128, 459-478, (2001) · Zbl 0982.90028
[9] Fargier, H.; Lang, J.; Sabbadin, R., Towards qualitative approaches to multi-stage decision making, Int. J. approx. reason., 19, 441-471, (1998) · Zbl 0947.68132
[10] L. Garcia, R. Sabbadin, Possibilistic influence diagrams, in: Proc. of ECAI’06, 2006, pp. 372-376
[11] R.A. Howard, J.E. Matheson, Influence diagrams, in: Readings on the Principles and Applications of Decision Analysis, 1984, pp. 719-762
[12] Jensen, F.V., Bayesian networks and decision graphs, (2001), Springer · Zbl 0973.62005
[13] Mackworth, A., Consistency in networks of relations, Artificial intelligence, 8, 99-118, (1977) · Zbl 0341.68061
[14] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Publishing Company · Zbl 0557.68033
[15] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann
[16] C. Pralet, G. Verfaillie, T. Schiex, Composite graphical models for reasoning about uncertainties, feasibilities and utilities, in: Proc. of CP’05—Workshop on Preferences and Soft Constraints, Sitges, Spain, 2005 · Zbl 1183.68588
[17] C. Pralet, G. Verfaillie, T. Schiex, Decision with uncertainties feasibilities and utilities: Towards a unified algebraic framework, in: Proc. of ECAI’06, 2006, pp. 427-431 · Zbl 1183.68588
[18] C. Pralet, G. Verfaillie, T. Schiex, Decomposition of multi-operator queries on semiring-based graphical models, in: Proc. of CP’06, Nantes, France, 2006, pp. 437-452 · Zbl 1160.68558
[19] C. Pralet, G. Verfaillie, T. Schiex, From influence diagrams to multioperator cluster DAGs, in: Proc. of UAI’06, Cambridge, MA, USA, 2006
[20] Puterman, M.L., Markov decision processes, (1994), John Wiley and Sons · Zbl 0336.93047
[21] Raiffa, H., Decision analysis: introductory lectures on choices under uncertainty, (1968), Addison-Wesley Reading, MA · Zbl 0181.21802
[22] Sabbadin, R., Possibilistic Markov decision processes, Engrg. appl. artificial intelligence, 14, 287-300, (2001)
[23] Shachter, R.D., Evaluating influence diagrams, Oper. res., 34, 6, 871-882, (1986)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.