×

zbMATH — the first resource for mathematics

Using possibilistic logic for modeling qualitative decision: answer set programming algorithms. (English) Zbl 1316.68173
Summary: A qualitative approach to decision making under uncertainty has been proposed in the setting of possibility theory, which is based on the assumption that levels of certainty and levels of priority (for expressing preferences) are commensurate. In this setting, pessimistic and optimistic decision criteria have been formally justified. This approach has been transposed into possibilistic logic in which the available knowledge is described by formulas which are more or less certainly true and the goals are described in a separate prioritized base. This paper adapts the possibilistic logic handling of qualitative decision making under uncertainty in the Answer Set Programming (ASP) setting. We show how weighted beliefs and prioritized preferences belonging to two separate knowledge bases can be handled in ASP by modeling qualitative decision making in terms of abductive logic programming where (uncertain) knowledge about the world and prioritized preferences are encoded as possibilistic definite logic programs and possibilistic literals respectively. We provide ASP-based and possibilistic ASP-based algorithms for calculating optimal decisions and utility values according to the possibilistic decision criteria. We describe a prototype implementing the algorithms proposed on top of different ASP solvers and we discuss the complexity of the different implementations.

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
68N17 Logic programming
Software:
ASPIDE; Smodels
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Amgoud, L.; Prade, H., Using arguments for making and explaining decisions, Artif. Intell., 173, 413-436, (2009) · Zbl 1343.68219
[2] Baral, C., Knowledge representation, reasoning and declarative problem solving, (2003), Cambridge University Press · Zbl 1056.68139
[3] Benferhat, S.; Brewka, G.; Berre, D. L., On the relation between qualitative choice logic and possibilistic logic, (Proceedings of the 10th International Conference on Information Processing and Management of Uncertainty (IPMU 2004), (2004)), 951-957
[4] Benferhat, S.; Dubois, D.; Prade, H., Representing default rules in possibilistic logic, (Proceedings of the 3rd International Conference on Principles of Knowledge Representation and Reasoning, KRʼ92, Cambridge, MA, (1992)), 673-684
[5] Benferhat, S.; Dubois, D.; Prade, H., Practical handling of exception-tainted rules and independence information in possibilistic logic, Appl. Intell., 9, 101-127, (1998)
[6] Bonet, B.; Geffner, H., Arguing for decisions: A qualitative model of decision making, (Horwitz, E., Proceedings of the 12th Conference on Uncertainty in Artificial Intelligence (UAIʼ96), (1996), Morgan Kaufmann), 98-105
[7] Bosc, P.; Pivert, O.; Prade, H., A possibilistic logic view of preference queries to an uncertain database, (Proceedings of 19th IEEE International Conference on Fuzzy Systems (FUZZ-IEEEʼ10), (2010)), 581-595
[8] Boutilier, C., Toward a logic for qualitative decision theory, (Doyle, J.; Sandewall, E., Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning (KRʼ94), (1994), Morgan Kaufmann), 75-86
[9] Brafman, R. I.; Tennenholtz, M., On the foundations of qualitative decision theory, (Proceedings of the 13th National Conference on Artificial Intelligence, vol. 2, AAAIʼ96, (1996), AAAI Press), 1291-1296
[10] Brewka, G., Answer sets and qualitative decision making, Synthese, 146, 171-187, (2005) · Zbl 1101.68853
[11] Brewka, G., Answer sets and qualitative optimization, Log. J. IGPL, 14, 413-433, (2006) · Zbl 1111.68119
[12] Brewka, G.; Benferhat, S.; Le Berre, D., Qualitative choice logic, Artif. Intell., 157, 203-237, (2004) · Zbl 1085.68159
[13] Brewka, G.; Niemelä, I.; Syrjänen, T., Logic programs with ordered disjunction, Comput. Intell., 20, 333-357, (2004)
[14] Brewka, G.; Niemelä, I.; Truszczyński, M., Answer set optimization, (Gottlob, G.; Walsh, T., Proceedings of 18th International Joint Conference on Artificial Intelligence (IJCAIʼ03), (2003), Morgan Kaufmann), 867-872
[15] Buccafurri, F.; Leone, N.; Rullo, P., Enhancing disjunctive Datalog by constraints, IEEE Trans. Knowl. Data Eng., 12, 845-860, (2000)
[16] Confalonieri, R.; Nieves, J.; Osorio, M.; Vázquez-Salceda, J., Dealing with explicit preferences and uncertainty in answer set programming, Ann. Math. Artif. Intell., 65, 159-198, (2012) · Zbl 1258.68139
[17] Confalonieri, R.; Prade, H., Answer set programming for computing decisions under uncertainty, (Liu, W., Proceedings of the 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2011), Lect. Notes Artif. Intell., vol. 6717, (2011), Springer-Verlag Berlin, Heidelberg), 485-496 · Zbl 1341.68243
[18] Confalonieri, R.; Prade, H., Encoding preference queries to an uncertain database in possibilistic answer set programming, (Greco, S.; Bouchon-Meunier, B.; Coletti, G.; Fedrizzi, M.; Matarazzo, B.; Yager, R. R., Advances in Computational Intelligence: Proceedings of 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-based Systems (IPMU 2012), Part I, Commun. Comput. Inf. Sci., vol. 297, (2012), Springer Berlin/Heidelberg), 511-520 · Zbl 1252.68300
[19] Confalonieri, R.; Prade, H.; Nieves, J. C., Handling exceptions in logic programming without negation as failure, (Liu, W., Proceedings of the 11th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2011), Lecture Notes Artif. Intell., vol. 6717, (2011), Springer-Verlag Berlin, Heidelberg), 509-520 · Zbl 1341.68021
[20] Denecker, M.; Kakas, A. C., Abduction in logic programming, (Kakas, A. C.; Sadri, F., Computational Logic: Logic Programming and Beyond, Lect. Notes Comput. Sci., vol. 2407, (2002), Springer Berlin/Heidelberg), 402-436 · Zbl 1012.68503
[21] Doyle, J.; Thomason, R. H., Background to qualitative decision theory, AI Mag., 20, 55-68, (1999)
[22] Dubois, D.; Fargier, H.; Prade, H., Fuzzy constraints in job-shop scheduling, J. Intell. Manuf., 6, 215-234, (1995)
[23] Dubois, D.; Lang, J.; Prade, H., Possibilistic logic, (Gabbay, D. M.; Hogger, C. J.; Robinson, J. A.; Siekmann, J. H., Handbook of Logic in Artificial Intelligence and Logic Programming, Nonmonotonic Reasoning and Uncertain Reasoning, vol. 3, (1994), Oxford University Press, Inc. New York, NY, USA), 439-513
[24] Dubois, D.; Le Berre, D.; Prade, H.; Sabbadin, R., Using possibilistic logic for modeling qualitative decision: ATMS-based algorithms, Fundam. Inform., 37, 1-30, (1999) · Zbl 0930.68146
[25] Dubois, D.; Prade, H., Possibility theory as a basis for qualitative decision theory, (Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAIʼ95), (1995), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 1924-1930
[26] Dubois, D.; Prade, H., Possibilistic logic: a retrospective and prospective view, Fuzzy Sets Syst., 144, 3-23, (2004) · Zbl 1076.68084
[27] Dubois, D.; Prade, H.; Sabbadin, R., A possibilistic logic machinery for qualitative decision, (Proceedings of AAAI Spring Symposium on Qualitative Preferences in Deliberation and Practical Reasoning, (1997), AAAI Press), 47-54
[28] Dubois, D.; Prade, H.; Sabbadin, R., Decision-theoretic foundations of qualitative possibility theory, Eur. J. Oper. Res., 128, 459-478, (2001) · Zbl 0982.90028
[29] Eiter, T.; Faber, W.; Leone, N.; Pfeifer, G., The diagnosis frontend of the DLV system, AI Commun., 12, 99-111, (1999)
[30] Eiter, T.; Gottlob, G., On the computational cost of disjunctive logic programming: propositional case, Ann. Math. Artif. Intell., 15, 289-323, (1995) · Zbl 0858.68016
[31] Eiter, T.; Gottlob, G.; Leone, N., Abduction from logic program: semantics and complexity, Theor. Comput. Sci., 189, 129-177, (1997) · Zbl 0893.68022
[32] Eiter, T.; Leone, N.; Mateis, C.; Pfeifer, G.; Wien, T.; Scarcello, F., The KR system DLV: progress report, comparisons and benchmarks, (Cohn, L. S.A. G.; Shapiro, S., Proceedings 6th International Conference on Principles of Knowledge Representation and Reasoning (KRʼ98), (1998), Morgan Kaufmann), 406-417
[33] Febbraro, O.; Reale, K.; Ricca, F., ASPIDE: integrated development environment for answer set programming, (Delgrande, J. P.; Faber, W., Logic Programming and Nonmonotonic Reasoning, Lect. Notes Comput. Sci., vol. 6645, (2011), Springer Berlin, Heidelberg), 317-330
[34] Fox, J.; Glasspool, D.; Grecu, D.; Modgil, S.; South, M.; Patkar, V., Argumentation-based inference and decision making - a medical perspective, IEEE Intell. Syst., 22, 34-41, (2007)
[35] Garcia, L.; Ngoma, S.; Nicolas, P., Dealing automatically with exceptions by introducing specificity in ASP, (Sossai, C.; Chemello, G., Proceedings of the 10th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARUʼ99), Lecture Notes Artif. Intell., vol. 5590, (2009), Springer-Verlag Berlin, Heidelberg), 614-625 · Zbl 1245.68185
[36] Gebser, M.; Kaufmann, B.; Neumann, A.; Schaub, T., Conflict-driven answer set solving, (Sangal, R.; Mehta, H.; Bagga, R. K., Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAIʼ07, (2007), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 386-392
[37] Grabos, R., Qualitative model of decision making, (Bussler, C.; Fensel, D., Artificial Intelligence: Methodology, Systems, and Applications, Lecture Notes Artif. Intell., vol. 3192, (2004), Springer Berlin/Heidelberg), 480-489 · Zbl 1187.68544
[38] Grabos, R., Answer set programming and combinatorial multicriteria decision making, Int. J. Uncertain. Fuzziness Knowl.-Based Syst., 14, 393-420, (2006) · Zbl 1102.68652
[39] Kakas, A. C.; Kowalski, R. A.; Toni, F., Abductive logic programming, J. Log. Comput., 2, 719-770, (1992) · Zbl 0778.68081
[40] Leone, N.; Pfeifer, G.; Faber, W.; Eiter, T.; Gottlob, G.; Perri, S.; Scarcello, F., The DLV system for knowledge representation and reasoning, ACM Trans. Comput. Log., 7, 499-562, (2006) · Zbl 1367.68308
[41] Lloyd, J. W., Foundations of logic programming, (1987), Springer-Verlag New York, NY, USA · Zbl 0547.68005
[42] Matt, P. A., Argumentation as a practical foundation for decision theory, (2010), Department of Computing, Imperial College London, PhD thesis
[43] von Neumann, J.; Morgenstern, O., Theory of games and economic behavior, (1944), Princeton University Press Princeton, NJ · Zbl 0063.05930
[44] Nicolas, P.; Garcia, L.; Stéphan, I.; Lefèvre, C., Possibilistic uncertainty handling for answer set programming, Ann. Math. Artif. Intell., 47, 139-181, (2006) · Zbl 1105.68104
[45] Niemelä, I.; Simons, P., Smodels - an implementation of the stable model and well-founded semantics for normal LP, (Dix, J.; Furbach, U.; Nerode, A., Proceeding of 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMRʼ97), Lect. Notes Comput. Sci., vol. 1265, (1997), Springer-Verlag London, UK), 421-430
[46] Nieves, J. C.; Confalonieri, R., A possibilistic argumentation decision making framework with default reasoning, Fundam. Inform., 113, 41-61, (2011) · Zbl 1241.68116
[47] Pearl, J., System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning, (Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, TARK ʼ90, (1990), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 121-135
[48] Perri, S.; Scarcello, F.; Leone, N., Abductive logic programs with penalization: semantics, complexity and implementation, Theory Pract. Log. Program., 5, 123-159, (2005) · Zbl 1093.68020
[49] Sabbadin, R., Decision as abduction?, (Prade, H., Proceedings of 13th European Conference on Artificial Intelligence, ECAI 1998, (1998), John Wiley and Sons Chichester), 600-604
[50] Savage, L. J., The foundations of statistics, (1972), Dover New York · Zbl 0276.62006
[51] Simons, P.; Niemelä, I.; Soininen, T., Extending and implementing the stable model semantics, Artif. Intell., 138, 181-234, (2002) · Zbl 0995.68021
[52] Syrjänen, T.; Niemelä, I., The smodels system, (Eiter, T.; Faber, W.; Truszczyński, M., Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMRʼ01, Lect. Notes Comput. Sci., vol. 2173, (2001), Springer Berlin, Heidelberg), 434-438 · Zbl 1010.68797
[53] Tan, S. W.; Pearl, J., Qualitative decision theory, (Proceedings of the 12th National Conference on Artificial Intelligence, vol. 2, AAAIʼ94, (1994), American Association for Artificial Intelligence Menlo Park, CA, USA), 928-933
[54] Tan, S. W.; Pearl, J., Specification and evaluation of preferences under uncertainty, (Doyle, J.; Sandewall, E.; Torasso, P., Proceedings of the 4th International Conference on Principles of Knowledge Representation and Reasoning, KRʼ94, (1994), Morgan Kaufmann), 530-539
[55] Toni, F.; Sergot, M., Argumentation and answer set programming, (Balduccini, M.; Son, T., Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, Lect. Notes Comput. Sci., vol. 6565, (2011), Springer Berlin/Heidelberg), 164-180 · Zbl 1326.68279
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.